О сложности реализации функций многозначной логики формулами специального вида

• Автор: Трущин, Дмитрий Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 78 с.

Оглавление
Введение

1 Определения и вспомогательные утверждения

1.1 Основные определения и обозначения

1.2 Некоторые замкнутые классы

1.3 Бинарные операции с правым сокращением

2 Булевы функции

2.1 Эквивалентные преобразования си-формул

2.2 Верхние оценки функций Шеннона

2.3 Реализация монотонных функций

2.4 Реализация немонотонных функций

3 Двоично представимые функции трехзначной логики
3.1 Критерий двоичной представимости функции
3.2 Частичная эквивалентность многочленов
3.3 Сопоставление многочленов формулам
3.4 Верхние оценки функции Шеннона для класса двоично
представимых функций
3.5 Нижние оценки функции Шеннона для класса двоично
представимых функций
3.6 Верхние оценки глубины для произвольной функции
4 Функции многозначной логики
4.1 Функции ИЗ Рк!2

4.2 Верхние оценки глубины для произвольной функции
Список литературы

Введение
Данная работа относится к математической теории синтеза и сложности управляющих систем — одному из основных разделов дискретной математики и математической кибернетики. В ней рассматривается задача о реализации функций многозначной логики формулами специального вида над конечными базисами.
Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения их сложности. В общем случае эта задача, может быть сформулирована следующим образом. Рассматривается набор базисных элементов, из которых по некоторым правилам строятся более сложные объекты — управляющие системы (например, схемы из функциональных элементов, контактные схемы, формулы). Заданы правила, позволяющие каждой системе сопоставить реализуемую ей функцию. Кроме того, каждой системе сопоставлено положительное число (сложность), которое характеризует ее стоимость. Рассматриваемая задача состоит в построении по заданной функции такой управляющей системы, которая реализует эту функцию и является оптимальной относительно выбранной меры сложности; при этом сложность построенной системы называется сложностью этой функции. Для заданного множества функций исследуется также поведение функции Шеннона, которая характеризует сложность реализации в рассматриваемом классе управляющих систем самой сложной функции, принадлежащей этому множеству и зависящей от фиксированного числа перменных.
Пусть к > 2. Положим Ек — {0,1 1}. Обозначим через
Рк множество всех функций &-значной логики. Формулы над конечными

Рассмотрим произвольный набор (Ьх
ги(Ьь ...Ьп) = 147(1(71(61))
Тогда гн(х1
представима. Тем самым достаточность также доказана.
3.2 Частичная эквивалентность многочленов
Пусть У = {у1, у2
Пусть п > 1. Будем говорить, что многочлен от переменных У1, , Уп является допустимым, если существует такое непустое конечное подмножество N множества N0, и для каждого набора а £ N существует такой коэффициент Со-, что рассматриваемый многочлен имеет вид
Множество всех допустимых многочленов обозначим через £}„. Многочлен, все коэффициенты которого равны 0, мы будем называть нулевым. Два многочлена из назовем равными, если их разность есть нулевой многочлен. Многочлены из принимают значения в Е3, поэтому каждый такой многочлен задает некоторую функцию ИЗ Рз ОТ переменных Ух, , уп. Через Уп обозначим множество всех непустых подмножеств множества {1,2
Будем говорить, что два многочлена Р, С Є 0.п частично эквивалентны (обозначение Р ~ С), если для любого набора (щ
Замечание 3.2.1. Пусть 1 < т < п, Р, <5, Т, Т' 6 £}„, р > 2. Тогда справедливы следующие утверждения.
сг=(<7і