completeness theorem for propositional logic
for any wff . The “if” part of the statement is the soundness theorem, and is proved here (http://planetmath.org/TruthValueSemanticsForPropositionalLogicIsSound). We will prove the “only if” part, which is also known as the completeness portion of the theorem. We will give a constructive proof of this. Before proving this, we state and prove some preliminary facts:
if and , then .
Facts 1 and 3 come from the axiom schema . From , we have , so . If is , we have fact 1, and if is , we have fact 3.
Fact 2: this is proved here (http://planetmath.org/SubstitutionTheoremForPropositionalLogic).
all the more so.
Fact 5: by induction on the number of occurrences of in . If , then is either or a propositional variable . In the first case, is , and from , we get , or . In the second case, . Now, suppose there are occurrences of in . Let be the propositional variables in . By unique readability, is for some unique wff’s and . Since each and has no more than occurrences of , by induction, we have
where the propositional variables in are , and in are . So
Next, we want to show that . We break this into four cases:
if is and is : then is , and use Fact 1
if is and is : then is , and use Fact 2
if is and is : then is , and use Fact 3
if is and is : then is , and use Fact 4.
In all cases, we have by applying modus ponens,
Fact 6 is proved here (http://planetmath.org/SubstitutionTheoremForPropositionalLogic). ∎
Propositional logic is complete with respect to truth-value semantics.
Suppose is a tautology. Let be the propositional variables in . Then
for any valuation . Since is . We have
If , then we are done. So suppose . Pick a valuation such that , and a valuation such that and Then
where the first deducibility relation comes from and the second comes from . By Fact 6 above,
So we have eliminated from the left of . Now, repeat this process until all of the have been eliminated, and we have . ∎
The completeness theorem can be used to show that certain complicated wff’s are theorems. For example, one of the distributive laws
To see that this is indeed a theorem, by the completeness theorem, all we need to show is that it is true using the truth table: