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