-2

I am trying to simplify the following expression:

$(p \wedge r) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q \wedge r)$

I know that I should get $r \vee (\neg p \wedge q)$ but I am not sure how to explain.

Could you please help ?

Thanks a lot !

lmsteffan
  • 671
Martin Raynier
  • 9

1 Answers1

0

The ideal way is to use methods such as Karnaugh map to minimize your Boolean function. It can get problematic as the number of variables get larger if you decide to use algebra techniques.

I can propose a method which is very intuitive. We will use the 'Resolution method' (an alternative to Quine–McCluskey algorithm), then we will use Boolean algebra to minimize the expression.

For DNF, we will use this rule: $$(x \wedge a) \vee (\neg x \wedge b) \iff (x \wedge a) \vee (\neg x \wedge b) \vee (a \wedge b)$$ where $(a \wedge b)$ is your resolvent.

  1. We shall apply the layer algorithm, and find our resolvents. $$ \begin{align} (p \wedge r) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q \wedge r) & \space \space \space \text{(Layer 0)} \\ \vee (q \wedge r) \vee (\neg q \wedge r) \vee (\neg p \wedge r) & \space \space \space \text{(Layer 1)} \\ \end{align} $$

  2. We shall minimize the expression using Boolean algebra. $$ \begin{align} & (p \wedge r) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q \wedge r) \vee (q \wedge r) \vee (\neg q \wedge r) \vee (\neg p \wedge r) & \space \space \space \text{} \\ \iff \space & (p \wedge r) \vee (\neg p \wedge q) \vee (q \wedge r) \vee (\neg q \wedge r) \vee (\neg p \wedge r) \space \space \space \text{[Absorption]} \\ \iff \space & r \vee (\neg p \wedge q) \vee r \space \space \space \text{[Distributivity, Complement]} \\ \iff \space & r \vee (\neg p \wedge q) \\ \end{align} $$

Hope it helps.

Eddy Y
  • 416
  • Thanks a lot Eddy ! However, I didn't get how you were applying absorbtion law between first and second line. – Martin Raynier Oct 18 '22 at 07:20
  • Hi Martin. I shall zoom into the terms on the first and second line: $$ (p \wedge r) \vee ... \vee (\neg p \wedge \neg q \wedge r) \vee ... \vee (\neg q \wedge r)$$ $$ \iff ... \vee (\neg q \wedge r) \vee ...$$

    So by rule of absorption (or by factorizing the terms): $$ (\neg p \wedge \neg q \wedge r) \vee (\neg q \wedge r) = (\neg p \vee t) \wedge (\neg q \wedge r) = (t) \wedge (\neg q \wedge r) = (\neg q \wedge r)$$ Take note, $t$ means true.

    Hope it clarifies. Thank you. (PS: Please do upvote my original post if it solves your problem.)

     – Eddy Y Oct 18 '22 at 10:50
  • Much clearer now Eddy. Thank you !

    I have 2 more questions for tomorrow.

     – Martin Raynier Oct 18 '22 at 14:55
  • Now working on CNF, and I am having the following:

    $ \lnot(p \to q) \lor (r \to p) \equiv \lnot ( \lnot p \lor q) \lor (\lnot r \lor p) \equiv (p \land \lnot q) \lor (\lnot r \lor p) \equiv (p \lor \lnot r)$

    I didn't get how to go from $(p \land \lnot q) \lor (\lnot r \lor p) \equiv (p \lor \lnot r) $

    Lastly, using conditional statement, how to go from $ (\lnot p \to \lnot q) \equiv (p \lor \lnot q) $

     – Martin Raynier Oct 19 '22 at 01:37
  • It's the same thing. You might just need to rearrange and/or factorize your terms to get your answer.

    Hint for $(1):$ $$ \begin{align} & (p \wedge \neg q) \vee (\neg r \vee p) \ \iff & (p \wedge \neg q) \vee \neg r \vee p \ \iff & (p \wedge \neg q) \vee p \vee \neg r \ \iff & ... \ \end{align} $$

    I'm sure you know how to carry on from here.

    Hint for $(2):$ Just apply the conditional rule directly.

     – Eddy Y Oct 19 '22 at 11:59