|
This article is cited in 3 scientific papers (total in 3 papers)
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 Lomonosov Moscow State University
Abstract:
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
Keywords:
Boolean function, function of three-valued logic, function of $k$-valued logic, polarized polynomial form (PPF), complexity, upper estimate, lower estimate.
Received: 09.10.2014
Citation:
Svetlana N. Selezneva, “Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms”, Diskr. Mat., 27:1 (2015), 111–122; Discrete Math. Appl., 26:2 (2016), 115–124
Linking options:
https://www.mathnet.ru/eng/dm1319https://doi.org/10.4213/dm1319 https://www.mathnet.ru/eng/dm/v27/i1/p111
|
Statistics & downloads: |
Abstract page: | 545 | Full-text PDF : | 190 | References: | 59 | First page: | 25 |
|