Сложность булевых функций в классах полиномиальных форм

• Автор: Балюк, Александр Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Иркутск
• Количество страниц: 94 с.

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

Глава 1. Классы полиномиальных форм

§ 1. Основные понятия и терминология

§ 2. Иерархия классов операторных пучков

§ 3. Обзор результатов по полиномиальным формам

Глава 2. Функция Шеннона и нахождение коэффициентов полиномиальных форм

§ 4. Коэффициенты полиномиальных форм по обратимым операторам

§ 5. Общие свойства функции Шеннона для операторных полиномиальных формах

§ 6. Точные значения функции Шеннона для а-кронекеровых и

свободно-кронекеровых классов полиномиальных форм

Глава 3. Сложные функции в классах полиномиальных форм
§ 7. Функции экспоненциальной сложности в классе полиномиальных нормальных форм
§ 8. Свойства специальных булевых функций
§ 9. Функции наибольшей сложности в классах операторных полиномиальных нормальных форм
§ 10. Функции наибольшей сложности в классах операторных
полиномиальных форм
Заключение
Список литературы

Введение

При проектировании современных вычислительных устройств важную роль играет аппарат дискретных функций. На современном этапе развития цифровой техники наиболее распространенным является кодирование сигнала двумя или тремя состояниями. Третье состояние чаще всего используется только на аппаратном уровне и лишь для указания того, что устройство еще не обработало входные данные или данные не готовы. Это связано с физическими ограничениями на скорость срабатывания устройств. Несмотря на то, что скорость работы цифровых устройств постоянно повышается, существует некоторый физический предел этого роста. Поэтому в настоящее время ведутся разработки дискретных устройств с большим числом состояний. Однако, пока они носят экспериментальный характер.
До сих пор аппарат булевых функций является наиболее адекватным для проектирования цифровой, в том числе микропроцессорной техники. Постоянное стремление к повышению быстродействия систем, уменьшению их размера, потребляемой энергии и стоимости ставит задачи не только поиска новых технологий реализации цифровых устройств, но и более простой и эффективной реализации существующих. Это ведет к интенсивному исследованию и проектированию различных регулярных структур. Одними из наиболее распространенных являются программируемые логические матрицы (PGA и FPGA).
Теория булевых функций изначально была ориентирована на решение практических задач реализации цифровых устройств. Были созданы различные математические модели непосредственно отражающие аппаратную реализацию. Это оказало влияние и на терминологию. Так в теории булевых функций исследуются схемы из функциональных элементов, П-схемы, релейно-контактные схемы и другие структуры.
Одним из основных способов задания булевых функций является

формульное или, иначе, термальное представление. Одним из вопросов формульных представлений является вопрос о принципиальной возможности реализации тех или иных булевых функций формулами, использующими специально выбранные, базисные функции. Этот вопрос был решен Э. Постом [20, 44, 45].
И в теории, и в приложениях одним из наиболее интересных вопросов является вопрос о сложности представлений булевых функций с помощью тех или иных структур. Важными результатами в этом направлении, являются асимптотически точные оценки сложности реализаций булевых функций формулами и схемами из функциональных элементов, которые принадлежат О. Б. Лупанову [15, 16, 17, 18, 29]. Однако, несмотря на полученные экспоненциальные оценки, нахождение конкретных функций большой сложности, другими словами, нахождение эффективных нижних оценок, сопряжено с определенными трудностями [30, 31]. К настоящему времени построены лишь булевы функции, сложность которых в классе схем из функциональных элементов линейна [34], а в классе формул полиномиальна. Обзор результатов по этим вопросам можно найти в [21, 27, 28]. В более специализированных классах представлений удается получить более высокие эффективные нижние оценки сложности.
Одной из разновидностей представлений булевых функций является реализация их нормальными формами. Нормальные формы непосредственно реализуются на программируемых логических матрицах. Поэтому их исследование представляет определенный практический интерес.
Хорошо исследован вопрос о реализации булевых функций дизъюнктивными и конъюнктивными нормальными формами [25, 33, 42, 46, 26]. Однако здесь уже для хорошо известных и часто применяемых функций, например, для линейной, найдены высокие нижние оценки сложности, которые совпадают с верхними оценками [19]. Величина этих оценок накладывает определенные ограничения на возможности практической

Таким образом, матрица 2.1 имеет диагональный вид. Следовательно, пучок В, определяемый нумерацией (Ъ°,..., Ъ1), является обратным к А.
Осталось только применить теорему 1. <
§ 5. Общие свойства функции Шеннона для операторных полиномиальных формах
Введем специальным образом отношение эквивалентности на классах базисных пучков. Пусть ф : {е, р, (1} -л {е,р,с1} — взаимнооднозначное отображение. Обобщим это отображение на операторы, пучки и классы пучков. Пусть фп : {е,р, с!} —» {е,р, Ф = {фп | п 6 М}.
• Пусть а — произвольный оператор длины п. Определим отображение Ф по правилу Ф(а) = Ъ, где Ь, = ф{(аф, г € {0,..., п}.
• Отображение Ф продолжается на пучок следующим образом. Пусть А — пучок операторов размерности п и (а0,..., а1) — его нумерация, тогда Ф(А) = В, где В — пучок размерности п, который определяется своей нумерацией (Ь°,..., Ъ1), в которой Ъа — Ф(а<г), д € Еп.
• Отображение Ф продолжается на класс пучков С следующим образом: Ф(С) = {Ф(А) I А € С).
Классы пучков С и С-2, будем называть -^-эквивалентными, если существует определенное выше отображение Ф, такое что Ф((71) = С2. Очевидно, что ^-эквивалентность является отношением эквивалентности.
Легко видеть, что для любых двух операторов а и Ъ одинаковой длины, классы К [а) и К(Ь). Е(а) и .Е'(Ь), С(а) и С(Ъ) попарно ф-эквивалентны.