On bases of closed classes of Boolean vector functions

V. A. Taimanov

Diskretnaya Matematika, Tome 31 (2019) no. 3, pp. 78-92.

Résumé

A functional system of Boolean vector functions with a naturally defined superposition operation is considered. It is shown that each closed class of vector functions with $\alpha$- or $\delta$-functions as components has a finite basis.

Détail

Keywords: Boolean vector functions, superposition, functional systems.

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. Logic and Comput. Sci., Novi Sad, Yugoslavia, 1997, 1–2 | MR

[4] S. S. Marchenkov, “On the completeness in the system $P_3 \times P_3$”, Discrete Math. Appl., 2:6 (1992), 587–606 | DOI | MR | Zbl

[5] S. S. Marchenkov, “On the Slupecki classes in the systems $P_k \times \dots \times P_l$”, Discrete Math. Appl., 3:2 (1993), 147-–160 | DOI | MR | MR | Zbl

[6] S. S. Marchenkov, “On precomplete classes in Cartesian products of $P_2$ and $P_3$”, Discrete Math. Appl., 4:3 (1994), 209–228 | DOI | MR | Zbl

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

[8] Romov B.A., “O reshetke podalgebr pryamykh proizvedenii algebr Posta konechnoi stepeni”, Matematicheskie 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, 1987, no. 4, 9–14 | MR | Zbl

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

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

[12] Romov B.A., “The completness problem on the product of algebras of finite-valued logic”, ISMVL, Boston, USA, 1994, 184–186

[13] “On Cartesian powers of $P_2$”, Int. Conf. Fund. Comput. Theor., Lect. Notes Comput. Sci., 278, 1984, 435–435 | DOI | MR | Zbl

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

[15] Taimanov V.A., “On bases of closed classes of vector functions of many-valued logic”, Discrete Math. Appl., 27:2 (2017), 117–121 | DOI | DOI | MR | MR | Zbl

[16] Taimanov V.A., “On some properties of vector functions of Boolean algebra”, Discrete Math. Appl., 29:2 (2019), 131–141 | DOI | DOI | MR

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

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

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

[20] Markov A.A., Vvedenie v teoriyu kodirovaniya, Nauka, M., 1982, 192 pp. | MR

[21] Dickson L.E., “Finitness of the odd perfect and primitive abundant numbers with $n$ distinct prime factors”, Amer. J. Math., 35 (1913), 413–422 | DOI | MR | Zbl