A function whose arguments, as well as the
function itself, assume values from a two-element set (usually
).
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:
,
,
,
,
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
 |
where the
,
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
-dimensional
unit cube, etc. In the last-named case every selection of length
of values of the arguments (0 or 1) is regarded as a vertex of the
-dimensional
unit cube, in which case a Boolean function of
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
-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.