EF Proof by counterexample

Section 6.7 Proof by counterexample

Sometimes we want to prove that

P ⇏ Q;

i.e. that

P \to Q

is not a tautology.

The equivalence

P \to Q \Leftrightarrow (P \land C_{1} \to Q) \land \dots \land (P \land C_{m} \to Q)

holds for any set of cases

C_{1}, C_{2}, \dots, C_{m}

such that

C_{1} \lor \dots \lor C_{m}

is a tautology. (See Section 6.4.)

So if

P \land C_{i} \to Q

is not a tautology for at least one

i,

then

P \to Q

also cannot be a tautology. Again, this also works in the universal case since

\forall

distributes over

\land

counterexample: 🔗
relative to the logical implication $P \Rightarrow Q,$ a statement $C$ such that $P \land C \to Q$ is false

In Exercise 6.12.8, you are asked to prove the following statement by proving the contrapositive.

🔗
If $2^{n} - 1$ prime, then $n$ is prime.

Prove that the converse of this statement is false.

The converse statement is “If

n

is prime, then

2^{n} - 1

is prime.” But the case

n = 11

is a counterexample:

2^{11} - 1 = 2047 = 23 \cdot 89

is not prime even though

n = 11

is prime.