Skip to main content

Subsection 2.7.5 Counterexamples

To show that a Boolean expression is a tautology, we must show that it is true for all values of its variables.

But to show that an expression is not a tautology, it suffices to show just one set of values that make the expression false. We call such a set of values a counterexample.

Similarly, we can refute the claim that an expression is a contradiction by showing a single set of values that make the expression true.

Consider the expression:

(( p \(\rightarrow \) r) \(\rightarrow \) s) \(\equiv \) ((s \(\rightarrow \)r) \(\rightarrow \) p)

We want to show that it is not a tautology. (Another way to think of it is that there are exceptions to it.) To prove that it’s not a tautology, we can simply find one of those exceptions.

You can use the Truth Table app to do this yourself.

www.truthtables.org/#/true/((p->r)->s)=((s->r)->p) 3 

There are two counterexamples to the claim that this expression is a tautology. One of them is p = True, r = True and s = False.

Exercises Exercises

1.

Consider the claim: \(\neg ( a \wedge ( b \wedge c )) \equiv (\neg a \wedge (\neg b \wedge \neg c)) \)

Build a truth table for it. You can do it in the Truth Table app:

www.truthtables.org/#/true/!(a|(b|c))=(!a|(!b|!c)) 4 

Which of the following is true:

  1. The claim is a tautology.

  2. The claim is a contradiction.

  3. The claim is neither a contradiction nor a tautology and a proof that it isn’t a tautology is the case in which a = True, b = True, and c = True.

  4. The claim is neither a contradiction nor a tautology and a proof that it isn’t a tautology is the case in which a = False, b = True, and c = True.

  5. The claim is neither a contradiction nor a tautology and a proof that it isn’t a contradiction is the case in which a = False, b = False, and c = True.

Answer.
Solution.
truthtables.org
truthtables.org