|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Немонотонная сложность как обобщение инверсионной сложностистатья
- Авторы: Кочергин В.В., Михайлович А.В.
- Журнал: ХХI век: итоги прошлого и проблемы настоящего плюс
- Номер: 04 (38)
- Год издания: 2017
- Первая страница: 98
- Последняя страница: 105
- Аннотация: Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность~--- число использований немонотонных элементов (монотонные функции <<бесплатны>>). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только отрицание, А. А. Марковым установлено точное значение немонотонной сложности (называемой в этом случае инверсионной сложностью). В настоящей работе дан обзор результатов, обобщающих теорему Маркова, а также представлены новые оценки немонотонной сложности.
- Добавил в систему: Кочергин Вадим Васильевич