What kind of clauses are available in conjunctive normal form?
2020
What kind of clauses are available in conjunctive normal form?
- A.
Disjunction of literals
- B.
Disjunction of variables
- C.
Conjunction of literals
- D.
Conjunction of variables
Attempted by 361 students.
Show answer & explanation
Correct answer: A
Key fact: In conjunctive normal form (CNF) each clause is a disjunction (OR) of literals, and the whole formula is a conjunction (AND) of those clauses.
Literal = a variable or its negation (for example, x or ¬x).
Clause example: (x1 OR ¬x2 OR x3) — this is a disjunction of literals.
Formula example in CNF: (x1 OR ¬x2 OR x3) AND (¬x1 OR x4) — clauses joined by AND.
Why the other phrasings are wrong:
Describing clauses as a disjunction of variables is too restrictive because it excludes negated variables; CNF clauses allow negations.
Describing clauses as a conjunction of literals confuses clause structure with the top-level form: clauses are ORs of literals, while the top-level combination of clauses is an AND.