DeMorgan's Laws

It is not straightforward, though not difficult, to negate a conjunction or a disjunction of two propositions. There are chances of making subtle errors in this process, which requires careful attention.

How can we negate a conjunction or a disjunction of two propositions? DeMorgan’s celebrated laws provide the answer. Once we understand these laws, we will be able to apply the negation operator to compound propositions, significantly enhancing our capabilities. There are two natural parts to this question; let’s consider them one by one.

Negation of a conjunction

Let’s first look at how we can negate a conjunction. Let $p$ and $q$ be two propositions. According to DeMorgan’s first law:

$$\begin{equation} \neg\left(p \land q\right)\equiv \neg p \lor \neg q. \end{equation}$$

Making a truth table for both expressions in equivalence (1) verifies this law:

$p$	$q$	$\neg p$	$\neg q$	$p \land q$	$\neg\left(p \land q\right)$	$\neg p \lor \neg q$
T	T	F	F	T	F	F
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	F	T	T	F	T	T

The last two columns of the truth table contain the same truth values, thereby proving the law formally. We can also write this law in our “bar” notation as:

$$\overline{ \left(p \land q\right)} \equiv {\overline p} \lor \overline{ q}.$$

We can use verbal reasoning to verify this law: The left-hand side of equivalence (1) is true exactly when $p$ and $q$ are not simultaneously true. At the same time, the right-hand side is true if at least one of them is false. These are two different ways of saying the same thing.

Another way to understand this law is to say that to refute $p \land q$; we have to either refute $p$ or refute $q$.

In comparison, let’s construct the truth table for $\neg\left(p \land q\right)$ and $\neg p \land \neg q$.

$p$	$q$	$\neg p$	$\neg q$	$p \land q$	$\neg\left(p \land q\right)$	$\neg p \land \neg q$
T	T	F	F	T	F	F
T	F	F	T	F	T	F
F	T	T	F	F	T	F
F	F	T	T	F	T	T

The last two columns of the truth table are not the same. This shows that negation does not distribute over conjunction. Note that $\neg ( p \land q )$ differs from $\neg p \land \neg q$ exactly when one of the propositions $p$ or $q$ is true, and the other is false.

Examples

Let’s look at a few examples to understand further this negation operator’s behavior in the conjunction of two propositions.

---

Consider the following propositions:

• $s_m$: Sara likes mathematics.
• $s_c$: Sara likes coffee.

---

Let $L \equiv s_m \land s_c$ and $N = \neg L$. The proposition $L$ says Sara likes mathematics and coffee. In contrast, $N$ asserts that it is not the case that Sara likes mathematics and coffee.

The proposition $L$ is true when Sara dislikes both mathematics and coffee. What if Sara likes mathematics, but she does not like coffee? Or if she likes coffee and does not like mathematics? Then $L$ will be false, and therefore $N$ will be true. The statement $N$ is false only if Sara likes both the coffee and the mathematics.

Now consider,

$$B \equiv \neg s_m \land \neg s_c.$$

The statement $B$ says that it is not the case that Sara likes mathematics and it is not the case that Sara likes coffee.

If Sara likes mathematics and does not like coffee, then $B$ is false because she likes mathematics. What about $N$? It is true because she does not like coffee, and therefore is not the case that she likes both mathematics and coffee because she does not like coffee.

Note: $N$ is very different from $B$. To understand this difference we should focus on the cases when the truth value of $N$ and $B$ differ. This happens precisely when $s_m$ and $s_c$ have different truth values.

Let’s look at another example.

---

Consider the following propositions:

• $m_d$: Maria has a dog.
• $m_c$: Maria has a cat.

---

Now let,

• $p \equiv m_d \land m_c$: Maria has a dog and a cat.
• $q \equiv \neg\left(m_d \land m_c \right)$: It is not the case that Maria has a dog and a cat.

The proposition $q$ will be true if Maria does not have a cat, regardless of whether she has a dog or not. Similarly, $q$ will be true if Maria does not have a dog, regardless of whether she has a cat or not. Hence,

$$q \equiv \neg m_d \lor \neg m_c.$$

Negation of a disjunction

DeMorgan’s second law describes how to negate a disjunction of two propositions. According to DeMorgan’s second law:

$$\begin{equation} \neg\left(p \lor q\right)\equiv \neg p \land \neg q. \end{equation}$$

Where $p$ and $q$ are two arbitrary propositions. Once again, equivalence (2) is easily verified by making a truth table.

$p$	$q$	$\neg p$	$\neg q$	$p \lor q$	$\neg\left(p \lor q\right)$	$\neg p \land \neg q$
T	T	F	F	T	F	F
T	F	F	T	T	F	F
F	T	T	F	T	F	F
F	F	T	T	F	T	T

The last two columns of the truth table contain the same truth values, thereby proving the law. We can also write this law in our “bar” notation as,

$$\overline{ \left(p \lor q\right)} \equiv {\overline p} \land \overline{ q}.$$

Once again, verbal reasoning clarifies why this law holds: The left-hand side of Equivalence (2) when true, asserts that it is not the case that $p$ or $q$ are true. At the same time, the right-hand side claims that both $p$ and $q$ are false. Again, these are two different ways of saying the same thing.

Another way to understand this law is to say that to refute $p \lor q$, we have to refute $p$ and refute $q$.

Quiz

Examples

Let’s look at a few examples to comprehend this behavior of the negation operator on the disjunction of two propositions.

The proposition $m_p$ will only be false if Maria does not have a cat and she also does not have a dog; this is precisely the scenario when $m_n$ should be true and should be false otherwise. Therefore,

$$m_n \equiv \neg m_d \land \neg m_c.$$

---

Let’s consider,

• $E_g$: Elizabeth is wearing glasses.
• $S_g$: Smith is wearing glasses.

---

The disjunction of $E_g$ and $S_g$ gives us:

• $G =E_g \lor S_g$: Elizabeth is wearing glasses or Smith is wearing glasses.

The proposition $G$ is only false when both Elizabeth and Smith are not wearing glasses. Therefore, the negation of $G$ is only true when both Elizabeth and Smith are not wearing glasses.

• $N = \neg G$: It is not the case that Elizabeth is wearing glasses or Smith is wearing glasses.
• $\neg E_g \land \neg S_g$: Elizabeth is not wearing glasses, and Smith is not wearing glasses.

We have,

$$N \equiv \neg G \equiv \neg E_{g} \land \neg S_{g}.$$

Summarizing DeMorgan’s laws

We summarize the DeMorgan’s laws in the table below:

DeMorgan’s law	Description	Logical Equivalence	Law in bar notation
1	Negating a conjunction of two propositions	$\neg\left(p \land q\right) \equiv \neg p \lor \neg q$	$\overline{( p \land q)} \equiv \overline{p} \lor \overline{q}$
2	Negating a disjunction of two propositions	$\neg\left(p \lor q\right) \equiv \neg p \land \neg q$	$\overline{( p \lor q)} \equiv \overline{p} \land \overline{q}$

There is a simple way to remember these laws:

“When we push negation through the two basic binary operations, they switch their roles.”

Alert: The above colloquial phrase must be understood precisely and used with care.

Generalized form

To look at the generalized version of DeMorgan’s laws, assume the conjunction of $n$ propositions.

$$p\equiv p_1\land p_2\land p_3\land \cdots\land p_n.$$

If we look at $\neg p$,

$$\neg p \equiv \neg\left(p_1\land p_2\land p_3\land \cdots\land p_n\right).$$

As conjunction operator is associative, we can view the above logical equivalence as,

$$\neg p \equiv \neg\left(p_1 \land \left( p_2 \land p_3 \land \cdots \land p_n\right)\right).$$

Now applying the DeMorgan’s law gives:

$$\neg q=\neg p_1\lor \neg\left(p_2\land p_3\land \cdots\land p_n\right).$$

Let’s do one more step.

Note: Distributive law does not hold for the negation operator. DeMorgan’s laws provide us with a way to handle this situation.

Quiz

Application in real life

Let’s now look at an example with important implications in real life. Consider an insurance company that requires a client, Carla, to have yearly health checkups. Furthermore, Carla must see a doctor from a designated list upon developing any symptoms.

---

Let,

• $H$: Carla gets an annual health checkup.

• $D$: Carla visits a designated doctor for first advice upon developing any symptoms.

---

The insurance pays the health expense if she meets both requirements.

Let,

$$I \equiv H \land D.$$

If $I$ is true, Carla can claim her health expenses. Carla needs to understand when the insurance company can deny her health expenses. She has to understand when $I$ is false or equivalently when $\neg I$ is true. According to DeMorgan’s law:

$$\neg I \equiv \neg H \lor \neg D.$$

DeMorgan’s law entails that if she fails to go for a yearly checkup or fails to consult a doctor from the designated list for first advice upon developing any symptoms, she does not fulfill the insurance company’s requirements.

As seen under the light of DeMorgan’s laws, the harshness of these requirements becomes apparent. The insurance company’s demands are fair if Carla fully understands them.

To fully understand such legalese, we must understand the meaning of sentences that simultaneously use negation, conjunction, and disjunction.