Boolean circuit¶

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8244
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Circuit Complexity, Computational Complexity → Computer Science & Software Engineering

Core Idea¶

Boolean circuit is treated here as the recurring circuit complexity identity summarized by this source-grounded definition: In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length. Boolean circuits are defined in terms of the logic gates they contain.

How would you explain it like I'm…

Yes-No Machine Chain

A Boolean circuit is like a set of little yes-no machines hooked together. Each machine takes a few yes-or-no signals in and gives one yes-or-no out, like 'say yes only if both inputs say yes.' Signals flow from start to finish, and the circuit has no memory — the same inputs always give the same answer.

Logic Gate Network

A Boolean circuit is a pattern of logic gates wired together, where each gate takes a fixed number of bits (0s and 1s) and outputs one bit. Common gates are AND, OR and NOT, but you can even build everything out of NAND gates. The bits go in one end and the answer comes out the other, and the circuit does not store anything between uses. Real computer parts like adders are modeled this way. Because one circuit handles a fixed number of input bits, to solve a problem for every size of input you need a whole family of circuits, one for each length.

Combinational Logic Circuit

A Boolean circuit is a mathematical model of combinational digital logic: a network of gates, each computing a fixed Boolean function of a fixed number of input bits and producing one output bit. The gate set is part of the definition — for example AND, OR and NOT, or NAND alone. Because a single circuit has a fixed number of inputs, complexity theory decides a language with a family of circuits, one per input length. Boolean circuits model components such as multiplexers, adders and arithmetic logic units. They exclude sequential logic: there are no feedback loops or memory elements, so the output depends only on the current inputs.

In computational and circuit complexity, a Boolean circuit is a mathematical model of combinational logic: a directed acyclic graph whose input nodes carry bits and whose internal nodes are gates, each computing a Boolean function of a fixed number of input bits and producing a single output bit. Circuits are specified by the gates they contain, for example binary AND and OR with unary NOT, or binary NAND alone. Because the graph is acyclic, there is no state; sequential logic is outside the model. A single circuit has a fixed number of inputs, so a formal language is decided by a family of circuits, one per input length, with the n-th circuit accepting exactly the length-n strings in the language. This per-length structure underlies circuit-complexity measures such as size and depth. The model also describes concrete digital components like multiplexers, adders, and ALUs.

Scope of Application¶

Formal definition. In giving a formal definition of Boolean circuits, Vollmer starts by defining a basis as set B of Boolean functions, corresponding to the gates allowable in the circuit model.
Formal definition. Each vertex corresponds to either a basis function or one of the inputs, and there is a set of exactly m nodes which are labeled as the outputs.
Formal definition. The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.
Formal definition. Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs.
Formal definition. A common basis for Boolean circuits is the set {AND, OR, NOT}, which is functionally complete, i.e. from which all other Boolean functions can be constructed.

Clarity¶

A clear use of Boolean circuit names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits.

Manages Complexity¶

Boolean circuit compresses multiple circuit complexity details into a stable diagnostic relation. The source shows both the central mechanism—in giving a formal definition of Boolean circuits, Vollmer starts by defining a basis as set B of Boolean functions, corresponding to the gates allowable in the circuit model.—and the practical consequence—p/poly also has the interesting feature that it can be equivalently defined as the class of languages.

Abstract Reasoning¶

Type the carrier. Identify the circuit complexity entities to which the claim applies.
State the relation. Use the source-grounded identity: In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits.
Check operation and conditions. Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs.
Demand recognition evidence.

Knowledge Transfer¶

Within the home domain. Knowledge about Boolean circuit transfers literally when a new case preserves the same carrier type, relation, and recognition test. In giving a formal definition of Boolean circuits, Vollmer starts by defining a basis as set B of Boolean functions, corresponding to the gates allowable in the circuit model. Each vertex corresponds to either a basis function or one of the inputs, and there is a set of exactly m nodes which are labeled as the outputs. Beyond the home domain. No canonical parent is asserted for Boolean circuit.

Relationships to Other Abstractions¶

Current abstraction Boolean circuit Domain-specific

Parents (1) — more general patterns this builds on

Boolean circuit is a kind of Logic Circuit Domain-specific

Boolean circuit satisfies the defining boundary of Logic Circuit: A logic circuit is an interconnected arrangement of logical elements that maps encoded input states and internal state, if any, to output states according to a specified Boolean or multivalued function under timing, electrical, and implementation constraints.

Hierarchy path (1) — routes to 1 parentless root

Boolean circuit → Logic Circuit → System → Composition → Gestalt Principles → Holism

Neighborhood in Abstraction Space¶

Boolean circuit sits in a moderately populated region (48^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Computation Models & Complexity Classes (37 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08