[Math] Soundness of a rule of a proof system with respect to the truth tables

logicpredicate-logicpropositional-calculus

I have the following question:
"Explain the concept of the soundness of a rule of a proof system with respect to the truth tables"

Would it be correct to state the following:

"A rule of a proof system is sound with respect to the truth tables iff the conditions of the rules (requirements of the rule) ensure that the final formula will behave according to it's intended truth table."?

This is a question in a practice exam, and I can not find a specific mentioning so far, by scanning Google and Proof Wiki.

What would the correct answer be?

Thank you.

Best Answer

Let's consider the following rule (modus ponens):

$$\rm{If} ~~~\vdash P \rightarrow Q ~~~~\rm{and}~~~ \vdash P\rm{, ~~~~then}~~~~ \vdash Q$$

To prove that it's sound with respect to truth-tables it will suffice to show that:

$$\rm{If} ~~~\models P \rightarrow Q ~~~~\rm{and}~~~ \models P\rm{, ~~~~then}~~~~ \models Q$$

Which says that every row of the truth-table that makes $(P \rightarrow Q)$ and $P$ true, also makes $Q$ true.

Proof. Among the two rows that make $P$ true, only the $[P=Q=\top]$-row makes $(P \rightarrow Q)$ true. And since $Q$ is true on that row, we've shown that the rule is sound with respect to truth-tables.

What is true of this rule is true of the others. (In your particular context, of course.)

Note. Showing that all the rules are sound is not enough to establish the soundness of your proof system with respect to truth-tables, because you will also have to show that all the axioms of the system (say $P \lor \lnot P)$ are assigned the value $\top$ on all rows of the truth-table.

Related Solutions

[Math] Proof With and Without Truth Tables

If you number the statements as

If the tax rate and the unemployment rate both go up, then there will be a recession
If the GNP goes up, then there will not be a recession
The GNP and taxes are both going up

then you can exclude all but one of the rows of the truth table as being contrary to these statements

P Q R S Comment

T T T T No - 2
T T T F No - 3
T T F T No - 1
T T F F No - 1, 3
T F T T No - 2
T F T F No - 3
T F F T 
T F F F No - 3
F T T T No - 2, 3
F T T F No - 3
F T F T No - 3
F T F F No - 3
F F T T No - 2, 3 
F F T F No - 3
F F F T No - 3
F F F F No - 3

That leaves $P$ and $S$ true and $R$ and $Q$ false. In particular $Q$ is false and so unemployment is not going up.

Logic – Proof of the Distributive Law in Implication

Use the equivalence $\quad a \rightarrow b \equiv \lnot a \lor b\tag{1}\;$

to transform the implications into disjunctions,

then use one of the distributive laws you know $(2)$:

$$\begin{align}(p → q) ∧ (p → r) &\equiv (\lnot p \lor q) \land (\lnot p \lor r)\tag{by (1)}\\ \\ & \equiv \lnot p \lor (q\land r)\tag{by (2)} \\ \\ & \equiv p \rightarrow (q \land r)\tag{by (1)}\end{align}$$

Best Answer

Related Solutions

[Math] Proof With and Without Truth Tables

Logic – Proof of the Distributive Law in Implication

Related Question