Questions: Conjunctive and Disjunctive Normal Forms

Question 1

You have a propositional formula in DNF. Which reasoning task can be checked most efficiently directly from the DNF structure?

• A. Validity (is the formula true in all models?)
• B. Satisfiability (is there any model that makes the formula true?)
• C. Equivalence to another formula
• D. Converting to CNF

Answer: (B)

DNF makes satisfiability trivially easy: a DNF formula is satisfiable if and only if at least one conjunct is consistent — contains no literal and its negation. Just scan each conjunct for a contradiction; if none has one, the formula is satisfiable. Validity, by contrast, is hard in DNF (every conjunct must be a tautology). CNF reverses this: satisfiability is hard (the NP-complete SAT problem), but checking whether the formula can be falsified is easy (does any clause have all literals simultaneously falsifiable?).

Question 2

What is the CNF of ¬(p ∧ ¬q)?

• A. p ∧ ¬q
• B. ¬p ∧ q
• C. ¬p ∨ q
• D. p ∨ ¬q

Answer: (C)

Apply De Morgan's law: ¬(p ∧ ¬q) = ¬p ∨ ¬(¬q) = ¬p ∨ q. This is already a single clause (a disjunction of literals), so it is in CNF. The result is ¬p ∨ q. Note that this is also in DNF (a single conjunct with two literals is degenerate — a single-literal DNF). The key step is recognizing that De Morgan's law converts ¬(A ∧ B) into ¬A ∨ ¬B, pushing the negation inward.

Question 3

A DNF formula is satisfiable if and only if it contains at least one conjunct that does not contain both a literal and its negation.

• T. True
• F. False

Answer: True

A DNF conjunct (like p ∧ ¬q ∧ r) is satisfiable exactly when it is internally consistent — no variable appears both positively and negated in the same conjunct. If such an assignment exists for one conjunct, the whole DNF is satisfiable (set variables to satisfy that conjunct; ignore other conjuncts). If every conjunct contains a complementary literal pair (p and ¬p), every conjunct is a contradiction, so the formula is unsatisfiable. This makes DNF satisfiability a linear-time check.

Question 4

Nearly every propositional formula has a unique CNF representation.

• T. True
• F. False

Answer: False

CNF and DNF representations are NOT unique. A formula can have many equivalent CNF representations. For example, (p ∨ q) and (p ∨ q) ∧ (p ∨ q) are logically equivalent CNFs of the same formula. The canonical CNF derived from a truth table (one clause per falsifying row) is unique, but general CNF conversion does not produce a canonical form. The misconception of uniqueness likely comes from conflating 'normal form' with 'canonical form' — normal forms impose structural constraints, not uniqueness.

Question 5

Why is CNF, rather than DNF, the standard input format for modern SAT solvers, even though DNF makes satisfiability easy to check?

Model answer: DNF makes satisfiability easy for a single formula, but converting an arbitrary formula to DNF can cause an exponential blowup in size. A formula with n variables may have a DNF with up to 2ⁿ conjuncts. SAT solvers instead work on CNF, where the resolution proof method operates efficiently: two clauses (A ∨ p) and (B ∨ ¬p) resolve to (A ∨ B), eliminating a variable. Resolution requires CNF structure. While CNF satisfiability is NP-complete in theory, modern DPLL/CDCL solvers exploit CNF's clause structure to prune the search space dramatically in practice.

The tradeoff is: DNF gives you an easy satisfiability check but blows up in size during conversion; CNF stays compact but makes satisfiability hard. For practical automated reasoning, the compactness of CNF and the tractability of resolution outweigh the theoretical ease of DNF satisfiability checking.