Section Progress:

8.2 Chain of Equivalences

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

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

Solution: we use two equivalences you already know 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.)

8.2 Chain of Equivalences