?
О сложности реализации формулами функций из P<sub>k,2</sub>, k≥3.
С. 23–27.
In book
М.: Институт прикладной математики им. М.В. Келдыша РАН, 2011.
Mikhailovich A., Kochergin V., М.: Физматлит, 2024.
Added: March 10, 2025
Kochergin V., Mikhailovich A., Mathematical notes 2023 Vol. 113 No. 5 P. 794–803
The problem of determining the nonmonotone complexity of the implementation ofk-valued logic functions by logic circuits in bases consisting of all monotone (with respect to thestandard order) functions and finitely many nonmonotone functions is investigated. In calculatingthe complexity measure under examination only those elements of the circuit which are assignednonmonotone basis functions are taken into ...
Added: November 19, 2023
Kochergin V., Mikhailovich A., В кн.: Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.).: М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022. С. 76–79.
Установлена нижняя оценка немонотонной сложности функций многозначной логики, отличающающаяся от известной верхней оценки не более чем на абсолютную константу ...
Added: October 29, 2022
Mikhailovich A., Kochergin V., В кн.: Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова.: Изд-во механико-математического факультета МГУ, 2019. С. 129–131.
Added: December 7, 2021
Kochergin V., Mikhailovich A., Ученые записки Казанского университета. Серия: Физико-математические науки 2020 Т. 162 № 3 С. 311–321
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 type of elements are monotone functions with zero weight.
The second type of elements are non-monotone elements with unit weight.
The non-empty set of elements of this type is ...
Added: December 6, 2021
Danilov B. R., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2015 Т. 4 № 36 С. 58–77
Background
The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem ...
Added: December 2, 2019
V.V. Kochergin, A.V. Mikhailovich, Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 13–25
We investigate the realization complexity of k-valued logic functions k ≥ 2 by combinational circuits in an infinite basis that includes the negation of the Lukasiewicz function, i.e., the function k−1−x, and all monotone functions. Complexity is understood as the total number of circuit elements. For an arbitrary function f, we establish lower and upper ...
Added: April 22, 2019
Kochergin Vadim V., Mikhailovich Anna V., Discrete Mathematics and Applications 2017 Vol. 27 No. 5 P. 295–302
The paper is concerned with the complexity of realization of 𝑘-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 ...
Added: March 14, 2018
Kochergin V.V., Mikhailovich A.V., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 1 P. 40–58
The complexity of realization of k-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function x+1(mod k)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds ...
Added: March 11, 2018
Mikhailovich A.V., Kochergin V.V., Siberian Electronic Mathematical Reports 2017 Vol. 14 P. 1100–1107
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 type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements ...
Added: September 28, 2017
Kochergin V., Mikhailovich A., Дискретный анализ и исследование операций 2018 Т. 25 № 1 С. 42–74
The complexity of realization of k-valued logic functions by circuits in a special infinite basis is invesigated. This basis consists of Post negation (i.e. function x+1(mod k)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. The upper and the lower bounds of the complexity were ...
Added: September 28, 2017
Mikhailovich A., Kochergin V., В кн.: Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем".: Улан-Удэ: Издательство Бурятского госуниверситета, 2017. С. 48–52.
Problem of multi-valued function realization by logic circuits in special bases is investigated. These bases consist of all monotone functions with zero weight and finite number of non-monotone functions with unit weight. ...
Added: September 22, 2017
Mikhailovich A., В кн.: Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем".: Улан-Удэ: Издательство Бурятского госуниверситета, 2017. С. 91–95.
Lattice of all closed classes from closure of all functions from Janov and Muchnik examples has been described. ...
Added: September 22, 2017
Улан-Удэ: Издательство Бурятского госуниверситета, 2017.
The collection represents proceedings of the 5th school-seminar "Syntax and Semantics of Logic Systems" (Ulan-Ude, 08.08.2017 - 12.08.2017). The conference subject area includes: theory of models and universal algebra; theory of boolean and finite-valued functions; formal languages and logic calculus; mathematical logic in education. ...
Added: September 22, 2017
Mikhailovich A., В кн.: Материалы XVIII международной конференции "Проблемы теоретической кибернетики" (Пенза, 19-23 июня 2017 г.).: М.: МАКС Пресс, 2017. С. 166–168.
All closed classes from Muchnik's example of closed class with infinite bases are described. ...
Added: September 21, 2017
Михайлович А. В., Кочергин В. В., В кн.: Материалы XVIII международной конференции "Проблемы теоретической кибернетики" (Пенза, 19-23 июня 2017 г.).: М.: МАКС Пресс, 2017. С. 142–144.
The problem of multi-valued functions realization by circuits over special basis is inverstigated. The basis consis of Post negation and all monotone functions. ...
Added: September 21, 2017
Mikhailovich A., Kochergin V., Дискретная математика 2016 Т. 28 № 4 С. 80–90
In this paper we consider the complexity of realization of k-valued logic functions by logic circuits over an infinite complete basis of special type. This basis contain all monotone functions with zero weight and non-monotone functions with non-zero weight. The problem of the complexity of a Boolean functions realization over basis containing all monotone functions ...
Added: February 25, 2017
Mikhailovich A., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 209–212.
Closed classes of three-valued logic, generated by periodical functions taking values from the set {0,1} are considered. Criteria of basis exitstence and finite basis existence for classes generated by periodical functions with period of the form p^k (p is fixed prime number, k is arbitrary natural number) are obtained. ...
Added: September 1, 2016
Mikhailovich A., Kochergin V., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 142–145.
Different generalizations of Markov's theorem conserning inversion complexity of Boolean functions systems are considered. ...
Added: August 31, 2016
Mikhailovich A., / Series math "arxiv.org". 2016.
Closed classes of three-valued logic generated by periodic symmetric funtions that equal $1$ in tuples from $\{1,2\}^n$ and equal $0$ on the rest tuples are considered. Criteria for bases existence and finite bases existence for these classes is obtained. ...
Added: April 15, 2016
Mikhailovich A., В кн.: Материалы X молодежной научной школы по дискретной математике и ее приложениям.: М.: Издательство ИПМ РАН, 2015. С. 51–55.
Closed classes of three-valued logic functions generated by quazi-symmetric functions that take values from the set {0,1} are considered. Criteria of basis existence and finite basis existence have been obtained. ...
Added: April 8, 2016
Mikhailovich A. V., Kochergin V. V., / Series math "arxiv.org". 2015.
The minimum number of NOT gates in a logic circuit computing a Boolean function is called the inversion complexity of the function. In 1957, A. A. Markov determined the inversion complexity of every Boolean function and proved that $\lceil\log_{2}(d(f)+1)\rceil$ NOT gates are necessary and sufficient to compute any Boolean function f (where d(f) is the ...
Added: October 20, 2015
Mikhailovich A., В кн.: Труды IX Международной конференции "Дискретные модели в теории управляющих систем".: М.: МАКС Пресс, 2015. С. 163–166.
Closed classes of multi-valued logic are observed. Families of closed classes generated by function with special properties are considered. Criteria for basis existence have been obtained for these classes. ...
Added: March 28, 2015