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

→ Main article : 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

→ Main article : 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).