?
О сложности реализации формулами функций из P<sub>k,2</sub>, k≥3.
С. 23-27.
In book
М. : Институт прикладной математики им. М.В. Келдыша РАН, 2011
О замкнутых классах функций трехзначной логики, порожденных периодическими симметрическими функциями
Mikhailovich A., В кн. : Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20–25 июня 2011 г.). : Н. Новгород : Нижегородского госуниверситета, 2011. С. 319-322.
В работе изучается семейство замкнутых классов, порожденных периодическими симметрическими функциями с ограниченным периодом. Показано, что такой класс имеет базис тогда и только тогда, когда порождающая система содержит конечное число функций. ...
Added: November 22, 2012
Mikhailovich A., Moscow University Mathematics Bulletin 2012 Vol. 67 No. 1 P. 41-45
Closed classes of functions of three-valued logic whose generating systems include nonmonotone symmetric functions taking values in the set {0,1} are studied. It is shown that in some cases the problems of existence of a basis and existence of a finite basis can be reduced to a similar problem for reduced generated systems. ...
Added: October 30, 2012
Mikhailovich A., / Cornell University. Series math "arxiv.org". 2015.
Closed classes of three-valued logic generated by symmetric funtions that equal 1 in almost all tuples from {1,2}n and equal 0 on the rest tuples are considered. Criteria for bases existence for these classes is obtained. ...
Added: March 28, 2015
Mikhailovich A., В кн. : Материалы VIII молодежной научной школы по дискретной математике и ее приложениям (Москва, 24–29 октября 2011 г.). Ч. II.: М. : Механико-математический факультет МГУ, 2011. С. 16-19.
Рассматривается некоторое семейство замкнутых классов функций трехзначной логики, порожденных монотонными симметрическими функциями. Для этих классов получены критерии базируемости и конечной порожденности. ...
Added: November 23, 2012
Dagaev D., Вестник Московского университета. Серия 1: Математика. Механика 2012 Т. 67 № 4 С. 58-61
A certain countable set of families of classes of three-valued logic functions taking values from the set {0,1} is considered. For each class from these families and for each its finite generating system, the order of growth of the corresponding Shannon depth function is obtained. ...
Added: October 4, 2012
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
Dagaev D., Вестник Московского университета. Серия 1: Математика. Механика 2011 Т. 66 № 3 С. 60-63
The problem of the realization complexity for functions of the three-valued logic taking values from the set {0, 1} by formulas over incomplete generating systems is considered. Upper and lower asymptotic estimates for the corresponding Shannon functions are obtained. ...
Added: October 4, 2012
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
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
Dagaev D., В кн. : Математические вопросы кибернетики. Вып. 18.: М. : Физматлит, 2013. С. 35-122.
В работе рассматривается задача о сложности реализации функций трехзначной логики формулами над конечными системами. Для ряда замкнутых классов функций трехзначной логики, принимающих два значения, и некоторых их порождающих систем получены верхние и нижние оценки для соответствующих функций Шеннона по сложности и глубине.
Работа выполнена при финансовой поддержке РФФИ, грант №11-01-00508, и программы фундаментальных исследований Отделения математических ...
Added: October 12, 2012
Mikhailovich A., Прикладная дискретная математика 2015 № 1 С. 17-26
Closed classes of three-valued logic functions whose generating systems consist of symmetric functions taking values in the set {0, 1} and taking value 1 on bounded number of layers from {1, 2}^n are consideder. Criteria of existence of a basis and existence of finite basis are obtained for these classes. There shown how existence of ...
Added: March 11, 2015
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
Mikhailovich A., Kochergin V., В кн. : Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова. : Изд-во механико-математического факультета МГУ, 2019. С. 129-131.
Added: December 7, 2021
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
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
Dagaev D., Вестник Московского университета. Серия 1: Математика. Механика 2010 Т. 65 № 2 С. 53-56
Upper and lower estimates for the complexity of functions of the 3-valued logic taking values from the set {0, 1} with linear Boolean restrictions are derived. ...
Added: October 4, 2012
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., В кн. : Материалы IX молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.). : М. : Издательство ИПМ РАН, 2013. С. 80-85.
Closed classes of functions of three-valued logic whose generating systems include nonmonotone symmetric functions taking values in the set {0,1} and taking value 1 on restricted number of layers are studied. Cryteria of existence of basis and existence of finite basis has been obtained. ...
Added: October 24, 2013
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
Mikhailovich A., В кн. : Материалы XI Международного семинара «Дискретная математика и её приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.). : М. : Механико-математический факультет МГУ, 2012. С. 204-206.
Изучаются замкнутые классы функций трехзначной логики, принимающие значения из множества {0,1}. Для класса монотонных функций получено описание всех порождающих систем, состоящих из монотонных симметрических функций. ...
Added: October 9, 2012
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., Вестник Московского университета. Серия 1: Математика. Механика 2012 № 1 С. 58-62
Изучаются замкнутые классы функций трехзначной логики, порождающие системы которых содержат симметрические функции, принимающие значения из множества {0, 1}. Показано, что в некоторых случаях задачи о базируемости и конечной порожденности для таких классов сводятся к аналогичным задачам для классов, порождающие системы которых являются подмножествами порождающих систем исходных множеств. ...
Added: October 30, 2012
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
Mikhailovich A., В кн. : Математические вопросы кибернетики. Вып. 18.: М. : Физматлит, 2013. С. 123-212.
Closed classes of functions of many-valued logic are studied. Problem on the basis existence is considered for some families of closed sets. Functions from generating systems are symmetric functions taking the values from the set {0,1} and equal to zero on the unit collection and collections containing at least one zero. Furthermore, closure of any ...
Added: March 25, 2014