CODEWITHSUNDEEP
booleanlogicboolean-logiccnf
SKennedy09
SKennedy09

Reputation: 69

Converting a query to CNF

I've recently been trying to learn logic, but I've come across a query that I can't do and I'm not quite sure where I'm going wrong. When converting a query to CNF, what do you do when you come to this particular situation?

(a AND NOT(b AND c)) AND (d OR e)
= (a AND NOT b) OR (a AND NOT c) AND (d OR e)
=

How would i re-arrange this to get it into CNF form? Am I doing something completely wrong?

Thanks for your help, Sean

Upvotes: 3

Views: 543

Answers (1)

Valentin Montmirail
Valentin Montmirail

Reputation: 2640

I use the symbols: 

^ for AND
v for OR 
~ for NOT

and here is how you can transform your formula in CNF:

  (a ^ ~(b ^  c)) ^ (d v e)
= (a ^ (~b v ~c)) ^ (d v e)    // DeMorgan:   ~(A ^ B) <=> (~A v ~B)
=  a ^ (~b v ~c)  ^ (d v e)
= CNF

Every clauses are separated by AND and contain only OR. With your syntax it gives: 

a AND (NOT b OR NOT c) AND (d OR e)

I hope it helps :)

Upvotes: 0

Related Questions