2008•Unpublished venueRequires access

Fundamental Results in Propositional Logic

Raymond Smullyan

Open publisher page 0 citations

Abstract

It should be intuitively obvious that any formula provable by the tableau method must really be a tautology, or, equivalently, the fact that a tableau closes must mean that the origin is not satisfiable (not true under any interpretation). This intuition can be justified by the following argument. If a tableau T is satisfiable, then any immediate extension T1 of T is satisfiable, hence any immediate extension T2 of the extension T1 is satisfiable, and so forth. Thus every extension of T is satisfiable, and hence no extension of T can close. If all finite subsets of a denumerable set S are satisfiable, then S is satisfiable. This is known as the Compactness Theorem for Propositional Logic. For a denumerable set S of formulas, if all finite subsets of S are satisfiable, then no tableau for S can close.

About this research paper

What this paper is about

It should be intuitively obvious that any formula provable by the tableau method must really be a tautology, or, equivalently, the fact that a tableau closes must mean that the origin is not satisfiable (not true under any interpretation). This intuition can be justified by the following argument. If a tableau T is satisfiable, then any immediate extension T1 of T is satisfiable, hence any immediate extension T2 of the extension T1 is satisfiable, and so forth. Thus every extension of T is satisfiable, and hence no extension of T can close. If all finite subsets of a denumerable set S are satisfiable, then S is satisfiable. This is known as the Compactness Theorem for Propositional Logic. For a denumerable set S of formulas, if all finite subsets of S are satisfiable, then no tableau for S can close.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

It should be intuitively obvious that any formula provable by the tableau method must really be a tautology, or, equivalently, the fact that a tableau closes must mean that the origin is not satisfiable (not true under any interpretation). This intuition can be justified by the following argument. If a tableau T is satisfiable, then any immediate extension T1 of T is satisfiable, hence any immediate extension T2 of the extension T1 is satisfiable, and so forth. Thus every extension of T is satisfiable, and hence no extension of T can close. If all finite subsets of a denumerable set S are satisfiable, then S is satisfiable. This is known as the Compactness Theorem for Propositional Logic. For a denumerable set S of formulas, if all finite subsets of S are satisfiable, then no tableau for S can close.

Key concepts: Autoepistemic logic, Zeroth-order logic, Propositional variable, Well-formed formula, Propositional calculus, Computer science, Intermediate logic, Mathematics

Related papers

Back to paper searchBrowse research topicsOriginal source
Fundamental Results in Propositional Logic — Research Paper | ScholarLens