6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Look up "soundness vs. completeness". $\endgroup$ – dfeuer Nov 2 '13 at 23:58
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.