Questions tagged [conjunctive-normal-form]

A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals.

123 questions
Filter by
Sorted by
Tagged with
63k views

Find DNF and CNF of an expression

I want to find the DNF and CNF of the following expression $$x \oplus y \oplus z$$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...
210 views

447 views

Why Conjunctive Normal Form (CNF) is used instead of simply AND + NOT

I am looking at Conjunctive Normal Form examples, such as this: ${\displaystyle (A\lor \neg B\lor \neg C)\land (\neg D\lor E\lor F)}$ where it is a conjunction (AND) of disjunctions (ORs). So it's ...
8k views

Every sentence in propositional logic can be written in Conjunctive Normal Form

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question: Any propositional logic sentence is logically equivalent to ...
36 views

49 views

A fomular for CNF-DNF conversion

I just see this nice generalisation of sets: \bigcup_{(i,j) \in I \times J} (A_i \times B_j) = \bigcup_{i \in I} \bigcup_{j \in J} (A_i \times B_j) = \Biggl(\bigcup_{i \in I} A_i\Biggr) \times \...
66 views

help prove this propositional logic equivalency [duplicate]

I'm really stuck on proving this propositional logic equivalency. I've tried De Morgan's law, and double negation to see if I could get it, but no luck. Any help is greatly appreciated! P.S Please, ...
I want to create an algorithm for a CNF formula with clause length n on m literals that is mistake bound by $m^{O(n)}$. I know that I want to take the input and use feature expansion to create a ...