Abstract
We propose to combine interactive proof construction with proof automation for a fragment of first-order logic called Coherent Logic (CL). CL allows enough existential quantification to make Skolemization unnecessary. Moreover, CL has a constructive proof system based on forward reasoning, which is easy to automate and where standardized proof objects can easily be obtained. We have implemented in Prolog a CL prover which generates Coq proof scripts. We test our approach with a case study: Hessenberg’s Theorem, which states that in elementary projective plane geometry Pappus’ Axiom implies Desargues’ Axiom. Our CL prover makes it possible to automate large parts of the proof, in particular taking care of the large number of degenerate cases.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bezem, M., Coquand, T.: Newman’s lemma—a case study in proof automation and geometric logic. In: Păun, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science, vol. 2, pp. 267–282. World Scientific, Singapore (2004)
Bezem, M., Coquand, T.: Automating coherent logic. In: Sutcliffe, G., Voronkov, A. (eds.) Proceedings LPAR-12. Lecture Notes in Computer Science, vol. 3825, pp. 246–260. Springer-Verlag, Berlin (2005)
Bezem, M., Hendriks, D.: Web page including CL tool, input files, Coq files. http://www.cs.vu.nl/~diem/research/ht/.
Bezem, M., Hendriks, D., de Nivelle, H.: Automated proof construction in type theory using resolution. J. Autom. Reason. 29(3), 253–275 (2002)
Bonichon, R., Delahaye, D., Doligez, D.: Zenon: an extensible automated theorem prover producing checkable proofs. In: Dershowitz, N., Voronkov, A. (eds.) Proceedings LPAR-14. Lecture Notes in Computer Science, vol. 4790, pp. 151–165. Springer-Verlag, Berlin (2007)
Coxeter, H.S.M.: The Real Projective Plane, 2nd edn. Cambridge University Press, Cambridge (1955)
Cronheim, A.: A proof of Hessenberg’s theorem. Proc. AMS 4(2), 219–221 (1953)
de Nivelle, H.: Translation of resolution proofs into short first-order proofs without choice axioms. Inf. Comput. 199(1), 24–54 (2005) [Special Issue on the 19th International Conference on Automated Deduction (CADE-19)]
de Nivelle, H., Meng, J.: Geometric resolution: a proof procedure based on finite model search. In: Harrison, J., Furbach, U., Shankar, N. (eds.) International Joint Conference on Automated Reasoning 2006, p. 15. Springer, Seattle (2006)
Harper, R., Honsell, F., Plotkin, G.D.: A framework for defining logics. J. ACM, 40(1), 143–184 (1993)
Hessenberg, G.: Beweis des Desarguesschen Satzes aus dem Pascalschen. Math. Ann. 61, 161–172 (1905)
Johnstone, P.: Sketches of an Elephant: A Topos Theory Compendium, vol. 2. Oxford University Press, London (2002)
Kusak, E., Leończuk, W.: Hessenberg theorem. Formaliz. Math. 2(2), 217–219 (1991)
Nederpelt, R.P., Geuvers, J.H., de Vrijer, R.C. (eds.): Selected Papers on Automath. North-Holland, Amsterdam (1994)
Paulson, L.C.: Isabelle: A Generic Theorem Prover (with a contribution by T. Nipkow). Lecture Notes in Computer Science, vol. 828. Springer, Berlin (1994)
Paulson, L.C.: A generic tableau prover and its integration with Isabelle. J. Univers. Comput. Sci. 5(3), 73–87 (1999)
Robinson, J.A., Voronkov, A. (eds.): Handbook of Automated Reasoning (in 2 volumes). Elsevier and MIT Press, Amsterdam (2001)
Skolem, Th.: Logisch-Kombinatorische Untersuchungen über die Erfüllbarkeit und Beweisbarkeit Mathematischen Sätze nebst einem Theoreme über Dichte Mengen, Skrifter I, 4, 1–36, Det Norske Videnskaps-Akademi, 1920. In: Fenstad, J.E. (ed.) Selected Works in Logic, pp. 103–136. Universitetsforlaget, Oslo (1970)
Sutcliffe, G., Suttner, C.: The TPTP problem library: CNF release v1.2.1. J. Autom. Reason. 21(2), 177–203 (1998)
Sutcliffe, G., Suttner, C.: The state of CASC. AI Commun. 19(1), 35–48 (2006)
The Coq development team. The Coq Proof Assistant Reference Manual, version 8.1, 2006. http://coq.inria.fr/.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bezem, M., Hendriks, D. On the Mechanization of the Proof of Hessenberg’s Theorem in Coherent Logic. J Autom Reasoning 40, 61–85 (2008). https://doi.org/10.1007/s10817-007-9086-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10817-007-9086-x