Tautological consequence and counterexamples

Question

I know that in order to check if Q is a tautological consequence of P1, P2, ..., Pn I can look at the truth table.

If, wherever P1, P2, ..., Pn are true also Q is true, than Q is a tautological consequence of P1, P2, ..., Pn.

I also know that if I can't find a counterexample, that is a row of the truth table where P1, P2, ..., Pn are true and Q false, then I can assert that Q is a tautological consequence of P1, P2, ..., Pn.

I can't understand why the last thing is true. Intuitively if I can't find a counterexample, I cannot say anything, nor that it is true nor that it is false.

The problem is that my intuition is wrong.

How can I understand that fact?

Answer 1

Denote $\mathcal P=1$ to mean every component $P_i$ is true. We say the statements $P_1,\ldots, P_n$ tautologically imply $Q$ if and only if for every row in the truth table $$\mathcal P=1 \Rightarrow Q=1\tag{1} $$ Negate the former statement. There exists a row in the truth table satisfying $$\mathcal P=1 \quad \&\quad Q=0\tag{2} $$ To show there is no tautological implication, it suffices to show statement (2) is true (find a counterexample). If no such counterexample exists, then statement (1) must be true, but that means the statements $P_i$ tautologically imply $Q$.

Answer 2

Because there is a finite number of rows to check, you can check them all one by one. If you didn't find any row for which $P_1,\ldots,P_n$ are True and $Q$ is False, then this means that in all rows for which $P_1,\ldots,P_n$ are True, $Q$ is True, too.

Answer 3

I can't understand why the last thing is true. Intuitively if I can't find a counterexample, I cannot say anything, nor that it is true nor that it is false.

The problem is that my intuition is wrong.

Your intuition is not exactly wrong. Failing to find something is not enough prove that it cannot be found. However....

The key is being certain that the exploration is exhaustive; that is being sure that no cases remain unexamined.  Thus you have not merely failed to find a counter example, but have successfully demonstrated that one cannot be found.  That the conclusion must be true for all interpretations where the premises are all true (because you have indeed verified that this is so for every one).

Answer 4

One can always fear not to have checked correctly all the lines of the truth table.

So the most secure method is to rephrase the " tautological consequence test" in terms of corresponding conditional.

The assertion " Q is a tautological consequence of premises P1, P2, P3...Pn " is equivalent to the assertion

" the conditional formula [(P1&P2&P3&...&Pn) --> Q ] is a tautology ".

Using this rephrasing , you make a truth-table for this last conditional formula, and you only have to look at the last column of your truth table. If you have only the truth value T in this column, it is guaranteed that Q is a tautological consequence of your set of premises. If you have at least one time the value F in the last column, you know Q is not a tautological consequence.

Now, to answer precisely your question ( regarding what you point as difficult to understand). Knowing that ( A --> B) is the same thing as "it is not the case that A is true and B is false", you can seee that the following 4 assertions are equivalent.

(1) the formula ( P1&P2&P3...&Pn) --> Q ) is a tautology,in other words, is true in all possible cases ( all possible " interpretation")

(2) For all possible interpretation i if premises P1, P2, P3...Pn are all true in i , then Q is true in i

( Here, we quantify over the set of all possible interpretations)

(3) There is no possible interpretation i such that P1, P2, P3...Pn are all true in i and Q is not true in i

( In order to pass from (2) to (3) we use the predicate logic equivalence : For all x, phi(x) <--> there is no x such that ~ phi(x) )

(4) The set of interpretations in which premisses P1, P2, P3...Pn are all true is included in the set of interpretations in whic Q is true.

( Here, the universe is I= the set of all possible interpretations)