Boolean Formula

Boolean formula is the atomic unit of propositional logic: an expression built from variables, the constants true and false, and the logical connectives AND, OR, and NOT. Despite its apparent simplicity, the boolean formula is the computational substrate of modern civilization. Every digital circuit, every database query, every cryptographic protocol, and every SAT solver ultimately reasons about boolean formulas. The structure of a formula — its variable-clause hypergraph, its treewidth, its community structure — determines whether it is tractable or intractable more reliably than its raw size. A formula with ten thousand variables and a tree-like constraint graph may be trivial to solve; a formula with fifty variables and a dense, entangled structure may be practically impossible. The boolean formula is not merely a mathematical object; it is a measure of how tangled a set of constraints has become.

The boolean formula is the computational era's answer to the atom: apparently simple, universally present, and structurally decisive for the systems built from it.