Equivalent forms of compound statements allow us to replace one symbolic expression by another without changing truth values. Among the most frequently used equivalences are De Morgan's Laws. These laws explain how negation passes through conjunction and disjunction. In this lesson, De Morgan's Laws will be used to negate compound statements, simplify expressions, and translate English statements into logically accurate negations. :::theorem[De Morgan's Laws] Let $p$ and $q$ be primitive statements. Then $$\begin{equation*} \neg(p\land q)\Leftrightarrow\neg p\lor\neg q \end{equation*}$$ and $$\begin{equation*} \neg(p\lor q)\Leftrightarrow\neg p\land\neg q. \end{equation*}$$ These are called De Morgan's Laws. ::: :::proof Given that $p$ and $q$ are primitive statements. To prove De Morgan's Laws. The statement $\neg(p\land q)$ is true exactly when $p\land q$ is false. The conjunction $p\land q$ is false when at least one of $p$ and $q$ is false. Therefore, $$\begin{equation*} \neg(p\land q)\Leftrightarrow\neg p\lor\neg q. \end{equation*}$$ Again, the statement $\neg(p\lor q)$ is true exactly when $p\lor q$ is false. The disjunction $p\lor q$ is false only when both $p$ and $q$ are false. Therefore, $$\begin{equation*} \neg(p\lor q)\Leftrightarrow\neg p\land\neg q. \end{equation*}$$ Hence, De Morgan's Laws hold. $\square$ ::: :::definition[Negation of a Conjunction] For statements $p$ and $q$, $$\begin{equation*} \neg(p\land q)\Leftrightarrow\neg p\lor\neg q. \end{equation*}$$ Thus, the negation of an and statement becomes an or statement of the negations. ::: :::definition[Negation of a Disjunction] For statements $p$ and $q$, $$\begin{equation*} \neg(p\lor q)\Leftrightarrow\neg p\land\neg q. \end{equation*}$$ Thus, the negation of an or statement becomes an and statement of the negations. ::: A common mistake is to distribute negation without changing the connective. For example, $\neg(p\land q)$ is not logically equivalent to $\neg p\land\neg q$. The connective changes when negation moves across a compound statement. Hence, and becomes or, while or becomes and. Use the comparator to test the correct De Morgan form against a common incorrect form. Choose truth values for $p$ and $q$, then select which negated statement you want to study. The correct transformed expression always matches the original negated expression. The incorrect form fails in at least one row because it distributes negation without switching the connective. :::scientific-preview[De Morgan Law Comparator] ::: :::example[Arithmetic Analogy] For real numbers $a$ and $b$, $$\begin{equation*} -(a+b)=(-a)+(-b). \end{equation*}$$ This resembles the movement of negation through an expression, but logic has an additional feature: the connective changes. Thus, $$\begin{equation*} \neg(p\land q)\not\Leftrightarrow\neg p\land\neg q, \end{equation*}$$ while $$\begin{equation*} \neg(p\land q)\Leftrightarrow\neg p\lor\neg q. \end{equation*}$$ ::: :::solved-problem Verify the first De Morgan's Law by truth table. ::: :::solution Given that $p$ and $q$ are primitive statements. To prove that $\neg(p\land q)\Leftrightarrow\neg p\lor\neg q$, construct the truth table: $$\begin{equation*} \begin{array}{c|c|c|c|c|c|c} p&q&p\land q&\neg(p\land q)&\neg p&\neg q&\neg p\lor\neg q\\ \hline 1&1&1&0&0&0&0\\ 1&0&0&1&0&1&1\\ 0&1&0&1&1&0&1\\ 0&0&0&1&1&1&1 \end{array} \end{equation*}$$ The columns for $\neg(p\land q)$ and $\neg p\lor\neg q$ are identical. Hence, the first De Morgan's Law is verified. ::: :::solved-problem Verify the second De Morgan's Law by truth table. ::: :::solution Given that $p$ and $q$ are primitive statements. To prove that $\neg(p\lor q)\Leftrightarrow\neg p\land\neg q$, construct the truth table: $$\begin{equation*} \begin{array}{c|c|c|c|c|c|c} p&q&p\lor q&\neg(p\lor q)&\neg p&\neg q&\neg p\land\neg q\\ \hline 1&1&1&0&0&0&0\\ 1&0&1&0&0&1&0\\ 0&1&1&0&1&0&0\\ 0&0&0&1&1&1&1 \end{array} \end{equation*}$$ The columns for $\neg(p\lor q)$ and $\neg p\land\neg q$ are identical. Hence, the second De Morgan's Law is verified. ::: :::solved-problem Negate the statement: Norma is doing her mathematics homework, and Karen is practicing her piano lessons. ::: :::solution Let $p$ mean Norma is doing her mathematics homework, and let $q$ mean Karen is practicing her piano lessons. The statement is $p\land q$. Its negation is $\neg(p\land q)$. Using De Morgan's Law, $$\begin{equation*} \neg(p\land q)\Leftrightarrow\neg p\lor\neg q. \end{equation*}$$ Therefore, the negation is: Norma is not doing her mathematics homework, or Karen is not practicing her piano lessons. ::: :::solved-problem Negate the statement: If Harold passes his Pascal course and finishes his data structures project, then he will graduate at the end of the semester. ::: :::solution Let $p$ mean Harold passes his Pascal course, $q$ mean Harold finishes his data structures project, and $r$ mean Harold graduates at the end of the semester. The statement is $(p\land q)\to r$. Its negation is $\neg[(p\land q)\to r]$. Using the negation of an implication, $$\begin{equation*} \neg[(p\land q)\to r]\Leftrightarrow(p\land q)\land\neg r. \end{equation*}$$ Therefore, the negation is: Harold passes his Pascal course and finishes his data structures project, but he does not graduate at the end of the semester. ::: :::exercise Negate and simplify: (1) $p\land(q\lor r)\land(\neg p\lor\neg q\lor r)$. (2) $(p\land q)\to r$. (3) $p\to(\neg q\land r)$. ::: :::answer (1) $\neg p\lor(\neg q\land\neg r)\lor(p\land q\land\neg r)$. (2) $p\land q\land\neg r$. (3) $p\land(q\lor\neg r)$. ::: :::faq[Frequently Asked Questions] Q: Why does and change to or? A: The negation of both being true means at least one is false, so the connective becomes or. Q: Is $\neg(p\lor q)$ the same as $\neg p\lor\neg q$? A: No. By De Morgan's Law, $\neg(p\lor q)\Leftrightarrow\neg p\land\neg q$. Q: Does De Morgan's Law apply to English statements? A: Yes, after the English statements are translated into symbolic form. ::: :::call-to-action[Apply De Morgan's Laws] subtitle: Practise negating conjunctions and disjunctions before studying distributive laws for logical connectives. button: Next Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/distributive-laws-for-logical-connectives button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/equivalent-forms-of-compound-statements :::