Post's thesis and wrong Janov-Mucnik's statement in multi-valued logic
Maydim A. Malkov
Russian Research Center for Artificial Intelligence, Moscow, Russia
Email address:
To cite this article:
Maydim A. Malkov. Post's thesis and wrong Janov-Mucnik's statement in multi-valued logic. Pure and Applied Mathematics Journal. Vol. 4, No. 4, 2015, pp. 172-177. doi: 10.11648/j.pamj.20150404.16
Abstract: Post stated that multi-valued logic has no principle difference with respect to two-valued logic. But Janov and Mucnik stated that multi-valued logic has essentially difference with respect to two-valued logic. We show that Post’s thesis is well but Janov-Mucnik’s statement is wrong.
Keywords: Multi-Valued Logic, Post Algebra, Fictitious Closed Sets of Functions, Classification of Function
1. Introduction
Multi-valued logic attracts the intense attention because of the connection with computer technology.
Post ([1], 1921) stated that multi-valued logic has no principle difference with respect to two-valued logic. In particular, he proved that every predicate of multi-valued logic can be presented by logical formula with connectives and , as in 2-valued logic. But Janov and Munik ([2], 1959) stated that multi-valued logic has essentially difference with respect to two-valued logic because there are continuum of closed sets of functions. But these closed sets are fictitious objects of multi-valued logic. It is natural that the number of fictitious object is continuum since almost every theory has infinitely more fictitious objects with respect to essential objects. And multi-valued logic has countable number of essential closed sets. Two-valued logic has countable number of essential closed sets, too.
This paper is devoted to confirm Post’s thesis.
2. Conjunctive (CNF) and Disjunctive (DNF) Normal Forms in Multi-Valued Logic
These normal forms use connectives , and .
Post gave definitions of the connectives. He produced them by computable functions: , , and . These definitions hold in 2-valued logic too.
Definitions of CNF and DNF in multi-valued logic differ from definitions in 2-valued logic only by number of negations: CNF is conjunction of disjuncts of literals, DNF is a disjunction of conjuncts of literals, literals are logical variables with or without negations.
If we have a table (a sequence of lines) of a function then we can build full CNF and full DNF corresponding to the function. And we build full DNF by using the next rule, which holds as in 2-valued logic as in multi-valued logic:
• we create a sequence of lines of the table such that the lines have value in function-column,
• we delete in lines of the sequence,
• we replace value of -th variable in every line of the sequence by ,
• these lines connected by create full DNF.
The similar rule exists for full CNF too.
Reduced DNFs have no superfluous literals with respect to full DNFs, shortest DNFs have no superfluous conjuncts. These DNFs are built in multi-valued logic as in 2-valued logic.
Instead of DNF Post used expansion of a function in 2-valued logic: (DNF, DNF), where DNF is DNF of a function and DNF is DNF of negation of the function. In -valued logic an expansion of a function is (DNF, DNF,...,DNF). Hear DNF is DNF of a function, DNF is DNF of negation of the function, DNF is DNF of -times negation of the function.
Post used the expansion to build classification of Boolean functions. And we can use the expansion to build classification of functions of multi-valued logic.
We have similar results for CNFs.
This confirms Post’s thesis.
3. Classification of Functions
3.1. Preiterative Algebra
Now there are 3 algebras for classification of functions: Post (or preiterative), Mal’cev (or iterative) and clone algebras.
Mal’cev gave mathematically precise definitions of preiterative and iterative algebras. By Mal’cev, preiterative algebra has 4 primitive operations: cyclic permutation of variables of a function, permutation of two variables, identification of two variables and substitution a function into a function (for more details see below). Iterative algebra has one more operation that adds fictitious variables in a function.
Unfortunately, preiterative algebra is ignored by contemporary researches. For example, the monograph [3] used only iterative and clone algebras. Only Rosenberg displayed an interest for Mal’cev’s results. He devoted one of his works [4] to Mal’cev. He marked "Preiterative sets are slightly more general than clones". In reality, the preiterative algebra is more general than the algebra of clones (Rosenberg used "sets" instead of "algebra"). But Rosenberg continues to use only iterative and clone algebras since the algebras are more simple to get new results.
Mal’cev called iterative algebra Post iterative algebra. But Post did not use the algebra. Therefore we call it Mal’cev algebra.
Mal’cev algebra is a part of Post algebra. And clone algebra is a part of Mal’cev algebra.
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. Only they generate closed sets of functions.
These fundamental operations are primitives.
Primitives are those operations that build all other operations. The formal definitions of primitives were given by Mal’cev [5]. We have generalized the definitions.
By informally, the primitive is the cyclic operation: a function becomes the function . The primitive is permutation operation: a function becomes the function . The primitive is identification operation: a function becomes the function . The primitive * is a substitution operation: a function and a function become the function .
Sometimes the operation of adding a fictitious variable is considered as primitive. It was shown [6] that this operation is not primitive since fictitious functions add fictitious variables to a function by using the substitution operation, but fictitious functions can be generated by essential functions.
Algebras with and exist too. Using the formula for number of functions of arity , we find that the universe is empty at and that the universe contains only functions of arity 1 at . Algebra with exists too, and it has countable number of functions for every .
Again Post’s thesis is confirmed.
3.2. Family of Functions and First Equivalence Relation
We will prove that there are 6 levels of classification of functions. The same levels of classifications exist in 2-valued logic. This confirms Post’s thesis.
A family is a set of functions with the same type of diagonals. We will call families of functions with the same type of diagonals briefly families.
Families were introduced by Post. There are 4 families in two-valued logic: , , , . Post’s classification of function and of their closed sets is based on the families.
Families of functions exist for all including . The number of these families is .
The family is defined standardly: . The family is defined standardly, too: . Definitions of the other families are special in -valued logics since the logic has constants. But the definitions are an extension of Post’s definitions and they hold for 2-valued logic too.
We denote all families by , where . And every function of a family has the diagonal equal to if , and not equal to if , i.e., if only . We say that a function of a family preserves values .
Therefore we denote family by and family by . A constant belongs to 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 . Functions of the families preserve 1 and 0 respectively.
We call functions of or of families or .
The next theorem is useful.
Theorem Any function of family generates functions of family .
Proof. The operations of permutations 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 , be the substitution of into , and denotation of family of be .
Then for all . In this case for all , therefore . If for all then since, by definition, and for all . But if for some then this . In this case . The proof is finished.
Corollary A function of the family generates only function of this family. A function of the family can 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 any family with denotation .
The Webb function and all other generators of P (usually they are named Sheffer functions) can belong only to the family for all including .
Families realize a natural classification of functions since they are disjoint. This means that there is an equivalence relation.
Definition Two functions are equivalent if they belong to the same family.
Families realize the first level of the function classification. There are 6 levels of the classification.
3.3. Types of Functions and Second Equivalence Relation
In 2-valued logic Post defined 2 conditions and for functions. In -valued logic there are conditions . And this holds for all including .
In the next definition we call tuple a line of a table of a function with value of the function. A tuple contains only values of variables of a function since the value of the function is pointed out by the subscript. And we call a column a part of a column in a table such that the part belongs to all tuple of a function.
Definition A function satisfies a condition
• () if every of tuples in the table of the function has a column with value of variables and if there exist tuples which have no column with value of variables,
• () if all tuples have a column with value , the number of tuples equals m.
If a function does not satisfy a condition of the first part of definition then the function satisfies a condition of the second part of definition. Indeed, let a function do not satisfy . Then all tuples are absent or tuples exist but tuples are absent. In the former case the function satisfies the condition . In the latter case the function satisfies the condition .
So, a function satisfies the condition if tuples are absent. If tuples exist but the value is absent in some tuple, then the function satisfies condition . A constant satisfies if (since the constant is not equal ) and satisfies (since the constant equals =j).
The conditions and a name of a family form a type.
Definition The type of a function is .
And the type of a constant is .
Every function belongs only to one type.
Definition Two functions are equivalent by the second equivalence relation if they have the same type.
The first equivalence relation divides the set of all functions into families. The second equivalence relation divides families into subfamilies with the same type.
3.4. Classes of Compositions of Function
Closed sets of functions are called sometimes classes. This is not well since classes must be disjoint. But a closed set can contain other closed sets, therefore these closed sets are disjoint.
A closed set becomes empty or not empty after removing closed sets contained into it. Now we use only closed sets that become non-empty after removing their closed sets.
Definition A class of function’s compositions is a non-empty part of a closed set remaining after removing all other closed sets from the closed set.
Further we call classes of function’s compositions briefly classes. A name of a class is a name of a closed set containing the class.
Theorem Classes are disjoin.
Proof. Any function generates a closed set. Every function of a class generates its closed set . This function cannot belong to a class of a closed set contained in since, by definition, the function does not belong to any closed set contained in . And the function cannot belong to a class of another closed set since the function generates only the closed set .
So any function of a class of a closed set is the member of one membered basis of the closed set. We must take one of these functions as a representative of bases. For that we introduce an order of functions.
Definition A function is greater than if the arity of is greater than the arity of . If the arity of equals the arity of then whenever , where is the ordinal number of : the ordinal is the contents of the column with values of the function at reading the column from top to down.
Definition The minimal function of a class of a closed set is called the generator of the closed set.
So the representative of bases of a closed set is its generator.
3.5. Third Equivalence Relation
We must prove that all functions of a class have the same type. Before we must prove one lemma. And, for simplification, we will say that a function has if it satisfies a condition .
Lemma All functions of a class belong to the same family.
Proof. By the theorem of the previous subsection, functions generate only functions. Therefore a class containing an function contains only functions and its closed set contains only functions, too. By the theorem, functions of the family can generate only functions of the family and functions. A class containing a function of family contains only function of the family since functions do not belong to the class. By the theorem, functions of a family generate functions of the family and of a family , but functions of families and belong to different classes. This means that a class containing a function of a family contains functions only of the family .
Theorem All functions of a class have the same type.
Proof. It is enough to prove that the functions satisfy the same conditions. And the conditions are or . At first we will prove two preliminary statements and then we will prove the theorem.
• Let a function of a class be the generator of the class and satisfy a condition for some . We must prove the statement that generates the class of functions with . For that we will use the induction rule.
If then generates functions with . The statement holds in this case. Let all functions of a class have if the class is generated by with and let now have . Then generates class of functions with since functions with belong to the other classes. The statement is proved.
• Let a function of a class be the generator of the class and satisfy a condition for some . We must prove the statement that generates the class of functions with . For that we will use the induction rule.
If then and all functions of the class generated by have . The statement holds in this case. Let all functions of a class have if the class is generated by with and let now have . Then generates the class of functions with since functions with belong to the other classes. The statement is proved.
• All functions of a class have the same .
Indeed, let a function have and let a function have . Then the function cannot generate the function . Hence the functions cannot belong to the same class. Only functions with the same can belong to the same class.
This means that classes create the third level of the classification.
Definition Two functions are equivalent by the third equivalence relation if they belong to the same class.
The third equivalence relation continues the classification of functions: the set of functions is divided into families, every family has subfamilies, every subfamily has classes.
3.6. Functions with the Same Range and Fourth Equivalence Relation
Classes of compositions have subclasses of functions with the same range.
Indeed, if a function has a range with one member then the function is a constant or the function is fictitious. Hence, in this case a closed set contains only the constant or contains the function, a constant generated by the function, and all fictitious functions of the same range.
A class of a closed set containing only a constant has only the constant. The class of closed sets containing a constant and its fictitious functions has only the fictitious functions.
If a function has a range with two members then the function can generate functions that have ranges with one or two members. The functions, which have ranges with two members, form a class, since the functions, which have ranges with one member, belong to the other classes.
And so on.
The next equivalence relation continues the classification of functions.
Definition Two functions are equivalent by the fourth equivalence relation if they have the same range.
This is the forth level of the classification.
We call a range containing not all values and all subsets of the range a partial range. There are partial complete generators of all functions with the same partial range.
Definition A complete generator is a generator of all functions. Complete generators usually are called Sheffer functions. A partial complete generator is a generator of all functions that have the same partial range.
If then there are 60 partial generators for every partial range with 2 values [7] (there are 3 such partial ranges: , , ). And there are 3 774 complete generators [9].
If then every of the subclasses has 13 920 partial complete generators for every partial range with 2 values and has 5 494 944 partial complete generators for every partial range with 3 values [8]. There are 942 897 552 complete generators [8].
3.7. Fictitious Functions and Fifth Equivalence Relation
If a subclass has a fictitious function of two or more arity then the subclass contains infinite number of fictitious functions since every essential function has infinite number of fictitious functions by adding fictitious variables to the essential function.
Fictitious functions are superfluous. They are absent in applied algebras. But in abstract algebras fictitious functions are used for construction other functions. For example, the construction of recursive functions uses fictitious functions although the functions can be constructed without fictitious functions.
The next equivalence relation continues the classification of functions.
Definition Two functions are equivalent by the fifth equivalence relation if they are both essential or they are both fictitious.
We use the relation to construct classes of the fifth level. The classes are subclasses of classes of the previous level. The classes of the fifth level allow us to isolate fictitious functions from essential. There is a bijection between all classes of essential functions of the preiterative algebra and all classes of the iterative algebra. A pare of classes of the algebras becomes equal if we remove fictitious functions in the iterative algebra. So all properties of functions in the iterative algebra can be found in the preiterative algebra.
3.8. Functions with Renumbered Variables and Sixth Equivalence Relation
The other superfluous functions are functions with renumbered variables since a numeration of variables of a new constructed function is subjective. A renumeration of variables of a function does not change the essence of the function but changes the structure of table of the function. Hence the table becomes new and we have a new function that is superfluous. So we must take only one of functions with renumbered variables. For that we take the minimal function from the functions. We call the function non-renumbered and we call the other functions renumbered.
We continue to classify functions.
Definition Two functions are equivalent by the sixth equivalence relation if they both are non-renumbered or if they both are renumbered.
This relation allows us to construct classes of the sixth level. The classes are subclasses of classes of fifth level. And we isolate non-renumbered functions from renumbered.
One non-renumbered function has a finite number of its renumbered. But the number is very big at large .
So we have constructed 6 levels of classification of functions. Two-valued logic has the same 6 levels [6]. This confirms Post’s thesis.
4. Classification of Closed Sets and Fictitious Closed Sets
4.1. Classification of Closed Sets
There are two theories: the theory of -valued functions and the theory of closed sets of -valued functions.
The main problem of any theory is classification of its objects. The next problem is to find fictitious (useless) objects and to remove them.
We have constructed classification of objects of the first theory, they are functions. We have found that fictitious objects are fictitious functions or renumbered functions. And we have isolated the fictitious objects.
Now we construct the classification of objects of the second theory. These objects are closed sets.
Again we use natural classification of objects: every object belongs only to one class and classes are disjoint. For that we use the number of members contained in minimal bases of closed sets.
Every infinite closed set has infinite number of bases. We use the minimal basis: a basis is minimal if it has the least number of members. If there are several bases with the number of members then we use the basis which maximal member is minimal among the other bases (we do not use basis with minimal member among the other bases since a basis with the minimal member can have very big maximal member). If we have several such bases then we use the pre-maximal members and so on.
We introduce the next classification of closed sets.
Definition The class of closed sets contains closed sets without a basis. The class of closed sets contains closed sets with membered minimal basis. The class of closed sets contains closed sets only with infinite bases.
This classification covers all closed sets and every closed set belongs to only one of classes. This means that classes of closed sets are disjoint. Below we call classes of closed sets briefly classes.
There are 3 classes if : , , and [10]. And there are all classes if [11].
Each class with finite has countable closed sets. The class has continuum closed sets [11].
A member of is a closed set that is upper limit of the sequence of closed sets of such that any member of the sequence contains the previous closed set [11].
Any member of is a closed set that does not contain other closed sets or contains other closed sets but it becomes not empty after removing the sets. By the previous section, contains all classes of functions.
Any member of is a union of closed sets of . This member becomes empty after removing all of the closed sets from it.
Any member of is a closed set containing infinite number of closed sets of such that the union of any pare of the closed sets is a member of .
4.2. Fictitious Closed Sets
Every function generates some closed set. The other closed sets are fictitious (useless)^{i}. Only the class does not contain fictitious closed sets. We have used its closed sets to construct the classification of functions. Every essential closed sets of the classification become a class of functions after removing the other closed sets contained in the closed set. Fictitious closed sets become empty after removing closed sets contained in it. Therefore fictitious closed sets are useless for the classification of functions like fictitious variables are useless for calculation of functions.
Only the class contains the 6 levels of the more deep classification, the other classes have only one level. But we have constructed the more deep classification of fictitious closed sets for [10], and this classification has demonstrated useless of the construction.
Any theory must give a classification of all theory’s objects including fictitious. But it is enough to construct only the first level of the classification of fictitious objects since fictitious objects need not in a more deep classification.
By Janov and Munik [2], multi-valued logic is essentially different with respect to two-valued logic since we have continuum of closed sets of functions. But except closed sets of , all closed sets are fictitious, i.e. useless and superfluous. Closed sets of are countable.
Fictitious objects are in any theory and there number, as a rule, is infinity more with respect to the number of essential objects. In the theory of functions we have infinite number of fictitious functions for every essential function (by adding fictitious variables). So it is natural that the number of fictitious closed sets is continuum but the number of essential closed sets is countable.
So, we have shown that conjunctive and disjunctive normal forms are the same as in 2-valued logic as in multi-valued logic. We have shown that Post algebra holds for all logics including -valued logic. We have shown that there are 6 levels of classification of functions, they are the same as in 2-valued logic as in multi-valued logic. We have built the classification of closed sets of functions for all logics. There are essential and fictitious closed sets, the number of essential closed sets is countable (in all logics) and the number of fictitious sets is continuum. But fictitious closed sets are useless and usually are excluded. All this means that Post’s thesis is well and Janov-Munik’s statement is wrong.
References
^{i} Do not confuse fictitious closed sets and fictitious functions. There are fictitious closed sets of non-fictitious functions and non-fictitious closed sets of fictitious functions.