Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms

Svetlana N. Selezneva

Diskretnaya Matematika, Tome 27 (2015) no. 1, pp. 111-122.

Résumé

A polarized polynomial form (PPF) (modulo $k$) is a modulo $k$ sum of products of variables $x_1, \dots, x_n$ or their Post negations, where the number of negations of each variable is determined by the polarization vector of the PPF. The length of a PPF is the number of its pairwise distinct summands. The length of a function $f(x_1, \dots, x_n)$ of $k$-valued logic in the class of PPFs is the minimum length among all PPFs realizing the function. The paper presents a sequence of symmetric functions $f_n(x_1, \dots, x_n)$ of three-valued logic such that the length of each function $f_n$ in the class of PPFs is not less than $\lfloor 3^{n+1}/4 \rfloor$, where $\lfloor a \rfloor$ denotes the greatest integer less or equal to the number $a$. The complexity of a system of PPFs sharing the same polarization vector is the number of pairwise distinct summands entering into all of these PPFs. The complexity $L_k^{\rm PPF}(F)$ of a system $F = \{f_1, \dots, f_m\}$ of functions of $k$-valued logic depending on variables $x_1, \dots, x_n$ in the class of PPFs is the minimum complexity among all systems of PPFs $\{p_1, \dots, p_m\}$ such that all PPFs $p_1, \dots, p_m$ share the same polarization vector and the PPF $p_j$ realizes the function $f_j$, $j = 1, \dots, m$. Let $L_k^{\rm PPF}(m, n) = \max\limits_{F}L_k^{\rm PPF}(F)$, where $F$ runs through all systems consisting of $m$ functions of $k$-valued logic depending on variables $x_1, \dots, x_n$. For prime values of $k$ it is easy to derive the estimate $L_k^{\rm PPF}(m, n) \le k^n$. In this paper it is shown that $L_2^{\rm PPF}(m, n) = 2^n$ and $L_3^{\rm PPF}(m, n) = 3^n$ for all $m \ge 2$, $n = 1, 2, \dots$ Moreover, it is demonstrated that the estimates remain valid when consideration is restricted to systems of symmetric functions only. \def\acknowledgementname{Funding

Détail

Keywords: Boolean function, function of three-valued logic, function of $k$-valued logic, polarized polynomial form (PPF), complexity, upper estimate, lower estimate.

Bibliographie

[1] Ugryumov E. P., Tsifrovaya skhemotekhnika, BKhV-Peterburg, SPb., 2004

[2] Astola J. T., Stankovich R. S., Fundamentals of switching theory and logic design, Springer, Dordrechht, The Netherlands, 2006

[3] Sasao T., Besslich P., “On the complexity of mod-2 sum PLA's”, IEEE Trans. on Comput., 39:2 (1990), 262–266 | DOI

[4] Suprun V. P., “Slozhnost bulevykh funktsii v klasse kanonicheskikh polyarizovannykh polinomov”, Diskretnaya matematika, 5:2 (1993), 111–115 | Zbl

[5] Peryazev N. A., “Slozhnost bulevykh funktsii v klasse polinomialnykh polyarizovannykh form”, Algebra i logika, 34:3 (1995), 323–326 | MR | Zbl

[6] Selezneva S. N., “O slozhnosti predstavleniya funktsii mnogoznachnykh logik polyarizovannymi polinomami”, Diskretnaya matematika, 14:2 (2002), 48–53 | DOI | MR | Zbl

[7] Selezneva S.N., “O slozhnosti polyarizovannykh polinomov funktsii mnogoznachnykh logik, zavisyaschikh ot odnoi peremennoi”, Diskretnaya matematika, 16:2 (2004), 117–120 | DOI | MR | Zbl

[8] Kirichenko K. D., “Verkhnyaya otsenka slozhnosti polinomialnykh normalnykh form bulevykh funktsii”, Diskretnaya matematika, 17:3 (2005), 80–88 | DOI | MR | Zbl

[9] Selezneva S. N., Dainyak A. B., “O slozhnosti obobschennykh polinomov $k$-znachnykh funktsii”, Vestnik Mosk. un-ta. Seriya 15. Vychisl. matem. i kibern, 2008, no. 3, 34–39 | MR

[10] Markelov N. K., “Nizhnyaya otsenka slozhnosti funktsii trekhznachnoi logiki v klasse polyarizovannykh polinomov”, Vestnik Mosk. un-ta. Seriya 15. Vychisl. matem. i kibern., 2012, no. 3, 40–45 | MR

[11] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnykh logikakh”, Trudy Matem. in-ta im. V.A. Steklova, 51 (1958), 5–142

[12] Stolov E. L., “Matematicheskaya model generatora sluchainykh chisel na osnove trekhznachnoi logiki”, Prikladnaya diskretnaya matematika, 2 (2012), 43–49

[13] Mazurov A. A., “O statsionarnykh klassakh funktsii trekhznachnoi logiki”, Vestnik Mosk. un-ta. Seriya 15. Vychisl. matem. i kibern., 2012, no. 2, 37–43 | MR | Zbl

[14] Alekhina M. A., Barsukova O. Yu., “O nadezhnosti skhem, realizuyuschikh funktsii iz $P_3$”, Izv. vyssh. uchebn. zaved. Povolzhskii region. Fiz.-matem. nauki, 1 (2012), 57–65

[15] Alekhina M. A., Barsukova O. Yu., “Otsenki nenadezhnosti skhem v bazise Rossera–Turketta”, Izv. vyssh. uchebn. zaved. Povolzhskii region. Fiz.-matem. nauki, 1(29) (2014), 5–19