CODEWITHSUNDEEP
discrete-mathematicsconjunctive-normal-form
Fahin Miah
Fahin Miah

Reputation: 19

How can I simplify the following CNF

(¬p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r)

I could not simplify the above CNF. Could anyone please help me to simplify the statement

Upvotes: -1

Views: 303

Answers (1)

Patrick87
Patrick87

Reputation: 28332

We can make a truth table for this:

p   q   r   (¬p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r)
0   0   0   1
0   0   1   0
0   1   0   0
0   1   1   0
1   0   0   1
1   0   1   0
1   1   0   1
1   1   1   0

If this truth table is correct, then an equivalent expression is:

(¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r)

We can factor out to simplify a bit...

[¬q ∨ (p ∧ q)] ∧ ¬r

We can also recognize that ¬q ∨ (p ∧ q) = ¬q ∨ p ...

(¬q ∨ p) ∧ ¬r

This seems to match the truth table we got, so if that truth table is right, this expression is almost surely minimal or close to it. It only uses each variable once and so the only way that springs to mind to try to improve it is De Morgan, but it doesn't look like it reduces the number of operations even, so this might be as good as it gets.

Upvotes: 0

Related Questions