1
$\begingroup$

So, I'm stuyding up on discrete math (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/) and came across the following explanation of what it means for an inference rule to be sound:

A key requirement of an inference rule is that it must be sound: any assignment of truth values that makes all the antecedents true must also make the consequent true. So if we start off with true axioms and apply sound inference rules, everything we prove will also be true.

As an expample modus ponens is given, along with its truth table. And sure enough: when P and p=>q have a true valuation, q has a true valuation as well.

A bit later I ran into the converse implication, which should not hold: Not(P) => Not(Q) : P => Q. And sure enough, the truth tables for these are different, so the must not be equivalent.

But when I'm taking a second look at the table, at some valuation the antecendent, Not(P) => Not(Q), is true, but in that same line in the table, the consequent, P => Q holds true as well.

So, clearly, I'm not quite understanding this rule about soundness. Could anyone explain a bit further?

$\endgroup$
1
$\begingroup$

The truth tables here with "0" as falsity and "1" as truth are (in Polish notation) are

p  q  Np  Nq  CNpNq   Cpq
0  0  1   1   1       1
0  1  1   0   0       1
1  0  0   1   1       0
1  1  0   0   1       1

So, yes if p=0, and q=0, then it holds that if CNpNq, then Cpq. In other words, for some instance (or in other words some valuation of the variables "p" and "q") of CNpNq, Cpq follows. However, if a rule is sound, then for any instance (valuation of the variables) where CNpNq=1, Cpq=1 also. If p=1, q=0, then CNpNq=1, but Cpq=0. Thus, it does not hold for any instance where CNpNq=1, that Cpq=1, and thus the rule of is not sound.

$\endgroup$
  • $\begingroup$ Ah, yeah, totally clear now. Just having observed that the truth tables were indeed inequal was enough. Thanks for the clarification! $\endgroup$ – Apeiron Jul 7 '14 at 5:27

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.