Proof of Theorem by Truth Table
Jump to navigation
Jump to search
Theorem
Let $\phi$ be a propositional 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:
- $(1): \quad \hat {p_1}, \hat {p_2}, \ldots, \hat {p_n} \vdash \phi$ is provable if the entry for $\phi$ in line $l$ is $\T$
- $(2): \quad \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): \quad$ 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): \quad$ Suppose $\phi$ is of the form $\neg \phi_1$.
There are two cases to consider:
Suppose $\phi$ evaluates to $\T$.
This needs considerable tedious hard slog to complete it. In particular: More hard work. I'll come back to this once I've got some more basics done. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |