Monotone Boolean functions, and the monotone Boolean circuits that compute them, have
been intensively studied in complexity theory. In this paper we study the structure of Boolean …

The problem of the complexity of multi-valued logic functions realization by circuits in a
special basis is investigated. This kind of basis consists of elements of two types. The first …

Рассматривается задача о сложности реализации функций k-значной логики схемами
в бесконечных полных базисах, содержащих все монотонные функции; вес …

Negation-limited circuits have been studied as a circuit model between general circuits and
monotone circuits. In this paper, we consider limiting negations in formulas. The minimum …

Аннотация Исследуется сложность реализации функций k-значной логики (k≥ 3)
схемами из функциональных элементов в бесконечном базисе, состоящем из …

The minimum number of NOT gates in a Boolean circuit computing a Boolean function f is
called the inversion complexity of f. In 1958, Markov determined the inversion complexity of …

Under study is the complexity of the realization of k-valued logic functions (k≥ 3) by logic
circuits in the infinite basis consisting of the Post negation (ie, the function (x+ 1) mod k) and …

The minimum number of NOT gates in a Boolean circuit computing a Boolean function is
called the inversion complexity of the function. In 1957, AA Markov determined the inversion …

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 …

The minimum number of NOT gates in a logic circuit computing a Boolean function is called
the inversion complexity of the function. In 1957, AA Markov determined the inversion …