Список выпусков > Серия «Математика». 2017. Том 22
О сложности стандартных форм мультифункций
Если рассматривать дискретные функции на множестве A, то мультифункции можно определить как функции на множестве 2A, при этом значения мультифункций для значений аргументов из A задаются, а для значений, не являющихся одноэлементными множествами, определяются как объединение всех значений мультифункции на одноэлементных множествах. Таким же образом определяется суперпозиция для мультифункций.
Мультифункции являются обобщением различных моделей неопределенности, частичных и гиперфункций. Такие модели можно применять, например, при работе с неполной и противоречивой информацией в интеллектуальных системах.
Для мультифункций можно определить стандартные формы через мультифункцию пересечения. Представление мультифункции в классе стандартных форм не является единственным. Для них можно естественным образом ввести понятие сложности по количеству компонент пересечения.
В данной статье рассматривается связь между мультифункциями, принимающими всего два значения, и булевыми функциями. Показано, что сложность стандартных форм любой из таких мультифункций совпадает с длиной дизъюнктивной нормальной формы соответствующей булевой функции. В статье получена верхняя оценка сложности стандартных форм мультифункций, а также приведена последовательность мультифункций, сложность которой совпадает с этой верхней оценкой. Таким образом, получено значение сложности класса n-местных мультифункций (функцииШеннона). Также предложен алгоритм минимизации мультифункций ранга 2 от 4 и менее аргументов, основанный на последовательном переборе формул всё большей сложности. С помощью данного алгоритма найдены сложности всех 4-местных мультифункций ранга 2.
Ссылка для цитирования:
Казимиров А.С. О сложности стандартных форм мультифункций // Известия Иркутского государственного университета. Серия Математика. 2017. Т. 22. С. 63-70. https://doi.org/10.26516/1997-7670.2017.22.63
1. Лупанов О. Б. О реализации функций алгебры логики формулами конечных классов (формулами ограниченной глубины) в базисе «И», «ИЛИ», «НЕ» / О. Б. Лупанов // Проблемы кибернетики. Вып. 6. – М. : Физматгиз, 1961. – С. 5–14.
2. Пантелеев В. И. Критерий полноты для недоопределенных частичных булевых функций / В. И. Пантелеев // Вестн. НГУ. Сер. Математика, механика, информатика. – 2009. – Т. 9, вып. 3. – C. 95–114.
3. Перязев Н. А. Клоны, ко-клоны, гиперклоны и суперклоны / Н. А. Перязев // Учен. зап. Казан. гос. ун-та. Сер. Физико-математические науки. – 2009. – Т. 151,кн. 2. – С. 120–125.
4. Перязев Н. А. Минимизация мультиопераций в классе стандартных форм / Н. А. Перязев, И. А. Яковчук // Изв. Иркут. гос. ун-та. Сер. Математика. – 2009. – T. 2, № 2. – С. 117–126.
5. Перязев Н. А. Стандартные формы мультиопераций в суперклонах / Н. А. Перязев // Изв. Иркут. гос. ун-та. Сер. Математика. – 2010. – T. 3, № 4. – С. 88–95.
6. Перязев Н. А. Суперклоны мультиопераций / Н. А. Перязев // Дискретные системы в теории управляющих систем : тр. VIII Междунар. конф. – М. : МАИС Пресс, 2009. – С. 233–238.
7. Шаранхаев И. К. О методе декомпозиции мультифункций / И. К. Шаранхаев // Дискретные модели в теории управляющих систем : IХ Междунар. конф. : труды / отв. ред.: В. Б. Алексеев, Д. С. Романов, Б. Р. Данилов. – М. : МАКС Пресс, 2015. – С. 266-267.
8. Kazimirov A. Decision support system based on 4-valued logic with multiinterpretations / A. Kazimirov, V. Panteleyev, L. Riabets, S. Vinokurov // Proceedings of International Conference on Soft Computing and MeasurementsSCM 2015, May 19–21, St. Petersburg, Russia, 2015. – P. 198–199.
9. Peryazev N. A. Galois theory for clones and superclones / N. A. Peryazev, I. K. Sharankhaev // Discrete Mathematics and Applications. – 2016. – Vol. 26, N 4. – P. 227–238. https://doi.org/10.1515/dma-2016-0020
10. Romov B. A. The completeness problem in partial hyperclones / B. A. Romov // Discrete Mathematics. – 2006. – Vol. 306. – P. 1405–1414. https://doi.org/10.1016/j.disc.2005.11.033
11. Decision Support System for Medical Prescriptions Based on 4-Valued Logic / S. Vinokurov, A. Kazimirov, N. Pustovoytov, A. Frantseva // Proceedings of the XIX International Conference on Soft Computing and Measurement, SCM 2016, May 25–27, St. Petersburg, Russia, 2016. – P. 307–308.