Proof of Theorem by Truth Table

Theorem

Let $\phi$ be a logical formula whose atoms are $p_1, p_2, \ldots, p_n$.

Let $l$ be the line number of any row in the truth table of $\phi$.

For all $i: 1 \le i \ne n$, let $\hat {p_i}$ be defined as:

$\hat {p_i} = \begin{cases} p_i & : \text {the entry in line } l \text { of } p_i \text { is } T \\ \neg p_i & : \text {the entry in line } l \text { of } p_i \text { is } F \end{cases}$

Then:

• $\hat {p_1}, \hat {p_2}, \ldots, \hat {p_n} \vdash \phi$ is provable if the entry for $\phi$ in line $l$ is $T$
• $\hat {p_1}, \hat {p_2}, \ldots, \hat {p_n} \vdash \neg \phi$ is provable if the entry for $\phi$ in line $l$ is $F$

Proof

$1:$ Suppose $\phi$ is an atom $p$.

Then we need to show that $p \vdash p$ and $\neg p \vdash \neg p$.

These are proved in one line in the proof of the Law of Identity.

$2:$ Suppose $\phi$ is of the form $\neg \phi_1$.

There are two cases to consider:

• Suppose $\phi$ evaluates to $T$.