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. :::definition[Invalid Argument] 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 invalid argument if there exists a truth-value assignment for which all the premises are true and the conclusion is false. ::: :::definition[Counterexample] A 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. ::: :::definition[Invalidity by Counterexample] 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. :::calculator[Counterexample Tester] ::: :::solved-problem 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$. ::: :::solution 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. ::: :::solved-problem Determine the validity of the argument $p\to q,\ q\to s,\ r\to\neg s,\ \neg p\lor r\ \therefore\ \neg p$. ::: :::solution 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. ::: :::remark 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. ::: :::solved-problem Show that $[(p\land\neg q)\land[p\to(q\to r)]]\to\neg r$ is invalid. ::: :::solution 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. ::: :::solved-problem 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. ::: :::solution 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. ::: :::exercise 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$. ::: :::answer (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. ::: :::faq[Frequently Asked Questions] Q: How many counterexamples are needed to prove invalidity? A: One correct counterexample is enough. Q: What must a counterexample satisfy? A: It must make every premise true and the conclusion false. Q: If I cannot find a counterexample quickly, is the argument valid? A: Not necessarily. A failed search suggests checking the argument by rules of inference or a full truth table. ::: :::call-to-action[Practise Counterexample Testing] subtitle: Use invalid arguments and counterexamples to separate unsupported conclusions from valid logical deductions. button: Review Section | /discrete-mathematics/mathematical-logic/logical-implication-and-rules-of-inference/valid-arguments-and-logical-implication button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-implication-and-rules-of-inference/proofs-using-several-rules-of-inference :::