Simplify Conjunctive Normal Form?

2.6k Views Asked by At

is there any kind of general rules to follow or algorithm for trying to simplify something in conjunctive normal form? Specifically, I'm trying:
(P or Q) and P and (Q or R) and (P or notP or R) and (notQ or R)
I got that the 4th one is always true because it has complementary literals so
(P or Q) and P and (Q or R) and (notQ or R)
(P or Q) and P and (R or (Q and notQ)
(P or Q) and P and R
(P or Q) and (P or P) and R
(P or (Q and P)) and R
And then I got stuck. The answer I was supposed to get to was (P and R) so I feel like I was close but I'm not sure how to get rid of (P or Q). Are there some sort of rules to make this not-just-guess-work? (Sorry in advance, not sure how to even put in logic symbols so I figured I'd just use words)

1

There are 1 best solutions below

2
On

From $(P\vee Q)\wedge P\wedge R$.
By the distributive law of conjunction over disjunction, $((P\wedge P)\vee (Q\wedge P))\wedge R$
By idempotency, $(P\vee (Q\wedge P))\wedge R$.
By the distributive law $(P\wedge(1 \vee Q))\wedge R$
By annihilation for 1, $(P\wedge 1)\wedge R$
By absorption for 1, $P\wedge R$

Regarding your question, there are no methodical rules to simplify boolean expressions without defining a normal form which we could identify and which would allow us to recognize when the algorithm ends.