Diskretnaya Matematika General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Diskr. Mat., 2015, Volume 27, Issue 1, Pages 111–122 (Mi dm1319)  This article is cited in 1 scientific paper (total in 1 paper)

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, …, 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, …, 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, …, 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^PPF(F)$ of a system $F = \{f_1, …, f_m\}$ of functions of $k$-valued logic depending on variables $x_1, …, x_n$ in the class of PPFs is the minimum complexity among all systems of PPFs $\{p_1, …, p_m\}$ such that all PPFs $p_1, …, p_m$ share the same polarization vector and the PPF $p_j$ realizes the function $f_j$, $j = 1, …, m$. Let $L_k^PPF(m, n) = \max\limits_{F}L_k^PPF(F)$, where $F$ runs through all systems consisting of $m$ functions of $k$-valued logic depending on variables $x_1, …, x_n$. For prime values of $k$ it is easy to derive the estimate $L_k^PPF(m, n) \le k^n$. In this paper it is shown that $L_2^PPF(m, n) = 2^n$ and $L_3^PPF(m, n) = 3^n$ for all $m \ge 2$, $n = 1, 2, …$ 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.

 Funding Agency Grant Number Russian Foundation for Basic Research 13-01-00684-а13-01-00958-а This work was supported by the Russian Foundation for Basic Research, projects no. 13-01-00684-a and 13-01-00958-a.

DOI: https://doi.org/10.4213/dm1319  Full text: PDF file (438 kB) References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2016, 26:2, 115–124 Bibliographic databases:    UDC: 519.716.325
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 Citation in format AMSBIB
\Bibitem{Sel15} \by Svetlana N. Selezneva \paper Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms \jour Diskr. Mat. \yr 2015 \vol 27 \issue 1 \pages 111--122 \mathnet{http://mi.mathnet.ru/dm1319} \crossref{https://doi.org/10.4213/dm1319} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3468145} \elib{https://elibrary.ru/item.asp?id=23780140} \transl \jour Discrete Math. Appl. \yr 2016 \vol 26 \issue 2 \pages 115--124 \crossref{https://doi.org/10.1515/dma-2016-0009} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000375870900004} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84968884486} 

Linking options:
• http://mi.mathnet.ru/eng/dm1319
• https://doi.org/10.4213/dm1319
• http://mi.mathnet.ru/eng/dm/v27/i1/p111

 SHARE:      Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. I. Mamontov, S. M. Ryabinov, “Ob odnom metode ekonomii pamyati pri klassifikatsii tekstov”, Programmnye sistemy: teoriya i prilozheniya, 8:4 (2017), 133–147  • Number of views: This page: 322 Full text: 95 References: 42 First page: 25 Contact us: math-net2021_04 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2021