Pure and Applied Mathematics Journal
Volume 6, Issue 1, February 2017, Pages: 14-24

Finite Closed Sets of Functions in Multi-valued Logic

M. A. Malkov

Russian Research Center for Artificial Intelligence, Moscow, Russia

Email address:

To cite this article:

M. A. Malkov. Finite Closed Sets of Functions in Multi-Valued Logic. Pure and Applied Mathematics Journal. Vol. 6, No. 1, 2017, pp. 14-24.
doi:
10.11648/j.pamj.20170601.13

Received: January 3, 2017; Accepted: January 14, 2017; Published: February 20, 2017


Abstract: The article is devoted to classification of close sets of functions in k-valued logic. We build the classification of finite closed sets. The sets contain only constants and unary functions since sets containing even a two-ary function are infinite. Formulas of the number of finite sets and minimal sets exist for all natural k. We find the numbers of closed sets containing the identity function f (x)=x or a constant for all k. We give the number of sets on levels of inclusions at k up to 10. The inclusion diagrams are present at k up to 5, at k=6 we give inclusion diagrams of sets containing only function f (x)=x and constant 0. We find isomorphic sets and use only one of the isomorphic sets to build the diagrams.

Keywords: Discreat Mathematics, Multi-valued Logic, Function Classification


1. Introduction

Multi-valued logic attracts intensive attention because of the connection with computer technology.

The first theories of multi-valued logic were born in the works of J. Lukasiewicz ([1], 1920) and E. Post ([2], 1920). Now there are almost a hundred theories of multivalued logic but theory of Post’s logic is more popular. We will use this theory.

E. Post gave more complete theory of his logic in [3] (1921). Later (1976), A. Mal’cev gave the further development of the theory in [4]. He created two algebras, which he called Post’s iterative and Post’s preiterative, these algebras are very different. Post used the preiterative algebra implicitly. Therefore it is more correctly to call Post’s preiterative algebra Post algebra and Post’s iterative algebra Mal’cev algebra. All closed sets are subalgebras of Post algebra. Unfortunately his Post algebra did not receive due recognition and almost all consequent investigators ignored it.

The survey [5] did not mention any Mal’cev’s works but contained some results of his works. I. Rosenberg [6] gave extensive account of Mal’cev’s results and marked "Preiterative sets are slightly more general than clones" (he used preiterative sets instead of preiterative algebra). In reality the preiterative (Post) algebra is more general than the clone algebra. The clone algebra uses not all functions but every classification of objects of a theory must include all objects of the theory. So the classification of functions must use all functions, the number of which is  for -ary functions and for 0-ary functions (constants) too. We will give the full classification for  and for  as beginning. This is classification of finite closed sets, too. They are absent in the clone algebra.

The monograph [7] has not mentioned the Rosenberg work. It has mentioned many of Mal’cev’s works but it has used only Mal’cev algebra (this algebra is not sound, see 2.1).

The first purpose of any theory is classification of objects of the theory. Every object must belong to a class and classes must be disjoint. We call such the classification natural.

The first purpose of multivalued logic is classification of multivalued functions. The full classification of 2-valued (Boolean) functions was given by E. Post [8]. His classes are closed sets of functions. It was shown in [9] that this classification was natural. Its closed sets do not disjoin but their subsets, not containing the other closed sets, are disjoint. Every closed set has only one of the subsets. This means that classifications of closed sets and the subsets have the same inclusion diagram.

Such the classification of 3-valued functions is absent now, since amount of classes is very big, this amount is uncountable. But a simple classification of -valued functions exists for all natural  and for  too [10]. The classification has only one level. The full classification must have more levels. Post’s classification has 14 levels. The other classifications use only some of closed sets. As a rool, these classifications are unnatural.

The classification of linear functions was the earliest and best investigated. A. A. Salomaa (1964, [11]) was the first who determined linear closed sets. His results were improved by J. Bagynszki and J. Demetrovics (1976, [12], 1982, [13]). A. Szendrei (1978, 14]) and J. Bogynszki (1979, [15]) established that the set of linear functions is finite, if k is square-free. S. S. Marchevkov (2015, [16]) defind all 23 closed sets of linear functions in three-valued logic. The other results were given in [17-20,7].

The classification of selfdual functions was given by S. S. Marchenkov in [21] (1979) and in [22] (1980). D. N. Zhuk (2015, [23]) stated that he had found all clones of self-dual functions.

The classification of idempotent functions was given by S. S. Marchenkov in [24] (1999). The classification of monotone functions was given by H. Machida in [25] (1979). I. Rosenberg gave the classification of all maximal closed sets in [25] (1965), in [26] (1970), and in [27] (1973). He found 5 types of minimal clones (1986, [28]).

There are very much works devoting to problems of fullness of function’s sets. But fundamental results were got by G. Rousseau in [29] (1967) and were improved by P. Schofield in [30] (1969). They produced Sheffer functions by using little information.

This article is devoted to finite closed sets (subalgebras of Post algebra) and has, except introduction, 2 sections and the appendix.

The section "Algebra of function compositions (Post algebra)" contains the information necessary for construction of finite closed sets. We give the mathematically precise definition of Post preiterative algebra and the definition of closed sets. These definitions are extensions of Mal’cev’s, since Mal’cev’s definition excludes constants but our definitions include constants. We introduce, by natural numbering, an order of functions. We assign a number to a function such that the number contains a table of the function in coded form. We present Lau’s result for the number of minimal closed sets and give the definition of family of functions with the same diagonal.

The section "Finite closed sets" constructs the classification of finite closed sets. We introduce levels of finite closed sets. Level 0 contains minimal closed sets. Level  has closed sets containing closed sets of level . We find the numbers of closed sets on levels for 2 ≤ k ≤ 10. We find the number of closed sets containing the constant 0 and belonging to level 2 (level 1 is primitive) for all finite . The number of closed sets containing the function  and belonging to level 1 is also given for all finite .

In appendix we build diagrams of conclusions of closed sets at 1 ≤ k ≤ 5. For  we build only diagrams of closed sets containing 0 and .

We use short proofs of theorems since full proofs give very large size of the paper. We use some statements without proofs if the proofs are obvious.

We use  only as a value of logic and  only as arity of functions. We denote functions of closed sets by  or by . A name of a closed set is the name of the minimal generator of the set. And all operations of additions use modulo  in -valued logic.

2. Algebra of Function Compositions (Post Algebra)

2.1. Definition of Post Algebra

Closed sets of functions are constructed by using compositions (superpositions) of the functions. So we must define the algebra of function composition. We will use the algebra to construct the classification of finite closed sets.

Mal’cev ([4]) gave the following definition of the algebra of compositions.

Definition The Post algebra P is

where  is the set of all -valued everywhere defined functions with the domain ; , ,  and * are primitive operations (primitives) over these functions. In accordance with the standard definition of algebras,  is the universe of the algebra, , ,  and * are the fundamental operations of the algebra.

Primitives are the operations that build all other operations.

The operation of adding a fictitious variable is considered as primitive in Mal’cev algebra. It is shown in [31] that this operation is not primitive since fictitious variables can be added by the operation of substitution of fictitious functions. But fictitious functions can be generated by non-fictitious functions. And Sheffer functions generate all functions in Post algebra. This means that Mal’cev algebra is not sound. But this algebra becomes sound if fictitious functions are absent in the algebra. Hence the operation of adding fictitious variables must be absent. And primitives of this algebra and Post algebra become the same. But the algebras have different objects: objects of Post algebra include fictitious functions and objects of the new Mal’cev algebra exclude the functions.

Algebras with  and  exist too. By the formula  for number of function of arity , closed sets of  are empty, closed sets of  contain one function for every .

We will give the new definitions of primitives. The definitions are a very strong extension of Mal’cev’s. In particular, Mal’cev’s definitions exclude constants. Then generators cannot build constants. But constants are inseparable part of functions and they must be built. The number of constants equals .

So the new definitions are needed.

2.2. Operation  of Cyclic Permutation

This operation provides a cyclic permutation of variables in a function. The cyclic permutation is an element of the symmetric group. We put a word  to each symbol  in the next definitions.

Definition The unary operation  of cyclic permutation is

The operation  is denoted by  in the symmetric group.

The operation  locates the first column of the table of  after -th column and then shifts all the columns to the left. The operation renumbers variables of functions, too.

2.3. Operation  of Long Permutation

This is one more operation of the symmetric group.

Definition The unary operation of long permutation  provides permutation of the first and the last variables in functions:

The operation  is denoted by  in the symmetric group. This operation realizes permutation of the first and -th columns of the table of .

Using the operation  and  one can get all elements of the symmetric group. In this group the element  realizes to renumber variable  to . The other variables are renumbered by analogy. We will call a pair  and  a permutation operation.

Mal’cev defined short permutations but they do not apply to unary functions.

2.4. Operation  of Identification

This operation is an element of a monoid, the operation gives permutations with repetitions.

Definition The unary operation  of identification equalizes the first and last variables and deletes the last variable in a function:

This operation removes lines of the table of , if they have different values in the first and last columns. As a result, the columns become equal, the last column becomes superfluous and is deleted. The arity of  is decreased by 1. This is impossible for unary essential (non-fictitious) functions since, after removing the variable-column, only one line must be left in the table. It is not clear which line must be left. So we cannot decrease arity and the operation must not change the function. If a unary function is fictitious then we can leave any line of the column since all lines equal. As result the function becomes a constant.

So the operation  is applied to all functions of the universe.

The operation allows to generate any 0-ary function. In particular, the Webb function generating all functions generates constants only through this operation.

The operation  is denoted by . The operation gives permutations with repetitions, these repetitions are for . This notation emphasizes that the table  has -th column to be deleted. The notation  emphasizes that the first column is removed. Generically,  since they are different functions.

Mal’cev used the identification of the first and the second variables. This operation has the same result for deleting the first or the second variables. This is not essential. But Mal’cev’s definition gives the wrong result for fictitious unary functions and is not applied to constants. This is essential.

2.5. Operation * of Substitution

This operation is main in compositions.

Definition The two-ary operation * of substitution replaces the first variable in a function  by a function :

This operation, together with the operations  and , realizes any substitution.

In accordance with the first definition of the operation *, the substitution of the first variable of a function  by a function  creates a function . If  then we get an -ary function. And the function has value of the constant for any values of variables. This fact is reflected in the second definition of the operation *. But this definition does not apply to substitute a constant into a constant. The substitution of a constant into a constant does not change the latter constant. This is reflected in the last definition.

Consequently, a constant can be produced only if we substitute a constant into a constant. This means that Webb function can not create all functions, if we use only the operation of substitution, since the function can not create any constant. But the function can create any unary fictitious function and then the latter function creates a constant after applying the operations of identification.

The definitions of the operation and of the previous three operations use natural numeration of variables in a function. A numeration is natural if a function  contains only variables ,..., (m ≤ n) in any order and with repetitions, but every  must be present. This is one of properties of Post algebra.

2.6. Order of Functions

We use an order on functions to construct classification of finite closed sets.

The order is realized by numbering of functions. The function number is a pair of numbers , where  is an arity and j is an ordinal number for functions with the same arity. This ordinal number is contents of the function-column in -number system, if we read the column from top to bottom. For example, the 3-valued function with function-column (0, 1, 2) has the number (3, 0*32+1*31+2*30)=(3, 5). Thus, the number  of a function determines its table uniquely. The symbol  with these  and  is the name of the function. A function from a set of functions is called minimal if the function has the number less than the numbers of the other functions of the set.

2.7. Minimal Subalgebras

Every minimal subalgebra generates only itself. It contains a constant or a unit of some monoid.

We have found more simple proof of the next theorem on numbers of minimal subalgebras.

Theorem (Lau, 2006) The number of minimal subalgebras equals .

Proof. Unary functions will be named just functions.

Any minimal subalgebra has only one function and the function must be unit of a monoid or a constant.

Let  at  for some function  and let values of  for the other  be members of :

The function is a unit of a monoid. Indeed,

because of .

The number of such functions equals  since the sequence  has values from 0,..., 0 ( times) to  ( times).

Let  for  values of : , and let values of  be members of  for the other . Then the function is a unit of a monoid too. The number of different  equals . Hence, the number of all functions to be units for given  equals . The number of all the functions equals .

The number includes constants. Indeed, if  then functions are fictitious. But the number of fictitious functions equals the number of constants since every constant is generated by a fictitious function.

2.8. Family of Functions with the Same Diagonal

We will call families of functions with the same diagonal briefly families.

Families were introduced by Post. There are 4 families in two-valued logic: , , , . Post’s classification of function and their closed sets is based on the families.

Families of functions exist in all -valued logics too. The number of these families is . We will use them to classify finite closed sets.

The family  is defined standardly: . The family  is defined standardly, too: . Definitions of the other families are special in -valued logics but they are an extension of Post’s definitions.

We denote all types of families by , where 0 ≤ mk-1. Every function of a family has the diagonal  equal to , if , and not equal to , if . So  family is denoted by  and the  family is denoted by . A constant  belongs to the family  since a diagonal of a constant is this constant. The  family of two-valued logic is denoted by  and the  family is denoted by .

The next theorem is very useful in Post algebra.

Theorem Any function of a family  generates functions of a family .

Proof. The operations of permutation and identification do not change a family of a function. The operation of substitution can change a family of functions.

Let functions ,  be of the same family ,  , and denotation of family of  be .

We have  for every . In this case  for all . Then  since  can equal  for some . But if  for all  then . The proof is finished.

Corollary A function of the family  generates only function of this family. A function of the family  may generate functions of any family.

Proof. The denotation of family  is the set  and there is no family with denotation  such that . The family  has the denotation  and  for every family with denotation .

Families realize a natural classification of functions since they are disjoint. The Webb function and all other generators of P (usually they are named Sheffer functions) can belong only to the family .

3. Finite Closed Sets

3.1. Branches and Bundles of Branches

An inclusion diagram of finite closed sets (finite subalgebras) consists of branches.

Definition A set of subalgebras in an inclusion diagram is called a branch if the set is a sequence of subalgebras such that the last subalgebra belongs to level 0 of the inclusion diagram, before the last subalgebra belongs to level 1, and so on. Two branches are isolated if they have no common subalgebra. A bundle of branches is a set of all branches with the same minimal subalgebra. Two branches are isolated if they have no common subalgebra.

By definition, isolated branches and bundles have different minimal subalgebras.

Bundles of branches can be isomorphic.

Definition Two bundles of branches are isomorphic if there is a one-to-one mapping of subalgebras of these bundles such that the bundles have identical inclusions of the subalgebras.

Using isomorphism we can build more beautiful diagrams by using only one of isomorphic bundles of branches (see Fig. 4-6).

We call the boundary of two isomorphic bundles a mirror. If a bundle has several isomorphic bundles then the bundle has several mirrors.

3.2. Main Properties of Finite Subalgebras

Finite closed sets are subalgebras. The main property of the subalgebras is the next: their unary functions are elements of a monoid

where the top row contains values of variables, the bottom row contains values of a function. A product of the elements is a unary functions.

The following theorem gives another useful property.

Theorem 1 Branches are isolated.

Proof. Let a subalgebra belong to two branches. Then the subalgebra has two minimal subalgebras, i.e. it has two units. But any monoid has only one unit.

By theorem, bundles of branches are isomorphic too. Therefore bundles create natural classification: every subalgebra belongs only to one branch.

Theorem 2 Any function of a bungle containing function  is permutation, i.e. the range of the function is . Any function of a branch not containing  is not permutation, i.e. the range of the function is a proper subset of .

Proof. By compositions, only permutation functions can generate  and these functions cannot generate non-permutation functions.

Theorem 3 A bungle containing a constant   has only functions of the family .

Proof. A constant  belongs to the family . By the theorem in 2.8, only functions of families  and  may generate a function of family . But a unary function of family  cannot generate functions of family . Indeed, the unary function may generate functions of family  only if it is . But , i.e. the function generates a function of family  but not

The converse is not true. By the theorem in 2.8, a function of a family  can generate functions of every family except the  family.

3.3. Number of Subalgebras

There is no formula for the number of subalgebras for all  since all finite symmetric groups are created by subalgebras but some symmetric groups are sporadic. Conditionally we put minimal subalgebras on level 0, we put subalgebras directly containing minimal subalgebras on level 1, we put subalgebras directly containing level 1 on level 2, and so on.

We have found all subalgebras of all levels at k ≤ 10. The numbers of the subalgebras are present in table 1 (in 3.6). But diagrams containing subalgebras of all levels are present only at k ≤ 5 since the other diagrams have big volume. Only branches containing 0 and  are present at . The diagrams are in the appendix.

The number of minimal subalgebras for all  was given in the previous section. In the next subsections we will give the number of subalgebras, containing constant 0, on level 2 (level 1 is trivial) and the number of subalgebras, containing function , on level 1.

3.4. Subalgebras Containing Constants

Constants are on level 0. They are generated only by fictitious functions. Therefore, all subalgebras on level 1 have fictitious functions, their number equals the number of constants, i.e. equals . Every subalgebra on this level contains two functions: a constant and a fictitious function.

The next theorem allows to build all subalgebras on level 2 and to count their numbers. Each of these subalgebras is three-membered. One member is a generator of a subalgebra, the second member is a fictitious function, the third member is a constant.

Theorem If a subalgebra belongs to level 2 and contains a constant then the number of such the subalgebras equals .

Proof. It is enough to find the number of subalgebras for constant 0 since the numbers of subalgebras for other constants are the same.

We represent a function of a subalgebra of the second level in the form . Then

(1)

since one of functions of any subalgebra of level 2 must generate the fictitious function of the subalgebra of level 1 (level 1 contains only one subalgebra and this subalgebra contains one of fictitious functions), but right part of the equation is this fictitious function. We have  in this equation since the generator belongs to family {0}. And  for some .

Let  and the remaining  do not equal zero. In this case, equation (1) holds only if all these  equal 1. The number of such functions is 1. The same result we have if  at .

Let  and the remaining . Then equation (1) holds if the remaining  are members of the set . The number of such functions equals  since the number of  equals .

Let  and the remaining  do not equal 0. Then equation (1) holds if the  are members of the set . The number of such the functions equals  since the number of  is .

We have used equations . If we will use  with another values of  then the number of all such variants of the  equals  since 1 ≤ I ≤ k-1 and the number of  equals  ( is excluded). Hence the number of all functions (and all subalgebras) equals . We exclude  and  since at least two . And at least one . So the number of subalgebras for all constants equals .

3.5. Subalgebras Containing x

Every unary function of the subalgebras is an element of the symmetric group. A product of functions is a product of elements of the symmetric group. A power of a function is multiple product, in which every factor is the function. And every element of the group can be present as a set of cycles.

Level 0 contains only one minimal subalgebra . We must find numbers of subalgebras of the other levels.

Let level 1 be given. We will call subalgebras of level 1 briefly subalgebras. Every subalgebra has several functions to be generators of the subalgebra and function . A name of a subalgebra is a name of minimal generator of the subalgebra. We call minimal generators briefly generators. The next lemmas and the next theorem specify the number of subalgebras.

Lemma 1 A generator of a subalgebra of level 1 can have several cycles of the same length  ( is a prime number) and several cycles of length 1. Subalgebras with the other generators do not belong to level 1.

Proof. We can exclude cycles of length 1 since they are not changed by generations. If a function has a cycle of prime length  then the function and its powers generate the same functions. Indeed, the function and its powers are

The first function has the cycle . The second function has the cycle . The last function has  cycles of length 1.

Every of the functions is defined by its first value since the other values are defined by adding 1 to subscript. The first function generates functions with the first values , i.e. with all values. The second function generates functions with the first values , i.e. with all values, too. And all of the functions, except the last, generate the same functions since  is prime. Hence subalgebras of the functions belong to level 1 (the subalgebra of the last function belongs to level 0).

If a function has several cycles of the same length  then it and its powers generate the same functions. If a function has a cycle of non-prime length or cycles of different prime lengths then the function and its powers generate different functions. So the subalgebra of the function does not belong to level 1. The lemma is proved.

Lemma 2 The number a (k, p, m) of subalgebras, which minimal generators have m cycles of length p, equals

if every subalgebra belongs to level 1 and contains .

Proof. If a minimal generator of a subalgebra has m cycles of length p, if the subalgebra belongs to level 1, and if the subalgebra contains , then we called such the subalgebra briefly subalgebra.

The number of subalgebras equals the number of the functions divided by  since every subalgebra has  functions, every of which generates all of the functions. Therefore we begin to calculate the number of functions. The functions are differed by their cycles.

Let . Then cycles of length 1 are absent in functions.

If  then a cycle of a function is  since the first component of any cycle must be minimal, i.e. 0. The number of such different cycles equals . And the number of subalgebras with  and  is . The lemma holds in this case.

If  then there are two cycles in the minimal generator of a subalgebra: . The number of different values of the second component in the first cycle is . If the component is fixed then the number of different values of the next component is . And the number of all different component of the first cycle is . The number of different values of components of the second cycles is  since the component  must be minimal and the component is fixed. Hence the number of different values of all components is  since value  must be absent in this factorial. And the number of different subalgebras is . The lemma holds in this case too.

If  then the number of different cycles equals  since values , ,...,  must be absent in the factorial. And the number of subalgebras equals . The lemma holds again.

Let , where  be the number of cycles of length 1. Then the number of different cycles of length 1 equals the number of combinations of  elements out of the set of  elements. The number of the other different cycles equals . So the number of subalgebras equals

since . The lemma is proved. □

Theorem The number a (k) of subalgebras equals

if every subalgebra belongs to level 1 and contains . Here  is maximal  in -valued logic and  is the integral part of the devision.

Proof follows from the previous lemmas. □

3.6. Number of Subalgebras on Levels

The numbers of subalgebras on levels have obtained by a computer for k≤10. The numbers are present in table 1. The table also gives the number of subalgebras containing constant 0 and the number of subalgebras containing function  for every level.

 

Table 1. Levels for all subalgebras and for subalgebras containing 0 or .

L 2 3 4 5 6 7 8 9 10
0 3 10 41 196 1 057 6 322 41 393 293 608 2 237 921
of 0 2 3 4 5 6 7 8 9 10
of x 1 1 1 1 1 1 1 1 1
1 3 13 113 1 106 11 287 121 738 1 409 459 17 629 186 237 965 591
of 0 2 3 4 5 6 7 8 9 10
of x 1 4 13 41 151 652 2 675 10 579 59 071
2 - 6 63 1 125 21 390 442 218 8 304 058 177 910 764 4 108 864 830
of 0 - 6 36 200 1 170 7 392 50 568 372 528 2 936 070
of x - - 3 25 210 1 281 9 394 77 946 665 340
3 - - 24 420 8 040 161 175 5 023 116 140 139 468 4 100 363 280
of 0 - - 24 420 5 880 82 530 1 233 456 19 979 064 351 712 080
of x - - - - - 105 2 100 21 168 252 000
4 - - - - 720 27 720 934 080 32 384 016 1 177 212 960
of 0 - - - - 720 27 720 813 120 22 695 120 641 723 040
of x - - - - - - - - -
5 - - - - - - - - 3 628 800
of 0 - - - - - - - - 3 628 800
of x - - - - - - - - -
total 6 29 241 2 847 42 494 759 173 15 712 106 368 357 042 9 630 273 382

The number of minimal subalgebras (level 0) equals

The number of subalgebras belonging to level 2 and containing 0 equals

The number of subalgebras belonging to level 1 and containing  equals

4. Appendix

The diagrams of inclusions of finite subalgebras are presented below. The name of each subalgebra is the name of generator of the subalgebra. The superscript in the name is the number of isomorphic subalgebras. The subscript is a family of generators of subalgebras, but family names are present without braces and commas. A superscript is missing if the number of isomorphic subalgebras equals 1 or if every isomorphic subalgebra is present in a diagram. If a subalgebra in a diagram contains two subalgebras then the number of its isomorphic subalgebras is the sum of two digits corresponding to the left and right subalgebras. If the digits are absent then the number of the isomorphic subalgebras equals 1.

Figure 1. One-valued logic.

Figure 2. Two-valued logic.

Figure 3. Three-valued logic.

Figure 4. Four-valued logic

Figure 5. Five-valued logic.

Figure 6. Six-valued logic is presented by two of 8260 branches. The first branch contains 0, the second branch contains $x$. The first branch has 2 subbranches. The first subbranch is presented in the first diagram by one of 20 isomorphic parts, the second branch is presented in the second diagram. The third diagram presents the communication between all isomorphic parts of the first subbranch. A name of a part is a name of subalgebra which has the minimal name on level 2 of the part (000001 in the first diagram). There are subalgebras belonging to several parts, the subalgebras are placed on boundaries of the parts, the boundaries are isomorphic as it follows from the third diagram. The second branch is presented by 3 of 165 isolated subbranches. The fourth diagram contains one of 60 isomorphic parts of the first subbranch and one of 60 isomorphic parts of the second subbranch. Communications of both parts with the other parts are more complex than communications in the third diagram. The last diagram presents the third branch entirely. Each of the first and second subbranches has 60 isomorphic subbranches, the third branch has 45 isomorphic.


References

  1. Lukasievisz J. O logice tro jwartosciowej. Ruch Filozoficny (1920) 5, 170-171 (Polish).
  2. Post E. L. Determination of all closed systems of truth tables. Bulletin Amer. Math. Society (1920) 26, 437.
  3. Post E. L. Introduction to a general theory of elementary propositions. Amer. J. Math., 43, No 4, 163-185 (1921).
  4. Mal’cev A. I. Iterative Post algebras.NGU, Novosibirsk (1976) (in Russian).
  5. Miyakawa M., Stojmenovic I., Lau D., Rosenberg I., Classifications and basis enumerations in many-valued logics - a survey, 17-th Int. Symp. on Multiple-Valued Logic, Boston, 152-160 (1987).
  6. Rosenberg I. Mal’cev algebras for universal algebra terms, Conference: Algebraic Logic and Universal Algebra in Computer Science, proceedings of conference, 195-208 (1988).
  7. Lau D. Function algebras on finite sets, Springer, Berlin, 2006.
  8. Post E. L. Two-valued iterative systems of mathematical logic. Princeton Univ. Press, Princeton, 1941.
  9. Malkov M. A. Classification of Boolean functions and their closed sets, SOP Trans. of applied Math. 1 No 2, 172-193 (2014).
  10. Malkov M. A. Classification of closed sets of functions in multi-valued logic, SOP Trans. on applied Math. 1 No 3, 96-105 (2014).
  11. Salomaa A. A. On infinitely generated sets of operations in infinite subalgebras, Ann. Univ. Turku, Ser A I, 74, 1-12 (1964).
  12. Bagynszki J., Demetrovics J. Linearis osztályok szerkezete primszám értékü logikában, Közl.-MTA Számitastech. Automat. Kutató Int. Budapest, 16, 25-53 (1976).
  13. Bagynszki J., Demetrovics J. The lattice of linear classes in prime-valued logics, Banach Center Publications (Warszava), 7, 105-123 (1982).
  14. Szendrey A. On closed sets of linear operations over a finite set of scuare-free cardinality, Electron. Informationnsverarb. Kybernet., 14, 547-559 (1978).
  15. Bagynszki J. The lattice of closed classes of linear functions defined over a finite ring of square-free order, K. Marx Univ. of Economics, Dept. of Math., Budapest, 2 (1979).
  16. Marchenkov S. S. Closed classes of three-valued logic that contain essentialy multi-place functions, Discrete Math. and Applications, 25 4, 233-240 (2015).
  17. Szendrei A. Idempotent reductions of abelian groups, Acta Sci. Math. (Szeged) 38, 171-182 (1976).
  18. Lau D. Uber die Anzahl von abgeschlossenen Mengen von linearen Functionen der n-werstigen Logik, Electron. Informationsverarb. Kybernet., 14, 567-569 (1978).
  19. Szendrei A. On the idempotent reductions of modulas I – II, Universal Algebra, Proc. Colloq., Esztergom/Hung. 1977, Colloq. Math. Soc. János Bolyai, 29, 753-780 (1982).
  20. Lau D. Uber abgeschlossene Mengen linearer Functionen in mehrwertigen Logiken, J. Inf. Process. Cybern. EIK, 24 7/8, 367-381 (1988).
  21. Marchenkov S. S. On closed classes of selfdual functions in multi-valued logic, Problemy Kybernetiki, 36, 5-22 (1979).
  22. Marchenkov S. S., Demetrovics J., Hannak L. On closed classes of self-dual functions in P3, Methods of discrete analisis for solution of combinatorial problems, 34, 38-73 (1980).
  23. Zhuk D. N. The lattice of the clones of self-dual functions in three-valued logic, J. of Multiple-valued Logic and Soft Computing, 24, 1-4, 251-316 (2015).
  24. Marchenkov S. S. A-classification of idempotente functions in multi-valud logic, Discretn. Anal. Issled. Oper., Ser. 1, 6 1, 19-43 (1999).
  25. Rosenberg I. G. La structure des fonctions de plusieeurs variables sur un ensemble fini, C. R. Acad. Sci. Paris, Ser A-B, 260, 3817-3819 (1965).
  26. Rosenberg I. G. Uber die functionale Vollst andigkeit in der mehrwertigen Logiken, Rozpravy Ceskoslovenske Acad. Ved. Rada Mat. Prirod, 80, 3-93 (1970).
  27. Rosenberg I. G. The number of maximal closed classes in the set of functions over a finite domain, J. combinat. Theory, Ser. A 14, 1-7 (1973).
  28. Rosenberg I. G. Minimal clones I: The five types, Lectures in Universal Algebra (L. Szabo, A. Szendrei eds.), Colloq. Math. Soc. J. Bolyai, 43, 405-427 (1986).
  29. Rousseau G. Completeness in finite algebras with a single operation, Proc. Amer. Math. Soc., 18, 1009-1013 (1967).
  30. Schofield P. Independent conditions for completeness of finite alfebra with a single operator, J. London Math. Soc., 44, 413-423 (1969).
  31. Malkov M. A. Algebra of logic and Post algebra (the theory of two-valued functions), Math. Logic, Moscow (2012).

Article Tools
  Abstract
  PDF(669K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931