Super-De Morgan functions and free De Morgan quasilattices

Yuri Movsisyan ; Vahagn Aslanyan

Open Mathematics, Tome 12 (2014), p. 1749-1761 / Harvested from The Polish Digital Mathematics Library

Résumé

A De Morgan quasilattice is an algebra satisfying hyperidentities of the variety of De Morgan algebras (lattices). In this paper we give a functional representation of the free n-generated De Morgan quasilattice with two binary and one unary operations. Namely, we define the concept of super-De Morgan function and prove that the free De Morgan quasilattice with two binary and one unary operations on nfree generators is isomorphic to the De Morgan quasilattice of super-De Morgan functions of nvariables.

Détail

Publié le : 2014-01-01

Zbl 06335869

EUDML-ID : urn:eudml:doc:268963

Bibliographie

[1] Anosov A.D., On homomorphisms of many-sorted algebraic systems in connection with cryptographic applications, Discrete Math. Appl., 2007, 17(4), 331–347. http://dx.doi.org/10.1515/dma.2007.028 | Zbl 1282.08005

[2] Arieli O., Avron A., The value of four values, Artificial Intelligence, 1998, 102, 97–141. http://dx.doi.org/10.1016/S0004-3702(98)00032-0 | Zbl 0928.03025

[3] Balbes R., Dwinger P., Distributive lattices, Univ. of Missouri Press, 1974. | Zbl 0321.06012

[4] Belnap N.D., A useful four valued logic, in: G. Epstein, J.M. Dunn (Eds)., Modern Uses of Multiple-Valued Logic, Reidel Publishing Comnpany, Boston, 1977, 7–73.

[5] Belousov V.D., Systems of quasigroups with generalized identities, Uspekhi Mat. Nauk, 1965, 20, 75–144. English transl. in Russian Math. Surveys 1965, 20, 73–143. | Zbl 0135.03503

[6] Berman J., Blok W., Stipulations, multi-valued logic and De Morgan algebras, Multi-valued Logic 2001, 7(5–6), 391–416. | Zbl 1016.03068

[7] Birkhoff G., Lattice Theory. 3rd edn., American Mathematical Society, Providence, Rhode Island, 1967.

[8] Bou F., Rivieccio U., The logic of distributive bilattices, Log. J. IGPL, 2011, 19, 183–216. http://dx.doi.org/10.1093/jigpal/jzq041 | Zbl 1214.03056

[9] Brzozowski J.A., A characterization of De Morgan algebras, International Journal of Algebra and Computation, 2001, 11, 525–527. http://dx.doi.org/10.1142/S0218196701000681 | Zbl 1025.06007

[10] Brzozowski J.A., De Morgan bisemilattices, Proceedings of the 30th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2000), May 23–25, 2000, p.173.

[11] Brzozowski J.A., Partially ordered structures for hazard detection, Special Session: The Many Lives of Lattice Theory, Joint Mathematics Meetings, San Diego, CA, January 6–9, 2002.

[12] Church A., Introduction to Mathematical Logic, Vol.1, Princeton University Press, Princeton, NJ 1956. (Volume 2 was newer published) | Zbl 0073.24301

[13] Crama Y., Hammer P.L., Boolean Functions: Theory, Algorithms, and Applications, Cambridge University Press, New York, 2011. http://dx.doi.org/10.1017/CBO9780511852008 | Zbl 1237.06001

[14] Denecke K., Wismath Sh.L., Hyperidentities and Clones, Gordon and Breach Science Publishers, 2000. | Zbl 0960.08001

[15] Gehrke M., Walker C., Walker E., A mathematical setting for fuzzy logics, Int. Journ. of Uncertainty, Fuzziness and Knowledge-based Systems 1997, 5(3), 223–238. http://dx.doi.org/10.1142/S021848859700021X | Zbl 1232.03016

[16] Gehrke M., Walker C., Walker E., Some comments on fuzzy normal forms, Proc. of the ninth IEEE Int. Conf. on Fuzzy Systems, FUZZ-IEEE, 2000, 7, 593–598.

[17] Grätzer G., Lattice Theory: Foundation, Springer Basel AG, 2011. | Zbl 1233.06001

[18] Grätzer G., Universal Algebra, Springer-Verlag, 2010.

[19] Hazewinkel M. (Editor), Handbook of algebra, Vol. 2, North-Holland, 2000.

[20] Kalman J.A., Lattices with involution, Trans. Amer. Math. Soc., 1958, 87, 485–491. http://dx.doi.org/10.1090/S0002-9947-1958-0095135-X | Zbl 0228.06003

[21] Kauffman L.H., 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.

[22] Kondo M., Characterization theorem of 4-valued De Morgan logic, Mem. Fac. Sci. Eng. Shimane Univ., Series B: Mathematical Science, 1998, 31, 73–80. | Zbl 0929.03032

[23] Koppitz J., Denecke K., M-Solid Varieties of Algebras, Springer, 2006. | Zbl 1094.08001

[24] Maltsev A.I., Algebraic systems, Grundlehren der mathematishen Wissenschaften, Vol.192, Springer-Verlag, New-York. | Zbl 1112.37052

[25] Maltsev A.I., Some questions of the theory of classes of models, Proceedeings of the fourth All-Union Mathematics Congress, 1963, 1, 169–190 (Russian).

[26] Markov A.A., Constructive logic (in Russian), Uspekhi Mat. Nauk, 1950, 5, 187–188.

[27] Melkonian V., Circuit integrating through lattice hyperterms,Discrete Math. Algorithms Appl., 2011, 3(1), 101–119. http://dx.doi.org/10.1142/S179383091100105X | Zbl 1219.90145

[28] Mobasher B., Pigozzi D., Slutzki G., Multi-valued logic programming semantics, An algebraic approach, Theorit. Comput. Sci., 1997, 171, 77–109. http://dx.doi.org/10.1016/S0304-3975(96)00126-0 | Zbl 0874.68046

[29] Moisil G.C., Recherches sur l’algebre de la logique, Annales scientifiques de l’universite de Jassy, 1935, 22, 1–117.

[30] Movsisyan Yu.M., Binary representations of algebras with at most two binary operations. A Cayley theorem for distributive lattices, International Journal of Algebra and Computation, 2009, 19(1), 97–106. http://dx.doi.org/10.1142/S0218196709004993 | Zbl 1174.06006

[31] Movsisyan Yu.M., Introduction to the theory of algebras with hyperidentities, Yerevan State University Press, Yerevan, 1986 (Russian). | Zbl 0675.08001

[32] Movsisyan Yu.M., Hyperidentities and hypervarieties in algebras, Yerevan State University Press, Yerevan, 1990 (Russian). | Zbl 0728.08013

[33] Movsisyan Yu.M., Bilattices and hyperidentities, Proc. Steclov Inst. Math., 2011, 274, 174–192. http://dx.doi.org/10.1134/S0081543811060113

[34] Movsisyan Yu.M., Hyperidentities of Boolean algebras, Izv. Ross. Akad. Nauk Ser.Mat., 1992, 56(3), 654–672. English transl. in Russ.Acad.Sci Izv. Math., 1993, 40, 607–622. | Zbl 0773.08003

[35] Movsisyan Yu.M., Hyperidentities in algebras and varieties, Uspekhi Mat. Nauk, 1998, 53(1(319)), 61–114. English transl. in Russian Math. Surveys 1998, 53(1), 57–108. http://dx.doi.org/10.4213/rm9

[36] Movsisyan Yu., Hyperidentities and hypervarieties, Sci. Math. Jpn., 2001, 54, 595–640. | Zbl 1003.08001

[37] Movsisyan Yu.M., On the representations of De Morgan algebras, Trends in logic III, Studialogica, Warsaw, 2005 http://www.ifispan.waw.pl/studialogica/Movsisyan.pdf

[38] Movsisyan, Yu.M., Boolean bisemigroups. Bigroups and local bigroups, CSIT Proceedings of the Conference, September 19–23, Yerevan, Armenia, 2005, 97–104.

[39] Movsisyan Yu.M., Interlaced, modular, distributive and Boolean bilattices, Armenian Journal of Mathematics, 2008, 1(3), 7–13. | Zbl 1281.06005

[40] Movsisyan Yu.M., Algebras with hyperidentities of the variety of Boolean algebras, Izv. Ross. Akad. Nauk Ser.Mat., 1996, 60(6), 127–168. English transl. in Russ.Acad.Sci.Izv. Math., 1996, 60, 1219–1260. http://dx.doi.org/10.4213/im98

[41] Movsisyan Yu.M., Aslanyan V.A., Hyperidentities of De Morgan algebras, Log. J. IGPL, 2012, 20, 1153–1174 (doi:10.1093/jigpal/jzr053). http://dx.doi.org/10.1093/jigpal/jzr053 | Zbl 1276.06005

[42] Movsisyan Yu.M., Aslanyan V.A., A functional representation of free De Morgan algebras, Proceedings of the Yerevan State University, Physical and Mathematical Sciences, 2012, 3, 14–16. | Zbl 1301.06028

[43] Movsisyan Yu.M., Aslanyan V.A., De Morgan functions and free De Morgan algebras, Demonstratio Math. http://www.mini.pw.edu.pl/demmath/papers_2008/2012-145-1.pdf.

[44] Movsisyan Yu.M., Aslanyan V.A., On computation of De Morgan and quasi-De Morgan functions, Computer Science and Information Technologies (CSIT), 2013, 1–6. IEEE Conference Publications (DOI: 10.1109/CSITechnol.2013.6710334). | Zbl 06323590

[45] Movsisyan Yu.M., Pashazadeh J., Matrix characterization of 4-ary algebraic operations of idempotent algebras, Comm. Algebra, 2014, 42, 2533–2541. http://dx.doi.org/10.1080/00927872.2013.824459 | Zbl 1303.08002

[46] Movsisyan Yu.M., Aslanyan V.A., A functional completeness theorem for De Morgan functions, Discrete Appl. Math., 2014, 162, 1–16. http://dx.doi.org/10.1016/j.dam.2013.08.006. http://dx.doi.org/10.1016/j.dam.2013.08.006 | Zbl 06344065

[47] Movsisyan Yu.M., Aslanyan V.A., Algebras with hyperidentities of the variety of De Morgan algebras, J. Contemp. Math. Anal., 2013, 5, 189–196. | Zbl 1302.06015

[48] Movsisyan Yu.M., Aslanyan V.A., Subdirectly irreducible algebras with hyperidentities of the variety of De Morgan algebras, J. Contemp. Math. Anal., 2013, 6, 52–58. | Zbl 1302.06016

[49] Movsisyan Yu.M., Aslanyan V.A., Boole-De Morgan algebras and quasi-De Morgan functions, Comm. Algebra (accepted). | Zbl 06323590

[50] Movsisyan Yu.M., Aslanyan V.A., Super-Boolean functions and free Boolean quasilattices, Discrete Math. Algorithm. Appl., 2014, 6(2), 1450024 (13 pages) (DOI: 10.1142/S179380914500244). http://dx.doi.org/10.1142/S1793830914500244

[51] Movsisyan Yu.M., Romanowska A.B., Smith J.D.H., Superproducts, hyperidentities, and algebraic structures of logic programming, Comb. Math. and Comb. Comp., 2006, 58, 101–111. | Zbl 1108.68028

[52] Sankappanavar H.P., A characterization of principal congruences of DeMorgan algebras and its applications, Math. Logic in Latin America, Proc. IV Latin Amer. Symp. Math. Logic, Santiago, (1978), 341–349. Nort-Holland Pub. Co., Amsterdam, 1980.

[53] Smith J.D.H., Romanowska A.B., Post-modern algebra, A Wiley-Interscience Publication, John Wiley and Sons, Inc., New York, 1999. http://dx.doi.org/10.1002/9781118032589 | Zbl 0946.00001

[54] Pashazadeh J., A characterization of De Morgan bisemigroup of binary functions, International Journal of Algebra and Computation, 2008, 18, 951–956. http://dx.doi.org/10.1142/S021819670800472X | Zbl 1158.06005

[55] Plotkin B.I., Universal algebra, algebraic logic, and databases, Kluwer Academic Publisher, 1994. http://dx.doi.org/10.1007/978-94-011-0820-1 | Zbl 0785.68025

[56] Taylor W., Hyperidentities and hypervarieties, Aequationes Math., 1981, 23, 30–49. http://dx.doi.org/10.1007/BF02188010 | Zbl 0491.08009