## You are here

Hometruth-value semantics for propositional logic is sound

## Primary tabs

# truth-value semantics for propositional logic is sound

The soundness theorem of propositional logic says the following: every theorem is a tautology. In symbol: $\vdash A$ implies $\models A$ for any wff $A$.

###### Theorem 1.

Propositional logic is sound with respect to truth-value semantics.

###### Proof.

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).

First, let us verify that $(A\to B)\to(\neg B\to\neg A)$ is a tautology. The corresponding truth table is

$A$ | $B$ | $\neg A$ | $\neg B$ | $A\to B$ | $\neg B\to\neg A$ | $(A\to B)\to(\neg B\to\neg A)$ |
---|---|---|---|---|---|---|

T | T | F | F | T | T | T |

T | F | F | T | F | F | T |

F | T | T | F | T | T | T |

F | F | T | T | T | T | T |

Checking the truth values in the last column confirms that $(A\to B)\to(\neg B\to\neg A)$ is a tautology.

Next, let us check that $(A\to(B\to C))\to((A\to B)\to(A\to C))$ is a tautology. This time, we use a “reduced” truth table.

$(A$ | $\to$ | $(B$ | $\to$ | $C))$ | $\to$ | $((A$ | $\to$ | $B)$ | $\to$ | $(A$ | $\to$ | $C))$ |
---|---|---|---|---|---|---|---|---|---|---|---|---|

T | T | T | T | T | T | T | T | T | T | T | T | T |

T | F | T | F | F | T | T | T | T | F | T | F | F |

T | T | F | T | T | T | T | F | F | T | T | T | T |

T | T | F | T | F | T | T | F | F | T | T | F | F |

F | T | T | T | T | T | F | T | T | T | F | T | T |

F | T | T | F | F | T | F | T | T | T | F | T | F |

F | T | F | T | T | T | F | T | F | T | F | T | T |

F | T | F | T | F | T | F | T | F | T | F | T | F |

Notice that the truth values under the third $\to$ are all $T$, hence $(A\to(B\to C))\to((A\to B)\to(A\to C))$ is a tautology.

Finally, we check that $A\to(B\to A)$ is a tautology. This can be done without truth tables. Let $v$ be a valuation. We may assume $v(A)=1$, since $v(A\to(B\to A))=1$ otherwise. If $v(A)=1$, then $v(B\to A)=1$ no matter what $v(B)$ is. Therefore, $v(A\to(B\to A))=1$, and $A\to(B\to A)$ is a tautology.

Next, we show that modus ponens preserves truths. In other words, $V(A)=V(A\to B)=1$ imply $V(B)=1$. But if not, then either $V(A)=0$, or $V(A\to B)=0$. ∎

The soundness theorem can be used to prove that certain wff’s of propositional logic are not theorems. For example, we show that the schema $A\to(A\land B)$ is not a theorem schema (an instance of it is not a theorem). Pick two distinct propositional variables $p$ and $q$, and use the truth table:

$A$ | $\to$ | $(A$ | $\land$ | $B)$ |
---|---|---|---|---|

T | T | T | T | T |

T | F | T | F | F |

F | T | F | F | T |

F | T | F | F | F |

Since the second column contains an $F$, $p\to(p\land q)$ is not true, and therefore $\not\vdash A\to(A\land B)$ by the soundness theorem. As another example, we show that the *disjunction property*

if $\vdash A\lor B$, then $\vdash A$ or $\vdash B$

is not true in classical propositional logic (it is true, however, in intuitionistic logic). To see this, let $A$ be $p\to q$ and $B$ be $q\to p$, where $p,q$ are propositional variables. Then $A\lor B$ is an instance of the theorem schema $(C\to D)\lor(D\to C)$. However, neither $\vdash A$ nor $\vdash B$, as illustrated in the following truth table:

$p$ | $q$ | $p\to q$ | $q\to p$ | $(p\to q)\lor(q\to p)$ |
---|---|---|---|---|

T | T | T | T | T |

T | F | F | T | T |

F | T | T | F | T |

F | F | T | T | T |

Notice that both the third and the fourth columns contain an $F$, and therefore by the soundness theorem, $A$ and $B$ are not theorems.

## 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