Laws of logic to simplify expression

Trying to understand how to simplify more complex formula's, for example

$\lnot ([(\lnot𝑞 \lor 𝑟) \land (\lnot𝑝 \land 𝑞 \land 𝑟)] \lor \lnot𝑟)$

I've started with this:

$= ¬ [(¬𝑞 ∨ 𝑟) ∧ (¬𝑝 ∧ 𝑞 ∧ 𝑟)] ∧ ¬¬𝑟$ (de Morgans Law)

$= ¬ [(¬𝑞 ∨ 𝑟) ∧ (¬𝑝 ∧ 𝑞 ∧ 𝑟)] ∧ 𝑟$ (double negation)

$= (¬ (¬𝑞 ∨ 𝑟) ∨ ¬ (¬𝑝 ∧ 𝑞 ∧ 𝑟)) ∧ 𝑟$ (de Morgans law)

$= ((¬¬𝑞 ∧ ¬𝑟) ∨ (¬¬𝑝 ∨ ¬𝑞 ∨ ¬𝑟)) ∧ 𝑟$ (de Morgans law)

$= ((𝑞 ∧ ¬𝑟) ∨ (𝑝 ∨ ¬𝑞 ∨ ¬𝑟)) ∧ 𝑟$ (double negation)

$= ((𝑞 ∧ ¬𝑟) ∧ 𝑟) ∨ ((𝑝 ∨ ¬𝑞 ∨ ¬𝑟) ∧ 𝑟 )$ (Distributive)

$= ((𝑞 ∧ ¬𝑟) ∧ 𝑟) ∨ (𝑝 ∧ 𝑟) ∨ (¬𝑞 ∧ 𝑟 ) ∨ (¬𝑟 ∧ 𝑟 )$ (Distributive)

However I think I'm going down the wrong track and would appreciate some help. Thanks

It might become easier to manipulate such logical expression, if you use another way of writing it as shown below. Then, logical manipulations become mere algebraic manipulation:

• $P\lor Q= P+Q$, $P\land Q = P\cdot Q = PQ$, $\lnot P = \overline{P}$, $0 =F$, $1=T$
• Then De-Morgan reads as follows: $\overline{P+Q} = PQ$
• Distributivity of $\land$: $(P+Q)R = PR+QR$
• Tautology and contradiction etc.: $Q\overline Q = 0$, $Q + \overline Q = 1$, $1+Q = 1$, etc.

That way, the transformation of your expression becomes quite short and easy to read:

$$\overline{ (\overline{Q} + R)(\overline{P} Q R) + \overline{R} } \stackrel{de Morgan}{=} \overline{ (\overline{Q} + R)(\overline{P} Q R) }R \stackrel{Distr.\;\&\; Q\bar Q=0}{=} \overline{ ( \overline{P} Q R) } R \stackrel{de Morgan}{=} (P + \overline{Q} + \overline{R})R \stackrel{Distr.\;\&\; R\bar R=0}{=} (P + \overline{Q})R$$

• Would you mind explaining the 2nd step again? The one with the distributive law? I understand the basis of it from what I've been taught, but I'm not sure what you're doing it with apart from the (q'+r)? I definitely agree that it's easier to do it as the shorthand notation, I should've done that sooner – Sarah Apr 29 '18 at 9:53
• In the second step I do the following (note that $AB = BA$): $(\overline{Q} + R)(\overline{P} Q R) \stackrel{Distr.}{=} \overline{Q}\, \overline{P} Q R + R \overline{P} Q R \stackrel{Q\bar Q=0 \;\&\; RR=R}{=} 0\cdot \overline{P} R + \overline{P} Q R \stackrel{0+X = X}{=}\overline{P} Q R$ – trancelocation Apr 29 '18 at 11:55
• Now that's clicked, thank you so much – Sarah Apr 30 '18 at 9:41

$$=((𝑞 ∧ ¬𝑟) ∧ 𝑟) ∨ (𝑝 ∧ 𝑟) ∨ (¬𝑞 ∧ 𝑟 ) ∨ (¬𝑟 ∧ 𝑟 )$$ (Distributive)

However I think I'm going down the wrong track and would appreciate some help.

No, that's okay. Follow with :

$$=((𝑞 ∧ ¬𝑟) ∧ 𝑟) ∨ (𝑝 ∧ 𝑟) ∨ (¬𝑞 ∧ 𝑟 ) ∨ 0$$ (Complementation)

$$=((𝑞 ∧ ¬𝑟) ∧ 𝑟) ∨ (𝑝 ∧ 𝑟) ∨ (¬𝑞 ∧ 𝑟 )$$ (Identity)

And similarly simplify the rest.

(Hint: next is Association)

Here are some tips:

Do you see how the term $\neg q \lor r$ is being conjuncted with $(\neg p \land q \land r)$?

Well, since that last term is a conjunction itself, you can drop the parentheses around them. So:

$(\neg q \lor r) \land (\neg p \land q \land r)=(\neg q \lor r) \land \neg p \land q \land r$

Now, the $r$ term will absorb the $\neg q \lor r$ term, and so:

$(\neg q \lor r) \land \neg p \land q \land r = \neg p \land q \land r$

Now, that term gets disjuncted with $\neg r$. Here is a handy equivalence:

Reduction

$\neg p \land (p \lor q) = \neg p \land q$

$\neg p \lor (p \land q) = \neg p \lor q$

So, using Reduction:

$[\neg p \land q \land r] \lor \neg r = [\neg p \land q] \lor \neg r$

OK, so now negate that, do a few DeMorgan's and you are done.

In general: Absorption and Reduction are your real friends when it comes to simplifying. Distribution on the other hand can make things more difficult ... unless your u go the other way around (i.e. 'undistribute')

• That way was a lot simpler than I was doing. We've always been told to do the deMorgans part first but that seemed to make it a lot harder to follow – Sarah Apr 29 '18 at 4:02