The paper has been introducing new concepts such as universal Boolean algebra, l basic algebras, free and canonical algebras, functionally complete and incomplete algebras, threshold universal algebra. The class of universal Boolean algebras 2 is represented in the form of an eleven-dimensional signature cube. This cube has been divided into four ninedimensional cubes 12 , 22 , 32 , 42 . Also the set of functionally incomplete algebras are found and the signature graph of this class is constructed. The class of all functionally complete algebras has been divided into fifteen classes and the signature graphs of each of these classes were constructed. All functionally complete algebras have been represented in the form of a signature graph. The powers of a class canonical algebras and free algebras have been installed and these signature graphs have been constructed. In the second part of paper the class of algebras 2 divided into four subclasses: internal functionally incomplete algebras, threshold functionally incomplete algebras, threshold functionally complete algebras and internal functionally complete algebras. Signature graphs of classes are constructed, the isomorphism of some subclasses of threshold functionally complete algebras is proved, the power of these classes and the location of algebras on signature graphs are determined. The signature graph of all threshold functionally complete algebras is given. Also, the concept of basic equivalence is introduced in the paper, the factor-grating M 2 / of the class of algebras M 2 is obtained.
The Theory of Boolean functions is one of the most important sections of discrete mathematics. It is the theoretical foundation of modern theories such as machine learning, artificial intelligence, methods of decision support and fuzzy logic.
In the paper, results are summarized obtained in works [
2020 Copyright for this paper by its authors.
Definition 1. Universal algebra U is called the compile pair A,
at set A (porter of algebras)
and (set of operations based on A ) [
Definition 2. Universal Boolean Algebra U A, is called Universal Algebra, where A 0,1, – set of Boolean operations. In the following Universal Boolean Algebras, we will call Boolean Algebras or Algebras.
Consider the set of Universal Boolean Algebras to the signature of them enter the operations Q 0, 1, , , , , , , , , | that is Ui A,i |i Q. Of course, 211 2048 algebras are formed 11-dimensional cube. In the following, we will call Signature cube or -cube. Each vertex of -cube put on correlation the Boolean vector of length 11. In this Boolean vector true (one) value defines the operations which enter the signature corresponding algebra. Vertexes of cube are reflected signature (list of operations), -vector or natural number, the decomposition of them modulo 2 defines -vector. Order relation of -cube represented in the following forms: Ui A,i U j A, j , if i j . Zero values of -cube is trivial algebra, where . -cube has
Cn1 11 algebras on the first circle and on each consecutive circle – C nk , n 11, k 1,11. An edge of -cube join algebras Ui A, i and U j A, j , where U j Ui increase (diminish) signature U j for one more operation in comparison with U i , if moves into the edge from down to up (up to down).
Definition 3. Algebra U A, is called functionally complete if the set of it functions, that is accord operation from , are formed the functionally complete systems otherwise algebra is called functionally incomplete [11].
Definition 4. Algebra U A, is called l basic if with operations of signature can be construct l bases.
Definition 5. An operation fi is called connected if it enters to composition to some base otherwise operation is called free operation.
Definition 6. Algebra U A, is called free algebra if its signature has free operations. Definition 7. Algebra U A, is called canonical algebra if it doesn’t have free operations.
Definition 8. The rank of free algebra is called a number that is equal numerosity of free operations.
Definition 9. Algebra U A, is called saturated if its arbitrary expansion of signature increases the basis of algebra.
Definition 10. The potential of edge that connects two adjacent algebras U1 and U 2 of cube with basics 1 and 2 (1 2 ) is called number 1 2 .
Definition 11. The potential of algebra is called the sum potentials of all edges (upper) going out of the algebra.
Consider the set of algebras 2 U A, , where A 0,1 and – set of the Boolean operations arnost of them does not exceed two. The class of algebras 2 can be represented as an 11-dimensional signature cube in Figure 1. of all algebras 2 , the signature of them is contained the operations , | , , |.
Construct partition of the set 2 12 22 32 42 , where 12 the set of algebras 2 its signature is not contained the Pierce’s arrow and the Sheffer’s touch | , and 22 , 32 , 42 sets
Consider the set of algebras of the class 12 formed an 11-dimensional signature cube ( cube) with the fixed tenth and eleventh zero value coordinates (Figure 2).
Denote the set of functionally incomplete algebras by 0 . This class contains eighty-eight algebras. The signature graph of functionally incomplete algebras is shown in Figure 3.
l base of algebras of class 0 is equal to zero.
The potential of all edges of the -cube is equal to zero represented in Figure 3.
To each vertex of n dimensional -cube conduct n edges n 9. The number of edges conducted to each vertex of the graph represented in Figure 3 is less than nine (except trivial algebra). 0,1, , , 0,1, , , , 0,1, , , , 1, , , , . From Absent edges connect algebras with the functionally complete of algebras. The following assertion takes place.
Assertion 2. The trivial algebra is the sole internal functionally incomplete algebra, another eighty-seven algebras are the threshold.
Definition 9 follows that the class 0 contains four saturated (pre-full) algebras with signatures
1. 2. circle where algebra is situated.
All algebras of class 0 are free.
The rank of each algebra Ui A, i 0 equals the power signature i or number of the Construct partition of the set 12 0 1 2 ... 15 , where l the set of l basic of algebras, l 0,1,...,15 . The class of functionally incomplete algebras 0 is defined in the previous sections. Consider the class of one-basic algebras 1 . The power of this class 1 is equal to seventytwo. graph of class 1 represented in Figure 4.
From Figure 4 we can see that algebras are situated in the circle as follows: second circle is contained nine canonical unsaturated algebras with two-operation bases; third circle is contained six canonical unsaturated algebras with three-operation bases, thirty free algebras which obtained by corresponding algebras second circle in way of expansion for one more operation. Since the basicity of algebras is the same as adjacent algebras of the second circle, therefore, the rank of these algebras is equal to one, and the edges which it connects have a potential value zero; fourth circle includes twenty-five free algebras, where there the rank is equal to two; saturated algebras are all algebras of this circle without algebras with numbers 178, 308, 402, 404, 418, 420. fifth circle is contained two free saturated algebras 434, 436 where the rank is equal to three. Based on performed analysis for canonical algebras of class 1 takes place assertion. Assertion 4. Class algebras include seventy-two algebras, where fifteen canonical algebras: two saturated canonical algebras and twenty-one saturated free algebras; fifty-seven free algebras: thirty algebras have the rank is equal to one, twenty-five algebras have the rank is equal to two, two algebras have the rank is equal to three.
The type of algebra we can recognize on the graph by the features described below. l Basic Algebras
Class 2 contains one hundred and five algebras. The third circle is contained the fourteen canonical unsaturated algebras. The fourteen canonical saturated algebras, twelve canonical unsaturated algebras, and thirty-five free unsaturated algebras are on the fourth circle where their rank is equal to one. The thirty free saturated algebras with the rank value two are contained on the fifth circle. graphs for the classes l ,l 2,3..., 6 , are shown in Figures 5-9.
The sets of algebras of classes 7 -15 are canonical saturated algebras and their graphs are 8 191, 253, 319, 379, 415, 431, 443, 445, 471, 478, 487, 494, 505; contained only isolated points: 7 95, 111, 222, 238, 343, 359, 247, 382, 463, 475, 477, 491, 493, 499, 502, 508; 9 127, 223, 239, 251, 254, 351, 367, 375, 381;10 503, 510; 11 447, 479, 495, 507, 509; 12 255, 383; 15 511.
From the obtained results we get the following assertions.
Assertion 5. The class of algebras 12 contains four hundred twenty-four functionally complete algebras.
The number of l basic algebras, l 1,2,...,15 and their location in circle of cube are given in Table 1.
For example, two one-base, thirty-two-basic, thirty-eight three-basic, thirty-nine four-basic, and fifteen five-basic algebras are contained on the fifth circle. The three-basic algebras are situated as follows: one algebra – on the third circle, eighteen algebras – on the fourth circle, thirty-eight – on the fifth circle, and nine algebras – on the sixth circle.
Assertion 6. The two hundred sixty-four canonical algebras exist in the class algebras 12 .
These algebras are formed the signature grating which is represented in Figure 10 and the distribution of algebras by the number of basics is given in Table 2.
All the functionally incomplete algebras are free algebras where the rank is equal to the power of signature.
Base 1 2 3 4 5 6 7 8 9 Assertion 7. The two hundred fifty-nine free algebras exist in the class algebras 12 .
The distribution of free algebras by rank is shown in the following Table 3.
The free algebras of the class 12 form the signature graph are represented in Figure 11. This graph is obtained from signature graph of sets 12 by the withdrawal canonical algebras.
Consider generalization of results is obtained from the class 12 to the classes 22 , 32 , 42 , that is class 2 . The class of algebras 22 forms 11-dimensional vectors with the fixed tenth one value coordinate and eleventh zero value coordinate. We can construct a 9-dimensional cube similar the cube of the class 12 . For the each k base algebra of class 2 exist sole corresponding k 1 basic algebra of the class 12 (in the corresponding algebras, the first nine coordinate coincide).
Similar considerations we can develop for algebras of classes 32 and 42 . The basicity of algebras of class 32 in relation to 12 increase to two. We can determine the quality k basic algebras of the class 2 defined by k 2k1 k2 , where k the number k basic algebras of the class 12 .
Assertion 8. The class of algebras 2 contains 2048 algebras where 88 algebras are functionally incomplete.
Definition 12. Algebras U1 A, 1 , U2 A, 2 which connects these algebras. are called adjacent algebras if exist edge An adjacent algebras and differ only one operation in -cube that is 1 2 1 2 1 . An adjacent algebras are located in nearby circle -cube.
is called threshold if it is contained an adjacent functionally complete and functionally incomplete algebras.
Definition 14. Algebra U A, is called internal if all adjacent algebras are functionally complete or functionally incomplete.
Definition 15. Functionally incomplete algebra is called pre-full if the expansion of signature converts algebra to functionally complete algebra.
Boolean algebras of class
M 2 consist four subclasses: M1 class of internal functionally
incomplete algebras; M 2 class of threshold functionally incomplete algebras; M 3 class of
threshold functionally complete algebras; M 4 class of internal functionally complete algebras [
In Figure 3 the graph of functionally incomplete algebras is shown.
Assertion 9. All functionally incomplete algebras of class M 2 are threshold.
Assertion 10. Functionally complete algebra is a threshold algebra if and only if there are operation enters into all bases of this algebra.
Construct partition of the set of threshold functionally complete algebras M 3 to subclasses M3 M31 M32 ... M39 M310 M311 , where M 3і , і 1,11 the set of all threshold functionally complete algebras which have adjacent edges are connected with algebras of class M 2 . The each an adjacent edge responds ith operation of set Q . It means that the signature of algebras of class M 3і enters ith operation аnd in the signature of corresponding adjacent algebras this operation doesn’t enter. Denote the class of functionally incomplete algebras by M 2і where signature is contained ith operation and M 2і the class of algebras is got from M 2і by the withdrawal of ith operation of signature that is
M 2і M 2 M 2i M 2i .
(1) 11 0 88
Class of algebras M 3і we can get with M 2і by the expansion of signature ith operation. If signature all of algebras M 2 expanse ith operation that is algebras M 2і and M 2і remain functionally incomplete and another algebras converts to class functionally complete algebras. Since M 2 88 and M 2і = M 2і we get M 2і 88 2 M 2i . Based on (1) is given Table 4. Number of algebras where the signature is contained ith operation 1 33 22 2 33 22 3 16 56 4 32 24 5 32 24 6 30 28 7 16 56 8 16 56 9 30 28 10 0 88
are called isomorphic if it is possible to establish between their vertexes such a bijection f that two vertexes u , v of a graph are adjacent if and only if f (u) and f (v) adjacent vertexes in the graph H .
The problem of recognizing isomorphisms of graphs belongs to the class NP - full. In [19] it was argued that "the search for individual criteria and features of isomorphisms for graphs of a class can be very difficult and not always successful." Modern papers of graph theory [20] are confirmed that the problem of graph isomorphism has not been solved.
Denote by Gi -graph that is defined the class of threshold functionally complete algebras M 2і . For each class M 2і graphs of the signature G1 G9 shown in Figures 12 - 16.
Assertion 6. The -graphs are isomorphic: G1 G2 , G4 G , G6 G9 , G7 G8 , G10 G11 . 5 The graphs G G9 are combined into one graph of signature depicted in Figure 17.
1
The isomorphism of the signature graphs Gi , i 1,9 is proved by the bijection of the vertexes given in Table 5.
Definition 17. Algebra U A, is called saturated in a class K if, as a result arbitrary extension of the signature, we obtain an algebra that does not belong K .
Based on Figure 17 the -graph of a class G of threshold algebras M2 include two hundred and nineteen algebras; fifteen canonical algebras with numbers 3, 6, 12, 66, 68, 80, 96, 130, 260, 25, 41, 152, 168, 273, 289; twelve the threshold algebras with numbers 183, 189,245, 315, 318, 378, 437, 442, 459.
Consider the classes of algebras M 2110 , M110, 11 , M1 11 that have been from M219 the extension of 2 2 their signatures by the Pierce’s arrow and the Sheffer’s touch | . M319,10 , M319,11 the classes of threshold algebras, and
M310 11 the class of internal functionally complete algebras.
G2 , G210, G211, G21011 -graphs of the corresponding classes M 2 , M 2110, M 2110,11, G2111. These graphs are isomorphic and their unification forms a -graph represented schematically in Figure 18. Based -graph represented in Figure 7 takes place the following theorems.
Theorem 1. Internal functionally incomplete algebras in the class M are absent.
Theorem 2. The set of Boolean algebras M consists of 88 threshold functionally incomplete algebras; 395 threshold functionally complete algebras; 1565 internal functionally complete algebras.
We can construct nine two-operation basics a1 0,, a2 0,, a3 , , a4 ,, a5 ,, a6 ,, a7 ,, a8 ,, a9 , and six three-operation basics a10 0,, , a11 0,, , a12 1,,, a13 1,,, a14 ,, , a15 ,, and two single-operation basics a16 , a17 | . It is possible to form 217 various combinations of basics from seventeen basics. The Universal Boolean Algebras do not exist for most combinations from the operations of which only those basics can be constructed that are included in the combination. But Universal Boolean algebras are existing with signatures from the operations of which we can build the same set of basics.
Each algebra Ui A, M 2 is matched with a seventeen-dimensional Boolean vector Hi 1i , 2i,,1i7, where ij 1, if the operations can form j -basic and ij 0 otherwise. The vector Hi is called the characteristic basis vector of algebra U i . Denote by B(Ui ) the set of all basics of algebra Ui A, i from the operations that are included to .
Definition 18. Algebras U1 and
U 2 M 2
are called basically equivalent
Let us construct a factor-grating M / by basis equivalence using characteristic basis vectors.
Algebras that come in the zero value element of the factor-grating have a characteristic basis vector
(0,0,,0) . The maximum element of the factor-grating is an algebra U * such that M * (1,1,,1) the signature of the element includes all seventeen operations.
If algebras U1 A, 1 and U2 A, 2
have characteristic basis vectors H1 11, 12 ,,117 and H2 12 , 22 ,,127, U1 U 2 if and only if H1 H 2 , that is i1 i2 , i 1,2,...,17 . Consider adjacent classes M 21 by basic equivalences . (0,0,,0)
The eighty-eight functionally incomplete algebras of class M 21 have a characteristic basis vector
[
The three classes consist of eight algebras: K81 80,81,88,208,209,336,344,464, K82 96,97,104,224,225,352,360,480, K83 112,113,120,240,241,368,376,490 have isomorphic signature graphs. The four classes consist of seven algebras: K71 3,11,19,35,51,259,267, K72 12,13,28,44,60,140,141, K73 131,139,147,163,179,387,395, K74 268,269,284,300,316,396,397 . These classes are represented in Figure 21. The twenty-two classes K 4t1 ,t1 1,2,...,22 consist of four algebras, the thirty classes K 4t2 ,t2 1,2,...,30 includes two algebras and one hundred seventy-six classes K1t3 ,t3 1,2,...,176 – one algebra. Signature gratings of these classes are represented in Figure 22.
We will construct a basis grating of the factor class 2 / . The vertexes of the grating are encoded by the binary codes of the basics or the signature code of canonical algebras that come into the corresponding class. The edges are encoded by the number of basics or codes of operations that connect canonical algebras. Each element of the factor class has one canonical algebra, and the other algebras are free. The factor-grating can be constructed using a set of canonical algebras.
The number of basic algebras in each circle is given in Table 6. 1 Figure 19: Signature Graph of class K10
From Table 2 it follows that power of the class M 21 / is equal to two hundred sixty-five algebras. The basic gratings M 22 / , M 23 / , M 24 / are isomorphic to grating M 21 / . If these gratings combine into one basic grating M2 / , then the corresponding algebras U ki of grating M 2i / , i 1, 2,3, 4 form sub gratings are represented in Figure 23. Theorem 3. The power of a class M2 / is equal to 1060 algebras.
Really M2 / M21 / M22 / M23 / M24 / 4 265 1060 . From seventeen bases it is possible to form 217 various combinations and only 1060 such combinations it is possible to find an algebra that has only those bases which are specified in the chosen combination.
The theory of Boolean functions is the foundation of modern discrete mathematics, mathematical logic, and computer science. This theory is used in combinatorics, theory of graphs, information and cryptology, theory of coding, and the theories such as machine learning, data mining, artificial intelligence, and neural networks. The complexity of algorithms for processing Boolean functions for a large number of variables requires the development of new methods in the analysis and representation of Boolean algebras. This paper has been using a description of Boolean algebras and their representation as graphs and lattices. That allows to significantly reduce the number of searches in the search algorithms for bases with specified characteristics. The construction of reliable technical systems involves the design of parallel circuits that use Boolean functions specified in different bases. The proposed work optimizes the search for algebras with given sets of basic.