Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
The minimum number of negations in circuits for systems of multi-valued functions
View through CrossRef
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 ⌈log
2
(
d
(
f
)+1)⌉. 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(mod
k
)) that is sufficient to realize an arbitrary function of
k
-valued logic is ⌈log
2
(
d
(
f
)+1)⌉ 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 ⌈log
k
(
d
(
f
)+1)⌉. 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.
Walter de Gruyter GmbH
Title: The minimum number of negations in circuits for systems of multi-valued functions
Description:
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 ⌈log
2
(
d
(
f
)+1)⌉.
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(mod
k
)) that is sufficient to realize an arbitrary function of
k
-valued logic is ⌈log
2
(
d
(
f
)+1)⌉ 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 ⌈log
k
(
d
(
f
)+1)⌉.
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.
Related Results
Feasibility of Plasmonic Circuits Merged with Silicon Integrated Circuits
Feasibility of Plasmonic Circuits Merged with Silicon Integrated Circuits
ABSTRACT
Plasmonic signal transmission via nanoscale plasmonic waveguides is a new technique with the potential to increase the information transfer capacity in s...
Single-Valued Neutrosophic Ideal Approximation Spaces
Single-Valued Neutrosophic Ideal Approximation Spaces
In this paper, we defined the basic idea of the single-valued neutrosophic upper (αn)δ, single-valued neutrosophic lower (αn)δ and single-valued neutrosophic boundary sets (αn)B of...
Multiple-valued cmos logic circuits with high-impedance output state
Multiple-valued cmos logic circuits with high-impedance output state
Principles and possibilities of synthesis and design of bus interface circuits with high-impedance output state in multiple-valued logic systems are described and proposed in the p...
Substructural Negations
Substructural Negations
We present substructural negations, a family of negations (or negative modalities) classified in terms of structural rules of an extended kind of sequent calculus, display calculus...
Etude et modélisation comportementale de « front-end » analogiques pour des environnements « fond de puits ».
Etude et modélisation comportementale de « front-end » analogiques pour des environnements « fond de puits ».
Cette thèse s’inscrit dans le domaine de la modélisation des circuits analogiques et mixtes.Le travail part d’une problématique industrielle concernant les circuits électroniques u...
An Introduction to Single-Valued Neutrosophic Primal Theory
An Introduction to Single-Valued Neutrosophic Primal Theory
This article explores the interconnections among the single-valued neutrosophic grill, single-valued neutrosophic primal and their stratification, uncovering their fundamental char...
Decidable fan theorem and uniform continuity theorem with continuous moduli
Decidable fan theorem and uniform continuity theorem with continuous moduli
AbstractThe uniform continuity theorem states that every pointwise continuous real‐valued function on the unit interval is uniformly continuous. In constructive mathematics, is s...
Triple-Valued Neutrosophic Set, Quadruple-Valued Neutrosophic Set, Quintuple-Valued Neutrosophic Set, and Double-valued Indetermsoft Set
Triple-Valued Neutrosophic Set, Quadruple-Valued Neutrosophic Set, Quintuple-Valued Neutrosophic Set, and Double-valued Indetermsoft Set
Concepts such as Fuzzy Sets, Neutrosophic Sets, Rough Sets, and Plithogenic Sets have been extensively studied to address uncertainty, finding diverse applications across various f...