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.

Filter by
Sorted by
Tagged with
3
votes
3answers
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 ...
4
votes
1answer
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 ...
3
votes
2answers
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 ...
3
votes
2answers
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$
2
votes
0answers
4k views

Converting DNF to CNF and vice versa

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 ...
2
votes
1answer
141 views

Boolean algebra - Converting DNF form to CNF

I've tried at least a dozen ways to convert this DNF to CNF, yet I always end up with something unusable. Here is the DNF: $$y= (A \wedge B \wedge \neg C \wedge D) \vee (A \wedge B \wedge C \wedge \...
2
votes
1answer
2k views

Get DNF from Karnaugh map

The following boolean expression in CNF form $$ (x \lor y) \land (x \lor \lnot z) $$ Has been mapped into the Karnaugh map below \begin{array}{| c | c | c | c | ...