Finite Closed Sets of Functions in Multivalued 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 MultiValued Logic. Pure and Applied Mathematics Journal. Vol. 6, No. 1, 2017, pp. 1424.
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 kvalued logic. We build the classification of finite closed sets. The sets contain only constants and unary functions since sets containing even a twoary 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, Multivalued Logic, Function Classification
1. Introduction
Multivalued logic attracts intensive attention because of the connection with computer technology.
The first theories of multivalued 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 0ary 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 2valued (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 3valued 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 squarefree. S. S. Marchevkov (2015, [16]) defind all 23 closed sets of linear functions in threevalued logic. The other results were given in [1720,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 selfdual 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 nonfictitious 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 (nonfictitious) functions since, after removing the variablecolumn, 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 0ary 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 twoary 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 functioncolumn in number system, if we read the column from top to bottom. For example, the 3valued function with functioncolumn (0, 1, 2) has the number (3, 0*3^{2}+1*3^{1}+2*3^{0})=(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 twovalued 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 ≤ m≤ k1. 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 twovalued 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 onetoone 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. 46).
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 nonpermutation 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 threemembered. 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 ≤ k1 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 nonprime 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.
References