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