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. In symbol, we have
$\models A\quad\mbox{iff}\quad\vdash A$ 
for any wff $A$. The “if” part of the statement is the soundness theorem, and is proved here. 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:
1. $A,B\vdash A\to B$
2. $A,\neg B\vdash\neg(A\to B)$
3. $\neg A,B\vdash A\to B$
4. $\neg A,\neg B\vdash A\to B$
5. Let $v$ be a valuation. For any wff $A$, let $v[A]$ be defined as follows:
$v[A]\textrm{ is }\left\{\begin{array}[]{ll}A&\textrm{if }v(A)=1,\\ \neg A&\textrm{if }v(A)=0.\end{array}\right.$ Suppose $p_{1},\ldots,p_{n}$ are the propositional variables in $A$. Then
$v[p_{1}],\ldots,v[p_{n}]\vdash v[A].$ 6. if $\Delta,A\vdash B$ and $\Delta,\neg A\vdash B$, then $\vdash B$.
Proof.
Facts 1 and 3 come from the axiom schema $B\to(A\to B)$. From $\vdash B\to(A\to B)$, we have $C\vdash B\to(A\to B)$, so $C,B\vdash A\to B$. If $C$ is $A$, we have fact 1, and if $C$ is $\neg A$, we have fact 3.
Fact 2: this is proved here.
Fact 4: By ex falso quodlibet, $\vdash\perp\to B$, so $A\vdash\perp\to B$, and therefore $\vdash A\to(\perp\to B)$ by the deduction theorem. Now, $(A\to(\perp\to B))\to((A\to\perp)\to(A\to B))$ is an axiom instance, so $\vdash(A\to\perp)\to(A\to B)$, or $\vdash\neg A\to(A\to B)$, or $\neg A\vdash A\to B$, and
$\neg A,\neg B\vdash A\to B$ 
all the more so.
Fact 5: by induction on the number $n$ of occurrences of $\to$ in $A$. If $n=0$, then $A$ is either $\perp$ or a propositional variable $p$. In the first case, $v[A]$ is $\neg\perp$, and from $\perp\vdash\perp$, we get $\vdash\perp\to\perp$, or $\vdash\neg\perp$. In the second case, $v[p]\vdash v[p]$. Now, suppose there are $n+1$ occurrences of $\to$ in $A$. Let $p_{1},\ldots,p_{m}$ be the propositional variables in $A$. By unique readability, $A$ is $B\to C$ for some unique wff’s $B$ and $C$. Since each $B$ and $C$ has no more than $n$ occurrences of $\to$, by induction, we have
$v[p_{{i(1)}}],\ldots,v[p_{{i(s)}}]\vdash v[B]\qquad\mbox{and}\qquad v[p_{{j(1)% }}],\ldots,v[p_{{j(t)}}]\vdash v[C],$ 
where the propositional variables in $B$ are $p_{{i(1)}},\ldots,p_{{i(s)}}$, and in $C$ are $p_{{j(1)}},\ldots,p_{{j(t)}}$. So
$v[p_{1}],\ldots,v[p_{m}]\vdash v[B]\qquad\mbox{and}\qquad v[p_{1}],\ldots,v[p_% {m}]\vdash v[C].$ 
Next, we want to show that $v[B],v[C]\vdash v[B\to C]$. We break this into four cases:

if $v[B]$ is $B$ and $v[C]$ is $C$: then $v[B\to C]$ is $B\to C$, and use Fact 1

if $v[B]$ is $B$ and $v[C]$ is $\neg C$: then $v[B\to C]$ is $\neg(B\to C)$, and use Fact 2

if $v[B]$ is $\neg B$ and $v[C]$ is $C$: then $v[B\to C]$ is $B\to C$, and use Fact 3

if $v[B]$ is $\neg B$ and $v[C]$ is $\neg C$: then $v[B\to C]$ is $B\to C$, and use Fact 4.
In all cases, we have by applying modus ponens,
$v[p_{1}],\ldots,v[p_{m}]\vdash v[B\to C].$ 
Fact 6 is proved here. ∎
Theorem 1.
Propositional logic is complete with respect to truthvalue semantics.
Proof.
Suppose $A$ is a tautology. Let $p_{1},\ldots,p_{n}$ be the propositional variables in $A$. Then
$v[p_{1}],\ldots,v[p_{n}]\vdash v[A]$ 
for any valuation $v$. Since $v[A]$ is $A$. We have
$v[p_{1}],\ldots,v[p_{n}]\vdash A.$ 
If $n=0$, then we are done. So suppose $n>0$. Pick a valuation $v$ such that $v(p_{n})=1$, and a valuation $v^{{\prime}}$ such that $v^{{\prime}}(p_{i})=v(p_{i})$ and $v^{{\prime}}(p_{n})=0$ Then
$v[p_{1}],\ldots,v[p_{{n1}}],p_{n}\vdash A\qquad\mbox{and}\qquad v[p_{1}],% \ldots,v[p_{{n1}}],\neg p_{n}\vdash A,$ 
where the first deducibility relation comes from $v$ and the second comes from $v^{{\prime}}$. By Fact 6 above,
$v[p_{1}],\ldots,v[p_{{n1}}]\vdash A.$ 
So we have eliminated $v[p_{n}]$ from the left of $v[p_{1}],\ldots,v[p_{n}]\vdash A$. Now, repeat this process until all of the $v[p_{i}]$ have been eliminated, and we have $\vdash A$. ∎
The completeness theorem can be used to show that certain complicated wff’s are theorems. For example, one of the distributive laws
$\vdash(A\land B)\lor C\leftrightarrow(A\lor C)\land(B\lor C)$ 
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:
$(A$  $\land$  $B)$  $\lor$  $C$  $\leftrightarrow$  $(A$  $\lor$  $C)$  $\land$  $(B$  $\lor$  $C)$ 

T  T  T  T  T  T  T  T  T  T  T  T  T 
T  T  T  T  F  T  T  T  F  T  T  T  F 
T  F  F  T  T  T  T  T  T  T  F  T  T 
T  F  F  F  F  T  T  T  F  F  F  F  F 
F  F  T  T  T  T  F  T  T  T  T  T  T 
F  F  T  F  F  T  F  F  F  F  T  T  F 
F  F  F  T  T  T  F  T  T  T  F  T  T 
F  F  F  F  F  T  F  F  F  F  F  F  F 
Similarly, one can show $\vdash(A\lor B)\land C\leftrightarrow(A\land C)\lor(B\land C)$.
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