Finite Closed Sets of Functions in Multi-valued Logic
Pure and Applied Mathematics Journal
Volume 6, Issue 1, February 2017, Pages: 14-24
Received: Jan. 3, 2017; Accepted: Jan. 14, 2017; Published: Feb. 20, 2017
Views 3037      Downloads 100
Author
M. A. Malkov, Russian Research Center for Artificial Intelligence, Moscow, Russia
Article Tools
Follow on us
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
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
Copyright
Copyright © 2017 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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).
ADDRESS
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
U.S.A.
Tel: (001)347-983-5186