Exact synthesis of small Boolean functions in three bases: an annotated atlas for n ≤ 5
Abstract
A map of a corpus that is mostly published; where a fact is not in a public deposit, §7 says so. It contains no new result. For each fact it says where the fact is, what certifies it, and what remains open. The cross-base laws belong to the companion paper Base laws for the formula–circuit gap at four inputs: AIG, MIG and XAG compared class by class, so this document stays an atlas: when it needs a law, it points to that paper.
Scope: Boolean functions of n ≤ 5 variables, exact synthesis (proved minimum size, not a heuristic bound), in three bases. Out of scope: depth, unbounded fan-in, asymptotic families, multi-output functions, and anything without a checkable artifact.
- Boolean circuit complexity
- exact synthesis
- formula size
- and-inverter graph
- majority-inverter graph
- XOR-AND graph
- SAT solving
- DRAT proofs
The DOI above always resolves to the latest version on Zenodo; this page hosts v1.0. Licensed CC BY 4.0.