# 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.

7 questions
Filter by
Sorted by
Tagged with
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 ...
793 views

### Is the minimal conjunctive normal form for positive formula unique? If so, how do you calculate it?

I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms. $$A$$ $$A \land (A \lor B)$$ The minimal example is $A$. Does ...
71 views

### First Order Logic - exactly one predicate is true

I am working on a question for an assignment and I am to declare a clause in Conjunctive Normal Form that says exactly one of three predicates is true. Or given a bit of context - given three suspects ...
955 views

### Is it possible for the DNF and CNF to be the same

For example can $A \land C$ be both the conjunctive normal form and the disjunctive normal form of $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$
I am fairly confident of the definition of CNF and DNF (e.g. why $(P \land Q)$ in both CNF and DNF. However, I'm a little shaky when it comes to converting between the two normal forms. Is it ...