A Boolean circuit is a finite directed acyclic graph of Boolean gates with designated inputs and outputs.
The size of a Boolean circuit counts its gates, or in another common convention its wires. The convention must be fixed when stating quantitative bounds. In switching arguments, new clauses created from a decision tree are not separate original gates to be charged in the failure union bound.
Circuit depth is the largest number of counted gates on any input-to-output path in the Boolean circuit. For an AND/OR circuit with negations on input literals, only the AND/OR gates are counted. This convention makes the restriction argument for the Linial-Mansour-Nisan theorem precise.
Given a finite acyclic Boolean circuit and its input assignment, determine the output bit. Topological gate evaluation places the problem in P; it is a standard P-complete problem under logspace many-one reductions. Boolean circuit evaluation is different from Circuit satisfiability problem, which asks whether some assignment succeeds.
The circuit value problem restricted to AND and NOT gates remains P-complete. Replace each OR by , using a constant-size gadget. Gate indices and gadget positions can be emitted in logarithmic space, and assignments are preserved. Constants, when needed, can be represented by fixed-valued input nodes.
The circuit satisfiability problem asks whether a Boolean circuit has an input on which its designated output is one. It is NP-complete.
A threshold Boolean function outputs one exactly when a weighted sum of its input bits reaches a specified threshold. The unweighted threshold function tests whether at least of its inputs are one.
A majority Boolean function outputs one when more than half its input bits are one. An odd number of inputs avoids a tie convention. For three bits its unique multilinear polynomial is , so the polynomial method for quantum query lower bounds requires at least two exact queries.
Its disjoint triples give a product of degree-three multilinear polynomials, with all-variable coefficient . Hence its degree is and its exact quantum query complexity is at least . At the input consisting of repeated triples, each of the one bits is a disjoint sensitive singleton. Thus block sensitivity is at least , implying a bounded-error quantum query complexity lower bound .
The dual of a Boolean function is . Swapping AND with OR and zero with one in a monotone circuit for produces a circuit for by De Morgan's laws.
Articles by others on the same topic
A **Boolean circuit** is a mathematical model used in computer science and electrical engineering to represent Boolean functions via a network of interconnected logical gates. Boolean circuits are foundational in the fields of digital logic design, computation theory, and complexity theory. ### Components of a Boolean Circuit: 1. **Variables**: These represent the inputs to the circuit, which can take on values of either true (1) or false (0).