Volume 8, Issue 1, February 2019, Page: 1-9
Algebra of Countably Functions and Theorems of Completeness
Maydim Malkov, Department of Mathematics, Research Center for Artificial Intelligence, Moscow, Russia
Received: Feb. 15, 2019;       Accepted: Mar. 18, 2019;       Published: Apr. 9, 2019
DOI: 10.11648/j.pamj.20190801.11      View  231      Downloads  64
Abstract
An algebraic approach to the theory of countable functions is given. Compositions (superpositions) of functions are used instead of recursions. Arithmetic and analytic algorithms are defined. All closed sets are founded. Mathematically precise definitions of logic algorithms with quantifiers of existence and universality are given. Logic algorithm for fast-growing function is built as example. Classification of functions is given. There are non-computable functions. These functions are fictitious (useless) and their set is continual. The set of computable functions is countable. Incompleteness of disjunction and negation, conjunction and negation, of Pierce, Sheffer and diagonal Webb functions is proved. The completeness of the set of one-place functions and any all-valued essential function (Slupecki theorem) is proved for computable functions. Existence of generators of all computable functions is proved too.
Keywords
Discrete Functions, Complete Sets of Functions, Algebra Countably-valued Functions, Logic Programming, Theory of Algorithms
To cite this article
Maydim Malkov, Algebra of Countably Functions and Theorems of Completeness, Pure and Applied Mathematics Journal. Vol. 8, No. 1, 2019, pp. 1-9. doi: 10.11648/j.pamj.20190801.11
Copyright
Copyright © 2019 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.
Reference
[1]
A. I. Mal'cev, Iterative Post algebras (Russian), Novosibirsk, Novosib. gos. un-t (1976).
[2]
S. V. Jablonskij, Functional constructions in k-valued logic (Russian), Tr. mat. inst. Steklova, 5-142 (1958).
[3]
E. L. Post, Two-valued iterative systems of mathematical logic, Princeton, Princeton Univ. Press (1941).
[4]
D. Lau, Functions algebra on finite sets, Berlin, Springer (2006).
[5]
S. S. Marchenkov, On FE-precomplete classes of countably valued logic (Russian), Discrete math., (2), 51–57 (2016).
[6]
A. I. Mal'cev, Iterative algebras ans Post manifold, (Russian), Algebra and logic, (2), 5-24 (1966).
[7]
A. Salomaa, On sequences of functions over an arbitrary system, Annales Universitatis Turkuensis AI (16), 5–13 (1963).
[8]
A. Salomaa, Some analogues of Sheffer functions in infinite-valued logics, Acta philosophica Fennica, 227-235 (1963).
[9]
G. P. Gavrilov, On functional completeness in countably valued logic, Problems of cybernetics, 5–64 (1965).
[10]
G. P. Gavrilov, Precomplete classes of parcially countably value logic contained all functions of a single variable (Russian), Discrete analysis methods in graph theory and logical functions, 12–24 (1976).
[11]
S. S. Marchenkov, On set power of precomplete classes in some classes of countably valued logic functions (Russian), Problems of cybernetics, 109–1981 (2015).
[12]
Ju. I. Janov, A. A. Muchnik, On existence of k-valued closed classes without finite basis (Russian), Dokl. Acad. Nauk SSSR, (1), 44–46 (1959).
[13]
IG Rosenberg, Über die functionale Vollständigkeit dem mehrvertigen Logiken von mehreren Verändlichen auf endlichen Mengen, Rozpravy Cs. Academie Ved, Ser. Math. Nat. Sci., 3-93 (1970).
[14]
M. A. Malkov, Classification of Boolean functions and their closed sets, SOP transactions on applied mathematics, (1), 1-20 (2014).
[15]
R. M. Robinson, Primitive recursive functions, Bull. Amer. Math. Soc., bf53, 925-942 (1947).
Browse journals by subject