## You are here

Homecompleteness theorem for propositional logic

## Primary tabs

# 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.

## Mathematics Subject Classification

03B05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections