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.