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






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


Diskr. Mat., 2016, Volume 28, Issue 4, Pages 80–90 (Mi dm1394)  

This article is cited in 3 scientific papers (total in 3 papers)

The minimum number of negations in circuits for systems of multi-valued functions

V. V. Kocherginab, A. V. Mikhailovichc

a Lomonosov Moscow State University
b Lomonosov Moscow State University, Bogoliubov Institute for Theoretical Problems of Microphysics
c National Research University "Higher School of Economics" (HSE), Moscow

Abstract: The paper is concerned with the complexity of realization of $k$-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be $0$. The complexity problem of realizations of Boolean functions over a basis having negation as the only nonmonotone element was completely solved by A. A. Markov. In 1957 he showed that the minimum number of NOT gates sufficient for realization of any Boolean function $f$ (the inversion complexity of the function $f$) is $\lceil\log_2(d(f)+1)\rceil$. Here $d(f)$ is the maximum number of the changes of the function $f$ from larger to smaller values over all increasing chains of tuples of variables values. In the present paper Markov's result is extended to the case of realization of $k$-valued logic functions. We show that the minimum number of Post negations (that is, functions of the form $x+1\pmod{k}$) that is sufficient to realize an arbitrary function of $k$-valued logic is $\lceil\log_2(d(f)+1)\rceil$ and the minimum number of Łukasiewicz negation (that is, functions of the form $k-1-x$) that is sufficient to realize an arbitrary $k$-valued logic function is $\lceil\log_k(d(f)+1)\rceil$. In addition, another classical Markov's result on the inversion complexity of systems of Boolean functions is extended to the setting of systems of functions of $k$-valued logic.

Keywords: multi-valued logic functions, logic circuits, circuit complexity, nonmonotone complexity, inversion complexity, Markov's theorem.

Funding Agency Grant Number
National Research University Higher School of Economics 14-01-0144
Russian Foundation for Basic Research 14-01-00598_а
This study was supported by the Academic Fund Programme of the National Research University Higher School of Economics in 2014/2015 (research grant no. 14-01-0144). The first author was supported by the Russian Foundation for Basic Research (project no. 14–01–00598).


DOI: https://doi.org/10.4213/dm1394

Full text: PDF file (480 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2017, 27:5, 295–302

Bibliographic databases:

UDC: 519.714
Received: 30.03.2016

Citation: V. V. Kochergin, A. V. Mikhailovich, “The minimum number of negations in circuits for systems of multi-valued functions”, Diskr. Mat., 28:4 (2016), 80–90; Discrete Math. Appl., 27:5 (2017), 295–302

Citation in format AMSBIB
\Bibitem{KocMik16}
\by V.~V.~Kochergin, A.~V.~Mikhailovich
\paper The minimum number of negations in circuits for systems of multi-valued functions
\jour Diskr. Mat.
\yr 2016
\vol 28
\issue 4
\pages 80--90
\mathnet{http://mi.mathnet.ru/dm1394}
\crossref{https://doi.org/10.4213/dm1394}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3699323}
\elib{http://elibrary.ru/item.asp?id=28119093}
\transl
\jour Discrete Math. Appl.
\yr 2017
\vol 27
\issue 5
\pages 295--302
\crossref{https://doi.org/10.1515/dma-2017-0030}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000414954500004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85031803813}


Linking options:
  • http://mi.mathnet.ru/eng/dm1394
  • https://doi.org/10.4213/dm1394
  • http://mi.mathnet.ru/eng/dm/v28/i4/p80

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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. V. V. Kochergin, A. V. Mikhailovich, “Asymptotics of growth for non-monotone complexity of multi-valued logic function systems”, Sib. elektron. matem. izv., 14 (2017), 1100–1107  mathnet  crossref
    2. V. V. Kochergin, A. V. Mikhailovich, “On the complexity of multivalued logic functions over some infinite basis”, J. Appl. Industr. Math., 12:1 (2018), 40–58  mathnet  crossref  crossref  elib
    3. V. V. Kochergin, A. V. Mikhailovich, “Exact Value of the Nonmonotone Complexity of Boolean Functions”, Math. Notes, 105:1 (2019), 28–35  mathnet  crossref  crossref  isi  elib
  • Дискретная математика
    Number of views:
    This page:205
    Full text:7
    References:31
    First page:27

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020