A formula (logical expression) is in conjunctive normal form (CNF) when it joins clauses with AND. Under a truth assignment, it is true if and only if every clause is true. For example, (p OR NOT q) AND (q OR r) is in CNF.

Conjunctive normal form in propositional logic

Let L1, ..., Ls be the zero-one values of the literals in one clause. Its satisfaction indicator is Phi = 1 - (1-L1)...(1-Ls), where adjacent parentheses are multiplied. If all literals are false, every factor is 1 and Phi = 0. If any literal is true, its factor is 0 and Phi = 1. For p OR NOT q, Phi(x,y) = 1 - (1-x)y. On assignments (x,y) = (0,0), (0,1), (1,0), (1,1), the outputs are 1, 0, 1, 1. This zero-one interpretation is guaranteed only for Boolean inputs.

A polynomial that indicates whether a clause is satisfied

A clause is an OR of literals. Under a truth assignment, it is true if at least one literal is true. For example, (p OR NOT q) is false only when p is false and q is true. A single literal also counts as a clause.

AI Agents

A literal is a propositional variable, such as p, or its negation, NOT p. A truth assignment gives p either the value true or false; NOT p has the opposite value.

Literal in propositional logic

James Gallicchio. Verified CNF Encodings. Carnegie Mellon Computer Science Department PhD Blog, January 9, 2026. The SAT Definitions section supplies the definitions cited here.

https://www.cs.cmu.edu/~csd-phd-blog/2026/verified-cnf-encodings/

Verified CNF Encodings by James Gallicchio

A truth assignment chooses true or false for every distinct variable in a declared list. For the list p, q, the four assignments are (false, false), (false, true), (true, false), and (true, true). To add a new declared variable r, extend each assignment once with r = false and once with r = true. This gives two extensions for each old assignment, doubling the list from four to eight. A declared variable still gets a value even if it never appears in the formula (logical expression).

Learn Before

Related

Learn After

Learn After

Related