View source for Boolean circuit

A '''Boolean circuit''' is a mathematical model of [[computation]] used in studying [[computational complexity theory]]. Boolean circuits are the main object of study in [[circuit complexity]] and are a special kind of [[circuit (computer theory)|circuit]]s; a [[formal language]] can be decided by a family of Boolean circuits, one circuit for each possible input length. In addition, they are used as a formal model for [[combinational logic]] in [[digital electronics]].

Boolean circuits are defined in terms of the [[logic gate|gates]] they contain. For example, a circuit might contain [[binary function|binary]] AND and OR gates and [[unary]] NOT gates, or be entirely described by binary [[NAND gate]]s. Each gate corresponds to some [[Boolean function]] that takes ''k'' bits as input and outputs a single bit.

Several important complexity measures can be defined on Boolean circuits, including circuit depth, circuit size, and number of alternations. In a circuit family, we consider the size complexity of a family, for example, to be the function of n that gives the size of the circuit that decides inputs of length n.

Several important complexity classes are defined in terms of Boolean circuits, including [[NC (complexity)|NC]]. NC is defined to be the set of [[Boolean function]]s that can be decided by uniform Boolean circuits of polynomial size and polylogarithmic depth. Here, the word ''uniform'' means that there must be some condition on the circuit family so that a description of a circuit can be computed from its index, n.

==Formal definition==
In giving a formal definition of Boolean circuits, [[Heribert Vollmer|Vollmer]] starts by defining a basis set ''B'' of Boolean functions, corresponding to the gates allowable in the circuit model. A Boolean circuit over a basis ''B'', with ''n'' inputs and ''m'' outputs, is then defined as a finite [[directed acyclic graph]]. Each vertex corresponds to either a basis function or one of the inputs, and there are a set of exactly ''m'' nodes which are labeled as the outputs.<ref>Vollmer 1999, p. 8.</ref> The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.<ref>Vollmer 1999, p. 9.</ref>

== Evaluation of a circuit ==
The problem ''CIRCUIT-EVAL'' takes as input the description of a Boolean circuit and a truth assignment to the variables of the circuit, and accepts only if the circuit evaluate to true. ''CIRCUIT-EVAL'' is [[P-complete]].<ref>S. Arora, B. Barak, ''Computational complexity, a modern approach'', page 119</ref>

== Footnotes ==
{{reflist}}

==References==
{{refbegin}}
*{{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | isbn = 3-540-64310-9}}
{{refend}}

{{DEFAULTSORT:Boolean Circuit}}
[[Category:Computational complexity theory]]
[[Category:Digital circuits]]
[[Category:Logic in computer science]]


{{comp-sci-theory-stub}}

[[cs:Kombinační obvod]]
[[zh:组合逻辑电路]]
[[Category:2Fix]]