De Morgan functions and free De Morgan algebras

• Autorzy: Movsisyan Y. M. , Aslanyan V. A.
• Języki publikacji: EN

Abstrakty

EN

It is commonly known that the free Boolean algebra on n free generators is isomorphic to the Boolean algebra of Boolean functions of n variables. The free bounded distributive lattice on n free generators is isomorphic to the bounded lattice of monotone Boolean functions of n variables. In this paper, we introduce the concept of De Morgan function and prove that the free De Morgan algebra on n free generators is isomorphic to the De Morgan algebra of De Morgan functions of n variables. This is a solution of the problem suggested by B. I. Plotkin.

Słowa kluczowe

EN

De Morgan function; free De Morgan algebra; monotone Boolean function

PL

funkcja De Morgana; algebra De Morgana; funkcja monotoniczna

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2014
• Tom: Vol. 47, nr 2
• Strony: 271--283
• Opis fizyczny: Bibliogr. 36 poz.

Twórcy

autor

Movsisyan Y. M.

• Department of Mathematics and Mechanics, Yerevan State University, Alex Manoogian 1, Yerevan 0025, Armenia

autor

Aslanyan V. A.

• Department of Mathematics and Mechanics, Yerevan State University, Alex Manoogian 1, Yerevan 0025, Armenia

Bibliografia

• [1] O. Arieli, A. Avron, The value of four values, Artificial Intelligence 102 (1998), 97–141.
• [2] R. Balbes, P. Dwinger, Distributive lattices, Univ. of Missouri Press, 1974.
• [3] N. D. Belnap, A useful for valued logic, in: G. Epstein, J. M. Dunn (Eds.), Modern Uses of Multiple-Valued Logic, Reidel Publishing Company, Boston, 1977, 7–73.
• [4] J. Berman, W. Blok, Stipulations, multi-valued logic and De Morgan algebras, Multi-Valued Logic 7(5-6) (2001), 391–416.
• [5] A. Białynicki-Birula, H. Rasiowa, On the representation of quasi-Boolean algebras, Bull. Acad. Polon. Sci. Ser. Math. Astronom. Phys. 5 (1957), 259–261.
• [6] G. Birkhoff, Lattice Theory, 3rd Ed., American Mathematical Society, Providence, Rhode Island, 1967.
• [7] F. Bou, U. Rivieccio, The logic of distributive bilattices, Log. J. IGPL 19 (2011), 183–216.
• [8] J. A. Brzozowski, A characterization of De Morgan algebras, Internat. J. Algebra Comput. 11 (2001), 525–527.
• [9] J. A. Brzozowski, De Morgan bisemilattices, Proceedings of the 30th IEEE International Symposium on Multiple-Valued Logic, (ISMVL 2000), May 23–25, (2000), p. 173.
• [10] J. A. Brzozowski, Partially ordered structures for hazard detection, Special Session: The Many Lives of Lattice Theory, Joint Mathematics Meetings, San Diego, CA, January 6–9, (2002).
• [11] Y. Crama, P. L. Hammer, Boolean Functions: Theory, Algorithms, and Applications, Cambridge University Press, New York, 2011.
• [12] R. Dedekind, Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler, Festschrift der Techn. Hochsch. Braunschwig bei Gelegenheit der 69, Versammlung deutscher Naturforscher und Ärzte, (1897), 1–40.
• [13] Z. Ésik, Free De Morgan Bisemigroups and Bisemilattices, Algebra Colloquium, Volume 10, Issue 1, June (2003), 23–32.
• [14] M. Gehrke, C. Walker, E. Walker, A mathematical setting for fuzzy logics, Internat. J. Uncertain. Fuzziness Knowledge-Based Systems 5(3) (1997), 223–238.
• [15] M. Gehrke, C. Walker, E. Walker, Some comments on fuzzy normal forms, Proceedings of the ninth IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2000, vol. 2, 593–598.
• [16] G. Grätzer, Lattice Theory: Foundation, Springer, Basel AG, 2011.
• [17] G. Grätzer, Universal Algebra, Springer-Verlag, 2010.
• [18] J. A. Kalman, Lattices with involution, Trans. Amer. Math. Soc. 87 (1958), 485–491.
• [19] L. H. Kauffman, De Morgan Algebras - completeness and recursion, Proceedings of the eighth International Symposium on Multiple-Valued Logic, IEEE Computer Society Press Los Alamitos, CA, USA, (1978), 82–86.
• [20] M. Kondo, Characterization theorem of 4-valued De Morgan logic, Mem. Fac. Sci. Eng. Shimane Univ. Ser. B Math. Sci. 31 (1998), 73–80.
• [21] A. D. Korshunov, Monotone Boolean functions, Uspekhi Mat. Nauk 58:5(353) (2003), 89–162. English translation in: Russian Math. Surveys 58(5) (2003), 929–1001.
• [22] A. A. Markov, Constructive logic, Uspekhi Mat. Nauk 5 (1950), 187–188, (in Russian).
• [23] B. Mobasher, D. Pigozzi, G. Slutzki, Multi-valued logic programming semantics, An algebraic approach, Theoret. Comput. Sci. 171 (1997), 77–109.
• [24] G. C. Moisil, Recherches sur l’algebre de la logique, Annales scientifiques de l’Universite de Jassy 22 (1935), 1–117.
• [25] Yu. M. Movsisyan, Introduction to the theory of algebras with hyperidentities, Yerevan State University Press, Yerevan, 1986, (in Russian).
• [26] Yu. M. Movsisyan, Hyperidentities and hypervarieties in algebras, Yerevan State University Press, Yerevan, 1990, (in Russian).
• [27] Yu. M. Movsisyan, Hyperidentities of Boolean algebras, Izv. Ross. Akad. Nauk Ser. Mat. 56 (1992), 654–672. English translation in: Russian Acad. Sci. Izv. Math. 40 (1993), 607–622.
• [28] Yu. M. Movsisyan, Algebras with hyperidentities of the variety of Boolean algebras, Izv. Ross. Akad. Nauk Ser. Mat. 60 (1996), 127–168. English translation in: Russian Acad. Sci. Izv. Math. 60 (1996), 1219–1260.
• [29] Yu. M. Movsisyan, Hyperidentities in algebras and varieties, Uspekhi Mat. Nauk 53:1(319) (1998), 61–114. English translation in: Russian Math. Surveys 53(1) (1998), 57–108.
• [30] Yu. M. Movsisyan, Hyperidentities and hypervarieties, Sci. Math. Jpn. 54 (2001), 595–640.
• [31] Yu. M. Movsisyan, Binary representations of algebras with at most two binary operations. A Cayley theorem for distributive lattices, Internat. J. Algebra Comput. 19(1) (2009), 97–106.
• [32] Yu. M. Movsisyan, V. A. Aslanyan, Hyperidentities of De Morgan algebras, Log. J. IGPL 20 (2012), 1153–1174. doi:10.1093/jigpal/jzr053