On the length of functions of $k$-valued logic in the class of polynomial normal forms modulo~$k$

M. A. Bashov ; S. N. Selezneva

Diskretnaya Matematika, Tome 26 (2014) no. 3, pp. 3-9

Résumé

Polynomial normal forms for functions of $k$-valued logics (for prime values of $k$) are considered. A polynomial normal form modulo $k$ (p.n.f.) is the sum modulo $k$ of products of variables, or variables with one or several Post negations, taken with some coefficients. The length of a p.n.f. is the number of distinct terms that appear in the form with nonzero coefficients. If $k$ is a prime number, then each function of $k$-valued logic may be represented by various p.n.f. The length of a function of $k$-valued logic in the class of p.n.f. is the minimum length of a p.n.f. representing this function. The Shannon function $L_k^{p.n.f.}(n)$ of the length of functions of $k$-valued logic in the class of p.n.f. is the maximum length of a function in the class of p.n.f. among all $n$-ary functions of $k$-valued logic. In this work the order of growth of the Shannon function $L_k^{p.n.f}(n)$ is established (for prime values of $k$): $L_k^{p.n.f.}(n) = \Theta\left (\frac{k^n}{n}\right )$.

Détail

Keywords: function of $k$-valued logic, Boolean function, polynomial representation, polynomial normal form, length, Shannon function, shading set, covering, minimal covering.