Open AccessМІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ ЗА НОМЕРАМИ НАБОРІВ ЗНАЧЕНЬ АРГУМЕНТІВ
Author(s) -
Віктор Федорович Сенчуков,
Тетяна Володимирівна Денисова
Publication year - 2019
Publication title -
otkrytye informacionnye i kompʹûternye integrirovannye tehnologii
Language(s) - English
Resource type - Journals
eISSN - 2663-2411
pISSN - 2071-1077
DOI - 10.32620/oikit.2019.83.11
Subject(s) - mathematics , sequence (biology) , connection (principal bundle) , function (biology) , boolean function , term (time) , variable (mathematics) , zero (linguistics) , canonical normal form , disjunctive normal form , combinatorics , representation (politics) , finite set , order (exchange) , set (abstract data type) , unit (ring theory) , discrete mathematics , algorithm , mathematical analysis , computer science , philosophy , law , linguistics , genetics , biology , geometry , quantum mechanics , evolutionary biology , political science , programming language , physics , mathematics education , finance , politics , economics
An original approach to analytic canonical minimization of switching (Boolean) functions, which is based on the representation of Boolean functions (BF) as a function of one variable – the number of the set í of values of its arguments, is proposed. For this, using the Antje function, the dependence (in the form of formulas) of the values of each of n variables on the number í is established. To construct a minimal disjunctive or conjunctive normal form of the BF are repelled from the corresponding perfect forms. In this connection the need to describe the sequence of numbers of sets, on which the variables take the values 1 and 0, arises. The common terms of such sequences can be obtained using the formula for the common term of a numerical sequence in a representation through the finite differences of its members. Further the connection between the sum of the values of atoms (term) ó(í) and the numbers of their values is established. With the help of the values of ó(í) , the question of gluing the constituents of the unit or zero is solved. Threedimensional and four-dimensional cubes whose vertices are labeled with sigmas are depicted for a function of three and four variables, respectively. Since the necessary condition for gluing the constituents – the modulus of the difference between sigmas is equal to one – is not sufficient, the gluing criterion is used: the constituents of a unit or zero are glued if and only if the Gamming distance between two values of ó(í) is equal to one. The general order for gluing the constituent of a unit or zero on the basis of the described means is obtained. A matrix of size m× n , where m is the number of simple implicant or implicent, n is the number of sets, on which the BF unit or zero values takes, is used to build deadlock forms; they are not represented by letters, but by sets of ones and zeros that correspond to them. The proposed approach to minimizing BF is called the í -minimization method. An example of minimizing of BF of five variables, given by the numbers of the sets í of values of its arguments, on which it takes values equal to one, that is – with the property f = 1, is given. The possibility of using the í -minimization of BF in bases other than the basis (∧, ∨, ), and in the future – an application to the minimization of BF of integer mathematical programming is discussed.