On bases of all closed classes of Boolean vector functions

V. A. Taimanov

Diskretnaya Matematika, Tome 34 (2022) no. 2, pp. 106-119.

Résumé

The functional system of Boolean vector functions with the naturally defined superposition operation is considered. It is shown that every closed class of this system admits a finite basis.

Détail

Keywords: Boolean vector function, superposition.

Bibliographie

[1] Yablonskii S.V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, M., 2003, 384 pp.

[2] Malcev I., “Graduated products of Post algebras”, Note on multiple-valued logic, 18:13 (1995), 1–4

[3] Malcev I., “Coordinated products of iterative algebras”, Proc. VIII Int. Conf. on logic and Computer Science, Novi Sad, Yugoslavia, 1997, 1–2 | MR

[4] Marchenkov S.S., “O polnote v sisteme $P_3 \times P_3$”, Diskretnaya matematika, 4:1 (1992), 126–145 | Zbl

[5] Marchenkov S.S., “O klassakh Slupetskogo v sistemakh $P_k \times \dots \times P_l$”, Diskretnaya matematika, 4:3 (1992), 135–148 | MR | Zbl

[6] Marchenkov S.S., “O predpolnykh klassakh v dekartovykh proizvedeniyakh $P_2$ i $P_3$”, Diskretnaya matematika, 6:2 (1994), 21–42 | Zbl

[7] Romov B.A., “Algoritm resheniya problemy polnoty v klasse vektornykh funktsionalnykh sistem”, Matem. modeli slozhnykh sistem., IK AN USSR, Kiev, 1973, 151–155

[8] Romov B.A., “O reshetke podalgebr pryamykh proizvedenii algebr Posta konechnoi stepeni”, Matem. modeli slozhnykh sistem., IK AN USSR, Kiev, 1973, 156–168

[9] Romov B.A., “O polnote na kvadrate funktsii algebry logiki i v sistemakh $P_k \times P_l$”, Kibernetika, 4 (1987), 9–14 | MR | Zbl

[10] Romov B.A., “Ob odnoi serii maksimalnykh podalgebr pryamykh proizvedenii algebr konechnoznachnykh logik”, Kibernetika, 3 (1989), 11–16 | MR | Zbl

[11] Romov B.A., “O funktsionalnoi polnote v sisteme $P_2 \times P_k$”, Kibernetika, 1 (1991), 1–8 | Zbl

[12] Romov B.A., “The completness problem on the product of algebras of finite-valued logic”, Proc. 24th Int. Symposium on Multiple-Valued Logic, IEEE, Boston, 1994, 184–186 | DOI

[13] Taimanov V.A., “O dekartovykh stepenyakh $P_2$”, Dokl. AN SSSR, 270:6 (1983), 1327–1330 | MR | Zbl

[14] Taimanov V.A., “O bazisakh zamknutykh klassov v $P_k \times P_m$”, Tezisy dokl. VIII Vsesoyuzn. konf. “Problemy teoret. kibernetiki”, Irkutsk, 1985, 188–189

[15] Taimanov V.A., “O bazisakh zamknutykh klassov vektor-funktsii mnogoznachnoi logiki”, Diskretnaya matematika, 28:2 (2016), 127–132 | MR

[16] Taimanov V.A., “O nekotorykh svoistvakh vektor-funktsii algebry logiki”, Diskretnaya matematika, 30:1 (2018), 114–128

[17] Taimanov V.A., “O bazisakh zamknutykh klassov vektor-funktsii algebry logiki”, Diskretnaya matematika, 31:3 (2019), 78–92

[18] Yablonskii S.V., Gavrilov G.P., Kudryavtsev V.B., Funktsii algebry logiki i klassy Posta, Nauka, M., 1966, 120 pp.

[19] Post E.L., “Introduction to a general theory of elementary propositions”, Amer. J. Math., 43 (1921), 163–185 | DOI | MR | Zbl

[20] Post E.L., Two-valued iterative systems of mathematical logic, Princeton Univ. Press, Princeton, 1941, 122 pp. | MR | Zbl

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