scientific article; zbMATH DE number 4012564
[For the entire collection see Zbl 0598.00008.] The aim of this paper is to advertise a notion of provability, originally known as Beth-semantic tableaux (Beth, 1959), then later adapted by R. Smullyan (1971) for classical logic and by M. Fitting (1969) for intuitionistic logic and for the modal system S4. The notion of provability we have in mind has the subformula property, i.e., each formula occurring in a proof of A is a subformula of A. Consequently, it is possible to describe a systematic procedure of searching for a proof of A such that (*) if this procedure does not provide a formal proof of A, then it yields a countermodel to A of the appropriate kind. An immediate result of this property (*) is the completeness theorem: if A is valid then A is formally provable. And what may be more important, using these proof systems one can give for many logics very perspicuous decidability proofs: in case the systematic search will terminate for all formulas in finitely many steps, the logic in question is clearly decidable. The present author has elaborated these ideas for intuionistic, modal, and counterfactual logics [J. Symb. Logic 41, 644-662 (1976; Zbl 0342.02013); Logique Anal. 23, 263-284 (1980; Zbl 0454.03007); J. Symb. Logic 48, 1-20 (1983; Zbl 0527.03005)]. As a consequence, rather theoretical decidability results for intuitionistic, modal, and counterfactual propositional calculi could be replaced by very practical decision procedures: given a formula A, the systematic procedure of searching for a proof of A constructs in a small, finite, number n(A) of steps (which, given A, can be determined in advance) either a formal proof of A (in which case A is formally provable and hence valid) or a concrete counterexample to A (in which case A is not valid and hence not formally provable). \textit{A. Urquhart} [J. Symb. Logic. 37, 159-169 (1972; Zbl 0245.02028)] presents an information-pieces semantics for relevant logic and mentions the decision problem for the set of all formulas valid in his information-pieces semantics as still being open [\textit{A. Urquhart}, The undecidability of entailment and relevant implication (to appear)]. Again, a Beth-type formal system can be developed such that the formulas provable in this system are precisely the formulas valid in Urquhart's semantics (\(\neg A\) is defined as \(A\to f)\). However, in this case the systematic search does not always terminate in finitely many steps.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3762280)