0
$\begingroup$

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

$\endgroup$
0

3 Answers 3

Reset to default
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Sarah
    Apr 29, 2018 at 9:53
  • $\begingroup$ 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$ $\endgroup$
    – trancelocation
    Apr 29, 2018 at 11:55
  • $\begingroup$ Now that's clicked, thank you so much $\endgroup$
    – Sarah
    Apr 30, 2018 at 9:41
0
$\begingroup$

$=((π‘ž ∧ Β¬π‘Ÿ) ∧ π‘Ÿ) ∨ (𝑝 ∧ π‘Ÿ) ∨ (Β¬π‘ž ∧ π‘Ÿ ) ∨ (Β¬π‘Ÿ ∧ π‘Ÿ ) $ (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)

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Sarah
    Apr 29, 2018 at 4:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .