x P(x) => Q(x) then its negation is
x NOT ( P(x) => Q(x) )
which, by Example 0.1.6, is equivalent to the statement
x ( P(x) AND NOT Q(x) ).
Hence x0 is a counterexample to the conjecture if P(x0) is true while Q(x0) is false.
| Chapter 0: Logic and Proofs |
|---|
x P(x) then its negation is NOT ( x P(x) ), which by the Quantifier Negation Rules 0.2.6, is equivalent to x NOT P(x).
Hence to disprove the statement x P(x) we only have to find one x0 such that P( x0) is false.
This x0 is called a counterexample to the conjecture x P(x).
If the conjectured result is of the form x P(x) => Q(x) then its negation is
x NOT ( P(x) => Q(x) )
which, by Example 0.1.6, is equivalent to the statement
x ( P(x) AND NOT Q(x) ).
Hence x0 is a counterexample to the conjecture if P(x0) is true while Q(x0) is false.
Example. Let x be a real number. Disprove the statement:
if x2 < 9 then x < 3. Solution. One counterexample to the statement is obtained by taking x0 = - 4 , since x02 = 16 < 9 and x0
3. This counterexample disproves the statement.
Note that if we wanted to disprove an existence statement such as x P(x) then its negation is NOT (x P(x)), which is equivalent to x NOT P(x). In this case we cannot use a counterexample, because we have to show that P(x) is false for all values of x.