2clause

2clause, also written 2-clause, refers to a clause consisting of exactly two literals in propositional logic. In conjunctive normal form (CNF), a 2-clause is a disjunctive clause containing two literals, such as (x ∨ ¬y). A formula is called 2-CNF if every clause has at most two literals; a 2-clause is a fundamental unit in such formulas. Two-literal clauses are central to the study of the 2-SAT problem, which asks whether a given 2-CNF formula can be satisfied.

A key property of 2-CNF formulas is that 2-SAT can be decided in linear time with respect to the number of variables and clauses. The standard method constructs an implication graph: for each clause (a ∨ b), add the implications (¬a → b) and (¬b → a). The formula is satisfiable iff no variable and its negation lie in the same strongly connected component of this graph. If a contradiction is avoided, a satisfying assignment can be extracted from the topological order of the strongly connected components. This linear-time algorithm is attributed to Aspvall, Plass, and Tarjan and is widely used in theoretical computer science and practical constraint solving.

2-clauses appear in various applications, including hardware verification, circuit design, and constraint-based scheduling, where problems can be reduced to 2-CNF form. They also serve as a subroutine in more general SAT solvers and in logic-based inference tasks. Related concepts include 2-SAT, CNF, and boolean logic, as well as other clause-length categories such as 1-clause and 3-clause.