Boolean algebra simplification (DNF)

Question

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 !

Answer 1

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.