Understanding the Basics of the De Morgan’s Laws

In the previous two posts, we have discussed about the logical operators and, or, and not.  Those two articles are preparation for this post.

Consider the following inequalities.

1.) x \leq 8

2.) -2 < x < 3 

The first inequality can also be represented as x < 8 or x = 8

Now, how do we find

not (x < 8 or x = 8).

To easily understand the question, we graph x \leq 8 first and then see what’s not on that graph. 

de morgan

As shown above, the points not on the graph of x \leq 8 are points on the graph of x > 8. They are points that are not on x = 8 and not on x < 8 or points on

not (x = 8) and not (x < 8).

Since the two logical statements are equivalent, we can write

not (x < 8 or x = 8) \equiv not (x = 8) and not (x < 8).

Now, if we represent x = 8 as p and x < 8 as q we can have the following equivalence.

not (p or q) \equiv  (not p) and (not q)*.

Let us consider the second inequality. 

The inequality -2 < x < 3 can also be represented as x > -2 and x < 3.

Now, how do we find

not (x > -2 and x < 3)?

Again, we are searching for the part of the graph that is not on the graph of -2 < x < 3. As shown below, it should be x \geq 3 or x \leq -2.

de morgan2

Therefore,

not (x > -2 and x <  3) \equiv not (x > 3)$ or not (x < -2)

If we represent this expression x > 3 by p or x < -2 by q, we can say that

not (p and q) \equiv (not p) or (not q) **

The relationships in * and ** are called the De Morgan’s Laws named after British mathematician and logician Augustus De Morgan.

We can prove the De Morgan’s Laws by examining the truth tables of the identities above. First, we see the truth tables of not (p and q) and not (p or q).

de morgan

Then, we also examine the truth table of not p or not q and not p and not q.

de morgan 2

As we can see, the identity not (p and q) in the first table is the same as not p or not q in the second table. Also, the truth values of not (p or q) in the first table is the same as not p and not q in the second table. This proves the conjecture in * and ** are logically equivalent. This is one of the proofs of the De Morgan’s Laws.  

Leave a Reply