Finite Mathematics

an area of mathematics that studies the properties of structures of a finite nature that arise in mathematics and its applications. Such finite structures may include, for example, finite groups, finite graphs, and certain mathematical models of information converters, finite automata, Turing machines, and so forth. Sometimes the subject matter of finite mathematics is expanded to include arbitrary discrete structures, such as certain algebraic systems, infinite graphs, certain types of computing schemes, and modular automata. The resulting discipline is referred to as discrete mathematics and is identified with finite mathematics. The term “discrete analysis” is occasionally used as a synonym for the concepts of “finite mathematics” and “discrete mathematics.” In what follows, the term “finite mathematics” is used in the broad sense that includes discrete mathematics.

In contrast to finite mathematics, classical mathematics is primarily concerned with the study of continuous objects. Whether we use classical mathematics or finite mathematics as the means of investigation depends on the type of problem being investigated and consequently on whether the model of the particular phenomenon is discrete or continuous. Thus, for example, in the problem of finding the mass of a radioactive substance at a given moment with a certain degree of accuracy, we may consider the process of the change of mass during radioactive disintegration to be continuous when in fact it is known to be discrete. The very division of mathematics into classical and discrete mathematics is rather arbitrary for, on the one hand, there is a considerable exchange of ideas and methods between them, and, on the other hand, the necessity often arises of studying models simultaneously possessing both discrete and continuous properties. It should also be noted that there exist areas of mathematics that use the methods of discrete mathematics to study continuous models (for example, algebraic geometry) and, conversely, the methods and ways of formulating problems typical of classical analysis are often used in the study of discrete structures (for example, asymptotic problems in number theory). These examples indicate the definite overlapping of classical and discrete mathematics.

Finite mathematics represents an important trend in mathematics. It is possible to single out its typical subject of study, methods, and problems, whose nature is largely determined by the necessity, characteristic of finite mathematics, for rejecting the fundamental concepts of classical mathematics—limit and continuity—and by the fact that the powerful methods of classical mathematics as a rule prove to be of little use in many problems of finite mathematics. In addition to delimiting finite mathematics by indicating its subject of study, it is also possible to define it by specifying its subdivisions. These include combinatorial analysis, the theory of graphs, coding theory, and the theory of functional systems. Viewed in these terms, finite mathematics stands for the study of finite structures. Viewed in less restrictive terms, finite mathematics includes both entire branches of mathematics, such as mathematical logic, and parts of these branches, such as number theory, algebra, computer science, and discrete probability theory.

The elements of finite mathematics arose in early antiquity. They developed parallel to other branches of mathematics and were to a significant extent a part of them. Typical for that period were problems that were related to the properties of integers and subsequently led to the creation of number theory. Here we might include the search for algorithms for the addition and multiplication of natural numbers by the ancient Egyptians (second millennium B.C.) and problems of summation and questions of divisibility of natural numbers considered by the Pythagorean school (sixth century B.C.). Later (17th and 18th centuries), games of chance stimulated the development of elementary combinatorial analysis and discrete probability theory (B. Pascal, P. Fermat). Problems common to number theory, algebra, and geometry gave rise (in the 18th and 19th centuries) to the most important concepts of algebra, such as group, field, and ring (J. Lagrange, E. Galois). Of a discrete nature, these concepts determined the development and content of algebra for many years to come. The tendency toward rigor in mathematical reasoning and analysis of the tool of mathematics—logic—led to the emergence of still another important branch of mathematics —mathematical logic (19th and 20th centuries).

However, finite mathematics achieved its greatest development in connection with practical problems that were the source of the new science of cybernetics and its theoretical counterpart —mathematical cybernetics (20th century). Man’s practical activity confronts cybernetics with a great variety of problems. Mathematical cybernetics studies these problems from the stand-point of mathematics. It is also a rich source of ideas and problems for finite mathematics and has introduced entirely new trends into that subject. Thus, applied problems requiring much numerical work stimulated the appearance of powerful numerical methods of problem-solving, which later developed into computer science, and the analysis of the concepts of “computability” and “algorithm” led to the creation of an important branch of mathematical logic—the theory of algorithms. The increasing flow of information and the related problems of information storage, processing, and transmission led to the rise of coding theory. Economics problems, electrical engineering problems, and purely mathematical problems required the development of graph theory. Problems of the construction and description of the operation of complex control systems led to the theory of functional systems. At the same time, mathematical cybernetics makes extensive use of the results of finite mathematics in the solution of its problems.

Finite mathematics has a number of unique features other than the ones already mentioned. Thus, in addition to existence problems found throughout mathematics, an important place in finite mathematics is occupied by problems connected with algorithmic solvability and the construction of specific solution algorithms—issues peculiar to finite mathematics. Another unique feature of finite mathematics is the fact that it was essentially the first mathematical discipline that showed the need for intensive study of discrete multiextremal problems, which arise frequently in mathematical cybernetics. The methods of classical mathematics for finding extrema rely largely on the smoothness of functions and prove to be ineffective in these problems. Typical problems of this type in finite mathematics are, for example, problems of finding optimal (in a certain sense) strategies in a chess game for a limited number of moves, as well as the important problem in mathematical cybernetics of constructing minimal disjoint normal forms for Boolean functions, that is, the problem of minimization of Boolean functions.

A unique feature of finite mathematics associated with problems involving finite structures is that, as a rule, solution algorithms exist for many of these problems, whereas in classical mathematics a complete solution of the problem is often possible only under extremely stringent restrictions. Examples of such problems are the aforementioned problems of chess strategies and of minimization of Boolean functions. An example of such an algorithm is that of surveying all possible alternatives. Such algorithms are very laborious and of little practical use. In this connection there arise new questions related to the conditions limiting the number of alternatives and leading to the reduction of individual problems, characterized by specific values of the parameters, to a general problem, characterized by an infinite set of parameter values. Other questions arise in connection with the imposition of restrictions on the methods of solution that are natural for this class of problems. The formulation of these questions and the development of relevant techniques are carried out for specific models provided by various branches of mathematics. These include, for example, models of minimization of Boolean functions and synthesis of control systems in mathematical cybernetics.