# 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,
- 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

- .

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

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

### Complexity classes

Some major complexity classes can be defined using Boolean circuits.

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

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