?
О немонотонной сложности функций k-значной логики
С. 142-145.
Исследуются различные обобщения известных теорем А. А. Маркова об инверсионной сложности систем булевых функций.
Ключевые слова: функции многозначной логикиmulti-valued logic functionsсхемная сложностьinversion complexityMarkov's theoremинверсионная сложностьтеорема Марковаlogic circuitnonmonotone complexityнемонотонная сложностьсхемы из функциональных элементов circuit complexity
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
В книге
М. : Изд-во механико-математического факультета МГУ, 2016
Mikhailovich A.V., Kochergin V.V., Siberian Electronic Mathematical Reports 2017 Vol. 14 P. 1100-1107
Добавлено: 28 сентября 2017 г.
Кочергин В. В., Михайлович А. В., Mathematical notes 2023 Vol. 113 No. 5 P. 794-803
Добавлено: 19 ноября 2023 г.
Михайлович А. В., Кочергин В. В., В кн. : Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем". : Улан-Удэ : Издательство Бурятского госуниверситета, 2017. С. 48-52.
Исследуется задача о сложности реализации систем функций k-значной логики схемами из функциональных элементов (логическими схемами) в базисах, состоящих из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан единичный вес. ...
Добавлено: 22 сентября 2017 г.
Михайлович А. В., Кочергин В. В., Дискретная математика 2016 Т. 28 № 4 С. 80-90
Рассматривается задача о сложности реализации функций k-значной логики схемами в бесконечных полных базисах, содержащих все монотонные функции; вес монотонных функций (стоимость использования) считается равным 0. Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А. А. Марковым. В 1957 году он установил, что минимальное число отрицаний, достаточное для ...
Добавлено: 25 февраля 2017 г.
Кочергин В. В., Михайлович А. В., Дискретный анализ и исследование операций 2018 Т. 25 № 1 С. 42-74
Исследуется сложность реализации функций k-значной логики (k > 2) схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста, т.е. функции x+1 (mod k), и всех монотонных функций. Под сложностью понимается общее число элементов в схеме. Для произвольной функии f установлены отличающиеся друг от друга не более чем на единицу нижняя и верхняя оценки ...
Добавлено: 28 сентября 2017 г.
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 ...
Добавлено: 14 марта 2018 г.
V.V. Kochergin, A.V. Mikhailovich, Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 13-25
Добавлено: 22 апреля 2019 г.
Михайлович А. В., Кочергин В. В., В кн. : Материалы XVIII международной конференции "Проблемы теоретической кибернетики" (Пенза, 19-23 июня 2017 г.). : М. : МАКС Пресс, 2017. С. 142-144.
Исследуется задача о сложности реализации функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста и всех монотонных функций. ...
Добавлено: 21 сентября 2017 г.
Михайлович А. В., Кочергин В. В., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98-105
Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность — число использований немонотонных элементов (монотонные функции «бесплатны»). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только ...
Добавлено: 28 сентября 2017 г.
Mikhailovich A. V., Kochergin V. V., / Cornell University. Series math "arxiv.org". 2015.
Добавлено: 20 октября 2015 г.
Михайлович А. В., Кочергин В. В., В кн. : Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова. : Изд-во механико-математического факультета МГУ, 2019. С. 129-131.
Добавлено: 7 декабря 2021 г.
Кочергин В. В., Михайлович А. В., В кн. : Проблемы теоретической кибернетики. Материалы заочного семинара XIX международной конференции. : Издательство Казанского (Приволжского) федерального университета, 2021. С. 75-78.
В работе исследуется сложность реализации функций многозначной логики над базисами, содержащими все монотонные функции и конечное число немонотонных функций. Получены верхняя и нижняя оценка, отличающиеся на константу, не зависящую от базиса. ...
Добавлено: 6 декабря 2021 г.
V.V. Kochergin, A.V. Mikhailovich, Mathematical notes 2019 Vol. 105 No. 1 P. 28-35
Добавлено: 22 апреля 2019 г.
Кочергин В. В., Михайлович А. В., Прикладная дискретная математика 2015 № 4 С. 24-31
Исследуется сложность реализации булевых функций и систем булевых функций схемами в базисе, состоящем из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан положительный вес. Для случая, когда отрицание является единственным элементом второго сорта, А. ...
Добавлено: 8 декабря 2015 г.
Кочергин В. В., Михайлович А. В., В кн. : Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.). : М. : Институт прикладной математики им. М.В. Келдыша РАН, 2022. С. 76-79.
Установлена нижняя оценка немонотонной сложности функций многозначной логики, отличающающаяся от известной верхней оценки не более чем на абсолютную константу ...
Добавлено: 29 октября 2022 г.
Михайлович А. В., Кочергин В. В., Математические заметки 2019 Т. 105 № 1 С. 32-41
Исследуется задача о сложности реализации булевых функций схемами в бесконечных полных базисах, содержащих все монотонные функции, имеющие при этом нулевой вес (стоимость использования) и конечное число немонотонных функций единичного веса. Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А.А. Марковым: минимальное число отрицаний, достаточное для ...
Добавлено: 28 сентября 2017 г.
Кочергин В. В., Михайлович А. В., Ученые записки Казанского университета. Серия: Физико-математические науки 2020 Т. 162 № 3 С. 311-321
Исследована задача о сложности реализации функций многозначной логики логическими схемами в базисе, состоящем из элементов двух типов. Элементами первого типа являются произвольные монотонные (относительно стандартного порядка) функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго типа, каждой такой функции приписан единичный вес. Установлены верхняя и нижняя оценки немонотонной сложности ...
Добавлено: 6 декабря 2021 г.
Kochergin V.V., Mikhailovich A.V., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 1 P. 40-58
Добавлено: 11 марта 2018 г.
A.V. Mikhailovich, V. V. Kochergin, / Cornell University. Series math "arxiv.org". 2015.
Добавлено: 15 июня 2015 г.
Михайлович А. В., Moscow University Mathematics Bulletin 2012 Vol. 67 No. 1 P. 41-45
Изучаются замкнутые классы функций трехзначной логики, порождающие системы которых содержат симметрические функции, принимающие значения из множества {0, 1}. Показано, что в некоторых случаях задачи о базируемости и конечной порожденности для таких классов сводятся к аналогичным задачам для классов, порождающие системы которых являются подмножествами порождающих систем исходных множеств. ...
Добавлено: 30 октября 2012 г.
Михайлович А. В., В кн. : Математические вопросы кибернетики. Вып. 18.: М. : Физматлит, 2013. С. 123-212.
В работе изучаются свойства замкнутых классов функций многозначной логики. Рассматривается задача о существовании базисов для некоторых семейств замкнутых классов. Функции из порождающих систем обладают следующими свойствами: каждая функция является симметрической, принадлежит множество P<sub>k,2</sub> (то есть принимает значения только из множества {0,1}), принимает значение 0 на единичном наборе и на всех наборах, содержащих хотя бы одну ...
Добавлено: 25 марта 2014 г.
Михайлович А. В., В кн. : Труды IX Международной конференции "Дискретные модели в теории управляющих систем". : М. : МАКС Пресс, 2015. С. 163-166.
В работе изучаются замкнутые классы функций многозначной логики. Рассматриваются семейства, порожденные функциями из множеств, обладающих специальными свойствами. Для таких классов получен критерий базируемости. ...
Добавлено: 28 марта 2015 г.
Михайлович А. В., В кн. : Материалы X молодежной научной школы по дискретной математике и ее приложениям. : М. : Издательство ИПМ РАН, 2015. С. 51-55.
В данной работе рассматривается семейство классов функций трехзначной логики, порожденных квазиоднослойными функциями принимающими значения из множества {0, 1}. Для таких классов получены критерии базируемости и конечной порождённости. ...
Добавлено: 8 апреля 2016 г.
Михайлович А. В., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 209-212.
В работе рассматриваются периодические симметрические функции трехзначной логики, принимающие значения из множества {0,1}. Для классов, порождённых функциями с периодом, являющимся степенью простого числа, получены критерии базируемости и конечной порождённости. ...
Добавлено: 1 сентября 2016 г.