Invalid Arguments and Counterexamples

After constructing proofs using several rules of inference, we must also know how to prove that an argument is not valid. Invalid arguments and counterexamples give the exact method. A counterexample is not a vague objection; it is a truth-value assignment that makes every premise true and the conclusion false. In this lesson, invalid arguments and counterexamples will be used to test symbolic and verbal arguments without building unnecessarily long truth tables.

Let

p_1,p_2,\ldots,p_n

be premises and let

q

be a conclusion. The argument

\begin{equation*} p_1,\ p_2,\ldots,p_n\ \therefore\ q \end{equation*}

is called an \textbf{invalid argument} if there exists a truth-value assignment for which all the premises are true and the conclusion is false.

Let

p_1,p_2,\ldots,p_n

be premises and let

q

be a conclusion. The argument

\begin{equation*} p_1,\ p_2,\ldots,p_n\ \therefore\ q \end{equation*}

is called an \textbf{invalid argument} if there exists a truth-value assignment for which all the premises are true and the conclusion is false.

A \textbf{counterexample} to an argument is a truth-value assignment for which all premises are true and the conclusion is false. A counterexample proves that an argument is invalid.

The argument

\begin{equation*} p_1,\ p_2,\ldots,p_n\ \therefore\ q \end{equation*}

is invalid if there exists a truth-value assignment such that

\begin{equation*} p_1=p_2=\cdots=p_n=1 \end{equation*}

and

\begin{equation*} q=0. \end{equation*}

To show invalidity, begin by forcing the conclusion to be false. Then use the premises to choose truth values that keep each premise true. If this can be done, the chosen assignment is a counterexample. If it cannot be done and the attempt always creates a contradiction, the argument may be valid. This method is often faster than constructing the full truth table.

A counterexample is a single assignment that makes every premise true and the conclusion false. Use the calculator to test the first invalid symbolic argument from this lesson. Try to force the conclusion

\neg s\to\neg t

to be false, then adjust the variables until all premises remain true. This turns the search method into a concrete checkable computation.

Determine whether the following argument is valid:

p,\ p\lor q,\ q\to(r\to s),\ t\to r\ \therefore\ \neg s\to\neg t

Let the premises be

\begin{equation*} p,\quad p\lor q,\quad q\to(r\to s),\quad t\to r. \end{equation*}

To test invalidity, seek an assignment for which all premises are true and the conclusion is false. Choose

\begin{equation*} p=1,\quad q=0,\quad r=1,\quad s=0,\quad t=1. \end{equation*}

Then

p

is true and

p\lor q=1\lor0=1

. Since

q=0

, the conditional

q\to(r\to s)

is true. Since

t=1

and

r=1

, the conditional

t\to r

is true. Now the conclusion is

\neg s\to\neg t

. Since

s=0

\neg s=1

. Since

t=1

\neg t=0

. Therefore

\begin{equation*} \neg s\to\neg t=1\to0=0. \end{equation*}

Thus all premises are true and the conclusion is false. Hence, the argument is invalid.

Determine the validity of the argument

p\to q,\ q\to s,\ r\to\neg s,\ \neg p\lor r\ \therefore\ \neg p

Let

p\to q

q\to s

r\to\neg s

, and

\neg p\lor r

be true. To test invalidity, suppose the conclusion

\neg p

is false. Then

p

is true. Since

p\to q

is true and

p

is true, Modus Ponens gives

q

. Since

q\to s

is true and

q

is true, Modus Ponens gives

s

. Since

\neg p\lor r

is true and

\neg p

is false, Disjunctive Syllogism gives

r

. Since

r\to\neg s

is true and

r

is true, Modus Ponens gives

\neg s

. Therefore both

s

and

\neg s

are true, a contradiction. Hence the conclusion

\neg p

cannot be false when all premises are true. Therefore, the argument is valid.

To show that an argument is invalid, it is not necessary to construct the full truth table. It is enough to find one assignment of truth values such that all premises are true and the conclusion is false. This assignment is the counterexample.

Show that

[(p\land\neg q)\land[p\to(q\to r)]]\to\neg r

is invalid.

To show invalidity, choose truth values so that the hypothesis is true and the conclusion is false. Let

\begin{equation*} p=1,\quad q=0,\quad r=1. \end{equation*}

Then

p\land\neg q=1\land1=1

. Also

q\to r=0\to1=1

. Therefore

p\to(q\to r)=1\to1=1

. Thus the hypothesis

\begin{equation*} (p\land\neg q)\land[p\to(q\to r)] \end{equation*}

is true. But

\neg r=0

. Therefore, the statement is false for this truth-value assignment. Hence, the argument is invalid.

Write the argument in symbolic form and determine whether it is valid. If there is a chance of rain or her red headband is missing, then Lois will not mow her lawn. Whenever the temperature is over

80^\circ\text{F}

, there is no chance of rain. Today the temperature is

85^\circ\text{F}

and Lois is wearing her red headband. Therefore Lois will mow her lawn.

Let

p

mean “There is a chance of rain,”

q

mean “Lois’s red headband is missing,”

r

mean “Lois will mow her lawn,” and

s

mean “The temperature is over

80^\circ\text{F}

.” The premises are

\begin{equation*} (p\lor q)\to\neg r,\quad s\to\neg p,\quad s\land\neg q. \end{equation*}

The conclusion is

r

. Given that

s\land\neg q

is true,

s

is true and

\neg q

is true. From

s\to\neg p

and

s

, Modus Ponens gives

\neg p

. Thus both

\neg p

and

\neg q

are true, so

p\lor q

is false. The premise

(p\lor q)\to\neg r

does not force

\neg r

when

p\lor q

is false. A counterexample is

\begin{equation*} s=1,\quad p=0,\quad q=0,\quad r=0. \end{equation*}

Then all premises are true, but the conclusion

r

is false. Hence, the argument is invalid.

Show that each argument is invalid by providing a counterexample: (1)

[(p\land\neg q)\land[p\to(q\to r)]]\to\neg r

. (2)

[((p\land q)\to r)\land(\neg q\lor r)]\to p

. (3)

p\leftrightarrow q,\ q\to r,\ r\lor\neg s,\ \neg s\to q\ \therefore\ s

. (4)

p,\ p\to r,\ p\to(q\lor\neg r),\ \neg q\lor\neg s\ \therefore\ s

(1) A counterexample is

p=1

q=0

r=1

. (2) A counterexample is

p=0

q=0

r=0

. (3) A counterexample is

p=1

q=1

r=1

s=0

. (4) A counterexample is

p=1

q=0

r=1

s=0

. Each assignment makes all premises true and the conclusion false.

One correct counterexample is enough.

It must make every premise true and the conclusion false.

Not necessarily. A failed search suggests checking the argument by rules of inference or a full truth table.

BMLabs Mathematics

BMLabs Mathematics

Invalid Arguments and Counterexamples

Invalid Arguments and Counterexamples

TESTING FAILURE OF VALIDITY

INVALID ARGUMENT

COUNTEREXAMPLE

INVALIDITY BY COUNTEREXAMPLE

HOW TO SEARCH FOR A COUNTEREXAMPLE

FINDING A COUNTEREXAMPLE BY TRUTH VALUES

COUNTEREXAMPLE TESTER

FREQUENTLY ASKED QUESTIONS

PRACTISE COUNTEREXAMPLE TESTING

Introduction To Discrete Mathematics

Paths and Circuits