Стягиваемые булевы функции и минимизация в нормальных формах

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

Оглавление
Введение
Глава I. Основные понятия и обзор результатов
§1. Основные понятия и терминология
§2. Обзор результатов, минимизация в дизъюнктивных
и полиномиальных нормальных формах
Глава II. Стягиваемые функции и построение сокращенной дизъюнктивной нормальной формы
§3. Оператор минимума и его свойства
§4. Построение сокращенной дизъюнктивной нормальной формы по полурешетке минимумов функции
§5. Стягиваемые функции
Глава III. Минимизация в полиномиальных нормальных
формах
§6. Алгоритмы построения минимальных полиномиальных нормальных форм, использующие библиотеки
представителей
§7. Нахождение сложных функций в классе полиномиальных нормальных форм
§8. Алгоритмы нахождения приближенных минимумов в
полиномиальных нормальных формах
Заключение
Список литературы
Введение
В конце XIX - начале XX веков исследования по булевым функциям были связаны с применением к логике и основаниям математики. При этом булевы функции рассматривались как логические формулы над связками конъюнкции, дизъюнкции. импликации, отрицания и эквивалентности. Для становления исследований по булевым функциям как самостоятельной теории существенным явилось открытие новых приложений к описанию релейно-контактных схем и помехоустойчивому кодированию. Задача минимизации булевых функций в классе дизъюнктивных нормальных форм (д.н.ф.) и полиномиальных нормальных форм (п.н.ф.) состоит в построении по произвольно заданной булевой функции реализующего ее терма вида ’Дизъюнкция конъюнкций” для д.н.ф. и ’’суммы конъюнкций” для п.н.ф. содержащие минимальное число слагаемых или дизъюнктов. Отдельные задачи, связанные с минимизацией д.н.ф., привлекали внимание специалистов по математической логике еще в XIX веке. Однако актуальной задача минимизации стала лишь в 40-50 годах XX века в связи с применением языка алгебры логики для синтеза управляющих устройств и электронных вычислительных машин. В 50-80 годах XX века было создано большое число эвристических алгоритмов минимизации, возникли различные методы и приемы, механические и электронные устройства, минимизи-
рующие карты и диаграммы для поиска минимальных дизъюнктивных нормальных форм булевых функций.
В основу многих алгоритмов минимизации в классе д.н.ф. положено решение известной комбинаторной задачи о нахождении минимального покрытия множества [6, 7, 18]. Задача минимального покрытия для минимизации в д.н.ф. состоит в том, чтобы из множества простых импликант функции выбрать минимальное подмножество простых импликант, которые реализуют исходную функцию. Задача построения всех простых импликант функции является частью задачи минимизации в классе д.н.ф. и заключается в построении сокращенной д.н.ф. Одним из наиболее известных алгоритмов построения сокращенной д.н.ф. является алгоритм Блейка-Порецкого [17, 24]. Квайн [36] предложил алгоритм построения сокращенной д.н.ф. по совершенной. В работах [13, 15] предложен модифицированный алгоритм Квайна, и этот алгоритм имеет сложность порядка т4, где т — длина совершенной д.н.ф. Из [5] известно, что длина совершенной д.н.ф. ассимптотически равна 2п , где п — количество переменных. Значит сложность алгоритма ассимптотически равна 16га-1.
Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И.И.Жегалкина [8, 9]. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения в кругах, далеких от логики.
§ 4. Построение сокращенной дизъюнктивной нормальной формы по полурешетке минимумов функции
В параграфе введен метод построения сокращенной д.н.ф. функций по верхней полурешетке минимумов этой же функции. Приведены два алгоритма, один для случая, когда исходная функция представлена в виде совершенной д.н.ф., второй для случая, когда исходная функция представлена д.н.ф. произвольного вида. Для алгоритма, исходная д.н.ф. которого — совершенная, дана оценка сложности.
Предложение 2.2. Пусть f(z,..., zk) — булева функция. Если существует набор переменных у = [у,... ,ym), {г/ь • • •, Ут} С {zu...,zk} такой, что ш?/(х, у) ф 0 и р — импликанта m~f(x,y), то р является импликантой и для
f(x,y), где X = (xi,...,xn),{xu...,xnj =
= {zh ..., zk}{yh ...,ym}. Если р простая для m f{x, у), то она простая и для f(x,y).
Доказательство. Пусть р — импликанта для ш~/(х, у), то
естьр/т~/(д, у) — ш~/(ж, у), тогда по свойству 1) оператора минимума
pvn/(^,f) =Uf[x,f).

Значит р V f(x, т) = f{x, т) для любого т, откуда следует, что р V f{x, у) = /(т,р).
Пусть pi является простой импликантой mf~f{x,y) и су-