Substitution rules allow us to replace equivalent substatements inside larger formulas. We now apply those rules to conditional statements, especially implications. The negation of an implication is one of the most important formulas in logic because it explains how to deny an if-then statement correctly. In this lesson, negation and duals of conditional statements will be expressed using equivalence laws and De Morgan's Laws. :::definition[Negation of an Implication] For statements $p$ and $q$, $$\begin{equation*} \neg(p\to q)\Leftrightarrow p\land\neg q. \end{equation*}$$ This formula says that the negation of an implication asserts the hypothesis and denies the conclusion. ::: Use the checker to practise the correct negation of an implication. The negation of if $p$, then $q$ is not another implication. It says that $p$ is true and $q$ is false. This is exactly the one case where the original implication fails. :::calculator[Implication Negation Checker] ::: :::proof Given that $p$ and $q$ are statements. To prove that $\neg(p\to q)\Leftrightarrow p\land\neg q$. Using implication as disjunction, $$\begin{equation*} p\to q\Leftrightarrow\neg p\lor q. \end{equation*}$$ Therefore, $$\begin{align*} \neg(p\to q)&\Leftrightarrow\neg(\neg p\lor q)\\ &\Leftrightarrow\neg\neg p\land\neg q\\ &\Leftrightarrow p\land\neg q. \end{align*}$$ Hence, $\neg(p\to q)\Leftrightarrow p\land\neg q$. $\square$ ::: :::solved-problem Negate and simplify $(p\lor q)\to r$. ::: :::solution Given that $p$, $q$, and $r$ are primitive statements. To negate the statement, write $\neg[(p\lor q)\to r]$. Using the negation of an implication, $$\begin{equation*} \neg[(p\lor q)\to r]\Leftrightarrow(p\lor q)\land\neg r. \end{equation*}$$ Hence, the negated and simplified statement is $(p\lor q)\land\neg r$. ::: :::example[English Negation of an Implication] Let $p$ mean Joan goes to Lake George, and let $q$ mean Mary pays for Joan's shopping spree. The implication $p\to q$ says: If Joan goes to Lake George, then Mary will pay for Joan's shopping spree. Its negation is $p\land\neg q$. Therefore, the negation is: Joan goes to Lake George, but Mary does not pay for Joan's shopping spree. ::: :::definition[Dual of an Implication] The implication $p\to q$ may be written as $\neg p\lor q$. The dual is obtained by replacing $\lor$ with $\land$. Therefore, $$\begin{equation*} (p\to q)^d\Leftrightarrow\neg p\land q. \end{equation*}$$ ::: :::solved-problem Negate and simplify $p\land(q\lor r)\land(\neg p\lor\neg q\lor r)$. ::: :::solution Given that $p$, $q$, and $r$ are primitive statements. To negate the statement, use De Morgan's Law: $$\begin{equation*} \neg[p\land(q\lor r)\land(\neg p\lor\neg q\lor r)]\Leftrightarrow\neg p\lor\neg(q\lor r)\lor\neg(\neg p\lor\neg q\lor r). \end{equation*}$$ Using De Morgan's Law again, $$\begin{align*} \neg(q\lor r)&\Leftrightarrow\neg q\land\neg r,\\ \neg(\neg p\lor\neg q\lor r)&\Leftrightarrow p\land q\land\neg r. \end{align*}$$ Hence, the negation is $\neg p\lor(\neg q\land\neg r)\lor(p\land q\land\neg r)$. ::: :::solved-problem Negate and simplify $(p\land q)\to r$ and $p\to(\neg q\land r)$. ::: :::solution Given that $p$, $q$, and $r$ are primitive statements. For the first statement, $$\begin{equation*} \neg[(p\land q)\to r]\Leftrightarrow(p\land q)\land\neg r\Leftrightarrow p\land q\land\neg r. \end{equation*}$$ For the second statement, $$\begin{align*} \neg[p\to(\neg q\land r)]&\Leftrightarrow p\land\neg(\neg q\land r)\\ &\Leftrightarrow p\land(q\lor\neg r). \end{align*}$$ Hence, the simplified negations are $p\land q\land\neg r$ and $p\land(q\lor\neg r)$. ::: :::exercise Write the dual of each statement: (1) $q\to p$. (2) $p\to(q\land r)$. Also negate and simplify: (3) $(p\lor q)\to r$. (4) $p\to(\neg q\land r)$. ::: :::answer (1) $\neg q\land p$. (2) $\neg p\land(q\lor r)$. (3) $(p\lor q)\land\neg r$. (4) $p\land(q\lor\neg r)$. ::: :::faq[Frequently Asked Questions] Q: Is the negation of an implication another implication? A: No. The negation of $p\to q$ is $p\land\neg q$. Q: What does the negation of an implication say in words? A: It says that the hypothesis is true and the conclusion is false. Q: How is the dual of an implication found? A: First rewrite the implication as $\neg p\lor q$, then change $\lor$ to $\land$. ::: :::call-to-action[Negate Conditionals Correctly] subtitle: Practise denying if-then statements before studying converse, inverse, and contrapositive forms. button: Next Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/converse-inverse-and-contrapositive button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/substitution-rules-for-logical-equivalence :::