00001 /*****************************************************************************/ 00002 /*! 00003 * \file arith_proof_rules.h 00004 * \brief Arithmetic proof rules 00005 * 00006 * Author: Vijay Ganesh, Sergey Berezin 00007 * 00008 * Created: Dec 13 02:09:04 GMT 2002 00009 * 00010 * <hr> 00011 * 00012 * License to use, copy, modify, sell and/or distribute this software 00013 * and its documentation for any purpose is hereby granted without 00014 * royalty, subject to the terms and conditions defined in the \ref 00015 * LICENSE file provided with this distribution. 00016 * 00017 * <hr> 00018 * 00019 */ 00020 /*****************************************************************************/ 00021 00022 #ifndef _cvc3__arith_proof_rules_h_ 00023 #define _cvc3__arith_proof_rules_h_ 00024 00025 #include <vector> 00026 00027 namespace CVC3 { 00028 00029 class Theorem; 00030 class Expr; 00031 class Rational; 00032 00033 class ArithProofRules { 00034 public: 00035 // Destructor 00036 virtual ~ArithProofRules() { } 00037 00038 //////////////////////////////////////////////////////////////////// 00039 // Canonization rules 00040 //////////////////////////////////////////////////////////////////// 00041 00042 //! ==> e = 1 * e 00043 virtual Theorem varToMult(const Expr& e) = 0; 00044 00045 //! ==> -(e) = (-1) * e 00046 virtual Theorem uMinusToMult(const Expr& e) = 0; 00047 00048 //! ==> x - y = x + (-1) * y 00049 virtual Theorem minusToPlus(const Expr& x, const Expr& y) = 0; 00050 00051 //! -(e) ==> e / (-1); takes 'e' 00052 /*! Canon Rule for unary minus: it just converts it to division by 00053 * -1, the result is not yet canonical: 00054 */ 00055 virtual Theorem canonUMinusToDivide(const Expr& e) = 0; 00056 00057 /** 00058 * Transform e = (SUM r t1 ... tn) @ 0 into (SUM t1 ... tn) @ -r. The first 00059 * sum term (r) must be a rational and t1 ... tn terms must be canonised. 00060 * 00061 * @param e the expression to transform 00062 * @return rewrite theorem representing the transformation 00063 */ 00064 virtual Theorem moveSumConstantRight(const Expr& e) = 0; 00065 00066 //! (c) / d ==> (c/d), takes c and d 00067 /*! Canon Rules for division by constant 'd' */ 00068 virtual Theorem canonDivideConst(const Expr& c, const Expr& d) = 0; 00069 //! (c * x) / d ==> (c/d) * x, takes (c*x) and d 00070 virtual Theorem canonDivideMult(const Expr& cx, const Expr& d) = 0; 00071 //! (+ c ...)/d ==> push division to all the coefficients. 00072 /*! The result is not canonical, but canonizing the summands will 00073 * make it canonical. 00074 * Takes (+ c ...) and d 00075 */ 00076 virtual Theorem canonDividePlus(const Expr& e, const Expr& d) = 0; 00077 //! x / d ==> (1/d) * x, takes x and d 00078 virtual Theorem canonDivideVar(const Expr& e, const Expr& d) = 0; 00079 00080 // Canon Rules for multiplication 00081 00082 // TODO Deepak: 00083 // e == t1 * t2 where t1 and t2 are canonized expressions, i.e. it can be a 00084 // 1) Rational constant 00085 // 2) Arithmetic Leaf (var or term from another theory) 00086 // 3) (POW rational leaf) 00087 // 4) (MULT rational mterm'_1 ...) where each mterm' is of type (2) or (3) 00088 // 5) (PLUS rational sterm_1 sterm_2 ...) where each sterm is of 00089 // type (2) or (3) or (4) 00090 virtual Theorem canonMultMtermMterm(const Expr& e) = 0; 00091 //! Canonize (PLUS t1 ... tn) 00092 virtual Theorem canonPlus(const Expr & e) = 0; 00093 //! Canonize (MULT t1 ... tn) 00094 virtual Theorem canonMult(const Expr & e) = 0; 00095 //! ==> 1/e = e' where e' is canonical; takes e. 00096 virtual Theorem canonInvert(const Expr & e) = 0; 00097 //! Canonize t1/t2 00098 virtual Theorem canonDivide(const Expr & e) = 0; 00099 00100 //! t*c ==> c*t, takes constant c and term t 00101 virtual Theorem canonMultTermConst(const Expr& c, const Expr& t) = 0; 00102 //! t1*t2 ==> Error, takes t1 and t2 where both are non-constants 00103 virtual Theorem canonMultTerm1Term2(const Expr& t1, const Expr& t2) = 0; 00104 //! 0*t ==> 0, takes 0*t 00105 virtual Theorem canonMultZero(const Expr& e) = 0; 00106 //! 1*t ==> t, takes 1*t 00107 virtual Theorem canonMultOne(const Expr& e) = 0; 00108 //! c1*c2 ==> c', takes constant c1*c2 00109 virtual Theorem canonMultConstConst(const Expr& c1, const Expr& c2) = 0; 00110 //! c1*(c2*t) ==> c'*t, takes c1 and c2 and t 00111 virtual Theorem 00112 canonMultConstTerm(const Expr& c1, const Expr& c2, const Expr&t) = 0; 00113 //! c1*(+ c2 v1 ...) ==> (+ c' c1v1 ...), takes c1 and the sum 00114 virtual Theorem canonMultConstSum(const Expr& c1, const Expr& sum) = 0; 00115 //! c^n = c' (compute the constant power expression) 00116 virtual Theorem canonPowConst(const Expr& pow) = 0; 00117 00118 // Rules for addition 00119 //! flattens the input. accepts a PLUS expr 00120 virtual Theorem canonFlattenSum(const Expr& e) = 0; 00121 00122 //! combine like terms. accepts a flattened PLUS expr 00123 virtual Theorem canonComboLikeTerms(const Expr& e) = 0; 00124 00125 //! e0 \@ e1 <==> true | false, where \@ is {=,<,<=,>,>=} 00126 /*! \param e takes e is (e0\@e1) where e0 and e1 are constants 00127 */ 00128 virtual Theorem constPredicate(const Expr& e) = 0; 00129 00130 //! e[0] @ e[1] <==> 0 @ e[1] - e[0], where @ is {=,<,<=,>,>=} 00131 virtual Theorem rightMinusLeft(const Expr& e) = 0; 00132 00133 //! e[0] @ e[1] <==> e[0] - e[1] @ 0, where @ is {=,<,<=,>,>=} 00134 virtual Theorem leftMinusRight(const Expr& e) = 0; 00135 00136 //! x @ y <==> x + z @ y + z, where @ is {=,<,<=,>,>=} (given as 'kind') 00137 virtual Theorem plusPredicate(const Expr& x, 00138 const Expr& y, const Expr& z, int kind) = 0; 00139 00140 //! x = y <==> x * z = y * z, where z is a non-zero constant 00141 virtual Theorem multEqn(const Expr& x, const Expr& y, const Expr& z) = 0; 00142 00143 //! Multiplying inequation by a non-zero constant 00144 /*! 00145 * z>0 ==> e[0] @ e[1] <==> e[0]*z @ e[1]*z 00146 * 00147 * z<0 ==> e[0] @ e[1] <==> e[1]*z @ e[0]*z 00148 * 00149 * for @ in {<,<=,>,>=}: 00150 */ 00151 virtual Theorem multIneqn(const Expr& e, const Expr& z) = 0; 00152 00153 //! x = y ==> x <= y and x >= y 00154 virtual Theorem eqToIneq(const Expr& e) = 0; 00155 00156 //! "op1 GE|GT op2" <==> op2 LE|LT op1 00157 virtual Theorem flipInequality(const Expr& e) = 0; 00158 00159 //! Propagating negation over <,<=,>,>= 00160 /*! NOT (op1 < op2) <==> (op1 >= op2) 00161 * 00162 * NOT (op1 <= op2) <==> (op1 > op2) 00163 * 00164 * NOT (op1 > op2) <==> (op1 <= op2) 00165 * 00166 * NOT (op1 >= op2) <==> (op1 < op2) 00167 */ 00168 virtual Theorem negatedInequality(const Expr& e) = 0; 00169 00170 //! Real shadow: a <(=) t, t <(=) b ==> a <(=) b 00171 virtual Theorem realShadow(const Theorem& alphaLTt, 00172 const Theorem& tLTbeta) = 0; 00173 00174 //! Projecting a tight inequality: alpha <= t <= alpha ==> t = alpha 00175 virtual Theorem realShadowEq(const Theorem& alphaLEt, 00176 const Theorem& tLEalpha) = 0; 00177 00178 //! Finite interval for integers: a <= t <= a + c ==> G(t, a, 0, c) 00179 virtual Theorem finiteInterval(const Theorem& aLEt, 00180 const Theorem& tLEac, 00181 const Theorem& isInta, 00182 const Theorem& isIntt) = 0; 00183 00184 //! Dark & Gray shadows when a <= b 00185 /*! takes two integer ineqs (i.e. all vars are ints) 00186 * "|- beta <= b.x" and "|- a.x <= alpha" and checks if "1 <= a <= b" 00187 * and returns (D or G) and (!D or !G), where 00188 * D = Dark_Shadow(ab-1, b.alpha - a.beta), 00189 * G = Gray_Shadow(a.x, alpha, -(a-1), 0). 00190 */ 00191 virtual Theorem darkGrayShadow2ab(const Theorem& betaLEbx, 00192 const Theorem& axLEalpha, 00193 const Theorem& isIntAlpha, 00194 const Theorem& isIntBeta, 00195 const Theorem& isIntx)=0; 00196 00197 //! Dark & Gray shadows when b <= a 00198 /*! takes two integer ineqs (i.e. all vars are ints) 00199 * "|- beta <= b.x" and "|- a.x <= alpha" and checks if "1 <= b < a" 00200 * and returns (D or G) and (!D or !G), where 00201 * D = Dark_Shadow(ab-1, b.alpha - a.beta), 00202 * G = Gray_Shadow(b.x, beta, 0, b-1). 00203 */ 00204 virtual Theorem darkGrayShadow2ba(const Theorem& betaLEbx, 00205 const Theorem& axLEalpha, 00206 const Theorem& isIntAlpha, 00207 const Theorem& isIntBeta, 00208 const Theorem& isIntx)=0; 00209 00210 //! DARK_SHADOW(t1, t2) ==> t1 <= t2 00211 virtual Theorem expandDarkShadow(const Theorem& darkShadow)=0; 00212 00213 //! GRAY_SHADOW(v, e, c, c) ==> v=e+c. 00214 virtual Theorem expandGrayShadow0(const Theorem& g)=0; 00215 00216 // [used to be] GRAY_SHADOW(t1, t2, i) ==> t1 = t2+i OR 00217 // GRAY_SHADOW(t1, t2, i+/-1) 00218 00219 //! G(x, e, c1, c2) ==> (G1 or G2) and (!G1 or !G2) 00220 /*! Here G1 = G(x,e,c1,c), 00221 * G2 = G(x,e,c+1,c2), 00222 * and c = floor((c1+c2)/2). 00223 */ 00224 virtual Theorem splitGrayShadow(const Theorem& g)=0; 00225 //! G(x, e, c1, c2) ==> e+c1 <= x AND x <= e+c2 00226 virtual Theorem expandGrayShadow(const Theorem& g)=0; 00227 00228 //! Optimized rules: GRAY_SHADOW(a*x, c, c1, c2) ==> [expansion] 00229 /*! Implements three versions of the rule: 00230 * 00231 * \f[\frac{\mathrm{GRAY\_SHADOW}(ax,c,c1,c2)} 00232 * {ax = c + i - \mathrm{sign}(i)\cdot j(c,i,a) 00233 * \lor GRAY\_SHADOW(ax, c, i-\mathrm{sign}(i)\cdot (a+j(c,i,a)))}\f] 00234 * 00235 * where the conclusion may become FALSE or without the 00236 * GRAY_SHADOW part, depending on the values of a, c and i. 00237 */ 00238 virtual Theorem expandGrayShadowConst(const Theorem& g)=0; 00239 //! |- G(ax, c, c1, c2) ==> |- G(x, 0, ceil((c1+c)/a), floor((c2+c)/a)) 00240 /*! In the case the new c1 > c2, return |- FALSE */ 00241 virtual Theorem grayShadowConst(const Theorem& g)=0; 00242 00243 //! a,b: INT; a < b ==> a <= b-1 [or a+1 <= b] 00244 /*! Takes a Theorem(\\alpha < \\beta) and returns 00245 * Theorem(\\alpha < \\beta <==> \\alpha <= \\beta -1) 00246 * or Theorem(\\alpha < \\beta <==> \\alpha + 1 <= \\beta), 00247 * depending on which side must be changed (changeRight flag) 00248 */ 00249 virtual Theorem lessThanToLE(const Theorem& less, 00250 const Theorem& isIntLHS, 00251 const Theorem& isIntRHS, 00252 bool changeRight)=0; 00253 00254 /*! \param eqn is an equation 0 = a.x or 0 = c + a.x, where x is integer 00255 * \param isIntx is a proof of IS_INTEGER(x) 00256 * 00257 * \return the theorem 0 = c + a.x <==> x=-c/a if -c/a is int else 00258 * return the theorem 0 = c + a.x <==> false. 00259 * 00260 * It also handles the special case of 0 = a.x <==> x = 0 00261 */ 00262 virtual Theorem intVarEqnConst(const Expr& eqn, 00263 const Theorem& isIntx) = 0; 00264 /*! @brief Equality elimination rule for integers: 00265 * \f[\frac{\mathsf{int}(a\cdot x)\quad 00266 * \mathsf{int}(C+\sum_{i=1}^{n}a_{i}\cdot x_{i})} 00267 * {a\cdot x=C+\sum_{i=1}^{n}a_{i}\cdot x_{i} 00268 * \quad\equiv\quad x=t_{2}\wedge 0=t_{3}} 00269 * \f] 00270 * See the detailed description for explanations. 00271 * 00272 * This rule implements a step in the iterative algorithm for 00273 * eliminating integer equality. The terms in the rule are 00274 * defined as follows: 00275 * 00276 * \f[\begin{array}{rcl} 00277 * t_{2} & = & 00278 * -(C\ \mathbf{mod}\ m+\sum_{i=1}^{n}(a_{i}\ \mathbf{mod}\ m) 00279 * \cdot x_{i}-m\cdot\sigma(t))\\ & & \\ 00280 * t_{3} & = & 00281 * \mathbf{f}(C,m)+\sum_{i=1}^{n}\mathbf{f}(a_{i},m)\cdot x_{i} 00282 * -a\cdot\sigma(t)\\ & & \\ 00283 * t & = & 00284 * (C\ \mathbf{mod}\ m+\sum_{i=1}^{n}(a_{i}\ \mathbf{mod}\ m) 00285 * \cdot x_{i}+x)/m\\ & & \\ 00286 * m & = & a+1\\ & & \\ 00287 * \mathbf{f}(i,m) & = & \left\lfloor \frac{i}{m} 00288 * +\frac{1}{2}\right\rfloor +i\ \mathbf{mod}\ m\\ & & \\ 00289 * i\ \mathbf{mod}\ m & = & i-m\left\lfloor\frac{i}{m} 00290 * +\frac{1}{2}\right\rfloor 00291 * \end{array} 00292 * \f] 00293 * 00294 * All the variables and coefficients are integer, and a >= 2. 00295 * 00296 * \param eqn is the equation 00297 * \f[a\cdot x = C + \sum_{i=1}^n a_i\cdot x_i.\f] 00298 * 00299 */ 00300 00301 /* 00302 virtual Theorem eqElimIntRule(const Expr& eqn, 00303 const Theorem& isIntLHS, 00304 const Theorem& isIntRHS) = 0; 00305 //! a <=> b ==> c AND a <=> c AND b. Takes "a <=> b" and "c". 00306 virtual Theorem cANDaIffcANDb(const Theorem& thm, 00307 const Expr& solvedEq) = 0; 00308 virtual Theorem substSolvedFormRule(const Expr& e1, 00309 ExprMap<Expr>& eMap) = 0; 00310 virtual Theorem aANDcIffbANDc(const Theorem& thm, const Expr& newEq) = 0; 00311 */ 00312 00313 /////////////////////////////////////////////////////////////////////// 00314 // Alternative implementation of integer equality elimination 00315 /////////////////////////////////////////////////////////////////////// 00316 00317 /*! @brief 00318 * \f[\frac{\Gamma\models ax=t\quad 00319 * \Gamma'\models\mathsf{int}(x)\quad 00320 * \{\Gamma_i\models\mathsf{int}(x_i) | x_i\mbox{ is var in }t\}} 00321 * {\Gamma,\Gamma',\bigcup_i\Gamma_i\models 00322 * \exists (y:\mathrm{int}).\ x=t_2(y)\wedge 0=t_3(y)} 00323 * \f] 00324 * See detailed docs for more information. 00325 * 00326 * This rule implements a step in the iterative algorithm for 00327 * eliminating integer equality. The terms in the rule are 00328 * defined as follows: 00329 * 00330 * \f[\begin{array}{rcl} 00331 * t & = & C+\sum_{i=1}^na_{i}\cdot x_{i}\\ 00332 * t_{2}(y) & = & 00333 * -(C\ \mathbf{mod}\ m+\sum_{i=1}^{n}(a_{i}\ \mathbf{mod}\ m) 00334 * \cdot x_{i}-m\cdot y)\\ & & \\ 00335 * t_{3}(y) & = & 00336 * \mathbf{f}(C,m)+\sum_{i=1}^{n}\mathbf{f}(a_{i},m)\cdot x_{i} 00337 * -a\cdot y\\ & & \\ 00338 * m & = & a+1\\ & & \\ 00339 * \mathbf{f}(i,m) & = & \left\lfloor \frac{i}{m} 00340 * +\frac{1}{2}\right\rfloor +i\ \mathbf{mod}\ m\\ & & \\ 00341 * i\ \mathbf{mod}\ m & = & i-m\left\lfloor\frac{i}{m} 00342 * +\frac{1}{2}\right\rfloor 00343 * \end{array} 00344 * \f] 00345 * 00346 * All the variables and coefficients are integer, and a >= 2. 00347 * 00348 * \param eqn is the equation ax=t: 00349 * \f[a\cdot x = C + \sum_{i=1}^n a_i\cdot x_i.\f] 00350 * 00351 * \param isIntx is a Theorem deriving the integrality of the 00352 * LHS variable: IS_INTEGER(x) 00353 * 00354 * \param isIntVars is a vector of Theorems deriving the 00355 * integrality of all variables on the RHS 00356 */ 00357 virtual Theorem eqElimIntRule(const Theorem& eqn, 00358 const Theorem& isIntx, 00359 const std::vector<Theorem>& isIntVars) = 0; 00360 00361 /*! 00362 * @brief return e <=> TRUE/FALSE for e == IS_INTEGER(c), where c 00363 * is a constant 00364 * 00365 * \param e is a predicate IS_INTEGER(c) where c is a rational constant 00366 */ 00367 virtual Theorem isIntConst(const Expr& e) = 0; 00368 00369 virtual Theorem equalLeaves1(const Theorem& thm) = 0; 00370 virtual Theorem equalLeaves2(const Theorem& thm) = 0; 00371 virtual Theorem equalLeaves3(const Theorem& thm) = 0; 00372 virtual Theorem equalLeaves4(const Theorem& thm) = 0; 00373 00374 //! x /= y ==> (x < y) OR (x > y) 00375 /*! Used in concrete model generation */ 00376 virtual Theorem diseqToIneq(const Theorem& diseq) = 0; 00377 00378 virtual Theorem dummyTheorem(const Expr& e) = 0; 00379 00380 virtual Theorem oneElimination(const Expr& x) = 0; 00381 00382 virtual Theorem clashingBounds(const Theorem& lowerBound, const Theorem& upperBound) = 0; 00383 00384 virtual Theorem addInequalities(const Theorem& thm1, const Theorem& thm2) = 0; 00385 00386 virtual Theorem implyWeakerInequality(const Expr& expr1, const Expr& expr2) = 0; 00387 00388 virtual Theorem implyNegatedInequality(const Expr& expr1, const Expr& expr2) = 0; 00389 00390 virtual Theorem integerSplit(const Expr& intVar, const Rational& intPoint) = 0; 00391 00392 virtual Theorem trustedRewrite(const Expr& expr1, const Expr& expr2) = 0; 00393 00394 virtual Theorem rafineStrictInteger(const Theorem& isIntConstrThm, const Expr& constr) = 0; 00395 00396 }; // end of class ArithProofRules 00397 } // end of namespace CVC3 00398 00399 #endif