On implicit extensions in many-valued logic

S. S. Marchenkov

Diskretnaya Matematika, Tome 35 (2023) no. 2, pp. 34-41.

Résumé

We consider Kuznetsov's implicit expressibility and its generalizations, when the implicit expressibility language is augmented with the additional disjunction, implication, and negation logical connectives. It is shown that, for each $k\geqslant 3$, the implicit extensions in $P_k$ have the cardinality of the continuum. For each $k\geqslant 3$, we also prove that each of the sets of positively implicit, implicatively implicit, and negatively implicit extensions in $P_k$ contains, respectively, as a proper subset, the set of positively implicit, implicatively implicit, and negatively implicit closed classes. We verify that, for $k\geqslant 2$, the functions of the set $H_k^*$ of homogeneous functions preserving the set $E_{k-1}$ can be used for producing implicatively implicit and negatively implicit extensions without changing the result.

Détail

Keywords: implicit extension, many-valued logic.

Bibliographie

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

[2] Danilchenko A. F., “Parametricheski zamknutye klassy funktsii trekhznachnoi logiki”, Izvestiya AN MSSR, 2 (1978), 13–20 | Zbl

[3] Kasim-Zade O. M., “O neyavnoi vyrazimosti bulevykh funktsii”, Vestnik MGU. Ser. 1: Matem., mekhanika, 2 (1995), 44–49 | MR | Zbl

[4] Kasim-Zade O. M., “O neyavnoi vyrazimosti v dvuznachnoi logike i kriptoizomorfizmakh dvukhelementnykh algebr”, Doklady RAN, 348:3 (1996), 299–301 | MR | Zbl

[5] Kasim-Zade O. M., “O neyavnykh formakh vyrazimosti v mnogoznachnykh logikakh”, Mater. Vseross. konf. «Diskretnyi analiz i issledovanie operatsii» (Novosibirsk, iyun 2004 g.), Izd-vo IM SO RAN, Novosibirsk, 2004, 32–35

[6] Kasim-Zade O. M., “O neyavnoi polnote v $k$-znachnoi logike”, Vestnik MGU. Ser. 1. Matem., mekhanika, 3 (2007), 9–13 | Zbl

[7] Kuznetsov A. V., “O sredstvakh dlya obnaruzheniya nevyvodimosti i nevyrazimosti”, Logicheskii vyvod, Nauka, M., 1979, 5–33

[8] Marchenkov S. S., “Odnorodnye algebry”, Problemy kibernetiki, 39, Nauka, M., 1982, 85–106 | MR

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

[10] Marchenkov S. S., Operatory zamykaniya logiko-funktsionalnogo tipa, MAKS Press, M., 2012, 99 pp.

[11] Marchenkov S. S., Silnye operatory zamykaniya, Fizmatlit, M., 2017, 94 pp.

[12] Marchenkov S. S., “Neyavnaya vyrazimost v mnogoznachnoi logike”, Vestnik MGU. Ser. 15: Vychisl. matem. i kibern., 3 (2022), 41–48

[13] Orekhova E. A., “Ob odnom kriterii neyavnoi polnoty v $k$-znachnoi logike”, Matem. voprosy kibernetiki, 11 (2002), 77–90, Fizmatlit, M. | MR

[14] Orekhova E. A., “O kriterii neyavnoi shefferovosti v trekhznachnoi logike”, Diskret. analiz i issled. operatsii. Ser. 1, 10:3 (2003), 82–105 | MR | Zbl

[15] Orekhova E. A., “Ob odnom kriterii neyavnoi polnoty v trekhznachnoi logike”, Matematicheskie voprosy kibernetiki, 12 (2003), 27–74, Fizmatlit, M.

[16] Starostin M. V., “Neyavno predpolnye klassy i kriterii polnoty v trekhznachnoi logike”, Vestnik MGU. Ser. 1. Matem., mekhanika, 2 (2018), 182–184

[17] Starostin M. V., “O nekotorykh neyavno predpolnykh klassakh funktsii, sokhranyayuschikh podmnozhestva”, Vestnik MGU. Ser. 1. Matem., mekhanika, 6 (2018), 36–40 | Zbl

[18] Starostin M. V., “O nekotorykh neyavno predpolnykh klassakh monotonnykh funktsii v $P_k$”, Diskretnaya matematika, 30:4 (2018), 106–114 | DOI

[19] Yanov Yu. I., Muchnik A. A., “O suschestvovanii $k$-znachnykh zamknutykh klassov, ne imeyuschikh bazisa”, DAN SSSR, 127:1 (1959), 44–46 | Zbl

[20] Burris S., Willard R., “Finitely many primitive positive clones”, Proc. Amer. Math. Soc., 101:3 (1987), 427–430 | DOI | MR | Zbl

[21] Danil'čenko A. F., “On parametrical expressibility of the functions of $k$-valued logic”, Colloq. Math. Soc. J. Bolyai, 28 (1981), 147–159 | MR | Zbl