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