Boolean circuit
Boolean circuits are defined in terms of the logic gates they contain.
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.
They are an abstraction that omits many aspects relevant to designing real digital logic circuits, such as metastability, fanout, glitches, power consumption, and propagation delay variability.
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.
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 is a set of exactly m nodes which are labeled as the outputs.
[1]: 8 The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.
[1]: 9 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.
Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs.
A particular circuit acts only on inputs of fixed size.
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).
In other words, a language is the set of strings which, when applied to the circuits corresponding to their lengths, evaluate to 1.
[2]: 355 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).
Several important complexity classes are defined in terms of Boolean circuits.
The most general of these is P/poly, the set of languages that are decidable by polynomial-size circuit families.
P/poly turns out to have a number of properties that make it highly useful in the study of the relationships between complexity classes.
In particular, it is helpful in investigating problems related to P versus NP.
A full description of the relations between P/poly and other complexity classes is available at "Importance of P/poly".
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.
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.
Logic circuits are physical representation of simple logic operations, AND, OR and NOT (and their combinations, such as non-sequential flip-flops or circuit networks), that form a mathematical structure known as Boolean algebra.
In the physical world we also encounter randomness, notable in small systems governed by quantization effects, which is described by theory of Quantum Mechanics.
Remedy to that is found in adding an ad-hoc random bit generator to logic networks, or computers, such as in Probabilistic Turing machine.
A recent work[4] has introduced a theoretical concept of an inherently random logic circuit named random flip-flop, which completes the set.
It conveniently packs randomness and is inter-operable with deterministic Boolean logic circuits.
