completeness theorem for propositional logic

The completeness theorem of propositional logic is the statement that a wff is tautology 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 ponens preserves truth. Since theorems are deduced from axioms and by applications of modus ponens, they are tautologies as a result.

Using truth tables, one easily verifies that every axiom is true (under any valuation). For example, if the axiom is of the form $A\to (B\to A)$, then we have

∎

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

Theorem 2.

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

Title	completeness theorem for propositional logic
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