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.

For example, a circuit might contain binary AND and OR gates and unary NOT gates, or be entirely described by binary NAND gates. Each gate corresponds to some Boolean function that takes a fixed number of bits as input and outputs a single bit. Boolean circuits provide a model for many digital components used in computer engineering, including multiplexers, adders, and arithmetic logic units, but they exclude sequential logic.

For Boolean circuit, the abstraction is narrower than the article's general subject matter: a positive case must preserve In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in circuit complexity, which is why this identity is domain-specific rather than prime.

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.

Structural Signature¶

Sig role-phrases:

Defining carrier — In other words, any problem that can be computed in polynomial time by a deterministic Turing machine can also be computed by a polynomial-size circuit family.
Constitutive relation — 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.
Operating condition — Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs.
Recognition evidence — Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations).
Admissible variation — The most general of these is P/poly, the set of languages that are decidable by polynomial-size circuit families.
Characteristic consequence — P/poly also has the interesting feature that it can be equivalently defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function.
Failure boundary — The class NC is the set of languages that can be solved by circuit families that are restricted not only to having polynomial-size but also to having polylogarithmic depth.

What It Is Not¶

Not the whole field of circuit complexity. The node requires the specific identity stated by In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits.
Not an over-broad reading. The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.
Not an over-broad reading. However, formal languages (the string-based representations of decision problems) contain strings of different lengths, so languages cannot be fully captured by a single circuit (in contrast to the Turing machine model, in which a language is fully described by a single Turing machine).
Not an over-broad reading. However, it just happens that this is not all there is.
Not automatically Logic gate. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Boolean circuit applies literally inside circuit complexity wherever the source-defined carrier and relation can be established. Its documented habitats include:

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.
Complexity measures. Formally, it can be shown that if a language is in \mathsf{TIME}(t(n)) , where t is a function t:\mathbb{N} \to \mathbb{N} , then it has circuit size complexity O(t^2(n)) .

Outside circuit complexity, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Theory or should be marked as analogy.

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. The strongest recognition evidence in the frozen account is: Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations). A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification The edges must also have some ordering, to distinguish between different arguments to the same Boolean function. so that a reader can reproduce the classification rather than infer it from topical resemblance.

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 recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

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. Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations).
Test variation. Change an implementation or setting while preserving the most general of these is P/poly, the set of languages that are decidable by polynomial-size circuit families.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Theory.

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. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Examples¶

Canonical¶

As a special case, a propositional formula or Boolean expression is a Boolean circuit with a single output node in which every other node has fan-out of 1. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits; recognition evidence → Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations)

Applied / In Practice¶

Several important complexity measures can be defined on Boolean circuits, including circuit depth, circuit size, and the number of alternations between AND gates and OR gates. The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → Complexity measures; invariant → In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits; boundary → the case exits the class when the edges must also have some ordering, to distinguish between different arguments to the same Boolean function

Structural Tensions¶

T1 — Stable identity versus admissible variation. The edges must also have some ordering, to distinguish between different arguments to the same Boolean function. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. However, formal languages (the string-based representations of decision problems) contain strings of different lengths, so languages cannot be fully captured by a single circuit (in contrast to the Turing machine model, in which a language is fully described by a single Turing machine). The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. However, it just happens that this is not all there is. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. For example, if there is any language in NP that is not in P/poly then P \neq NP. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. In other words, any problem that can be computed in polynomial time by a deterministic Turing machine can also be computed by a polynomial-size circuit family. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Boolean circuit literally, co-instantiate Theory, or only resemble it?

T6 — Autonomy versus reduction. 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. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Boolean circuit distinguish that the broader parent Theory leaves together?

Structural–Framed Character¶

Boolean circuit is mixed or framed-leaning. Its structural side is the repeatable organization summarized by In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. Its framed side is the circuit complexity vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Theory. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. The stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: In other words, any problem that can be computed in polynomial time by a deterministic Turing machine can also be computed by a polynomial-size circuit family. 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. It further constrains recognition and variation through: Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs. Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations).

What is domain-bound. circuit complexity supplies the operative entities, technical vocabulary, warrants, and exceptions that make Boolean circuit literal. Its documented scope includes the condition that 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. Another bounded application condition is that 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. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—The most general of these is P/poly, the set of languages that are decidable by polynomial-size circuit families.—and future graph densification may discover a defensible relation only if it preserves that boundary.

This entry is a kind of Logic Circuit.

Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for Boolean circuit. The reviewed identity is: In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

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

Not to Be Confused With¶

Theory. The parent omits the specialist differentia. Tell: Can the case establish In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits?
Logic gate. A functional element that maps one or more logical input values to an output value according to a Boolean operation. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Boolean network. A discrete dynamical system of Boolean variables whose values update according to assigned Boolean functions of other network nodes. Tell: Which entry's carrier, operation, and failure condition are satisfied?
XOR gate. A digital logic gate that outputs true exactly when an odd number of its binary inputs are true, implementing exclusive disjunction and two-input inequality. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Boolean circuit remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside circuit complexity lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Theory?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Boolean_circuit (revision 1319842041).

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.