×

Representing scope in intuitionistic deductions. (English) Zbl 0912.68188

Summary: Intuitionistic proofs can be segmented into scopes which describe when assumptions can be used. In standard descriptions of intuitionistic logic, these scopes occupy contiguous regions of proofs. This leads to an explosion in the search space for automated deduction, because of the difficulty of planning to apply a rule inside a particular scoped region of the proof. This paper investigates an alternative representation which assigns scope explicitly to formulas, and which is inspired in part by semantics-based translation methods for modal deduction. This calculus is simple and is justified by direct proof-theoretic arguments that transform proofs in the calculus so that scopes match standard descriptions. A Herbrand theorem, established straightforwardly, lifts this calculus to incorporate unification. The resulting system has no impermutabilities whatsoever – rules of inference may be used equivalently anywhere in the proof. Nevertheless, a natural specification describes how \(\lambda\)-terms are to be extracted from its deductions.

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03B60 Other nonclassical logic

Software:

Nuprl
Full Text: DOI

References:

[1] Aitken, S. J.; Reichgelt, H.; Shadbolt, N., Resolution theorem proving in reified modal logics, J. Automat. Reason., 12, 1, 103-129 (1994) · Zbl 0810.03009
[2] Andreoli, J. M., Logic programming with focusing proofs in linear logic, J. Logic Comput., 2, 3, 297-347 (1992) · Zbl 0764.03020
[3] Andrews, P. B., Theorem proving via general matings, J. Assoc. Comput. Mach., 28, 2, 193-214 (1981) · Zbl 0456.68119
[4] Auffray, Y.; Enjalbert, P., Modal theorem proving: an equational viewpoint, J. Logic Comput., 2, 3, 247-295 (1992) · Zbl 0757.03007
[5] Bibel, W., Automated Theorem Proving (1982), Vieweg: Vieweg Braunschweig · Zbl 0492.68067
[6] Bittel, O., Tableau-based theorem proving and synthesis of λ-terms in the intuitionistic logic, (Logics in AI. Logics in AI, Lecture Notes in Computer Science, vol. 633 (1992), Springer: Springer Berlin), 262-278 · Zbl 0925.03083
[7] Bittel, O., A tableau-based theorem proving method for intuitionistic logic, (Automated Deduction in Nonstandard Logics: Papers from the 1993 Fall Symp.. Automated Deduction in Nonstandard Logics: Papers from the 1993 Fall Symp., AAAI Press Technical Report FS-93-01 (1993)), 9-16
[8] Boyer, R. S.; Moore, J. S., The sharing of structure in theorem-proving programs, (Meltzer, B.; Michie, D., Machine Intelligence, 7 (1972), Edinburgh University Press), 101-116 · Zbl 0249.68032
[9] Constable, R. L., Implementing Mathematics with the Nuprl Proof Development System (1986), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[10] D’Agostino, M., Are tableaux and improvement on truth-tables, J. Logic Language Inform., 1, 235-252 (1992) · Zbl 0793.03059
[11] D’Agostino, M.; Gabbay, D. M., A generalization of analytic deduction via labelled deductive systems. part I: Basic substructural logics, J. Automat. Reason., 13, 243-281 (1994) · Zbl 0816.03012
[12] D’Agostino, M.; Mondadori, M., The taming of the cut. classical refutations with analytic cut, J. Logic Comput., 4, 285-319 (1994) · Zbl 0806.03037
[13] Debart, F.; Enjalbert, P.; Lescot, M., Multimodal logic programming using equational and order-sorted logic, Theoret. Comput. Sci., 105, 141-166 (1992) · Zbl 0756.68090
[14] Dyckhoff, R., Contraction-free sequent calculi for intuitionistic logic, J. Symbolic Logic, 57, 795-807 (1992) · Zbl 0761.03004
[15] Felty, A., A logic program for transforming sequent proofs to natural deduction proofs, (Schroeder-Heister, P., Proc. 1989 Internat. Workshop on Extensions of Logic Programming. Proc. 1989 Internat. Workshop on Extensions of Logic Programming, Lecture Notes in Artificial Intelligence (1991)), 157-178 · Zbl 1502.68063
[16] Fitting, M. C., Intuitionistic Logic, Model Theory and Forcing (1969), North-Holland: North-Holland Amsterdam · Zbl 0188.32003
[17] Fitting, M., Proof Methods for Modal and Intuitionistic Logics, (Synthese Library, vol. 169 (1983), D. Reidel: D. Reidel Dordrecht) · Zbl 0523.03013
[18] Fitting, M., A modal Herbrand theorem, Fund. Inform., 28, 101-122 (1996) · Zbl 0863.68102
[19] Gallier, J. H., Logic for Computer Science: Foundations of Automated Theorem Proving (1986), Harper and Row: Harper and Row New York · Zbl 0605.03004
[20] Gallier, J., Constructive logics. I. A tutorial on proof systems and typed λ-calculi, Theoret. Comput. Sci., 110, 2, 249-339 (1993) · Zbl 0772.03026
[21] Galmiche, D.; Perrier, G., On proof normalization in linear logic, Theoret. Comput. Sci., 135, 67-110 (1994) · Zbl 0815.03033
[22] Girard, J. Y., Linear logic, Theoret. Comput. Sci., 50, 1, 1-102 (1987) · Zbl 0625.03037
[23] Herbelin, H., A λ-caculus structure isomorphic to Gentzen-style sequent calculus structure, (CSL 94 (1994), Springer: Springer Berlin), 61-75 · Zbl 1044.03509
[24] Howard, W. A., The formulae-as-types notion of construction, (To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalism (1980), Academic Press: Academic Press New York), 479-490
[25] Jackson, P.; Reichgelt, H., A general proof method for first-order modal logic, (Proc. IJCAI (1987)), 942-944
[26] Kleene, S. C., Permutation of inferences in Gentzen’s calculi LK and LJ, (Two Papers on the Predicate Calculus (1951), American Mathematical Society: American Mathematical Society Providence, RI), 1-26 · Zbl 0047.25002
[27] Kleene, S. C., Introduction to Metamathematics (1952), North-Holland: North-Holland Amsterdam · Zbl 0047.00703
[28] Kripke, S. A., Semantical analysis of intuitionistic logic, (Crossley, J.; Dummett, M. A.E., Formal Systems and Recursive Functions (1965), North-Holland: North-Holland Amsterdam), 92-130 · Zbl 0137.00702
[29] Lincoln, P. D.; Shankar, N., Proof search in first-order linear logic and other cut-free sequent calculi, (LICS (1994)), 282-291
[30] Martin-Löf, P., Constructive mathematics and computer programming, (Cohen, L. J., Logic, Methodology and Philosophy of Science, vol. VI (1982), North-Holland: North-Holland Amsterdam), 153-175 · Zbl 0552.03040
[31] Miller, D., A logical analysis of modules in logic programming, J. Logic Programming, 6, 1-2, 79-108 (1989) · Zbl 0681.68022
[32] Miller, D.; Nadathur, G.; Pfenning, F.; Scedrov, A., Uniform proofs as a foundation for logic programming, Ann. Pure Appl. Logic, 51, 125-157 (1991) · Zbl 0721.03037
[33] Miller, D., A multiple-conclusion meta-logic, (Abramsky, S., Proc. Internat. Symp. on Logics Comput. Sci. (1994)), 272-281
[34] Nadathur, G., A proof procedure for the logic of hereditary Harrop formulas, J. Automat. Reason., 11, 115-145 (1993) · Zbl 0796.03012
[35] Ohlbach, H. J., Semantics-based translation methods for modal logics, J. Logic Comput., 1, 691-746 (1991) · Zbl 0746.03010
[36] Ohlbach, H. J., Optimized translation of multi modal logic into predicate logic, (Voronkov, A., Logic Programming and Automated Reasoning. Logic Programming and Automated Reasoning, Lecture Notes in Computer Science, vol. 698 (1993), Springer: Springer Berlin), 253-264 · Zbl 0793.68138
[37] Otten, J.; Kreitz, C., T-string-unification: unifying prefixes in non-classical proof methods, (TABLEAUX 96. TABLEAUX 96, Lecture Notes in Artificial Intelligence, vol. 1071 (1996), Springer: Springer Berlin), 244-260 · Zbl 1412.68251
[38] Prawitz, D., Ideas and results in proof theory, (Fenstad, J. E., Proc. 2nd Scand. Logic Symp., North-Holland. Proc. 2nd Scand. Logic Symp., North-Holland, Amsterdam (1971)), 235-307 · Zbl 0226.02031
[39] Schellinx, H., Some syntactical observations on linear logic, J. Logic Comput., 1, 537-559 (1991) · Zbl 0745.03025
[40] Shankar, N., Proof search in the intuitionistic sequent calculus, (Automated Deduction: CADE 11 (1992), Springer: Springer Berlin), 522-536 · Zbl 0925.03066
[41] Smullyan, R. M., First-order Logic, (Ergebnisse der Mathematik und ihere Grenzgebeite, vol. 43 (1968), Springer: Springer Berlin) · Zbl 0172.28901
[42] Smullyan, R. M., A generalization of intuitionistic and modal logics, (Leblanc, H., Truth, Syntax and Modality (1973), North-Holland: North-Holland Amsterdam), 274-293 · Zbl 0268.02017
[43] M. Stone, Efficient constraints on possible worlds for reasoning about necessity, Technical Report IRCS 97-7 and CIS 97-10, University of Pennsylvania.; M. Stone, Efficient constraints on possible worlds for reasoning about necessity, Technical Report IRCS 97-7 and CIS 97-10, University of Pennsylvania.
[44] Tammet, T., Proof strategies in linear logic, J. Automat. Reason., 12, 273-304 (1994) · Zbl 0821.03004
[45] Tennant, N., Autologic, (Edinburgh Information Technology Series, No. 9 (1992), Edinburgh University Press: Edinburgh University Press Edinburgh) · Zbl 0584.03008
[46] Troelstra, A. S.; van Dalen, D., (Constructivism in Mathematics, vol. 1 (1988), North-Holland: North-Holland Amsterdam) · Zbl 0661.03047
[47] Troelstra, A. S.; van Dalen, D., (Constructivism in Mathematics, vol. 2 (1988), North-Holland: North-Holland Amsterdam) · Zbl 0661.03047
[48] Veldman, W., An intuitionistic completeness theorem for intuitionistic predicate logic, J. Symbolic Logic, 41, 159-166 (1976) · Zbl 0355.02018
[49] Voronkov, A., Proof-search in intuitionistic logic based on constraint satisfaction, (TABLEAUX 96. TABLEAUX 96, Lecture Notes in Artificial Intelligence, vol. 1071 (1996), Springer: Springer Berlin), 312-329 · Zbl 1415.03010
[50] Wallen, L. A., Automated Proof Search in Non-Classical Logics: Efficient Matrix Proof Methods for Modal and Intuitionistic Logics (1990), MIT Press: MIT Press Cambridge · Zbl 0782.03003
[51] Schmitt, S., Ein erweiterter intuitionistischer Sequenzenkalkül und dessen Anwendung im intutitiotistischen Konnektionsbeweisen, (Master’s Thesis (1994), TH Darmstadt)
[52] Schmitt, S.; Kreitz, C., On transforming intuitionistic matrix proofs into standard-sequent proofs, (Proc. Fourth Workshop on Theorem Proving with Analytic Tableaux and Related Methods. Proc. Fourth Workshop on Theorem Proving with Analytic Tableaux and Related Methods, LNAI, volume 918 (1995)), 106-121
[53] Schmitt, S.; Kreitz, C., Converting non-classical matrix proofs into sequent-style systems, (McRobbie, M.; Slaney, J., Proc. Thirteenth International Conference on Automated Deduction. Proc. Thirteenth International Conference on Automated Deduction, LNAI, volume 1104 (1996)), 418-432 · Zbl 1415.03031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.