Fact-checked by Grok 2 weeks ago

Conjunctive normal form

Conjunctive normal form (CNF) is a standardized syntactic form for propositional logic formulas, consisting of a of one or more , where each is a disjunction of literals and a literal is either a or its . Any propositional logic formula can be converted to an equivalent CNF formula via a systematic process involving the elimination of logical connectives like implications and equivalences, application of to push negations inward, removal of double negations, and distribution of disjunctions over conjunctions, though this transformation may exponentially increase the formula's size. The resulting CNF preserves the original formula's , making it a canonical representation for logical expressions. CNF is foundational in as the input format for the (SAT), which determines whether a given CNF admits a truth assignment that makes it true; SAT was the first problem proven NP-complete by Stephen Cook in 1971. Modern SAT solvers, which efficiently handle large-scale CNF instances using techniques like DPLL and CDCL, rely on this form to achieve practical performance despite SAT's theoretical intractability. Beyond , CNF finds broad applications in , including of hardware and software systems where logical properties are encoded as CNF constraints to check for bugs or inconsistencies, planning by modeling goals and actions as problems, and via , a complete method that operates directly on CNF clauses. These uses underscore CNF's role in bridging logical reasoning with practical algorithmic solutions across diverse domains.

Definition and Syntax

Formal Definition

In propositional logic, a literal is either a propositional variable p (a positive literal) or its negation \neg p (a negative literal). A clause is a finite disjunction of literals, such as l_1 \vee l_2 \vee \cdots \vee l_k, where each l_j is a literal and k \geq 1. A conjunctive normal form (CNF) formula is a finite conjunction of clauses, denoted as \phi = \bigwedge_{i=1}^m \left( \bigvee_{j=1}^{k_i} l_{ij} \right), where m \geq 1, each k_i \geq 1, and each l_{ij} is a literal. Semantically, a CNF formula \phi is satisfied (true) under a truth assignment if and only if every clause is true, which occurs precisely when at least one literal in each clause is true. Special cases of CNF include the empty CNF (a conjunction with no clauses, m = 0), which is vacuously true as a ; a single-clause CNF ( m = 1), which reduces to a disjunction of literals; and a unit clause (a clause with a single literal, k_i = 1), which requires that literal to be true for the clause to hold. CNF serves as the syntactic dual to (DNF), where the roles of and disjunction are reversed.

Examples and Canonical Forms

A simple example of a conjunctive normal form (CNF) involving three propositional variables p, q, and r is (p \lor \lnot q) \land (\lnot p \lor r). This consists of two s, each a disjunction of literals, conjoined together, satisfying the syntactic structure of CNF. To verify the of this CNF , a can be constructed enumerating all $2^3 = 8 possible assignments to p, q, and r. The evaluates to true under several assignments, such as p = \top, q = \top, r = \top (where both clauses hold) and p = \bot, q = \bot, r = \top (where the second clause holds and the first simplifies appropriately), confirming it is satisfiable. The full is as follows:
pqrp \lor \lnot q\lnot p \lor rFormula
\top\top\top\top\top\top
\top\top\bot\top\bot\bot
\top\bot\top\top\top\top
\top\bot\bot\top\bot\bot
\bot\top\top\bot\top\bot
\bot\top\bot\bot\top\bot
\bot\bot\top\top\top\top
\bot\bot\bot\top\top\top
This approach demonstrates how truth tables establish satisfiability for small CNF instances by checking if any row yields true. An unsatisfiable CNF example is (p) \land (\lnot p), a of contradictory unit clauses over one p. Its truth table has two rows: when p = \top, the first clause holds but the second fails; when p = \bot, the second holds but the first fails, resulting in false for all assignments. A tautological CNF, which is satisfied by every assignment, can be the empty conjunction (conventionally true) or include tautological clauses like (p \lor \lnot p). For the latter, the truth table over p shows true in both rows, as the clause always evaluates to true regardless of p's value. Full disjunctions covering all assignments equivalently represent tautologies but align with ; in CNF, such coverage is achieved via empty or universally true clauses. The CNF of a , also known as the maxterm canonical form or product-of-sums form, is the complete of all maxterms corresponding to input where the function evaluates to false. Each maxterm is a disjunction of n literals (one per , complemented based on the assignment), and the form includes up to $2^n such clauses in the worst case, when the function is false everywhere. This representation is unique for a given and directly derives from it. The maxterms in the full are implicates of the . In contrast, the prime implicates form an irredundant basis for a minimal CNF, where a prime implicate is a implied by the that cannot be weakened (by removing literals) while remaining an implicate. The number of prime implicates remains bounded by $2^n in the worst case. For instance, the f(x, y, z) = x + yz has canonical CNF (x + y + z)(x + y + z')(x + y' + z), corresponding to maxterms for the assignments where f = 0.

Conversion to CNF

Syntactic Methods

Syntactic methods for converting propositional formulas to conjunctive normal form (CNF) rely on applying a series of logical equivalences to rewrite the formula structurally, preserving its semantics while achieving the desired syntax of a of disjunctions of literals. These transformations are purely algebraic, operating on the formula's syntax without reference to truth assignments or models. The process typically begins by eliminating non-standard connectives and normalizing negations, followed by distributive expansions to ensure the formula fits the CNF structure. A standard step-by-step proceeds as follows: First, eliminate implications using the A \to B \equiv \neg A \vee B, and equivalences using A \leftrightarrow B \equiv (\neg A \vee B) \wedge (A \vee \neg B). Next, reduce the to one using only (\neg), (\wedge), and disjunction (\vee) by handling negations. Finally, apply the distribution rule iteratively to push disjunctions inward. This guarantees an equivalent CNF for any propositional input. Handling negations involves pushing them inward through conjunctions and disjunctions using : \neg (A \wedge B) \equiv \neg A \vee \neg B and \neg (A \vee B) \equiv \neg A \wedge \neg B, along with elimination \neg \neg A \equiv A. This step converts the formula to (NNF), where negations apply only to atomic propositions, facilitating subsequent distribution. The core of the transformation is the distribution rule, which expands disjunctions over conjunctions: (A \wedge B) \vee C \equiv (A \vee C) \wedge (B \vee C). Applied iteratively, this rule converts any expression in NNF to by ensuring all disjunctions are within clauses connected by conjunctions. For instance, starting from (p \to (q \vee r)), first replace the to obtain \neg p \vee (q \vee r), which is already a single in CNF: \neg p \vee q \vee r. These syntactic transformations can lead to an increase in size in the worst case, with the number of clauses potentially reaching O(2^n) for a with n variables, primarily due to repeated applications of the on balanced conjunction-disjunction trees.

Semantic Methods

Semantic methods for converting propositional formulas to conjunctive normal form (CNF) rely on truth assignments and semantic properties, such as the formula's satisfying and falsifying valuations, to construct an equivalent CNF. These approaches ensure by directly capturing the formula's semantics but often at the cost of efficiency, as they may require enumerating all possible assignments. Unlike syntactic manipulations that distribute operators algebraically, semantic methods emphasize the formula's or dual representations to build clauses that precisely reflect the original semantics. The primary semantic technique is the truth-table method, which constructs a CNF by identifying all falsifying assignments of the and deriving a blocking for each. For a \phi over n , enumerate the $2^n possible truth assignments and determine those where \phi evaluates to false. For each falsifying assignment \alpha, form the consisting of the disjunction of literals that are false under \alpha: specifically, for each x, include x if \alpha(x) = \bot (false) and \neg x if \alpha(x) = \top (true). The resulting CNF is the of these , which is false precisely on the falsifying assignments of \phi and true otherwise, yielding . This method preserves both and equivalence to the original . Consider the example \phi = p \land (q \lor \neg r). The falsifying assignments are: (p=\bot, q=\bot, r=\bot), (p=\bot, q=\bot, r=\top), (p=\bot, q=\top, r=\bot), (p=\bot, q=\top, r=\top), and (p=\top, q=\bot, r=\top). The corresponding clauses are: \begin{align*} &(p \lor q \lor r), \\ &(p \lor q \lor \neg r), \\ &(p \lor \neg q \lor r), \\ &(p \lor \neg q \lor \neg r), \\ &(\neg p \lor q \lor \neg r). \end{align*} The CNF \phi' = (p \lor q \lor r) \land (p \lor q \lor \neg r) \land (p \lor \neg q \lor r) \land (p \lor \neg q \lor \neg r) \land (\neg p \lor q \lor \neg r) is logically equivalent to \phi. Another semantic approach involves first converting \phi to (DNF) using the —by conjoining literals for each satisfying assignment—then deriving a CNF via the operation from . The of two DNF terms (implicants) that differ in exactly one is obtained by removing the differing literals; repeated application generates the prime implicants of the DNF. To obtain the CNF of \phi, apply this to the DNF of \neg \phi to find its prime implicants, then negate the result to yield the prime implicates (clauses) forming an irredundant CNF equivalent to \phi. This leverages semantic duality: \text{CNF}(\phi) \equiv \neg \text{DNF}(\neg \phi). The operation, foundational to resolution-based reasoning, ensures the derived form captures essential semantic constraints. Semantic methods like these preserve by construction but do not always yield , as partial applications or approximations may alter truth values on some assignments while maintaining satisfiability; full , however, achieves . In contrast, syntactic provides an alternative for equivalence without explicit assignment . Limitations include exponential time and , as constructing the full requires O(2^n) operations, rendering the approach impractical for large n.

Advanced Transformation Techniques

The Tseitin transformation provides an efficient method for converting arbitrary propositional formulas into an equisatisfiable CNF representation, particularly suited for large-scale formulas where preserving structure is crucial. This technique introduces auxiliary variables to represent subformulas, encoding each —such as , or NOT—as a set of clauses that maintain satisfiability without equivalence. The resulting CNF has a size linear in the original formula's length, making it preferable over exponential syntactic expansions for practical applications in . For instance, to encode an where auxiliary variable A represents B \land C, the transformation generates the following clauses: (\neg B \lor \neg C \lor A) \land (B \lor \neg A) \land (C \lor \neg A) These clauses ensure A is true if and only if both B and C are true, using implications to propagate values during unit propagation in SAT solvers. Resolution-based conversion techniques leverage unit propagation and derived clauses to construct implicants incrementally, avoiding full expansion by focusing on resolvents that capture essential dependencies. In the Plaisted-Greenbaum transformation, a variant of this approach, one-way implications are encoded as clauses (e.g., \neg B \lor A for B \to A) for single-polarity subformulas, enabling resolution steps to build a structure-preserving CNF with linear size in many cases and fewer auxiliary variables than Tseitin's method. This method uses conditional to derive implicants, integrating unit to simplify during and reducing clause count while preserving assignability. Partial evaluation enhances CNF conversion by simplifying formulas through partial assignments or alternative representations before complete transformation, mitigating size explosion for complex inputs. Using binary decision diagrams (BDDs), the formula can be compactly represented, allowing evaluation of subpaths to propagate constants or detect redundancies, yielding a reduced intermediate form from which CNF clauses are extracted via path to the zero-terminal (negated for clauses). This approach is particularly effective for circuits or formulas with shared substructures, as BDDs enable simplification prior to clausal output.

Structural Properties

Clause Composition and Size Bounds

Clauses in conjunctive normal form (CNF) are disjunctions of literals and can be classified based on the presence of positive and negative literals. A positive clause contains only positive literals (unnegated variables), a negative clause contains only negative literals (negated variables), and a mixed clause includes both. The empty , which has no literals, is unsatisfiable under any , rendering the entire CNF formula false. Unit clauses consist of exactly one literal and play a key role in simplification algorithms. A restriction known as k-CNF limits each clause to at most k literals, influencing the of the problem. For instance, 2-CNF formulas, where clauses have at most two literals, can be solved in time using graph-based algorithms that model implications between variables. In contrast, 3-CNF formulas, with clauses limited to at most three literals, are NP-complete, establishing a fundamental hardness threshold for the general problem. Non-tautological clauses in CNF do not contain both a and its . The empty clause has length zero and is a special case of unsatisfiability. Non-empty non-tautological clauses have a minimal length of one literal. Tautological clauses, containing complementary literals such as x \lor \neg x, are always true and can be removed without altering the formula's semantics, as they contribute no constraint. Regarding size bounds, representing an arbitrary on n variables in CNF may require up to $2^n clauses in the worst case, corresponding to one clause per falsifying in the complete . This exponential bound highlights the potential succinctness loss when converting general formulas to CNF, as some functions like demand nearly this many clauses even in minimal representations. Composition rules ensure CNF formulas are irredundant. Absorbing clauses, or subsumption, occur when one clause's literals are a of another's; the longer clause is redundant and can be eliminated, as it is implied by the shorter one. These rules facilitate preprocessing in solvers by reducing formula size while preserving .

Maximal Representations

In conjunctive normal form (CNF), the maximum number of distinct non-tautological clauses possible for n propositional variables is $3^n - 1. This count arises because, for each of the n variables, a clause can include the positive literal, the negative literal, or neither, yielding $3^n possibilities including the empty clause (which represents falsehood and is typically excluded); subtracting the empty case gives the non-empty clauses. The conjunction of all $3^n - 1 such clauses forms an unsatisfiable formula, as any truth assignment falsifies at least the clause composed of the negated literals corresponding to the values assigned true under that assignment. A canonical unsatisfiable CNF uses exactly $2^n clauses, one corresponding to each possible truth over the n variables. Each such forbids a specific by disjoining the negations of the literals that are true under it, ensuring the clause has exactly n literals. For n=2 with variables p and q, this yields the unsatisfiable formula (\neg p \lor \neg q) \land ( \neg p \lor q ) \land (p \lor \neg q) \land (p \lor q). This construction is maximal in the sense of employing the longest possible clauses while achieving unsatisfiability with the fewest such full-length clauses; adding any subset of the remaining clauses preserves unsatisfiability. The dual construction for the constant true function (a ) in (DNF) requires $2^n terms, one for each truth assignment, to cover all possibilities exhaustively. In CNF, however, the is trivially represented by the empty of zero , as no restricting are needed; including any non- clause would render the non-tautological. Claude Shannon's 1949 counting argument establishes that most functions of n variables necessitate CNF (or equivalently, DNF) representations of size \Omega(2^n / n), implying that exponential clause counts are required for the majority of functions despite the existence of compact representations for specific ones like . This result underscores the inherent representational inefficiency of normal forms for general functions.

Computational Complexity

Satisfiability Problem

The Boolean satisfiability problem restricted to conjunctive normal form (CNF-SAT) asks whether there exists a truth to the variables of a given CNF φ such that φ evaluates to true, or to determine that no such exists (i.e., φ is unsatisfiable). A satisfying sets at least one literal true in every of φ, thereby making the entire true. One foundational approach to solving CNF-SAT is search, exemplified by the –Putnam–Logemann–Loveland (, which systematically explores partial assignments while applying inference rules to prune the search space. DPLL begins with unit propagation: if a contains only one unassigned literal, that literal must be true to satisfy the , so it is assigned true, and all clauses are simplified accordingly (e.g., clauses containing the become false if they reduce to the empty , indicating inconsistency). Next, pure literal elimination identifies literals that appear only positively or only negatively across all clauses; such a literal is assigned true (or false, respectively) without loss of , as setting it otherwise would falsify all clauses containing it. If no units or pures remain, DPLL performs clause splitting by selecting an unassigned variable, recursively checking under both possible assignments (true and false), and on failure. An alternative to is theorem proving, a deductive method that refutes unsatisfiability by deriving from the CNF clauses. In , two clauses containing complementary literals are combined to form a resolvent: from (l ∨ A) and (¬l ∨ B), where l is a literal and A, B are disjunctions of other literals, the resolvent is (A ∨ B). Repeated application generates new clauses until either the empty clause (⊥, denoting ) is derived—proving unsatisfiability—or no further progress is possible, suggesting (though requires exhaustive resolution). The and of propositional for CNF-SAT are well-established properties of the inference system. The Davis-Putnam procedure, a precursor to DPLL, relies solely on without branching or splitting: it applies unit resolution (resolving with unit clauses) and pure literal elimination exhaustively until the formula simplifies to (satisfiable) or (unsatisfiable). This complete but often inefficient method avoids search by fully expanding the closure. Consider the CNF formula φ = (p ∨ q) ∧ (¬p ∨ r) ∧ (¬q ∨ ¬r). Applying DPLL: No clauses initially, but no pure literals either. Split on p = true: the second clause simplifies to (r), a , so assign r = true; the third becomes (¬q ∨ ¬true) = (¬q), another , so q = false. The first clause is (true ∨ false) = true. All clauses satisfied, so φ is satisfiable under {p = true, q = false, r = true}. (Backtracking would confirm no need if this branch succeeds.)

Hardness and Approximability

The Cook-Levin theorem establishes that the for formulas in 3-conjunctive normal form (3-CNF-SAT) is NP-complete, achieved through a from arbitrary computations to a 3-CNF formula that encodes the machine's accepting paths. This reduction demonstrates that any problem in can be transformed into 3-CNF-SAT, highlighting its central role in . In contrast, 2-CNF-SAT is solvable in polynomial time, specifically linear time relative to the input size, by constructing an implication graph where literals are nodes and clauses represent directed edges, then checking for strongly connected components using algorithms like Tarjan's. The formula is satisfiable if and only if no variable and its negation lie in the same . For general k-CNF-SAT with k ≥ 3, the problem remains NP-complete, as shown by a straightforward from 3-CNF-SAT that introduces auxiliary variables to split longer clauses without altering . In random instances of 3-CNF-SAT, a occurs around a clause-to-variable ratio of 4.26, below which formulas are typically satisfiable and above which they are typically unsatisfiable, marking a sharp shift in algorithmic solvability. Regarding approximability, the for 3-CNF formulas (MAX-3-SAT) cannot be approximated within a factor of 7/8 + ε for any ε > 0 in time unless = , as implied by the through a gap-producing reduction that amplifies the distinction between satisfiable and unsatisfiable instances. As of 2025, no major breakthroughs have resolved the P vs. NP question for CNF-SAT variants, maintaining the foundational hardness results from the 1970s. However, quantum algorithms, such as extensions of the quantum approximate optimization algorithm (QAOA) tailored for k-SAT, have been explored for providing better approximations on near-term quantum hardware, showing potential quadratic speedups over classical methods in empirical studies. In practice, advances in SAT solvers, including enhancements and AI-driven heuristic evolution, have enabled solving large-scale instances, as seen in the SAT Competition 2025 where evolved solvers outperformed traditional ones.

Extensions and Applications

First-Order Logic Conversion

To convert (FOL) formulas into conjunctive normal form (CNF) for , such as in resolution-based systems, the process preserves while eliminating quantifiers and transforming the formula into a set of clauses. This transformation enables the application of unification and resolution rules to derive contradictions or proofs. The key steps involve obtaining , skolemization to remove existential quantifiers, and conversion to clausal form, as originally formalized in the context of machine-oriented theorem proving. The first step is to transform the formula into (PNF), where all quantifiers are moved to the front of the formula, leaving a quantifier-free . This is achieved by eliminating implications and biconditionals (e.g., A \rightarrow B becomes \neg A \vee B), pushing negations inward using and quantifier negations (e.g., \neg \forall x \, \phi(x) \equiv \exists x \, \neg \phi(x)), standardizing variables to avoid clashes, and pulling quantifiers outward via equivalences like \forall x ( \phi(x) \wedge \psi ) \equiv \forall x \, \phi(x) \wedge \psi if x does not occur free in \psi. Every FOL formula is equisatisfiable with a PNF version, ensuring no loss of logical content during this structural rearrangement. Next, skolemization eliminates existential quantifiers by replacing existentially quantified variables with Skolem constants or functions that depend on the preceding quantifiers. For a prenex in the form \forall x_1 \dots \forall x_n \exists y \, \phi(x_1, \dots, x_n, y), the existential y is replaced by a Skolem f(x_1, \dots, x_n), yielding \forall x_1 \dots \forall x_n \, \phi(x_1, \dots, x_n, f(x_1, \dots, x_n)); if no quantifiers precede it, a Skolem constant c is used instead (e.g., \exists y \, \phi(y) becomes \phi(c)). This step preserves but not equivalence, as the Skolemized implies the original but not vice versa; it is crucial for generating a suitable for resolution. The resulting universal formula is then converted to clausal form by dropping the implicit universal quantifiers (as all remaining variables are universally quantified), transforming the matrix into CNF via distribution of conjunctions over disjunctions (e.g., (A \wedge B) \vee C becomes (A \vee C) \wedge (B \vee C)), and representing the CNF as a set of clauses, where each clause is a disjunction of literals. The final clausal form is a of such clauses, equisatisfiable with the original . For instance, consider the formula \forall x (P(x) \rightarrow \exists y \, Q(x,y)): after prenex form \forall x \exists y ( \neg P(x) \vee Q(x,y) ), skolemization yields \forall x ( \neg P(x) \vee Q(x, f(x)) ), and dropping the quantifier gives the clause \neg P(x) \vee Q(x, f(x)). To handle the infinite nature of domains in theorem proving, the Herbrand universe provides a finite by generating ground terms from the and constant symbols in the clausal form (adding a dummy constant if none exist). Ground instances of the clauses over this can then be treated as propositional clauses for , with unsatisfiability in all Herbrand interpretations implying unsatisfiability of the original formula via Herbrand's . This grounding step is essential for practical computation, though it may require iterative expansion of the .

Practical Uses in Computing

Conjunctive normal form (CNF) formulas serve as the foundational input for modern SAT solvers, which utilize (CDCL) to efficiently resolve queries on industrial-scale instances. Pioneering implementations like MiniSat introduced key optimizations such as watched literals and lazy clause evaluation, enabling rapid progress in solving complex CNF problems. Glucose further advanced CDCL through improved learned clause database management using Literal Block Distance (LBD) for activity scoring and aggressive pruning, achieving top performance in solver competitions and handling millions of s. These tools have transformed verification, where adopted SAT solvers in the early to formally verify designs against specifications, scaling to verify billions of gates in microarchitectures like Pentium 4 successors. Despite the of 3-CNF , CDCL's empirical efficiency has made CNF indispensable for such tasks. In and automated planning, CNF enables the "planning as satisfiability" approach, where STRIPS operators—core to the (PDDL)—are encoded as time-layered CNF formulas to find action sequences achieving goals. This translation allows SAT solvers to tackle classical problems, optimizing plans for domains like and by iteratively increasing the time horizon until confirms a solution. Similarly, in , SAT-based bounded model checking converts transition systems and temporal properties into CNF, verifying safety in concurrent software; while SPIN primarily uses binary decision diagrams (BDDs), SAT-based bounded model checking can be applied to Promela models using external SAT solvers or hybrid tools like NuSMV for analysis. For , equivalence checking encodes two Boolean circuits into a single CNF formula via Tseitin transformation, where unsatisfiability proves identical output behaviors under all inputs, streamlining VLSI validation. As of 2025, enhances SAT solving by learning heuristic clause selection policies from solver traces, with approaches like NeuroSelect using to adaptively select clause deletion policies, reducing by 5.8% on large benchmarks when integrated with the Kissat solver. In cryptography, SAT solvers attack stream ciphers by CNF-encoding the key stream generation and initialization vectors, recovering keys for weakened variants like Grain and Bivium through exhaustive search acceleration. The #SAT variant, counting satisfying assignments in CNF, supports by quantifying valid configurations in product lines, enabling coverage analysis and diverse test suite generation without enumeration. For instance, #SAT solvers like SharpSAT approximate solution counts in feature models, identifying redundancy in test cases for configurable systems.

References

  1. [1]
    [PDF] Lecture 17: Logic II - Stanford University
    A conjunction of clauses is called a CNF formula, and every formula in propositional logic can be converted into an equivalent CNF. Given a CNF formula, we can ...
  2. [2]
    [PDF] Logic and Mechanized Reasoning Normal Forms
    Conjunctive Normal Form: Introduction. A literal is a propositional variable p or its negation ¬p. A propositional formula is in Conjunctive Normal Form (CNF).Missing: definition | Show results with:definition
  3. [3]
    [PDF] Lecture 4 1 Overview 2 Propositional Logic
    Jan 23, 2019 · A propositional formula is in conjunctive normal form (CNF) if it is the conjunction of disjunctions of literals. As noted above, Y is a CNF ...
  4. [4]
    [PDF] Finding Hard Instances of the Satisfiability Problem
    By SAT we mean the problem of proposi- tional satisfiability for formulas in conjunctive normal form (CNF). Although SAT is apparently intractable in the ...<|control11|><|separator|>
  5. [5]
    [PDF] Solving Quantified Verification Conditions using Satisfiability Modulo ...
    A state is either the distin- guished state Fail (denoting T-unsatisfiability) or a pair of the form M || F, where F is a formula in conjunctive normal form ( ...
  6. [6]
    [PDF] A Propositional Theorem Prover to Solve Planning and Other ...
    The theorem is proved true if and only if the formula is found unsatisfiable. The formula is presented in conjunctive normal form (CNF), also called clause form ...
  7. [7]
    [PDF] Verification Using Satisfiability Checking, Predicate Abstraction, and ...
    conjunctive normal form (CNF) and passing the resulting formula to a SAT ... verification and planning can be framed as QBF formulas. The Boolean.
  8. [8]
    [PDF] Propositional logic - CS@Purdue
    A formule φ is in conjunctive normal form (CNF) if it is a conjunction of a number of disjunctions of literals only. L ::= P | ¬P literal. C ::= L | C ∨ C.
  9. [9]
    [PDF] Normal Forms Logical Operators
    Sep 14, 2020 · Normal forms are a standard format for formulas. Types include NNF, CNF, DNF, and INF, which are restricted sets of formulas.
  10. [10]
    [PDF] Mathematical Logic - Stanford University
    Conjunctive Normal Form. ○ A propositional logic formula φ is in conjunctive normal form (CNF) if it is the many-way AND (conjunction) of clauses. ○ (x ...
  11. [11]
    Satisfiability - GW Engineering
    CNF expressions: A Conjunctive-Normal-Form (CNF) expression looks like this: (x'1 + x2) (x'1 + x3); It is a collection of clauses that are AND'ed together ...
  12. [12]
    [PDF] 3.5 Canonical Forms
    Example. Express the Boolean function F = x + y z as a product of maxterms. Solution: First, we need to convert the function into the product-of-OR terms by ...
  13. [13]
    [PDF] ENEE244-010x Digital Logic Design
    Each of the maxterms in maxterm canonical form is an implicate of the function. • An implicate of a function is a prime implicate if the implicate does not ...
  14. [14]
    [PDF] LOGIC IN COMPUTER SCIENCE: Modelling and Reasoning about ...
    ... Logic in Computer Science by Huth and Ryan is an exceptional book. I was amazed when I looked through it for the first time. In addition to propositional ...
  15. [15]
    How to Convert a Formula to CNF
    Here's a routine to convert any formula to CNF. CONVERT(φ): // returns a CNF formula equivalent to φ // Any syntactically valid propositional formula φ must ...
  16. [16]
    A Machine-Oriented Logic Based on the Resolution Principle
    A Machine-Oriented Logic Based on the Resolution Principle. Author: J. A. Robinson ... First page of PDF. Formats available. You can view the full content in ...
  17. [17]
    On the Complexity of Derivation in Propositional Calculus
    Tseitin, G.S. (1983). On the Complexity of Derivation in Propositional Calculus. In: Siekmann, J.H., Wrightson, G. (eds) Automation of Reasoning. Symbolic ...
  18. [18]
    Tseitin or not Tseitin? The Impact of CNF Transformations on ...
    In this paper, we compare three transformations (ie, distributive, Tseitin, and Plaisted-Greenbaum) for bringing feature-model formulas into CNF.
  19. [19]
    [PDF] Integrating CNF and BDD Based SAT Solvers
    ABSTRACT: This paper presents an integrated infras- tructure of CNF and BDD based tools to solve the Boolean. Satisfiability problem. We use both CNF and ...
  20. [20]
    [PDF] On CNF Conversion for SAT and SMT Enumeration
    This conversion is generally done by using variants of the Tseitin [78] or the Plaisted and Greenbaum [64] transformations, which generate a linear-size ...<|control11|><|separator|>
  21. [21]
    https://www.cs.unm.edu/~mccune/prover9/manual/2009-02A/glossary.html
  22. [22]
    Prover9 Manual: Glossary - UNM CS
    A positive clause has no negative literals. A negative clause has no positive literals. Note that the empty clause is both positive and negative. A mixed clause ...
  23. [23]
    [PDF] Conjunctive Normal Form and DPLL - University of Iowa
    ¬((p → q) ∧ (p ∧ q → r) → (p → r)). ¬(¬((p → q) ∧ (p ∧ q → r)) ∨ (p → r)) ⇒. ¬¬((p → q) ∧ (p ∧ q → r)) ∧ ¬(p → r) ⇒. (p → q) ∧ (p ∧ q → r) ∧ ¬(p → r) ⇒.
  24. [24]
    [PDF] Satisfiability Solvers - Cornell: Computer Science
    We will be interested in propositional formulas in a certain special form: F is in conjunctive normal form (CNF) if it is a conjunction (AND, ∧) of clauses, ...
  25. [25]
    [PDF] Preprocessing Techniques
    Example. The clause (a V b V ¯ b) is a tautology. Definition (Subsumption). Clause C subsumes clause D if and only if C C D. Example.Missing: absorbing | Show results with:absorbing
  26. [26]
    [PDF] Boolean Function Complexity
    This resulted into the following general lower bounds criterion: if a monotone boolean function has a monotone circuit of size t, then it is t-approximable.
  27. [27]
    [PDF] CNF Encodings of Parity - arXiv
    The minimum number of clauses in a CNF representation of the parity function x1 ⊕ x2 ⊕···⊕ xn is 2n−1. One can obtain a more compact CNF encoding by using non- ...
  28. [28]
    [PDF] On Subsumption Removal and On-the-Fly CNF Simplification
    A subsumed clause is redundant and can be removed from the original formula without changing the Boolean function it represents. Since redundant clauses consume ...Missing: tautological | Show results with:tautological
  29. [29]
    [PDF] Boolean Function Complexity
    Page 1. Stasys Jukna. Boolean Function Complexity. Advances and Frontiers ... A DNF is a k-DNF if each of its monomials has at most k literals; similarly, a.
  30. [30]
    [PDF] The Synthesis of Two-Terminal Switching Circuits
    The Synthesis of Two-Terminal Switching Circuits. By CLAUDE. E. SHANNON. PART I: GENERAL THEORY. 1. INTRODUCTION. HE theory of switching circuits may be divided ...
  31. [31]
    [PDF] Satisfiability: Algorithms, Applications and Extensions
    • Boolean Satisfiability (SAT) in a short sentence: – SAT is the problem of deciding (requires a yes/no answer) if there is an assignment to the variables of a ...
  32. [32]
    [PDF] The Boolean Satisfiability Problem: an overview of solving ... - Hal-Inria
    May 19, 2021 · Satisfiable and unsatisfiable CNF formula. A CNF formula is satisfiable if there is an assignment of truth values to its variables so that at ...<|separator|>
  33. [33]
    [PDF] A Machine Program for Theorem-Provingt - Free
    In [1] is set forth an algorithm for proving theorems of quantification theory which is an improvement in certain respects over previously available algorithms ...
  34. [34]
    [PDF] The Davis-Putnam-Logemann-Loveland Procedure
    A literal is an atom or a negated atom. A clause is a disjunction of literals. (possibly the empty disjunction ⊥). A formula is said to be in conjunctive.Missing: pure elimination
  35. [35]
    [PDF] The DPLL Algorithm
    The Davis-Putnam-Logemann-Loveland (DPLL) algorithm is a procedure that combines search and deduction to decide satisfiability of CNF formulas.Missing: pure | Show results with:pure
  36. [36]
    [PDF] DPLL (1962)
    Pure literal elimination : ⇒ q, ¬q. Choose literal q = true: ⇒ true, false. Choose literal q = false ... Davis-Putnam-Logemann-Loveland algorithm.Missing: basics | Show results with:basics
  37. [37]
    [PDF] A Maehine-Orlented Logic Based on the Resolution Principle
    It is called the resolution principle, and it is machine-oriented, rather than human- oriented, in the sense of the preceding remarks. The resolution principle ...
  38. [38]
    A Machine-Oriented Logic Based on the Resolution Principle
    The theory of the resolution process is presented in the form of a system of first<~rder logic with .just one inference principle (the resolution principle).
  39. [39]
    [PDF] Herbrand's Theorem and Ground Resolution
    In this lecture we introduce Herbrand structures and state Herbrand's theorem. We then prove the. Ground Resolution Theorem, which justifies the use of the ...
  40. [40]
    A Computing Procedure for Quantification Theory - ACM Digital Library
    The hope that mathematical methods employed in the investigation of formal logic would lead to purely computational methods for obtaining mathematical.
  41. [41]
    [PDF] Implementing the Davis–Putnam Method - UC Davis Math
    A new technique of indexing only the first and last literals of clauses yields a unit propagation procedure whose complexity is sublinear to the number of ...
  42. [42]
    [PDF] Lecture Notes on SAT Solvers & DPLL - Carnegie Mellon University
    In this lecture we will switch gears a bit from proving logical theorems “by hand”, to algorithmic techniques for proving them automatically.
  43. [43]
    [PDF] The Complexity of Theorem-Proving Procedures - Computer Science
    A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed. Throughout this paper, a set of strings means a ...
  44. [44]
    [PDF] COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP ...
    Garey/David S. Johnson. Page 2. Library of Congress ... 3 Proving NP-Completeness Results. 3.1 Six Basic NP-Complete Problems. 3.1.1 3-SATISFIABILITY.
  45. [45]
    [PDF] Bengt ASPVALL, Michael F. PLASS and Robert Endre TARJAN
    In this note we present a simple constructive algorithm for the evaluation of formulas having two literals per clause, which runs in linear time on a ran- dom ...Missing: SAT paper
  46. [46]
    Revisiting the cavity-method threshold for random 3-SAT
    Feb 7, 2019 · A detailed Monte Carlo study of the satisfiability threshold for random 3-SAT has been undertaken. In combination with a monotonicity assumption we find that ...<|control11|><|separator|>
  47. [47]
    [PDF] Some Optimal Inapproximability Results
    We prove optimal, up to an arbitrary ϵ > 0, inapproximability results for Max-Ek-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over- ...
  48. [48]
    Solving k–SAT problems with generalized quantum measurement
    Oct 27, 2025 · Quantum algorithms that optimize solutions for k-SAT, such as the quantum approximate optimization algorithm (QAOA), show a similar ...
  49. [49]
    [PDF] First Order Logic: Conversion to CNF
    First Order Logic: Conversion to CNF. 1. Eliminate biconditionals and implications: • Eliminate ⇔, replacing α ⇔ β with (α ⇒ β) ∧ (β ⇒ α). • Eliminate ...<|control11|><|separator|>
  50. [50]
    [PDF] First Order Logic: =1=Prenex normal form. Skolemization. Clausal form
    Theorem: Every first-order formula A can be transformed to a clausal form {C1,...,Ck} such that A is equally satisfiable with the universal closure (C1 ∧···∧ Ck) ...
  51. [51]
    [PDF] Resolution In First-Order Logic
    In this chapter, the resolution method presented in Chapter 4 for propositional logic is extended to first-order logic without equality.
  52. [52]
    [PDF] On the Glucose SAT solver - HAL Artois
    Feb 28, 2022 · The set of novelties introduced with the SAT solver Glucose is now considered as a standard for practical SAT solving.Missing: Intel | Show results with:Intel
  53. [53]
    Fifteen Years of Formal Property Verification in Intel - ResearchGate
    Aug 7, 2025 · Model checking technologies have been applied to hardware verification in the last 15 years. Pioneering work has been conducted in Intel ...
  54. [54]
    [PDF] Solving Huge Instances with Intel® SAT Solver - DROPS
    Aug 19, 2022 · -Learning (CDCL) SAT solvers are widely used [5]. They implement backtrack search, enhanced by conflict clause learning and many other ...Missing: hardware | Show results with:hardware
  55. [55]
    [PDF] Planning as Satisfiability
    Testing satisfiability of CNF formulas is a famous NP-complete problem ... Given: a STRIPS planning problem, and positive integer n. Output: “yes” if ...Missing: PDDL | Show results with:PDDL
  56. [56]
    [PDF] Planning as Satisfiability: Heuristics
    Aug 29, 2013 · The identification of invariants is important for many types of planning problems represented in languages like PDDL and STRIPS that only ...
  57. [57]
    [PDF] A Practical Demonstration of the Model Checkers SPIN & NuSMV a
    We will first use the tool to encode transition systems and LTL and CTL formulas to be model checked. 2. We will use the tool to perform bounded model checking.
  58. [58]
    [PDF] Combinational Equivalence Checking - ISEC
    Encode C1 and C2 into two propositional formulas ϕ1 and ϕ2. 2. Compute the Conjunctive Normal Form (CNF) of ϕ1 ⊕ ϕ2, using Tseitin encoding; i.e., CNF(ϕ1 ⊕ ϕ2).
  59. [59]
    NeuroSelect: Learning to Select Clauses in SAT Solvers
    Nov 7, 2024 · This paper introduces a new clause deletion metric to diversify existing clause deletion policies. Then, we propose to use machine learning to evaluate and ...
  60. [60]
    [PDF] Grain of Salt — An Automated Way to Test Stream Ciphers through ...
    Abstract. In this paper we describe Grain of Salt, a tool developed to automatically test stream ciphers against standard SAT solver-based attacks.
  61. [61]
    [PDF] Attacking Bivium Using SAT Solvers - Uni Ulm
    In this paper we present experimental results of an applica- tion of SAT solvers in current cryptography. Trivium is a very promising stream cipher candidate in ...
  62. [62]
    Evaluating state-of-the-art # SAT solvers on industrial configuration ...
    Jan 13, 2023 · In this paper, we focus on propositional model counting (for short # SAT) which determines the number of satisfying assignments for a given ...
  63. [63]
    [PDF] The SAT Revolution: Solving, Sampling, and Counting
    Uniform Generation of SAT Solutions: Given a Boolean formula, generate solutions uniformly at random, while scaling to industrial-size problems. 11. Page 13 ...