How can we make a messy sentence like this easier to understand?

~~~(~~(~P&~Q)v~(~R&~S))

Solution: we apply two equivalences that you already know in order to simplify it.

**DeMorgan’s Laws:**

~(PvQ) ⇔ ~P&~Q

~(P&Q) ⇔ ~Pv~Q

You’ve already learned DeMorgan’s Laws (DeM) and Double Negation (DN). Now we can use those principles to simplify a sentence with any wide-scope negations. When you use DeMorgan’s, just remember to change & to v or vice versa when you push the negation in.

You can keep simplifying until you end up with a sentence in NNF. With this technique you can take any sentence and find an equivalent sentence in NNF.

**Double Negation:**

P ⇔ ~~P

Here’s how it looks. Below the given formula, write another formula that eliminates a double negation or pushes a negation in with DeMorgan’s, and cite which principle you used on the right.

~~~(~~(~P&~Q)v~(~R&~S))

**⇔ ~((~P&~Q)v~(~R&~S)) DN**

Notice that we eliminated two pairs of negations at the same time. That is allowed.

**Only use one principle at a time, but you can apply it multiple times in one step.**

But we require that you only use one principle at a time, either DeM or DN, but not both.

Now the formula in blue has two negations that you might push in next: there is the negation around the whole sentence, and the negation around (~R&~S).

Here’s our tip: don’t do both at once; start from the outside in.

Let’s see if you can figure out what formula that creates.

Here’s how it looks. As we keep transforming the sentence we create a * chain of equivalences*.

~~~(~~(~P&~Q)v~(~R&~S))

**⇔ ~((~P&~Q)v~(~R&~S)) DN**

**⇔ ~(~P&~Q)&~~(~R&~S) DeM**

Your job is to finish the chain until you end up with a sentence in NNF.

There will often be different ways to create a chain, depending on what order you do the steps in. Just remember not to stop until you’ve reach NNF.

Here’s what our version looked like:

~~~(~~(~P&~Q)v~(~R&~S))

**⇔ ~((~P&~Q)v~(~R&~S)) DN**

**⇔ ~(~P&~Q)&~~(~R&~S) DeM**

**⇔ (~~Pv~~Q)&~~(~R&~S) DeM**

**⇔ (PvQ)&(~R&~S) DN**

Remember to only apply one principle at a time, and be careful not to accidentally drop parentheses that you need. (We did drop the outermost parentheses, since those aren’t needed once there is no wide-scope negation.)

Your turn to practice.

Here’s our chain:

~(~(PvQ)&~R)

**⇔ ~~(PvQ)v~~R DeM**

**⇔ (PvQ)vR DN**

Now let’s try a harder one. Make sure to work it out on paper before viewing the solution, or you won’t be learning the material!

Here’s the sentence:

~((~(~SvT)vU)&~R)

Use a chain to put it into NNF.

Here’s our solution:

~((~(~SvT)vU)&~R)

**⇔ ~(~(~SvT)vU)v~~R DeM**

**⇔ ~(~(~SvT)vU)vR DN**

**⇔ (~~(~SvT)&~U)vR DeM**

**⇔ ((~SvT)&~U)vR DN**

It’s not essential to find the shortest chain.

The most important thing is to be careful and keep all the parentheses straight. (Sometimes drawing a line above or below the sentence connecting each pair of parentheses can be helpful.)

Login

Accessing this textbook requires a login. Please enter your credentials below!