Boolean function

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

A Boolean function (also a logical function ) is a mathematical function of the form (sometimes also more general ). is a Boolean algebra . ${\displaystyle F\colon B^{n}\to B^{1}}$ ${\displaystyle F\colon B^{n}\to B^{m}}$ ${\displaystyle B}$

The function identifier, here , is generally chosen to be large for Boolean functions, since in a Boolean algebra the quantities used are preferably designated with capital letters. Boolean functions can then be used in expressions of Boolean algebra and can be treated like variables. The links of a Boolean algebra such as ∧, ∨ or ¬ look like special one- and two-digit Boolean functions, but they should not be confused with the corresponding Boolean functions. It is only a matter of links on a set about which nothing further is known, while all axioms of a Boolean algebra can be assumed as given for the domains of definition and values ​​of a Boolean function. ${\displaystyle F}$

Differentiation according to arity

As with the investigation of other types of functions, one likes to differentiate Boolean functions according to their arity . Due to the definition and value ranges that are restricted to the binary numbers , low-digit Boolean functions are relatively easy to use. So there are only 4 different single-digit Boolean functions that can be called identity , negation , constant 1 and constant 0 . For Boolean algebra, the negation is particularly important here. The number of two-digit Boolean functions is already 16. The most important are conjunction , disjunction , equivalence , antivalence , NAND and NOR . There are general -digit Boolean functions. For example, there are several four-digit Boolean functions. Boolean functions of various arithmetic are described in more detail below. ${\displaystyle 2^{2^{n}}}$ ${\displaystyle n}$ ${\displaystyle 2^{2^{4}}=2^{16}=65536}$

Zero-digit function

${\displaystyle n=0}$

2 ^{2 0} = 2 ¹ = 2

These are the two constants 1 and 0, also called true and false , verum and falsum , true and false .

One-digit function

${\displaystyle n=1}$

2 ^{2 1} = 2 ² = 4

The four possible Boolean functions with one variable are: ${\displaystyle y=f_{0}(x),\ldots ,f_{3}(x)}$

x	0	1	Function ( y =)	Surname
f 0	0	0	0	Contradiction
f 1	0	1	x	identity
f 2	1	0	¬ x = x = 1 - x	negation
f 3	1	1	1	tautology

Two-digit function

${\displaystyle n=2}$
For two variables there are ${\displaystyle y=f(x_{1},x_{2})}$

2 ^{2 2} = 2 ⁴ = 16

various Boolean functions. These functions are: ${\displaystyle y=f_{0}(x_{1},x_{2}),\ldots ,f_{15}(x_{1},x_{2})}$

Two-digit Boolean functions

x 1 , x 2	0, 0	0, 1	1, 0	1, 1	function			Surname
f 0	0	0	0	0	x 1 · x 1	0	x 1 ∧ ¬ x 1	Contradiction , null function
f 1	0	0	0	1	x 1 · x 2	⌊ x 1 , x 2 ⌋	x 1 ∧ x 2	Conjunction , AND ( x 1 , x 2 )
f 2	0	0	1	0	x 1 · x 2	x 1 > x 2	x 1 ↛ x 2	Inhibition of x 1
f 3	0	0	1	1	x 1	x 1	x 1	Identity of x 1
f 4	0	1	0	0	x 1 · x 2	x 1 < x 2	x 1 ↚ x 2	Inhibition of x 2
f 5	0	1	0	1	x 2	x 2	x 2	Identity of x 2
f 6	0	1	1	0	( X 1 · x 2 ) + ( x 1 · x 2 )	x 1 ≠ x 2	x 1 ↮ x 2	Non-equivalence , alternative , XOR ( x 1 , x 2 )
f 7	0	1	1	1	x 1 + x 2	⌈ x 1 , x 2 ⌉	x 1 ∨ x 2	Disjunction , OR ( x 1 , x 2 )
f 8	1	0	0	0	x 1 + x 2 = x 1 · x 2	1 - ⌈ x 1 , x 2 ⌉	x 1 ↓ x 2	Nihilition , Peirce function , NOR ( x 1 , x 2 )
f 9	1	0	0	1	( X 1 · x 2 ) + ( x 1 · x 2 )	x 1 = x 2	x 1 ↔ x 2	Equivalence , XNOR ( x 1 , x 2 )
f 10	1	0	1	0	x 2	1 - x 2	¬ x 2	Negation of x 2 , NOT ( x 2 )
f 11	1	0	1	1	x 1 + x 2	x 1 ≥ x 2	x 1 ← x 2	Replication
f 12	1	1	0	0	x 1	1 - x 1	¬ x 1	Negation of x 1 , NOT ( x 1 )
f 13	1	1	0	1	x 1 + x 2	x 1 ≤ x 2	x 1 → x 2	implication
f 14	1	1	1	0	x 1 · x 2 = x 1 + x 2	1 - ⌊ x 1 , x 2 ⌋	x 1 ↑ x 2	Exclusion , Sheffer function , NAND ( x 1 , x 2 )
f 15	1	1	1	1	x 1 + x 1	1	x 1 ∨ ¬ x 1	Tautology , one function

More than two variables

With three variables there are already 2 ⁸ = 256 Boolean functions, with four variables 2 ¹⁶ = 65,536, with five variables 2 ³² = 4,294,967,296, with six variables there are 2 ⁶⁴ = over 18 trillion, too many to include here depict all.

Graphic illustration

The graphical illustration of Boolean functions can take place at least for functions with a low order by plotting points in a coordinate system. One- digit functions can be plotted in a Cartesian coordinate system as the corner points of a unit square . For two-digit functions, this is still possible to some extent clearly using the corner points of a unit cube in a three-dimensional coordinate system. n-ary functions can generally be represented in an n + 1-dimensional coordinate system as an n + 1-dimensional unit hypercube.

Algebraic representability

However, from four variables at the latest, this representation becomes too complex to be clear. Therefore an algebraic approach is absolutely necessary for higher dimensions. In fact, it is possible to express any Boolean function (for example, arbitrarily defined by means of a function table) purely algebraically. A system of Boolean functions that makes this possible is also known as a complete operator system or link base . Complete operator systems are, for example, the AND-OR-NOT system, the AND non- equivalence system, the NAND and the NOR system. Note that these functions are not the links of the underlying Boolean algebra, but rather defined functions.

Boolean basic or basic functions

Every Boolean function with two or more inputs can be implemented with the functions AND (conjunction), OR (disjunction) and NOT (negation). This is also done in practice. Because of De Morgan's rule , two of these three basic functions are generally sufficient ( NOT together with OR or NOT together with AND ). Alternatively, all Boolean functions can also be implemented using NAND (the same applies to NOR ) or using ( AND , XOR and T ).

Example of an XOR function

With the XOR link , the output state is 1 (true) if the two input states x ₁ and x _{2 are} different:

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle y}$
0	0	0
0	1	1
1	0	1
1	1	0

Written in the disjunctive normal form :

${\displaystyle y={\bar {x_{1}}}x_{2}\vee x_{1}{\bar {x_{2}}}}$

Example majority function

Suppose you have three people, each with a switch in front of them. A lamp l should only light up when the majority, i.e. two of the people or all three, press their switch:

${\displaystyle l={\bar {s_{1}}}s_{2}s_{3}\vee s_{1}{\bar {s_{2}}}s_{3}\vee s_{1}s_{2}{\bar {s_{3}}}\vee s_{1}s_{2}s_{3}}$

Because and differ only in one state, one can let the distinguishing part eliminated and receives . ${\displaystyle {\bar {s_{1}}}s_{2}s_{3}}$ ${\displaystyle s_{1}s_{2}s_{3}}$ ${\displaystyle s_{2}s_{3}}$

The same applies to and , as well as to and , so that in the end the following optimized function remains: ${\displaystyle s_{1}{\bar {s_{2}}}s_{3}}$ ${\displaystyle s_{1}s_{2}s_{3}}$ ${\displaystyle s_{1}s_{2}{\bar {s_{3}}}}$ ${\displaystyle s_{1}s_{2}s_{3}}$

${\displaystyle l=s_{2}s_{3}\vee s_{1}s_{3}\vee s_{1}s_{2}}$

Complete logic systems

For a complete system or the link base , either the basic links AND or OR are required. You also need the NOT. This fact has an advantage for a circuit design: only two basic circuits are required to implement this complete system ((AND or OR) and NOT). All other operators can then be formed by combining the basic operators accordingly.

The NAND link or NOR link already represents such a complete system.

Normal forms (DNF, KNF, RSNF)

Every Boolean function can be represented in a normal form . A transfer from one normal form to another is possible. Normal forms are useful for certain algorithms, circuits, or proofs. Examples of normal forms are:

• Disjunctive Normal Form (DNF)
• Normal conjunctive form (CNF)
• Round sum normal form (RSNF)

Special Boolean functions

• The function that always calculates true is called tautology .
• The function that always calculates incorrectly is called contradiction .
• One-digit Boolean functions that always return exactly the input value are called identity .
• One- digit Boolean functions that always return exactly the inverse of the input value are called negation .
• A Boolean function is called symmetric if the function value only depends on the number of ones in the argument but not on their position, i.e. it is invariant to permutations of the input variables.

Boolean functions in combination

You can get more complex structures by combining several Boolean functions. For example, a half adder is obtained if the same inputs x and y are used for the AND and the XOR function, in order to obtain the carry state c at the output of the AND function  and the sum state at the output of the XOR function  s to get.

• 

  Half adder circuit

• 

  Half adder circuit symbol