1734 Sledgehammer manual \cite{isabelle-sledgehammer} for details. The |
1734 Sledgehammer manual \cite{isabelle-sledgehammer} for details. The |
1735 directory @{file "~~/src/HOL/Metis_Examples"} contains several small |
1735 directory @{file "~~/src/HOL/Metis_Examples"} contains several small |
1736 theories developed to a large extent using @{method (HOL) metis}. |
1736 theories developed to a large extent using @{method (HOL) metis}. |
1737 |
1737 |
1738 \end{description} |
1738 \end{description} |
|
1739 *} |
|
1740 |
|
1741 |
|
1742 section {* Algebraic reasoning via Gr\"obner bases *} |
|
1743 |
|
1744 text {* |
|
1745 \begin{matharray}{rcl} |
|
1746 @{method_def (HOL) "algebra"} & : & @{text method} \\ |
|
1747 @{attribute_def (HOL) algebra} & : & @{text attribute} \\ |
|
1748 \end{matharray} |
|
1749 |
|
1750 @{rail " |
|
1751 @@{method (HOL) algebra} |
|
1752 ('add' ':' @{syntax thmrefs})? |
|
1753 ('del' ':' @{syntax thmrefs})? |
|
1754 ; |
|
1755 @@{attribute (HOL) algebra} (() | 'add' | 'del') |
|
1756 "} |
|
1757 |
|
1758 \begin{description} |
|
1759 |
|
1760 \item @{method (HOL) algebra} performs algebraic reasoning via |
|
1761 Gr\"obner bases, see also \cite{Chaieb-Wenzel:2007} and |
|
1762 \cite[\S3.2]{Chaieb-thesis}. The method handles deals with two main |
|
1763 classes of problems: |
|
1764 |
|
1765 \begin{enumerate} |
|
1766 |
|
1767 \item Universal problems over multivariate polynomials in a |
|
1768 (semi)-ring/field/idom; the capabilities of the method are augmented |
|
1769 according to properties of these structures. For this problem class |
|
1770 the method is only complete for algebraically closed fields, since |
|
1771 the underlying method is based on Hilbert's Nullstellensatz, where |
|
1772 the equivalence only holds for algebraically closed fields. |
|
1773 |
|
1774 The problems can contain equations @{text "p = 0"} or inequations |
|
1775 @{text "q \<noteq> 0"} anywhere within a universal problem statement. |
|
1776 |
|
1777 \item All-exists problems of the following restricted (but useful) |
|
1778 form: |
|
1779 |
|
1780 @{text [display] "\<forall>x\<^sub>1 \<dots> x\<^sub>n. |
|
1781 e\<^sub>1(x\<^sub>1, \<dots>, x\<^sub>n) = 0 \<and> \<dots> \<and> e\<^sub>m(x\<^sub>1, \<dots>, x\<^sub>n) = 0 \<longrightarrow> |
|
1782 (\<exists>y\<^sub>1 \<dots> y\<^sub>k. |
|
1783 p\<^sub>1\<^sub>1(x\<^sub>1, \<dots> ,x\<^sub>n) * y\<^sub>1 + \<dots> + p\<^sub>1\<^sub>k(x\<^sub>1, \<dots>, x\<^sub>n) * y\<^sub>k = 0 \<and> |
|
1784 \<dots> \<and> |
|
1785 p\<^sub>t\<^sub>1(x\<^sub>1, \<dots>, x\<^sub>n) * y\<^sub>1 + \<dots> + p\<^sub>t\<^sub>k(x\<^sub>1, \<dots>, x\<^sub>n) * y\<^sub>k = 0)"} |
|
1786 |
|
1787 Here @{text "e\<^sub>1, \<dots>, e\<^sub>n"} and the @{text "p\<^sub>i\<^sub>j"} are multivariate |
|
1788 polynomials only in the variables mentioned as arguments. |
|
1789 |
|
1790 \end{enumerate} |
|
1791 |
|
1792 The proof method is preceded by a simplification step, which may be |
|
1793 modified by using the form @{text "(algebra add: ths\<^sub>1 del: ths\<^sub>2)"}. |
|
1794 This acts like declarations for the Simplifier |
|
1795 (\secref{sec:simplifier}) on a private simpset for this tool. |
|
1796 |
|
1797 \item @{attribute algebra} (as attribute) manages the default |
|
1798 collection of pre-simplification rules of the above proof method. |
|
1799 |
|
1800 \end{description} |
|
1801 *} |
|
1802 |
|
1803 |
|
1804 subsubsection {* Example *} |
|
1805 |
|
1806 text {* The subsequent example is from geometry: collinearity is |
|
1807 invariant by rotation. *} |
|
1808 |
|
1809 type_synonym point = "int \<times> int" |
|
1810 |
|
1811 fun collinear :: "point \<Rightarrow> point \<Rightarrow> point \<Rightarrow> bool" where |
|
1812 "collinear (Ax, Ay) (Bx, By) (Cx, Cy) \<longleftrightarrow> |
|
1813 (Ax - Bx) * (By - Cy) = (Ay - By) * (Bx - Cx)" |
|
1814 |
|
1815 lemma collinear_inv_rotation: |
|
1816 assumes "collinear (Ax, Ay) (Bx, By) (Cx, Cy)" and "c\<twosuperior> + s\<twosuperior> = 1" |
|
1817 shows "collinear (Ax * c - Ay * s, Ay * c + Ax * s) |
|
1818 (Bx * c - By * s, By * c + Bx * s) (Cx * c - Cy * s, Cy * c + Cx * s)" |
|
1819 using assms by (algebra add: collinear.simps) |
|
1820 |
|
1821 text {* |
|
1822 See also @{"file" "~~/src/HOL/ex/Groebner_Examples.thy"}. |
1739 *} |
1823 *} |
1740 |
1824 |
1741 |
1825 |
1742 section {* Coherent Logic *} |
1826 section {* Coherent Logic *} |
1743 |
1827 |