# Boolean circuit

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

## Formal definitions

### gate

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,${\ displaystyle \ wedge _ {k}}$${\ displaystyle k = 2}$${\ displaystyle \ wedge}$${\ displaystyle \ wedge = \ wedge _ {2}}$
• 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,${\ displaystyle \ vee _ {k}}$${\ displaystyle k = 2}$${\ displaystyle \ vee}$${\ displaystyle \ vee = \ vee _ {2}}$
• The negation gate : It has exactly one input and outputs 1 if and only if the input is 0.${\ displaystyle \ neg}$

### 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. ${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle \ Upsilon}$ ${\ displaystyle G = (V, E)}$

• There are nodes that have inputs that have no incoming edges.${\ displaystyle n}$${\ displaystyle i_ {1}, i_ {2}, \ dots, i_ {n} \ in V}$
• 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).${\ displaystyle \ upsilon \ in \ Upsilon}$
• There are also nodes that are marked as output nodes.${\ displaystyle m}$${\ displaystyle o_ {1}, o_ {2}, \ dots, o_ {m}}$

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. ${\ displaystyle \ Upsilon}$${\ displaystyle \ Upsilon = \ {\ wedge, \ vee, \ neg \}}$

### Function of the circuit

For an input , each node of the circuit is assigned a logical value as follows : ${\ displaystyle X = (x_ {1}, x_ {2}, \ dots, x_ {n})}$${\ displaystyle v \ in V}$${\ displaystyle C}$${\ displaystyle g_ {v} (X) \ in \ {0,1 \}}$

• Each input node gets the value , ie .${\ displaystyle i_ {j}}$${\ displaystyle x_ {j}}$${\ displaystyle g_ {i_ {j}} (X) = x_ {j}}$
• 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${\ displaystyle v \ in V}$${\ displaystyle k}$${\ displaystyle u_ {1}, \ dots u_ {k}}$${\ displaystyle \ upsilon \ in \ Upsilon}$${\ displaystyle g_ {v} (X)}$
${\ displaystyle g_ {v} (X) = \ upsilon (g_ {u_ {1}} (X), \ dots, g_ {u_ {k}} (X)}$

The Boolean function of a Boolean circuit is then ${\ displaystyle f_ {C} (X)}$${\ displaystyle C}$

${\ displaystyle f_ {C} (X) = (g_ {o_ {1}} (X), \ dots, g_ {o_ {m}} (X))}$.

### Terms

• The subcircuit of an internal node consists of all gates that are ancestors of , that is, of which there is a directed path to .${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle v}$
• The degree of a base is the maximum arity of its elements.${\ displaystyle \ Upsilon}$
• 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.${\ displaystyle C}$${\ displaystyle f_ {C} (\ cdot)}$${\ displaystyle X = (x_ {1}, \ dots, x_ {n}), Y = (y_ {1}, \ dots, y_ {n}), x_ {j} \ leq y_ {j}}$${\ displaystyle 1 \ leq j \ leq n}$${\ displaystyle f_ {C} (X) _ {j} \ leq f_ {C} (Y) _ {j}}$${\ displaystyle 1 \ leq j \ leq m}$

## complexity

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 .${\ displaystyle \ Upsilon}$

### Complexity classes

Some major complexity classes can be defined using Boolean circuits.

• The class NC and the associated hierarchy${\ displaystyle {\ mbox {NC}} ^ {i}}$
• The class AC and the associated hierarchy${\ displaystyle {\ mbox {AC}} ^ {i}}$

### 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 . ${\ displaystyle C}$${\ displaystyle \ Upsilon = \ {\ wedge, \ vee, \ neg \}}$${\ displaystyle X}$${\ displaystyle f_ {C} (X) = 1}$

## literature

• 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).