Overview - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


Overview of the QuantifierElimination Package

 

Description

List of QuantifierElimination Commands

List of QuantifierElimination Subpackages

Examples

References

Compatibility

Description

• 

The QuantifierElimination package contains routines for quantifier elimination (QE) over the reals, as well as other related auxiliary tools for working with Tarski formulae and other related formulae.

• 

QuantifierEliminate, PartialCylindricalAlgebraicDecompose, InsertFormula, and DeleteFormula are all routines to perform QE. The latter two routines are "evolutionary" methods [Ton19], which is a term usually referred to in other academic literature as "incremental".

• 

CylindricalAlgebraicDecompose is a routine to produce "stock" Cylindrical Algebraic Decompositions (CADs) for sets of polynomials or formulae. CADs have many uses in real algebraic geometry.

• 

PartialCylindricalAlgebraicDecompose can also be used for such purposes, where partial CAD is used to attempt to construct minimal geometry depending on truth values. Generally, PartialCylindricalAlgebraicDecompose is a quantifier elimination tool in the same manner as QuantifierEliminate. Where CAD is used for the purposes of quantifier elimination, the methodology is partial CAD [CH91] for lifting to aim for early termination.

• 

QuantifierEliminate, InsertFormula, and DeleteFormula use poly-algorithmic methodology for quantifier elimination between two prolific algorithms for QE, Virtual Term Substitution (VTS) and Cylindrical Algebraic Decomposition (CAD) [Ton20].

• 

Where VTS is implemented, the main sources of algorithms is [Kos16]. VTS is an algorithm best suited to elimination of quantified variables appearing at low degree in the input formula. VTS within QuantifierElimination is implemented to eliminate variables appearing up to quadratically in a formula, pending factorization of polynomials.

• 

Where quantifier elimination is offered by the package, routines follow an output syntax defined by a keyword option output. This option enables production of the quantifier-free answer for a QE problem, as well as "witnesses" that prove equivalence of QE to a quantifier-free answer. Additionally, requesting data provides QEData or CADData objects that enable QE in an incremental fashion, along with other methods to enable inspection of the data structures in greater detail. For more information, see the help page QuantifierElimination options.

• 

Witnesses can be requested for any QE formula that is fully quantified with only one type of quantifier symbol (forall or exists). Production of witnesses is possible under any methodology within QuantifierElimination, including poly-algorithmic or pure CAD. Production of witnesses from VTS is discussed in [Ton20, KS16].

• 

The methodology for production of CADs within QuantifierElimination is always projection and lifting, where the projection operator implemented is the Lazard projection operator [Laz94, MPP19].

• 

The QuantifierTools subpackage is a source of auxiliary tools for working with formulae and other outputs from QuantifierElimination.

• 

Where equational constraints are used within CAD in the package, curtain occurrences may prevent the output from being mathematically correct. The package implements algorithms to try to recover from such occurrences to maximize the chance of success [NDS19, Ton21].

• 

The package uses a number of keyword options that are common across routines for the package, especially those offering quantifier elimination. These options are dependent and specific to the methodology used within the routine on request.

• 

The work [Ton21] is the main academic source of reference for the package.

List of QuantifierElimination Commands

QuantifierEliminate

QuantifierElimination:-CylindricalAlgebraicDecompose

QuantifierElimination:-DeleteFormula

QuantifierElimination:-InsertFormula

QuantifierElimination:-PartialCylindricalAlgebraicDecompose

 

 

 

List of QuantifierElimination Subpackages

  

QuantifierTools

Examples

withQuantifierElimination

CylindricalAlgebraicDecompose,DeleteFormula,InsertFormula,PartialCylindricalAlgebraicDecompose,QuantifierEliminate,QuantifierTools

(1)

QuantifierEliminateexistsx,ax2+bx+c=0

a=0b=0c=0a=0b0ac2=0a<04acb2<0a04acb20a<04acb2<0

(2)

PartialCylindricalAlgebraicDecomposeexistsx&comma;ax3+bx2+cx+d=0

d<0c<0b<c23da<0d<0c<0b<c23d0<ad<0c<0b=c23da<RootOf729d4_Z254c3_Zd2+c6&comma;index=real1d<0c<0b=c23da=RootOf729d4_Z254c3_Zd2+c6&comma;index=real1d<0c<0b=c23dRootOf729d4_Z254c3_Zd2+c6&comma;index=real1<aa<0d<0c<0b=c23d0<ad<0c<0c23d<bb<c24da<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<0c<0c23d<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<0c<0c23d<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<0c<0c23d<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<0c<0c23d<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<aa<0d<0c<0c23d<bb<c24d0<ad<0c<0b=c24da<RootOf_Z54d2_Zc3&comma;index=real1d<0c<0b=c24da=RootOf_Z54d2_Zc3&comma;index=real1d<0c<0b=c24dRootOf_Z54d2_Zc3&comma;index=real1<aa<RootOf_Z54d2_Zc3&comma;index=real2d<0c<0b=c24da=RootOf_Z54d2_Zc3&comma;index=real2d<0c<0b=c24dRootOf_Z54d2_Zc3&comma;index=real2<ad<0c<0c24d<bb<0a<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<0c<0c24d<bb<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<0c<0c24d<bb<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<0d<0c<0c24d<bb<0a=0d<0c<0c24d<bb<00<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<0c<0c24d<bb<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<0c<0c24d<bb<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<ad<0c<0b=0a<RootOf_Z27d2_Z+4c3&comma;index=real1d<0c<0b=0a=RootOf_Z27d2_Z+4c3&comma;index=real1d<0c<0b=0RootOf_Z27d2_Z+4c3&comma;index=real1<aa<RootOf_Z27d2_Z+4c3&comma;index=real2d<0c<0b=0a=RootOf_Z27d2_Z+4c3&comma;index=real2d<0c<0b=0RootOf_Z27d2_Z+4c3&comma;index=real2<ad<0c<00<ba<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<0c<00<ba=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<0c<00<bRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<0d<0c<00<ba=0d<0c<00<b0<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<0c<00<ba=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<0c<00<bRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<ad<0c=0b<0a<0d<0c=0b<00<ad<0c=0b=0a<0d<0c=0b=00<ad<0c=00<ba<RootOf27_Z2d+4b3&comma;index=real1d<0c=00<ba=RootOf27_Z2d+4b3&comma;index=real1d<0c=00<bRootOf27_Z2d+4b3&comma;index=real1<aa<0d<0c=00<ba=0d<0c=00<b0<aa<RootOf27_Z2d+4b3&comma;index=real2d<0c=00<ba=RootOf27_Z2d+4b3&comma;index=real2d<0c=00<bRootOf27_Z2d+4b3&comma;index=real2<ad<00<cb<c23da<0d<00<cb<c23d0<ad<00<cb=c23da<0d<00<cb=c23d0<aa<RootOf729d4_Z254c3_Zd2+c6&comma;index=real1d<00<cb=c23da=RootOf729d4_Z254c3_Zd2+c6&comma;index=real1d<00<cb=c23dRootOf729d4_Z254c3_Zd2+c6&comma;index=real1<ad<00<cc23d<bb<c24da<0d<00<cc23d<bb<c24d0<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<00<cc23d<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<00<cc23d<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<00<cc23d<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<00<cc23d<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<ad<00<cb=c24da<RootOf_Z54d2_Zc3&comma;index=real1d<00<cb=c24da=RootOf_Z54d2_Zc3&comma;index=real1d<00<cb=c24dRootOf_Z54d2_Zc3&comma;index=real1<aa<RootOf_Z54d2_Zc3&comma;index=real2d<00<cb=c24da=RootOf_Z54d2_Zc3&comma;index=real2d<00<cb=c24dRootOf_Z54d2_Zc3&comma;index=real2<ad<00<cc24d<bb<0a<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<00<cc24d<bb<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<00<cc24d<bb<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<0d<00<cc24d<bb<0a=0d<00<cc24d<bb<00<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<00<cc24d<bb<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<00<cc24d<bb<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<ad<00<cb=0a<RootOf_Z27d2_Z+4c3&comma;index=real1d<00<cb=0a=RootOf_Z27d2_Z+4c3&comma;index=real1d<00<cb=0RootOf_Z27d2_Z+4c3&comma;index=real1<aa<RootOf_Z27d2_Z+4c3&comma;index=real2d<00<cb=0a=RootOf_Z27d2_Z+4c3&comma;index=real2d<00<cb=0RootOf_Z27d2_Z+4c3&comma;index=real2<ad<00<c0<ba<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<00<c0<ba=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1d<00<c0<bRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<0d<00<c0<ba=0d<00<c0<b0<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<00<c0<ba=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2d<00<c0<bRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<ad=0c<0b<0a<b24cd=0c<0b<0a=b24cd=0c<0b<0b24c<aa<0d=0c<0b<0a=0d=0c<0b<00<ad=0c<0b=0a<0d=0c<0b=0a=0d=0c<0b=00<ad=0c<00<ba<b24cd=0c<00<ba=b24cd=0c<00<bb24c<aa<0d=0c<00<ba=0d=0c<00<b0<ad=0c=0b<0a<0d=0c=0b<0a=0d=0c=0b<00<ad=0c=0b=0a=0d=0c=0b=0a<0d=0c=0b=00<ad=0c=00<ba<0d=0c=00<ba=0d=0c=00<b0<ad=00<cb<0a<0d=00<cb<0a=0d=00<cb<00<aa<b24cd=00<cb<0a=b24cd=00<cb<0b24c<ad=00<cb=0a<0d=00<cb=0a=0d=00<cb=00<ad=00<c0<ba<0d=00<c0<ba=0d=00<c0<b0<aa<b24cd=00<c0<ba=b24cd=00<c0<bb24c<a0<dc<0b<0a<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<dc<0b<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<dc<0b<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<00<dc<0b<0a=00<dc<0b<00<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<dc<0b<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<dc<0b<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<a0<dc<0b=0a<RootOf_Z27d2_Z+4c3&comma;index=real10<dc<0b=0a=RootOf_Z27d2_Z+4c3&comma;index=real10<dc<0b=0RootOf_Z27d2_Z+4c3&comma;index=real1<aa<RootOf_Z27d2_Z+4c3&comma;index=real20<dc<0b=0a=RootOf_Z27d2_Z+4c3&comma;index=real20<dc<0b=0RootOf_Z27d2_Z+4c3&comma;index=real2<a0<dc<00<bb<c24da<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<dc<00<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<dc<00<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<00<dc<00<bb<c24da=00<dc<00<bb<c24d0<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<dc<00<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<dc<00<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<a0<dc<0b=c24da<RootOf_Z54d2_Zc3&comma;index=real10<dc<0b=c24da=RootOf_Z54d2_Zc3&comma;index=real10<dc<0b=c24dRootOf_Z54d2_Zc3&comma;index=real1<aa<RootOf_Z54d2_Zc3&comma;index=real20<dc<0b=c24da=RootOf_Z54d2_Zc3&comma;index=real20<dc<0b=c24dRootOf_Z54d2_Zc3&comma;index=real2<a0<dc<0c24d<bb<c23da<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<dc<0c24d<bb<c23da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<dc<0c24d<bb<c23dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<dc<0c24d<bb<c23da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<dc<0c24d<bb<c23dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<aa<00<dc<0c24d<bb<c23d0<a0<dc<0b=c23da<RootOf729d4_Z254c3_Zd2+c6&comma;index=real10<dc<0b=c23da=RootOf729d4_Z254c3_Zd2+c6&comma;index=real10<dc<0b=c23dRootOf729d4_Z254c3_Zd2+c6&comma;index=real1<aa<00<dc<0b=c23d0<a0<dc<0c23d<ba<00<dc<0c23d<b0<a0<dc=0b<0a<RootOf27_Z2d+4b3&comma;index=real10<dc=0b<0a=RootOf27_Z2d+4b3&comma;index=real10<dc=0b<0RootOf27_Z2d+4b3&comma;index=real1<aa<00<dc=0b<0a=00<dc=0b<00<aa<RootOf27_Z2d+4b3&comma;index=real20<dc=0b<0a=RootOf27_Z2d+4b3&comma;index=real20<dc=0b<0RootOf27_Z2d+4b3&comma;index=real2<a0<dc=0b=0a<00<dc=0b=00<a0<dc=00<ba<00<dc=00<b0<a0<d0<cb<0a<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<d0<cb<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<d0<cb<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<00<d0<cb<0a=00<d0<cb<00<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<d0<cb<0a=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<d0<cb<0RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<a0<d0<cb=0a<RootOf_Z27d2_Z+4c3&comma;index=real10<d0<cb=0a=RootOf_Z27d2_Z+4c3&comma;index=real10<d0<cb=0RootOf_Z27d2_Z+4c3&comma;index=real1<aa<RootOf_Z27d2_Z+4c3&comma;index=real20<d0<cb=0a=RootOf_Z27d2_Z+4c3&comma;index=real20<d0<cb=0RootOf_Z27d2_Z+4c3&comma;index=real2<a0<d0<c0<bb<c24da<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<d0<c0<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real10<d0<c0<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real1<aa<00<d0<c0<bb<c24da=00<d0<c0<bb<c24d0<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<d0<c0<bb<c24da=RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real20<d0<c0<bb<c24dRootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index=real2<a0<d0<cb=c24da<RootOf_Z54d2_Zc3&comma;index=real10<d0<cb=c24da=RootOf_Z54d2_Zc3&comma;index=real10<d0<cb=c24dRootOf_Z54d2_Zc3&comma;index=real1<aa<RootOf_Z54d2_Zc3&comma;index=real20<d0<cb=c24da=RootOf_Z54d2_Zc3&comma;index=real20<d0<cb=c24dRootOf_Z54d2_Zc3&comma;index=real2<a0<d0<cc24d<bb<c23da<00<d0<cc24d<bb<c23d0<aa<RootOf27d2_Z2+18bcd+4c3_Z+4b3db2c2&comma;index