Binary decision diagram Created 2026-10-31 Updated 2026-11-05
A directed acyclic graph representing a Boolean function. A decision node tests a Boolean variable and has zero and one successors; evaluation follows the corresponding arrows until a terminal node returns a Boolean value. Sharing subgraphs can make a binary decision diagram much smaller than a binary decision tree.
Boolean cofactor 2026-10-31
The Boolean function obtained by assigning a fixed Boolean value to a chosen Boolean variable in . The original Boolean function satisfies .
Boolean formula Created 2026-10-06 Updated 2026-10-18
A Boolean formula is a finite expression built from Boolean variables and Boolean operations, equivalently a propositional formula with two-valued semantics. A Boolean valuation determines its truth value. In , logical negation acts only on , and the outer logical conjunction combines with . Occurrences of the same Boolean variable share one truth value. The Boolean satisfiability problem asks whether some Boolean valuation makes the Boolean formula true.
Boolean game 2026-10-24
A finite game represented succinctly by propositional logic. Each player controls a disjoint collection of Boolean variables and chooses their truth values. Together those choices determine a Boolean valuation. A player's goal is a propositional formula, with payoff one if satisfied and zero otherwise. The control sets normally form a set partition of all variables.
A pure strategy strategy profile is a Nash equilibrium if every unsatisfied player remains unsatisfied after every change to that player's controlled variables. Checking a candidate can therefore require solving a Boolean satisfiability problem, even though evaluating its current payoffs is easy.
Boolean literal Created 2026-10-06 Updated 2026-10-18
A Boolean literal is a Boolean variable or its logical negation . The two Boolean literals have opposite truth values: a Boolean valuation gives when false and true are encoded as zero and one. Thus makes the positive Boolean literal false and the negative Boolean literal true. A Boolean clause combines Boolean literals, and a Boolean-pair colouring gadget represents a Boolean variable and its logical negation by two vertices with opposite Boolean colours.
Boolean satisfiability problem Created 2026-09-24 Updated 2026-10-18
The Boolean satisfiability problem asks whether a Boolean formula has an assignment making it true. A complete assignment is a Boolean valuation: it gives every Boolean variable a truth value, consistently at all occurrences. A satisfying assignment, also called a model of a Boolean formula, makes the entire Boolean formula true. A solver's answer
SAT asserts that at least one satisfying assignment exists; UNSAT asserts that the input is an unsatisfiable Boolean formula. These are statements about existence, rather than the truth value under one particular Boolean valuation.For conjunctive normal form, or CNF, writeEach Boolean literal is a Boolean variable or its logical negation. Each Boolean clause uses inclusive logical disjunction: one true Boolean literal suffices. The outer logical conjunction requires every Boolean clause to succeed under the same Boolean valuation. Choosing a different Boolean valuation for each Boolean clause would answer a different question.
Consider the original three-Boolean variable exampleAt the Boolean valuation , the Boolean literals in have values , those in have values , and those in have values . Every Boolean clause therefore has truth value one, so has truth value one: this is a satisfying assignment.
An original satisfying assignment evaluated through Boolean literals, three Boolean clauses, and their logical conjunction
. Details. The complete truth table has Boolean valuations. Exactly two are satisfying assignments: and . In particular, satisfies the first two Boolean clauses but falsifies the third, so satisfying most Boolean clauses does not suffice for SAT. That different objective belongs to maximum satisfiability.
All eight Boolean valuations of the original CNF example, with its two satisfying assignments highlighted
. Details. A short proof of completeness avoids listing all eight rows. If , the Boolean clause forces , after which forces ; is already true. If , forces , after which forces ; is already true. These two cases exhaust the truth values of and produce precisely the two satisfying assignments above.
Verifying a satisfying assignment and finding a satisfying assignment are different tasks. Given a candidate, evaluate the Boolean formula once; finding a candidate requires choosing compatible truth values across all its Boolean clauses. The Cook-Levin theorem says that general SAT is NP-complete, even though a proposed satisfying assignment is efficiently checkable. Its proof encodes a bounded nondeterministic computation as a Boolean formula whose satisfying assignments describe accepting computations. Stephen A. Cook's 1971 paper established this connection between computational complexity theory and propositional logic.[ref]
The Complexity of Theorem-Proving Procedures by Stephen A. Cook. The Complexity of Theorem-Proving Procedures by Stephen A. Cook, 1971, §1, Theorem 1 and proof, pp. 2–3 of the revision-3 transcription: CNF encodes accepting computations
A concrete use is checking finite configuration rules. Let mean that an optional feature is enabled, that a fallback is selected, and that the feature's required component is installed. Require a feature or fallback, require the component whenever the feature is enabled, and forbid using the fallback with that component. Logical implication rewrites the second rule as ; De Morgan's laws rewrite the third rule as . Their logical conjunction is exactly , so its two satisfying assignments give the two allowed configurations. The usefulness of SAT lies in expressing local rules uniformly while demanding one globally consistent Boolean valuation. The conclusion concerns exactly these encoded rules.
Boolean variable Created 2026-10-06 Updated 2026-10-18
A Boolean variable takes one of two truth values, false or true, encoded as zero or one. It is an input to a Boolean formula; a Boolean literal uses the Boolean variable either positively or with logical negation. A Boolean valuation assigns one truth value to each distinct Boolean variable, so three distinct Boolean variables give eight possible complete assignments regardless of how often each appears.
Given a succinct Boolean game and a complete pure strategy strategy profile, determine whether it is a Nash equilibrium. The problem is co-NP-complete for goal propositional formulas, even with one player. This differs from existential equilibrium checking in a Boolean game, which searches for some qualifying Nash equilibrium.
A negative instance has a short complexity certificate: a currently unsatisfied player and new truth values for that player's controlled Boolean variables that make the goal true. Evaluating the current and changed propositional formulas takes polynomial time, proving membership in co-NP.
For hardness, given a propositional formula , let one player control and a fresh variable , with goal . The all-false candidate has payoff zero. It is a Nash equilibrium exactly when is an unsatisfiable Boolean formula, since any satisfying assignment permits an improvement by also setting true. This is a polynomial-time many-one reduction from unsatisfiability. The fresh guard ensures that the candidate loses independently of the input formula's value there.
Cardinality constraint Created 2026-10-25 Updated 2026-10-31
A cardinality constraint restricts how many members of a specified collection are selected or satisfy a property. For Boolean variables, exactly selected entries gives the displayed sum; upper and lower bounds give at-most and at-least variants. Constraint propagation can maintain the number already selected and the number still available. A requirement involving many variables is a global constraint, even when it has a compact arithmetic description.
Circuit complexity Created 2026-09-24 Updated 2026-11-05
Circuit complexity measures the resources of Boolean circuits computing a Boolean function. Circuit size counts logic gates or wires under a declared convention; circuit depth measures the longest dependency chain. The allowed logic gates and their fan-in are part of the model.
For the conjunction of Boolean variables, a chain of two-input AND gates uses logic gates and depth . A balanced binary tree still uses logic gates but reduces depth to . A depth- Boolean circuit of fan-in at most two can depend on at most inputs, so that depth is optimal for this function. An unbounded-fan-in AND gate would compute it in one layer, showing why the logic gate convention matters.
A circuit family supplies one Boolean circuit per input length. uniform circuit families impose an effective construction rule; an unrestricted nonuniform family can choose separate Boolean circuits independently. Lower bounds therefore need both the Boolean circuit model and the uniformity convention.
Decision node 2026-10-31
An internal vertex that tests a condition and selects an outgoing branch. In a binary decision diagram, a decision node tests a Boolean variable and has one zero arrow and one one arrow.
Represent each original value choice by a Boolean variable and impose an exactly-one constraint for each original variable. For every forbidden tuple of a constraint with scope , add the Boolean clause . A complete original assignment satisfies every constraint exactly when its one-hot indicators satisfy all these Boolean clauses: each forbidden-tuple Boolean clause excludes precisely that joint choice. A satisfying assignment decodes by reading the unique true indicator for each original variable.
For constraint domain sizes , pairwise uniqueness requires Boolean clauses. If a constraint has forbidden tuples and arity , its contribution is Boolean clauses and literal occurrences. Thus bounded arity gives a polynomial-size encoding in explicitly listed domains, whereas enumerating a succinct high-arity relation can be exponential in its description length. Unit propagation on this encoding can be weaker than arc consistency on the original binary constraints.
Exactly-one constraint 2026-10-25
A restriction requiring exactly one member of a set of Boolean variables to be true. A direct conjunctive normal form encoding combines one at-least-one Boolean clause, , with at-most-one Boolean clauses, for . The first supplies existence and the second supplies uniqueness. For , the empty at-least-one Boolean clause correctly makes the condition unsatisfiable.
Finite-variable dependence of a propositional rule base Created 2026-10-25 Updated 2026-10-31
Every finite collection of finite propositional formulas mentions only finitely many Boolean variables. Two Boolean valuations agreeing on those variables satisfy exactly the same formulas. They therefore have the same value under any weighted formula utility representation using that collection.
This observation limits representation over infinite sets. On , the function indicating whether the selected subset is infinite cannot be represented by a finite rule base: if is the finite set of mentioned indices, and agree on all those indices but require values zero and one. Completeness claims for finite propositional rule bases must therefore specify a finite underlying set or restrict the functions represented.
Horn-SAT forward-chaining algorithm Created 2026-09-28 Updated 2026-11-05
The Horn-SAT forward-chaining algorithm maintains the set of Boolean variables already forced true. Write each Horn clause as an implication , where the conclusion is either a Boolean variable or false. Start with . Whenever every antecedent belongs to , add the conclusion ; if the conclusion is false, report failure.
Every satisfying assignment must make all members of true: this holds initially and is preserved by each enabled implication. Thus an enabled false conclusion proves that no satisfying assignment exists. If no further Boolean variable can be added and no such failure occurs, interpreting exactly as true satisfies every Horn clause. It is the least satisfying assignment under inclusion of true Boolean variables.
For example, the clauses , and force . Adding makes the instance unsatisfiable. Each Boolean variable enters at most once. Indexing antecedent occurrences and maintaining a counter per clause permits one update per occurrence, avoiding repeated full scans.
Karnaugh map 2026-10-25
A truth table arranged so neighbouring cells differ in one Boolean variable, using Gray code order along each multi-bit axis. Opposite edges are also adjacent. A valid group contains all combinations of varying variables while every other variable stays fixed; it eliminates those variables and gives an implicant; covering the one-cells yields a disjunctive normal form. The method is associated with Maurice Karnaugh.
Minterm 2026-10-25
A conjunction containing each of a specified finite collection of Boolean variables exactly once, either positively or negated. It is satisfied by exactly one Boolean valuation of those variables. The minterms for all valuations are mutually exclusive and collectively exhaustive, so they can encode an arbitrary finite table of values.
Nonattacking knights problem 2026-10-25
Choose distinct squares of an chessboard so that no chosen pair has absolute coordinate differences or . One constraint satisfaction problem representation has square-valued variables, requiring distinctness and pairwise nonattack. Another has one Boolean variable per square, a cardinality constraint fixing their sum to , and one mutual-exclusion constraint for every edge of the knight attack graph. The first has fewer variables when is small but represents each unlabelled placement up to times; the second uses only binary constraint domains and sparse local attack restrictions.
One-row in-place Life update 2026-10-13
On a finite rectangular Conway's Game of Life board stored as an array of Boolean variables, retain the preceding row's old values in one auxiliary row. Before overwriting a column, retain rolling sums of the old three-cell vertical columns. Their sum minus the old center is the old neighbor count. Read the next column before changing the current one; replace the saved row entry by the old current cell. The invariant is that every count uses the previous generation, just as in the two-array algorithm. For a board with rows and columns this uses auxiliary storage and time. The boundary convention must still be implemented explicitly. The Life blinker and Life glider provide exact expected generations for checking it.
Partial Boolean assignment 2026-10-18
A partial Boolean assignment gives truth values to some of a Boolean formula's Boolean variables. An extension is a complete Boolean valuation agreeing on the assigned Boolean variables. In CNF, a Boolean clause containing a true assigned Boolean literal is already satisfied; a Boolean clause whose every Boolean literal is assigned false rules out all extensions. A Boolean clause with no true assigned Boolean literal and at least one unassigned Boolean variable is unresolved. An unresolved Boolean clause need not have a compatible extension with the other Boolean clauses.
For in Boolean satisfiability problem, setting already falsifies , so both choices of can be discarded. Setting only leaves unresolved and forces if a satisfying assignment is to survive; then forces . Branching on an unassigned Boolean variable into its two truth values and discarding branches with a false Boolean clause is sound: every satisfying assignment follows one branch and cannot extend a false Boolean clause. If all branches are eliminated, the original Boolean formula is an unsatisfiable Boolean formula.

