2

I am going through the accepted proof in this thread.

There is a section that uses absorption for a final reduction into the desired result.

How do I use two applications of absorption to:

$(\neg P \lor R \lor Q) \land (\neg P \lor R \lor \neg Q) \land (\neg P \lor Q) \land (\neg Q \lor R)$

to obtain:

$(\neg P \lor Q) \land (\neg Q \lor R)$

Where Absorption is defined as:

Absorption

$$P \land (P \lor Q) = P$$

When I attempted it, I did a few applications of the distributive property, but my results did not pattern match in an obvious way to the absorption pattern. I would like to see how this is done.

tree_traversal
  • 93

1 Answers1

1

Let $\neg P\vee Q=X,\neg Q\vee R=Y$. You thus want to simplify $(X\vee R)\wedge(\neg P\vee Y)\wedge X\wedge Y$. Since conjunction is commutative, it is equivalent to $(X\vee R)\wedge X\wedge(\neg P\vee Y)\wedge Y$. You'll need to apply the absorption law twice, once with the first and then with the last two terms:

$(X\vee R)\wedge X=X$ and $(\neg P\vee Y)\wedge Y=Y$. The final expression is $X\wedge Y$.

Shubham Johri
  • 17,659