Boolean function

A Boolean function (also logical function) is a mathematical function of the form (also general ). is a Boolean algebra.

The function identifier, in this case, is chosen for large Boolean functions in general, since the quantities used are preferably indicated by capital letters in a Boolean algebra. Boolean functions can then be used in expressions of Boolean algebra and can be treated as variables. The links of a Boolean algebra as ∧, ∨ or ¬ look like special one - and two-digit Boolean functions, they are not to be confused with the corresponding Boolean functions. It is only shortcuts to an amount about the nothing is further known, while for the definition and ranges of values ​​of a Boolean function already all the axioms of a Boolean algebra can be taken as given.

• 4.1 Example XOR function
• 4.2 Example of a majority function

Distinction by arity

As with the study of other types of functions also, a distinction Boolean functions like after their arity. Due to the restricted to the binary definition and value ranges down ary Boolean functions are relatively easy to handle. So there is absolutely only 4 different unary Boolean functions, which can be described as an identity, negation, constant 1 and constant 0. Here is the negation of particular importance for the Boolean algebra. The number of double-digit Boolean functions is already 16 Among the most important this include conjunction, disjunction, equivalence, non-equivalence, NAND and NOR. There are general - ary Boolean functions. For example, there are several four-digit Boolean functions. The following Boolean functions of different arity are described in more detail.

Zero digit function

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

Unary function

The four possible Boolean functions y = f0 (x ) ... f3 (x ) are connected to a variable:

Two-digit function

For two variables, y = f (X1, X2 ), there is

Different Boolean functions. These functions y = f0 (X1, X2 ), ... F15 (X1, X2 ) are:

More than two variables

For three variables, there are already 28 = 256 Boolean functions in four variables 216 = 65,536, with five variables 232 = 4,294,967,296, with six variables are there 264 = about 18 trillion, so too many to list them all here present.

Graphical illustration

The graphical representation of Boolean functions can be carried out at least for low -digit function by plotting points in a coordinate system. Digit functions can be applied as vertices of a unit square in a Cartesian coordinate system. For two-digit functions, this still manages reasonably clear by the vertices of a unit cube in a three-dimensional coordinate system. n-ary functions can generally be prepared in an n 1- dimensional coordinate system as an n 1- dimensional unit hypercube.

Algebraic representability

However, this representation is too complex from four variables at the latest, to be still vivid. Therefore necessarily an algebraic access is required for higher dimensions. In fact, it is possible to express any Boolean ( for instance by means of a function table arbitrarily fixed ) function purely algebraic. A system of Boolean functions, which enables this, is also referred to as a complete system or combination of operators base. Operators are complete systems as the AND-OR - NOT - system AND exclusive- system, the NAND and NOR system. Note that it is not for these functions to the links of the underlying Boolean algebra, but defined functions.

Boolean basic or basic functions

Each Boolean function with two or more inputs can be combined with the functions AND (conjunction ), realize OR ( disjunction ) and NOT ( negation). In practice, this is handled as well. Therefore, these three Boolean functions are the basic functions.

Basically because of De Morgan 's rule also extend two of these three basic functions (NOT with OR or NOT together with AND ).

Example XOR function

At the XOR combination of the initial state is 1 (true) if the two input states X1 and X2 are different:

In the disjunctive normal form is written:

Example Majority Function

Suppose you have three people, each with a switch on. A lamp l should only light up when the majority, that is, two or all three of the people, their switch press:

Because different and only in one state, you can let the differing part omitted and replaced by. The same applies for and and for and so that at the end the following optimized function remains:

Full Logic Modules

With the basic operations AND, OR and NOT all other links can be displayed. Thus one calls these links as a complete system or link-based. For a circuit design this fact has an advantage: There are only three basic circuits are needed to complete this system (AND, OR, NOT ) can be realized. By a suitable combination of basic operators then all other operators can be formed.

The NAND already provides such a complete system dar. evidence can this situation very simply by simulating a NAND basic operations AND, OR, and NOT. The same also applies to the logical NOR.

Normal forms ( DNF, CNF, RSNF )

Every boolean function may be represented in a normal form. A transfer from a normal shape to another is possible. Normal forms are useful for certain algorithms, circuits, or evidence. Examples of normal forms are:

• Disjunctive normal form ( DNF )
• Conjunctive Normal Form (CNF )
• Ring sum normal form ( RSNF )

Special Boolean functions

• The always true calculated function is called tautology.
• The always wrong calculated function is called contradiction.
• Digit Boolean functions exactly that return the input value, it is called identity.
• Digit Boolean functions, which return exactly the inverse of the input value, called negation.
• Balanced Boolean functions that are invariant under permutations of the input variables, ie the function value is only dependent on the number of ones in the case, but not on their position.

Boolean functions in combination

It is more complex structures obtained when integrating several Boolean functions. Thus, for example, a half adder, when the same inputs x and y for the AND and XOR function used at the output of the AND - function of the carry - state C, and the output of the XOR function of the sums of state s to get.

Half-adder circuit symbol

• Mathematical Logic