On the structure of equationally closed classes

S. S. Marchenkov

Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 18-30.

Résumé

We study the structure of equationally closed classes. We prove a theorem on representation of the graph of a function in an equationally closed class in the form of a union of the sets of values of special vector functions. For any $k\ge2$ we establish the equational generability of any equationally closed class in $P_k$ by the set of all its $k$-place functions. We find all equationally precomplete classes in $P_k$ and prove a criterion of equational completeness. Some results are extended from equationally closed classes to positively closed classes.

Bibliographie

[1] Golunkov Yu. V., “Polnota sistem funktsii v operatornykh algoritmakh, realizuyuschikh funktsii $k$-znachnoi logiki”, Veroyatnostnye metody i kibernetika, 1980, no. 17, 23–34

[2] Danilchenko A. F., “O parametricheskoi vyrazimosti funktsii trekhznachnoi logiki”, Algebra i logika, 16:4 (1977), 397–416 | MR | Zbl

[3] Kuznetsov A. V., “O sredstvakh dlya obnaruzheniya nevyvodimosti i nevyrazimosti”, Logicheskii vyvod, Nauka, Moskva, 1979, 5–33 | MR

[4] Marchenkov S. S., Diskretnaya matematika, 9:3 (1997), 125–152 | Zbl

[5] Marchenkov S. S., “$A$-klassifikatsiya funktsii mnogoznachnoi logiki”, Dokl. RAN, 366:4 (1999), 455–457 | MR | Zbl

[6] Marchenkov S. S., “O vyrazimosti funktsii mnogoznachnoi logiki v nekotorykh logiko-funktsionalnykh yazykakh”, Diskretnaya matematika, 11:4 (1999), 110–126 | Zbl

[7] Marchenkov S. S., Zamknutye klassy bulevykh funktsii, Fizmatlit, Moskva, 2000

[8] Marchenkov S. S., S-klassifikatsiya funktsii trekhznachnoi logiki, Fizmatlit, Moskva, 2001

[9] Marchenkov S. S., “Operatory zamykaniya s razvetvleniem po predikatu”, Vestnik MGU. Seriya 1. Matematika. Mekhanika, 2003, no. 6, 37–39

[10] Marchenkov S. S., Funktsionalnye sistemy s operatsiei superpozitsii, Fizmatlit, Moskva, 2004

[11] Marchenkov S. S., “Ekvatsionalnoe zamykanie”, Diskretnaya matematika, 17:2 (2005), 117–126 | Zbl

[12] Nguen Van Khoa, “Ob $L$-ekvivalentnosti sistem funktsii v mnogoznachnykh logikakh”, Algebra i logika, 27:1 (1988), 37–47 | MR

[13] Nguen Van Khoa, “O $G$-polnykh zamknutykh klassakh $k$-znachnoi logiki”, EIK, 26:5/6 (1990), 301–313 | Zbl

[14] Nguen Van Khoa, “K opisaniyu semeistva $G$-polnykh zamknutykh klassov $k$-znachnoi logiki”, Kibernetika, 5 (1990), 9–12

[15] Nguen Van Khoa, “O strukture samodvoistvennykh zamknutykh klassov trekhznachnoi logiki $P_3$”, Diskretnaya matematika, 4:4 (1992), 82–95 | MR | Zbl

[16] Nguen Van Khoa, “O semeistvakh zamknutykh klassov $k$-znachnoi logiki, sokhranyaemykh vsemi avtomorfizmami”, Diskretnaya matematika, 5:4 (1993), 87–108 | Zbl

[17] Nguen Van Khoa, “O zamknutykh klassa $k$-znachnoi logiki, samodvoistvennykh otnositelno tranzitivnykh grupp”, Diskretnaya matematika, 8:1 (1998), 129–156

[18] Solovev V. D., “Zamknutye klassy v $k$-znachnoi logike s operatsiei razvetvleniya po predikatu”, Diskretnaya matematika, 2:4 (1990), 19–25 | MR

[19] Taimanov V. A., “O funktsionalnykh sistemakh $k$-znachnoi logiki s operatsiyami programmnogo tipa”, Dokl. AN SSSR, 268:6 (1983), 1307–1310 | MR | Zbl

[20] Tarasova O. S., “Klassy $k$-znachnoi logiki, zamknutye otnositelno rasshirennoi operatsii superpozitsii”, Vestnik MGU. Seriya 1. Matematika. Mekhanika, 2001, no. 6, 54–57

[21] Tarasova O. S., “Klassy funktsii trekhznachnoi logiki, zamknutye otnositelno operatsii superpozitsii i perestanovki”, Vestnik MGU. Seriya 1. Matematika. Mekhanika, 2004, no. 1, 25–29

[22] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1986