Laws of logic to simplify expression

Question

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

Answer 1

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$$

Answer 2

$=((𝑞 ∧ ¬𝑟) ∧ 𝑟) ∨ (𝑝 ∧ 𝑟) ∨ (¬𝑞 ∧ 𝑟 ) ∨ (¬𝑟 ∧ 𝑟 ) $ (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)

Answer 3

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')