рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2026. Vol 55

On the Cardinality of the Lattice of Closed Classes of Polynomials in 𝑘-Valued Logic for Composite Numbers 𝑘

Author(s)

Svetlana N. Selezneva

Lomonosov Moscow State University, Moscow, Russian Federation

Abstract
Closed classes under superposition are examined in 𝑘-valued logic. E. Post established that the lattice (on inclusion) of all closed classes in two-valued logic is countable. Besides, each closed class has a finite basis in two-valued logic. Yu. I. Yanov and A. A. Muchnick proved that the lattice of all closed classes in 𝑘-valued logic is continuous at each 𝑘 > 3. Besides, there are closed classes without a basis and closes classes of a countable basis in 𝑘-valued logic at 𝑘 > 3. Because of the continuity on the lattice of all closed classes at 𝑘 > 3, its sub-lattices are examined. In particular, the closed class of all functions, that are represented by polynomials modulo 𝑘, is considered in 𝑘-valued logic. This closed class contains all functions of 𝑘-valued logic, if and only if 𝑘 is a prime number. If 𝑘 is a composite number, then this closed class is not even pre-complete. In works of A. N. Cherepov, A. B. Remizov, A. A. Krokhin, K. L. Safin, E. V. Sukhanov, D. G. Meschaninov and of others the structure of sub-lattices and of over-lattices is examined for the closed class of all polynomial functions at composites 𝑘. In this work at each composite number 𝑘 the continuity of the sub-lattice is established for the closed class of all polynomial functions in 𝑘-valued logic.
About the Authors
Svetlana N. Selezneva, Dr. Sci. (Phys.-Math.), Prof., Lomonosov Moscow State University, Moscow, 119991, Russian Federation, selezn@cs.msu.ru
For citation
Selezneva S. N. On the Cardinality of the Lattice of Closed Classes of Polynomials in 𝑘-Valued Logic for Composite Numbers 𝑘. The Bulletin of Irkutsk State University. Series Mathematics, 2026, vol. 55, pp. 123–133. (in Russian) https://doi.org/10.26516/1997-7670.2026.55.123
Keywords
𝑘-valued logic function, residue ring modulo 𝑘, polynomial, closed class, lattice of closed classes
UDC
519.716.5, 512.56, 512.714
MSC
06D25, 08A40, 13M10
DOI
https://doi.org/10.26516/1997-7670.2026.55.123
References
  1. Ayzenberg N.N., Semyon I.V. Nekotorye kriterii predstavimosti funktsiy 𝑘-znachnoy logiki polinomami po modulyu 𝑘 [Some Criteria for the Representability of 𝑘- Valued Logic Functions by Polynomials Modulo 𝑘]. Mnogoustoychivye elementy i ikh primenenie [Multi-Stable Elements and Their Application]. Moscow, Sovetskoe radio Publ., 1971, pp. 84–88. (in Russian)
  2. Ayzenberg N.N., Semyon I.V., Tsitkin A.I. Moschnost klassa funktsiy 𝑘-znachnoy logiki ot 𝑛 peremennykh, predstavimykh polinomami po modulyu 𝑘 [The Cardinality of the Class of 𝑘-Valued Logic 𝑛 Variables Functions which are Represented by Polynomials Modulo 𝑘]. Mnogoustoychivye elementy i ikh primenenie [Multi-Stable Elements and Their Application]. Moscow, Sovetskoe radio Publ., 1971, pp. 79–83. (in Russian)
  3. Krokhin A.A., Safin K.L., Sukhanov E.V. The Structure of the Lattice of Closed Classes of Polynomials. Discrete Math. Appl., 1997, vol. 7, no. 2, pp. 131–146. https://doi.org/10.1515/dma.1997.7.2.131
  4. Marchenkov S.S. Funktsionalnye sistemy s operatsiey superpositsii [Functional Systems with a Superposition Operation]. Moscow, Fizmatlit Publ., 2004, 104 p. (in Russian)
  5. Meshchaninov D.G. Closed Classes of Polynomials Modulo 𝑝2. Discrete Math. Appl., 2018, vol. 28, no. 3, pp. 167–178. https://doi.org/10.1515/dma-2018-0016
  6. Meshchaninov D.G. A method for Constructing Polynomials for Functions of 𝑘-Valued Logic. Discrete Math. Appl., 1995, vol. 5, no. 4, pp. 333–346. https://doi.org/10.1515/dma.1995.5.4.333
  7. Remizov A.B. The Overstructure of a Closed Class of Polynomials Modulo 𝑘. Discrete Math. Appl., 1991, vol. 1, no. 1, pp. 9–22. https://doi.org/10.1515/dma.1991.1.1.9
  8. Selezneva S.N. On the Number of Functions of 𝑘-Valued Logic which are Polynomials Modulo Composite 𝑘. Discrete Math. Appl., 2017, vol. 27, no. 1, pp. 7–14. https://doi.org/10.1515/dma-2017-0002
  9. Cherepov A.N. Description in 𝑃𝑘 for Structure of Closed classes which contain the class of polynomial. Problemy kibernetiki [Problems of Cybernetics]. Moscow, Nauka Publ., vol. 40, 1983, pp. 5–18. (in Russian)
  10. Yablonskiy S.V. Funktsionalnye postroeniya v 𝑘-znachnoy logike [Functional Constructions in 𝑘-Valued Logic]. Trudy Mat. Inst. Steklov Acad. Sci. SSSR [Proc. of Steklov Mathematical Institute of the USSR Academy of Sciences]. Moscow, 1958, vol. 51, pp. 5–142. (in Russian)
  11. Yanov Yu.I., Muchnik A.A. O suschestvovanii 𝑘-znachnykh zamknutykh klassov, ne imeyuschikh konechnogo basisa [On Existing of 𝑘-Valued Closed Classes which Have not a Finite Basis]. Dokl. Acad. Nauk SSSR [Reports of the USSR Academy of Sciences], 1959, vol. 127, no. 1, pp. 44–46. (in Russian)
  12. Post E. L. Introduction to a general theory of elementary propositions. Amer. J. Math., 1921, vol. 43, no. 4, pp. 163–185.

Full text (russian)