SAT solver: meaning and examples

A SAT solver is a program that decides whether a Boolean formula is satisfiable, returning a satisfying assignment when one exists, by search rather than by enumerating every row. The engine uses one for formulas with more than 20 inputs.

The Boolean satisfiability problem, SAT, asks whether some assignment makes a formula true. A solver answers it by propagating forced values and backtracking over choices, typically on a conjunctive normal form, and modern solvers handle formulas with thousands of variables that no truth table could list. Every exact check reduces to SAT: a tautology is a formula whose negation is unsatisfiable, and two formulas are equivalent when their XOR is unsatisfiable. The answer is exact, but a hard instance can take long, so a solver may also report that it did not finish.

The artefact on this page is a formula no table can show: all_24, the AND of 24 variables x1 to x24, whose table would have over sixteen million rows; the page has no truth table and the checks report no row count. The satisfiable check holds with the witness that sets all 24 variables TRUE, the contradiction check is violated with that same assignment, and the tautology check is violated with the counterexample that sets all 24 FALSE. Each witness was replayed through the evaluator before display, exactly as for small formulas.

SAT solvers sit under hardware verification, planning, package dependency resolution and software model checking, and SMT solvers extend them with arithmetic; the engine's SMT-LIB export hands a formula to such tools. The term is confused with a truth table generator (enumeration rather than search), with a theorem prover for richer logics, and with a simplifier. A verdict the solver cannot reach is reported as “Not determined”, never as a pass.

Example

all_24 := x1 AND x2 AND x3 AND x4 AND x5 AND x6 AND x7 AND x8 AND x9 AND x10 AND x11 AND x12 AND x13 AND x14 AND x15 AND x16 AND x17 AND x18 AND x19 AND x20 AND x21 AND x22 AND x23 AND x24 · output

Exact checks

Always true (tautology)? No Counterexample: x1 = F, x2 = F, x3 = F, x4 = F, x5 = F, x6 = F, x7 = F, x8 = F, x9 = F, x10 = F, x11 = F, x12 = F, x13 = F, x14 = F, x15 = F, x16 = F, x17 = F, x18 = F, x19 = F, x20 = F, x21 = F, x22 = F, x23 = F, x24 = F · Solver-checked

Always false (contradiction)? No Counterexample: x1 = T, x2 = T, x3 = T, x4 = T, x5 = T, x6 = T, x7 = T, x8 = T, x9 = T, x10 = T, x11 = T, x12 = T, x13 = T, x14 = T, x15 = T, x16 = T, x17 = T, x18 = T, x19 = T, x20 = T, x21 = T, x22 = T, x23 = T, x24 = T · Solver-checked

Can be true? Yes Example assignment: x1 = T, x2 = T, x3 = T, x4 = T, x5 = T, x6 = T, x7 = T, x8 = T, x9 = T, x10 = T, x11 = T, x12 = T, x13 = T, x14 = T, x15 = T, x16 = T, x17 = T, x18 = T, x19 = T, x20 = T, x21 = T, x22 = T, x23 = T, x24 = T · Solver-checked

The common slip

Reading a solver's silence as a result. When a check is not decided within its budget the engine says “Not determined”, which is neither holds nor violated; the pitfall page on timeouts explains why that is not a pass. Only a witness or an exhaustive sweep is evidence.

Questions

Is a solver's answer less trustworthy than a truth table's?

No. A satisfying assignment is checked by evaluating the formula on it, which is the same replay every witness on these pages gets. An unsatisfiable verdict rests on the solver's search being complete, and the engine reports a check it could not finish as undetermined rather than guessing.

Glossary

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.