arith_proof_rules.h

Go to the documentation of this file.
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

Generated on Tue Jul 3 14:33:34 2007 for CVC3 by  doxygen 1.5.1