Boolean function

function of the algebra of logic

A function whose arguments, as well as the function itself, assume values from a two-element set (usually $\{0,1\}$). Boolean functions are one of the main subjects of discrete mathematics, in particular, of mathematical logic and mathematical cybernetics. Boolean functions first occurred in the mathematical formulation of logical problems, and were named after G. Boole, who laid the foundation for the applications of mathematics in logic in the middle of the 19th century; cf. Algebra of logic.

One such problem is the construction of an algebra of propositions. To this purpose, one of the two values 0 ("false") or 1 ("true") is assigned to each proposition; the principal logical relations "and", "or", "not", "if … then", etc., can then be regarded as the respective "elementary" Boolean functions: $x\land y$, $x\lor y$, $Cx$, $x\to y$, etc. When this is done, the value of any complex proposition, constructed with the aid of the fundamental logical connectives from given propositions, is a Boolean function of the values of these propositions. Such a Boolean function is a composition of elementary Boolean functions corresponding to the logical connectives forming part of the complex proposition. It became clear later that the language of Boolean functions is suited for a description of the operation of discrete control systems (cf. Control system) such as contact schemes, diagrams of functional elements, logical networks, switching networks, etc. These control systems are constructed in accordance with certain rules from a number of initial elements, just as complex statements are constructed from simple ones. The rules governing the construction of such control systems as well as the operation of the initial elements are such that the operation of complex control systems can be described with the aid of Boolean functions. Boolean functions are also used in certain problems of integer programming that reduce to solving a system of Boolean equations of the form

$$f_1(x_1,\dotsc,x_n)=\dotsb=f_m(x_1,\dotsc,x_n)=0,$$

where the $f_i,i=1,\dotsc,m$, are Boolean functions. There are also other ways of using Boolean functions in discrete mathematics, so that the study of Boolean functions is of interest in its own right.

An essential feature in solving problems related to Boolean functions is the method of specifying Boolean functions. There are several such methods: tables, formulas, special classes of formulas known as normal forms (cf. Boolean functions, normal forms of), subsets of the vertices of an $n$-dimensional unit cube, etc. In the last-named case every selection of length $n$ of values of the arguments (0 or 1) is regarded as a vertex of the $n$-dimensional unit cube, in which case a Boolean function of $n$ arguments can be defined by the subset of the corners at which it assumes the value "1". This subset, when written out as a matrix whose rows are selections of values of the arguments of the Boolean function, is known as a Boolean matrix. If a Boolean function describes the operation of control systems, the latter can also be regarded as a method of specifying the Boolean function. One usually says that this control system realizes the given Boolean function. The realization of Boolean functions by many kinds of control systems is closely related to a large number of problems, such as synthesis, minimization, control and reliability problems, etc. Another type of problem arises in the study of properties and classes of Boolean functions specified by different methods; this is the study of the metric characterizations of various classes of normal forms of Boolean functions and the related geometrical properties of the $n$-dimensional unit cube (cf. Boolean functions, metric theory of), as well as of the various algebras of Boolean functions (cf. Many-valued logic; Equivalent transformations). The system of all classes of Boolean functions that are closed under composition was described by E. Post. It forms a countably-infinite lattice with five maximal (pre-complete) classes.

In certain cases it may be necessary to consider partial (i.e. not everywhere-defined) Boolean functions for which the problems listed have a specific character.

References

[1]	P.S. Novikov, "Elements of mathematical logic" , Oliver & Boyd and Acad. Press (1964) (Translated from Russian) MR0164868 Zbl 0113.00301
[2]	S.V. Yablonskii, G.P. Gavrilov, V.B. Kudryavtsev, "Functions of the algebra of logic and Post classes" , Moscow (1964) (In Russian)

Comments

Cf. [a2] for uses of Boolean functions and equations in switching theory and logical networks. Applications of Boolean functions and equations in operations research are discussed in [a1].

References

[a1]	P.L. Hammer, S. Rudeanu, "Boolean methods in operations research" , Springer (1968) MR0235830 Zbl 0155.28001
[a2]	S. Rudeanu, "Boolean functions and equations" , North-Holland (1974) MR0484821 Zbl 0321.06013