- When is a formula said to be in 3CNF? Please provide examples. - What is the t

Question

- When is a formula said to be in 3CNF? Please provide examples.
- What is the theoretical importance of the concept of 3CNF?
- Consider a formula F in CNF consisting of one disjunction with one literal, for example F = q. Discuss how to transform F into a 3CNF.
- Consider a formula F in CNF consisting of one disjunction with two literals, for example F = q r. Discuss how to transform F into a 3CNF.
- Consider a formula F in CNF consisting of one disjunction with four literals, for example F = q r s t. Discuss how to transform F into a 3CNF.

Explanation / Answer

Technically, you can write x¬xx¬x in 3-CNF as (xxx)(¬x¬x¬x)(xxx)(¬x¬x¬x), but you probably want a "real" example.

In that case, a 3CNF formula needs at least 3 variables. Since each clause rules out exactly one assignment, that means you need at least 23=823=8 clauses in order to have a non-satisfiable formula. Indeed, the simplest one is:

(xyz)(xy¬z)(x¬yz)(x¬y¬z)(¬xyz)(¬xy¬z)(¬x¬yz)(¬x¬y¬z)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.