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:
Propositional logic is sound with respect to truth-value semantics.
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 , then we have
Before proving the completeness portion of the theorem, we need the following
Propositional logic is complete with respect to truth-value semantics.
|Title||completeness theorem for propositional logic|
|Date of creation||2013-03-22 19:32:44|
|Last modified on||2013-03-22 19:32:44|
|Last modified by||CWoo (3771)|