Diskretnaya Matematika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 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

 Diskr. Mat., 2015, Volume 27, Issue 1, Pages 111–122 (Mi dm1319)

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

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} 

• 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