Exact synthesis of small Boolean functions in three bases: an annotated atlas for n ≤ 5

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 (doi:10.5281/zenodo.23913155), 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.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-03
DOI
https://doi.org/10.5281/zenodo.23913363
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Exact synthesis of small Boolean functions in three bases: an annotated atlas for n ≤ 5

Luiz Antonio Busnello
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Exact synthesis of small Boolean functions in three bases: an annotated atlas for n ≤ 5

Luiz Antonio Busnello
preprint en

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 (doi:10.5281/zenodo.23913155), 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.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon