Boolean circuit

from Wikipedia, the free encyclopedia

In theoretical computer science (especially in complexity theory ) a Boolean circuit is a mathematical model for digital circuits.

Formal definitions


Gates are the components that make up Boolean circuits. These receive Boolean inputs and combine them into a Boolean value as output. There are different types of tags that combine inputs differently. A tag type is a Boolean function that maps a k-tuple of Boolean values ​​to a Boolean value.

Examples of gate types:

  • The family of AND gates: For any arity k there is a gate that outputs 1 if and only if all inputs are 1. For we also note the gates with , that is,
  • The family of OR gates: For any arity k there is a gate that outputs 1 if and only if at least one input is 1. For we also note the gates with , that is,
  • The negation gate : It has exactly one input and outputs 1 if and only if the input is 0.

Boolean circuit

An -Input- -Output Boolean circuit over a base of gate types is a directed acyclic graph . The nodes of the graph are also known as gates.

  • There are nodes that have inputs that have no incoming edges.
  • The remaining nodes are called internal nodes.
  • A gate type is assigned to each internal node, the arity of which corresponds to the in-degree of the node (if necessary, the order of the incoming edges is also determined).
  • There are also nodes that are marked as output nodes.

A common choice for the base is (sometimes referred to as the standard base), since all Boolean functions can be formed with these gate types.

Function of the circuit

For an input , each node of the circuit is assigned a logical value as follows :

  • Each input node gets the value , ie .
  • Internal nodes are evaluated in such a way that all predecessors are evaluated first, before the node itself is evaluated and these values ​​are then combined according to the tag type.
For an internal node with direct ancestors and gate type , one calculates as

The Boolean function of a Boolean circuit is then



  • The subcircuit of an internal node consists of all gates that are ancestors of , that is, of which there is a directed path to .
  • The degree of a base is the maximum arity of its elements.
  • Monotonic circuit : A Boolean circuit in which the function is monotonic in the sense that whenever for , also for . It is often used to describe Boolean circuits that only consist of AND and OR gates.


Boolean circuits are in the complexity theory is important, especially in the branch of circuit complexity ( English Circuit complexity ).

Complexity measures for circuits

There are different measures for the complexity of a circuit:

  • Circuit size ( English circuit size ): The number of the internal nodes of the circuit.
  • Circuit depth ( English circuit depth ): the maximum length of a path from an input gate to an output gate.
  • Number of alternations of AND and OR gates ( English number of old nations ).
  • Ingrad / Ausgrad of the circuit: The maximum number of incoming / outgoing edges of a node of the circuit. The degree of in is limited by the base .

Complexity classes

Some major complexity classes can be defined using Boolean circuits.

  • The class NC and the associated hierarchy
  • The class AC and the associated hierarchy

Circuit evaluation problem

When evaluating a boolean circuit ( English Circuit Value Problem ) is calculated for a given input string to all input gates assigns a truth value, the values of the output gate. The problem of deciding whether an output gate of a circuit is true for a given input is P -complete.

Satisfiability problem for circuits

The satisfiability for circuits ( English circuit satisfiability problem ) is considered a Boolean circuit with base and a single output gate and asks whether there is an input that sets this gate to 1, ie, whether it's a are such that . The satisfiability problem for circuits is NP-complete .


  • K. Rüdiger Reischuk: Introduction to Complexity Theory: Volume 1: Basics of machine models , time and space complexity, nondeterminism . Teubner Verlag, 1999, ISBN 978-3-519-12275-3 , 2.2 Circuit families.
  • Christos H. Papadimitriou : Computational Complexity . Addison-Wesley, Reading / Mass, 1995, ISBN 978-0-201-53082-7 , 4.3 Boolean functions and circuits & 8 Reductions and completeness (English).