completeness theorem for propositional logic


The completeness theorem of propositional logicPlanetmathPlanetmath is the statement that a wff is tautologyMathworldPlanetmath iff it is a theorem. The if part of the statement is the soundness theorem, and the only if part is the completeness theorem. We will prove the two parts separately here. We begin with the easier one:

Theorem 1.

Propositional logic is sound with respect to truth-value semantics.

Proof.

Basically, we need to show that every axiom is a tautology, and that the inference rule modus ponensMathworldPlanetmath preserves truth. Since theorems are deduced from axioms and by applications of modus ponens, they are tautologies as a result.

Using truth tablesMathworldPlanetmath, one easily verifies that every axiom is true (under any valuation). For example, if the axiom is of the form A(BA), then we have

Before proving the completeness portion of the theorem, we need the following

Theorem 2.

Propositional logic is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath with respect to truth-value semantics.

Title completeness theorem for propositional logicPlanetmathPlanetmath
Canonical name CompletenessTheoremForPropositionalLogic
Date of creation 2013-03-22 19:32:44
Last modified on 2013-03-22 19:32:44
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 4
Author CWoo (3771)
Entry type Theorem
Classification msc 03B05