# Tautological consequence and counterexamples

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?

• If the statement that "there exists a row with every $p_i = 1$ and $q=0$" is false, then the opposite is true. – Alvin Lepik Mar 14 at 16:41

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.

• What if I restrict the possibilities by choosing an interpretation where the premises cannot be all true at the same moment. I will never find a counterexample, but I will not also find a case where all premises are true and the consequence is true. What can I say now? – zar Mar 15 at 15:34
• Then you can say one of two things: a) The interpretation is not correct and you should go for another one, or b) the interpretation is fine and the choice of $P_1,\ldots,P_n$ is such that it is impossible for all of them to be true at the same time (in other words, the set of $P_i$ is inconsistent). In this case, any formula (and not just $Q$) is a tautological consequence of $P_1,\ldots,P_n$. If you want details on why is that, I suggeste you make another question for it. – frabala Mar 15 at 15:48

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

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

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)