twoclause

Twoclause is a term used in mathematical logic and computer science to denote boolean formulas in conjunctive normal form in which every clause contains at most two literals. The standard formal name for this class is 2-CNF; as a family of formulas it sits between the general CNF-SAT problem and more restricted fragments.

Definition and structure: A boolean formula φ is twoclause if φ equals the conjunction of clauses C1 ∧ C2 ∧ … ∧ Ck, where each Ci is either a single literal l or a disjunction of two literals (l ∨ m). This makes twoclause a subset of CNF formulas with each clause of size at most two.

Example: (x ∨ y) ∧ (¬x ∨ z) ∧ (¬y) is a twoclause formula. It contains two-literal clauses and one-literal clauses, all within the two-literal bound.

Solving and complexity: The satisfiability problem for twoclause formulas is known as 2-SAT and is solvable in polynomial time, in fact linear time relative to the formula size. A common method builds an implication graph with a node for each literal and its negation. Each clause (a ∨ b) yields edges (¬a → b) and (¬b → a). A satisfying assignment exists exactly when no variable x has both x and ¬x in the same strongly connected component; a satisfying assignment can then be obtained by a topological order of the strongly connected components.

Applications and relationships: Twoclause appears in hardware verification, model checking, and constraint solving, where efficient encodings are beneficial. It is a proper subset of CNF formulas; while 2-SAT is solvable in linear time, general 3-CNF SAT is NP-complete, as are larger-clause CNFs. Variants may allow unit clauses, maintaining the overall tractability of the 2-CNF fragment.