Минимизация булевых функций кратко

Обновлено: 02.07.2024

В общем случае существует несколько способов записи одной и той же булевой функции. Сложность записи булевой функции можно оценивать числом элементарных операций, используемых в такой записи и образующих функционально полную систему булевых функций.

Задачу поиска наиболее простой записи булевой функции называют задачей минимизации. Такая задача возникает в ряде приложений. В частности, при проектировании устройств автоматики или вычислительных устройств их работа может быть описана некоторой булевой функцией или системой таких функций. Каждой элементарной функции в устройствах соответствует некоторый физический элемент (ячейка), реализующий эту функцию. И, следовательно, представлению булевой функции в минимальной форме соответствует более простое устройство автоматики или вычислительной техники по сравнению с устройством, реализующим не минимальную булеву функцию.

Наиболее распространённой формой представления булевой функции является дизъюнктивная нормальная форма. Поэтому задачу упрощения булевых функций обычно формулируют в классе ДНФ.

ДНФ булевой функции называют минимальной, если ей соответствует наименьший суммарный ранг R по сравнению с другими ДНФ этой же функции. Минимальную ДНФ булевой функции будем обозначать как МДНФ.

Поскольку методы минимизации булевых функций, разработанные для ДНФ, достаточно легко переносятся на конъюнктивные нормальные формы (КНФ), ограничимся рассмотрением методов минимизации в классе ДНФ.

В основном эти методы в явной или в неявной форме основаны на выполнении трех операций. Рассмотрим эти операции.

Две элементарных конъюнкции одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком отрицания одной из переменных.

Например, следующие элементарные конъюнкции являются соседними:

и .

Первая операция, называемая операцией склеивания,для элементарных конъюнкций осуществляется по следующему правилу: дизъюнкцию двух соседних конъюнкций некоторого ранга r можно заменить одной элементарной конъюнкций ранга r-1, являющейся общей частью исходных конъюнкций.

где A – некоторая элементарная конъюнкция. В этом случае говорят, что конъюнкции и склеиваются по переменной x. Например:

Здесь и две заданные конъюнкции были склеены по переменной , в одной из которых эта переменная без отрицания, а в другой – с отрицанием.

Вторая из операций называется операцией поглощения, и она осуществляется по правилу:

Дизъюнкцию двух элементарных конъюнкций разных рангов, из которых одна является собственной частью другой, можно заменить конъюнкцией, имеющим меньший ранг.

где А и В – некоторые элементарные конъюнкции.

Третья операция – операция неполного склеивания:

Введем некоторые понятия.

Булева функция называется импликантой функции , если функция равна нулю на всех тех же наборах, на которых равна нулю и функция f. Если есть импликанта функции f, то этот факт записывают следующим образом: .

Рассмотрим импликанты функции .

x	y
0	0	0	0	0	0	0
0	1	1	1	0	0	0
1	0	1	0	1	0	1
1	1	0	0	0	0	1

Конституента единицы в СДНФ функции f всегда является её импликантой. Для функции функции и являются конституентами елиницы из ее СДНФ.

Из определения импликанты следует, что если на некотором наборе значение равно единице, то и значение функции f на этом же наборе также равно единице и в этом случае говорят, что импликанта покрывает единицу функции f.

Чем меньше переменных содержит импликанта функции f по сравнению с конституентой единицы из ее СДНФ, тем больше единиц функции она покрывает.

Элементарная конъюнкция называется простой импликантой булевой функции , если U является импликантой функции f и никакая собственная часть U не является импликантой f .

Рассмотрим пример. Зададим функция f(x, y, z) таблицей истинност. (таблица ниже). СДНФ функции имеет вид:

Укажем импликанты и простые импликанты нашей функции.

x	y	z	f(x, y, z)
0	0	0	1	0	0	0	0	1
0	0	1	1	0	1	0	0	1
0	1	0	0	0	0	0	0	0
0	1	1	1	1	1	0	0	0
1	0	0	1	0	0	1	1	1
1	0	1	1	0	0	0	1	1
1	1	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0

Как видим из таблицы, конституента единицы является импликантой нашей функции, ее собственная часть - простой импликантой, поскольку ни , ни не являются импликантами. Аналогично имеем, , - импликанты нашей функции, - простая импликанта; покрывает 4 единицы нашей функции. Простые импликанты в таблице выделены серым цветом.

Справедливы следующие теоремы.

Всякая булева функция может быть представлена как дизъюнкция всех своих простых импликант.

Дизъюнкция всех простых импликант функции f называется сокращённой ДНФ этой функции. Сокращённая ДНФ булевой функции единственна.

Теорема 2. (теорема Квайна).

Если в совершенной дизъюнктивной нормальной форме булевой функции выполнить все операции неполного склеивания, а затем все операции поглощения, то в результате будет получена сокращенная дизъюнктивная нормальная форма этой функции, или дизъюнкция всех ее простых импликант.

Как следует из теоремы, чтобы получить все простые импликанты, мы проводим операции неполного склеивания. Это связано с тем, что одна и та же элементарная конъюнкция дизъюнктивной формы может склеиваться с несколькими конъюнкциями. При каждом таком склеивании образуются различные импликанты и, поэтому мы оставляем в выражении каждую элементарную конъюнкцию для использования ее при других склеиваниях.

От сокращенной ДНФ переходим к минимальной дизъюнктивной нормальной форме – МДНФ.

Рассмотрим один из методов минимизации булевых функций

Метод Квайна.

Этот метод удобен для нахождения МДНФ функции от любого числа переменных.

Алгоритм метода Квайна.

1. Записываем СДНФ булевой функции .

2. Проводим все возможные операции неполного склеивания конституент единицы СДНФ булевой функции, в результате операций получим элементарные конъюнкции ранга (n – 1). Проводим, если это возможно, операции поглощения между конъюнкциями различных рангов. Затем вновь проводим операции неполного склеивания и поглощения до тех пор, пока это возможно. Элементарная конъюнкция, которая не может больше участвовать в склеивании, является простой импликантой булевой функции.

3. Дизъюнкция простых импликант приводит к сокращённой ДНФ булевой функции: , где − простая импликанта.

5. Выбираем существенные импликанты, т.е. такое минимальное количество простых импликант, чтобы они совместно своими единицами покрывали все колонки импликантной матрицы.

6. Дизъюнкция существенных импликант приводит к МДНФ.

Рассмотрим пример. Найдем МДНФ булевой функции, заданной СДНФ:

1. Проведем операции неполного склеивания, их лучше выполнять последовательно, слева на право.

.
.
.
.
У нас все конституенты единицы участвовали в склеивании, поэтому операций поглощения нет. Элементарные конъюнкции больше не склеиваются между собой, следовательно, мы получили простые импликанты.

2. Из простых импликант строим сокращенную ДНФ функции:
.

3. Строим таблицу покрытия

Простые импликанты	Конституенты единицы

	1	1	0	0	0
	0	1	1	0	0
	0	0	1	0	1
	0	0	0	1	1

Выбираем существенные импликанты.

Первая импликанта входит в МДНФ обязательно, она единственная, кто покрывает единицу функции на наборе 000 (единственная единица в первой колонке), затем можно выбрать 3-ю и 4-ю простые импликанты. Получили МДНФ:

У нашей функции две МДНФ: к первой импликанте можно выбрать 2-ю и 4-ю. Получим:

Как видим, у булевой функции может быть несколько МДНФ.

Ранг обеих МДНФ, R = 6.

В тоже время, построив СКНФ заданной функции и проведя минимизацию методом Квайна в базисе КНФ, мы получим единственную МКНФ (минимальную конъюнктивную нормальную форму) меньшего ранга, R = 5.

Рассмотрим еще пример.

Проведем операции неполного склеивания.

1. .

2. .

3. .

4. .

5. .
Все конституенты единицы участвовали в склеивании, у нас нет операции поглощения. Импликанта больше не участвует в склеивании, это простая импликанта. Оставшиеся импликанты могут склеиваться между собой, продолжим склеивание.

6. .

7. .

Операции поглощения у нас опять нет, получили 2 простые импликанты. Сокращенная ДНФ функции имеет вид:

Построим таблицу покрытия.

Простые импликанты	Конституенты единицы

Обратите внимание, что простая импликанта состоит только из отрицания одной переменной и покрывает 4 единицы нашей функции.

Минимизация логических функций является одной из типовых задач в процессе обучения схемотехнике. Посему считаю, что такая статья имеет место быть, надеюсь Вам понравится.

Зачем это нужно?

Сложность логической функции, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок.

К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно, метод испытания импликант, метод импликантных матриц, метод Квайна-Мак-Класки и др. Эти методы наиболее пригодны для обычной практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. В тех случаях, когда число аргументов больше шести, обычно используют метод Квайна-Мак-Класки.

В процессе минимизации той или иной логической функции, обычно учитывается, в каком базисе эффективнее будет реализовать ее минимальную форму при помощи электронных схем.

Минимизация логических функций при помощи карт Карно

Карта Карно — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:

Возможность поглощения следует из очевидных равенств

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

$\infty$

Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2 n (n целое число = 0…) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
Область должна быть как можно больше, а кол-во областей как можно меньше;
Области могут пересекаться;
Возможно несколько вариантов накрытия.

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

Цель данного раздела – изложение основных методов построения минимальных дизъюнктивно нормальных форм.

6.1 Сокращенная и тупиковая ДНФ. В разделе 3 было показано, что любая булева функция может быть представлена дизъюнктивной нормальной формой. Следует отметить, что дизъюнктивная нормальная форма часто допускает упрощение. При этом путем различных тождественных преобразований получится дизъюнктивная нормальная форма, эквивалентная исходной, но содержащая меньшее число вхождений символов.

Дизъюнктивная нормальная форма называется Минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей дизъюнктивными нормальными формами.

Заметим, что если некоторый символ в формуле, скажем , встречается, например, два раза, то при подсчете числа символов в формуле он учитывается два раза.

Основной вопрос данного параграфа – это как для произвольной булевой функции построить ей минимальную дизъюнктивную нормальную форму. Эта задача называется Проблемой минимизации булевых функций.

Существует тривиальный алгоритм построения минимальной ДНФ для произвольной булевой функции . Для этого все ДНФ, составленные из символов упорядочиваются по числу букв и по порядку для каждой ДНФ Д проверяется соотношение . Первая по порядку ДНФ, для которой это соотношение выполняется, есть, очевидно, минимальная ДНФ функции .

Число различных ДНФ, составленных из переменных , равно .

Прежде чем доказать данное утверждение, приведем следующее определение.

Конъюнкция называется Элементарной, если при .

Число R называется Рангом элементарной конъюнкции. В случае r=0 конъюнкция называется Пустой и Полагается равной 1.

Так как каждая из N переменных либо не входит в элементарную, либо входят в нее с отрицанием, либо без отрицания, то число элементарных конъюнкций, составленных из равно . Ясно, что число различных ДНФ, составленных из переменной , равно числу подмножеств множества, из элементов, т. е. .

Рассмотрим геометрическую интерпретацию задачи минимизации булевых функций.

Обозначим через множество всех точек , где . Ясно, что - множество всех вершин единичного n-мерного куба.

Сопоставим каждой булевой функции Подмножество Из , определенное следующим образом:

Вершин трехмерного единичного куба

Данное соответствие является взаимно однозначным и обладает следующими свойствами:

1) булевой функции Соответствует подмножество ;

2) булевой функции соответствует подмножество ;

3) булевой функции соответствует подмножество .

Докажем утверждение 2. Пусть

А это значит, что .

Пусть ДНФ, где - элементарные конъюнкции. Подмножество называется интервалом R-го ранга, если оно соответствует элементарной конъюнкции К R-го ранга. Как показано выше, . Итак, с каждой ДНФ функции F связано покрытие такими интервалами , что .

Пусть - ранг интервала . Тогда совпадает с числом букв в ДНФ функции .

Теперь ясно, что задача построения минимальной ДНФ сводится к отысканию такого покрытия подмножества интервалами , чтобы число было наименьшим.

Интервал , содержащий , называется Максимальным для булевой функции, если не существует интервала , такого, что .

Заметим, что соотношение выполняется тогда и только тогда, когда элементарная конъюнкция получается из элементарной конъюнкции К путем вычеркивания непустого числа сомножителей.

Очевидно, что каждый интервал из содержится в некотором максимальном интервале. Если - список всех максимальных интервалов подмножества , то нетрудно видеть, что .

ДНФ булевой функции f, соответствующая покрытию подмножества всеми максимальными интервалами, называется Сокращенной ДНФ функции F.

Ясно, что сокращенная ДНФ для любой булевой функции f определяется однозначно.

Пример 1. Пусть . Обозначим , , . Найдем соответствующие этим конъюнкциям интервалы , , .

Изобразим эти интервалы

Очевидно, что и - все максимальные интервалы. Интервал не является максимальным, ибо . Следовательно, покрытию подмножества соответствует сокращенная ДНФ функции , равная .

Данный геометрический подход дает и метод построения сокращенной ДНФ.

Теперь рассмотрим аналитический метод построения сокращенной ДНФ – метод Блейка. Этот метод основан на следующей теореме.

Теорема 1. Если в произвольной ДНФ булевой функции F произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получиться сокращенная ДНФ функции F.

Следовательно, чтобы найти сокращенную ДНФ, надо к произвольной ДНФ данной функции применить правило обобщенного склеивания до тех пор, пока это возможно, а затем правило поглощения.

Пример 2. Найти сокращенную ДНФ для функции . Применяя правило обобщенного склеивания, получаем: .

Затем правило поглощения и находим сокращенную ДНФ: .

Рассмотрим еще один метод построения сокращенной ДНФ – метод Нельсона. Этот метод основан на следующей теореме.

Теорема 2. Если в произвольной КНФ булевой функции раскрыть все скобки в соответствии с дистрибутивным законом и устранить все элементарные поглощения, то в результате получится сокращенная ДНФ этой функции.

Пример 3. Найти сокращенную ДНФ для функции

После раскрытия скобок с помощью дистрибутивного закона, получаем:

Так как , , то имеем:

Далее, применяя правило поглощения, получаем сокращенную ДНФ:

Рассмотрим табличный метод построения сокращенной ДНФ. Этот метод основан на составлении прямоугольной таблицы (минимизирующей карты).

Минимизирующие карты для булевых функций от трех и от четырех переменных изображены на следующих таблицах.

X1 X2

Объединяя соседние клетки, соответствующие единичным значениям булевой функции f в максимальные интервалы, и сопоставляя им элементарные конъюнкции, получим сокращенную ДНФ. Отметим, что клетки, расположенные по краям таблицы, также считаются соседними. Покажем работу этого метода на следующем примере.

Пример 4. Найти сокращенную ДНФ для функции, заданной следующей таблицей.

X1 X2

В данной таблице объединены клетки в максимальные интервалы

Этим интервалам соответствуют элементарные конъюнкции

Следовательно, сокращенная ДНФ для данной функции имеет вид:

Построение сокращенной ДНФ есть только первый этап решения задачи минимизации булевой функции. В общем случае сокращенная ДНФ не является минимальной. Следующая теорема устанавливает связь между минимальной и сокращенной ДНФ.

Теорема 3. Минимальная ДНФ булевой функции получается из сокращенной ДНФ данной функции путем удаления некоторых элементарных конъюнкций.

Доказательство этого утверждения следует из того факта, что покрытие подмножества , отвечающее минимальной ДНФ, состоит только из максимальных интервалов. Действительно, если бы покрытие содержало не максимальный интервал, то его можно было бы заменить объемлющим максимальным интервалом. В результате этого сумма рангов интервалов данного покрытия уменьшилась бы, что противоречит предположению о минимальности ДНФ.

Покажем, что в классе монотонных функций понятия минимальной и сокращенной ДНФ совпадают.

Теорема 4. Сокращенная ДНФ монотонной булевой функции не содержит отрицаний переменных и является минимальной ДНФ этой функции.

Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции Равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .

Получили противоречие с максимальностью интервала . Итак, сокращенная ДНФ булевой функции Не содержит отрицаний переменных.

Пусть - любая элементарная конъюнкция из сокращенной ДНФ. Конъюнкция К является единственной конъюнкцией сокращенной ДНФ, которая обращается в единицу в вершине с координатами . Действительно, если бы в сокращенной ДНФ какая-нибудь другая элементарная конъюнкция обращалась в этой вершине в 1, то не содержала бы, во-первых, букв , и, во-вторых, букв . Поэтому в конъюнкцию могли бы входить лишь буквы , причем не все. Но тогда . Получили противоречие с максимальностью интервала . Следовательно, для любого максимального интервала существует вершина куба , которая покрывается только этим интервалом. Поэтому из покрытия соответствующего сокращенной ДНФ, нельзя удалить ни одного из интервалов. Теперь, применяя предыдущую теорему, получаем требуемый результат.

Следует отметить, что сокращенная ДНФ в большинстве случаев допускает дальнейшие упрощения за счет того, что некоторые элементарные конъюнкции могут поглощаться дизъюнкциями других элементарных конъюнкций. Действительно, в сокращенной ДНФ

Элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т. е. .

Ввиду этого введем следующее определение.

Покрытие области истинности булевой функции максимальными интервалами называется Неприводимым, если после удаления из него любого интервала оно перестает быть покрытием. ДНФ булевой функции , соответствующая неприводимому покрытию, называется Тупиковой.

Теорема 5. Всякая минимальная ДНФ является тупиковой.

Доказательство этого утверждения следует из того, что покрытие, соответствующее минимальной ДНФ, является неприводимым.

Заметим, что булева функция может обладать несколькими различными минимальными ДНФ. Существуют также тупиковые ДНФ, не являющиеся минимальными ДНФ. Соответствующие примеры будут разобраны ниже.

Из того, что минимальная ДНФ является тупиковой, следует общая схема решения задачи минимизации булевых функций.

1. Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2. Строятся все тупиковые ДНФ.

3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Рассмотрим алгоритм построения всех тупиковых ДНФ. Суть данного алгоритма состоит в следующем:

1) для булевой функции строим сокращенную ДНФ;

2) для каждой вершины из выделяем в сокращенной ДНФ функции F все такие элементарные конъюнкции , что ;

3) составляем выражение вида

4) применяем к выражению вида (*) законы дистрибутивности и поглощения. В результате получаем .

представление булевых функций нормальными формами (см. Булевых функций нормальные формы). простейшими относительно нек-рой меры сложности. Обычно под сложностью нормальной формы понимается число букв в ней. В этом случае простейшая форма наз. минимальной. Иногда в качестве меры сложности рассматривается число элементарных конъюнкций в дизъюнктивной нормальной форме или число сомножителей в конъюнктивной нормальной форме. В этом случае простейшая форма наз. кратчайшей. В силу двойственности дизъюнктивных и конъюнктивных нормальных форм достаточно рассматривать только дизъюнктивные нормальные формы (д. н. ф.). Построение кратчайших и минимальных д. н. ф. имеет каждое свою специфику. Множества минимальных и кратчайших д. н. ф. одной и той же функции могут находиться в любых теоретико-множественных соотношениях: содержаться одно в другом, иметь пустое пересечение или непустую симметрическую разность. Если для функции f обозначить через сложность минимальной д. н. ф., через - минимальную сложность кратчайшей д. н. ф., а через - наибольшее из отношений по всем функциям от ппеременных, то справедливо асимптотич. соотношение:

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

Исходным заданием функции в задаче минимизаций обычно считают таблицу, совершенную д. н. ф. (см. Бyлевых функций нормальные формы).или произвольную д. н. ф. На первом этапе от исходного задания осуществляется переход к так наз. сокращенной д. н. ф., к-рая определена для каждой функции однозначно. Существует большое число методов реализации этого перехода. Наиболее универсальный метод состоит в выполнении над д. н. ф. преобразований вида

Сокращенная д. н. ф. обладает тем свойством, что любая минимальная д. н. ф. получается из нее удалением нек-рых элементарных конъюнкций. Второй, наиболее трудоемкий, этап состоит в получении из сокращенной д. н. ф. всех тупиковых д. н. ф., среди к-рых содержатся и все минимальные. На этом этапе обычно используется геометрич. представление булевых функций. Пусть Е п обозначает множество всех вершин n-мерного единичного куба. Каждой булевой функции взаимно однозначно соответствует подмножество N^ , таких вершин где Пусть - элементарная конъюнкция ранга r, тогда множество наз. интервалом ранга r, соответствующим элементарной конъюнкции Говорят, что система интервалов образует покрытие множества , если

Так как равенства

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

Выбор минимальных д. н. ф. из всех тупиковых также оказывается весьма трудоемким процессом, поскольку для "почти всех" булевых функций от паргументов различных тупиковых д. н. ф. не меньше, чем . При этом разброс сложностей тупиковых д. н. ф. может быть очень велик, так что выбор случайной тупиковой д. н. ф. вместо минимальной может привести к большой погрешности.

Оценки числа тупиковых д. н. ф. и разброса сложностей показывают, что естестве. (входит во все минимальные д. н. ф. для ). Последний факт устанавливается обычно при помощи анализа конъюнкций, близких к рассматриваемой, т. е. входящих в окрестность этой конъюнкции (см. Алгоритм локальный). При этом разрешается накапливать информацию об элементарных конъюнкциях и использовать ее в дальнейшем анализе. Процедуры указанного вида получили назв. локальных алгоритмо в упрощения. Ниже приводятся нек-рые из них. В их описании используется понятие окрестности k- гоо порядка элементарной конъюнкции в д. н. ф. .

Окрестность нулевого порядка состоит из одной конъюнкции . Если есть окрестность (k-1)-го порядка, то окрестность k-ro порядка состоит из всех конъюнкций д. н. ф. , удовлетвбряющих одному из следующих условий:

1) имеет непустое пересечение хотя бы с одним интервалом, соответствующим конъюнкции из ;

2) , где удовлетворяют условию 1).

Алгоритм Куайна. На каждом шаге рассматривается окрестность одной из конъюнкций в д. н. ф. . В процессе работы алгоритма для каждой из конъюнкций делается попытка вычислить одно из свойств: -

" входит во все минимальные д. н. ф.", -

" - не входит ни в одну минимальную д. н. ф.".

Алгоритм работает следующим образом. 1) По очереди для каждой конъюнкции из строится окрестность . Проверяется включение: Если оно не имеет места, то отмечается нек-рым способом как входящая во все минимальные д. н. ф. В этом случае говорят, что входит в ядро д. н. ф. (является ядровой конъюнкцией). 2) Пусть на первом этапе в отмечены конъюнкции . Остальные конъюнкции из упорядочиваются, и для каждой такой конъюнкции проверяется включение Конъюнкции, для к-рых это соотношение выполнено, не входят ни в одну минимальную д. н. ф.; они удаляются из .

Алгоритм регулярных точек. Этот алгоритм на каждом шаге осматривает окрестность конъюнкции в д. н. ф. и удаляет конъюнкции, не входящие ни в одну тупиковую и, следовательно, ни в одну минимальную д. н. ф. В описании алгоритма используется понятие -пучка в д. н. ф. , представляющего собой для рассматриваемой точки из множество интервалов таких, что . Для конъюнкции из д. н. ф. точка из наз. регулярной относительно (21, 91), если существует точка такая, что и . Множество наз. р е-гулярным относительно , если все его точки регулярны относительно . Описываемый алгоритм основывается на том, что конъюнкция из сокращенной д. н. ф. функции f не входит ни в одну тупиковую д. н. ф. функции f тогда и только тогда, когда есть множество, регулярное относительно . Алгоритм проверяет в нек-ром порядке, являются ли интервалы конъюнкций, входящих в д. н. ф., регулярными множествами, и удаляет те из них, интервалы к-рых регулярны. Свойство интервала быть регулярным относительно полностью определяется окрестностью и, вообще говоря, не определяется окрестностью А- алгоритм. Здесь используется понятие д. н. ф., минимальной относительно д. н. ф. , т. е. такой д. н. ф., к-рая минимальна среди всех д. н. ф., эквивалентных и получающихся из опусканием нек-рых элементарных конъюнкций. Рассматриваются два свойства элементарной конъюнкции в д. н. ф.: - " входит во все д. н. ф., минимальные относительно ", н - " не входит ни в одну д. н. ф., минимальную относительно ".

Считается, что , если свойство имеет место, и в противном случае. Предполагается, что д. н. ф. составлены из конъюнкций с информационными отметками . При этом равенство означает, что свойство не вычислено ( =1, 2), а равенства означают, что ( =1,2). Конъюнкция с информационными отметками обозначается через . А-алгоритм вычисляет значения свойств для конъюнкций из д. н. ф. , используя для этого лишь конъюнкции из окрестности и их информационные отметки. Для конъюнкции ранга г из д. н. ф. множество наз. множеством первого типа относительно , если в д. н. ф. существуют конъюнкции рангов такие, что и

Разностью д. н. ф. наз. д. н. ф., состоящая из элементарных конъюнкций, входящих в и не входящих в .

До применения А-алгоритма все конъюнкции из рассматриваемой д. н. ф. имеют отметку ( ). Если выполнены шагов и отметку ( ) получили конъюнкции а отметку ( ) - конъюнкции , то -и шаг состоит в следующем. Упорядочивают нек-рым способом конъюнкции из д. н. ф. Если д. н.. ф. пустая, то А- алгоритм заканчивает свою работу. В противном случае после упорядочивания к.-л. способом конъюнкций из этой д. н. ф. выделяются первая по порядку конъюнкция и ее окрестности и в д. н. ф. и проверяется соотношение

Если оно выполнено, то отметка над заменяется на и - й шаг А-алгоритма заканчивается. Если оно не выполнено, то проверяется, можно ли представить в виде - множество, регулярное относительно ( ), а - множество первого типа относительно ( ). Если можно представить в таком виде, то отметка ( ) над заменяется на отметку ( ), и ( )-й шаг А-алгоритма заканчивается; если - нельзя, то описанная процедура применяется ко второй по порядку конъюнкции, и т. д. Если при этом ни у одной из конъюнкций отметка не изменится, то после просмотра всех конъюнкций работа А-алгоритма заканчивается.

Если за д. н. ф. принять сокращенную д. н. ф. функции , то все конъюнкции, получившие в алгоритме отметку ( ), не входят ли в одну минимальную д. н. ф. функции f; они удаляются из . Конъюнкции, получившие отметку ( ), входят во все минимальные д. н. ф. функции f. Рассматривались также различные частные случаи А-алгоритма.

Кольцевой алгоритм расставляет над конъюнкциями информационные отметки ( ), значение к-рых то же, что и в А-алгоритме. На каждом шаге кольцевой алгоритм использует конъюнкции, входящие в окрестность k-ro порядка нек-рой конъюнкции, и их информационные отметки. Ниже излагается упрощенный вариант этого алгоритма. В полном виде коль-.цевой алгоритм - наилучший в классе локальных алгоритмов со специальной памятью по окрестностям . Описанные выше алгоритмы являются частными случаями общего кольцевого алгоритма. Если

то каждому подмножеству сопоставляется не всюду определенная булева функция множество единиц к-рой есть , а множество нулей есть ; на множестве функция не определена. Множество таких функций обозначается через . До начала работы алгоритма все конъюнкции из рассматриваемой д. н. ф. имеют отметку ( ). Если выполнены i шагов и отметку ( ) получили конъюнкции а отметку ( ) - конъюнкции то -и шаг состоит в следующем. Упорядочивают нек-рым способом конъюнкции из д. н. ф. Если д. н. ф. пустая, то алгоритм заканчивает свою работу. В противном случае после упорядочения к.-л. способом всех конъюнкций этой д. в. ф. для конъюнкции , являющейся первой из них, и для каждой функции f из множества находятся все д. н. ф., реализующие f на ее области определения, к-рые составлены из конъюнкций окрестности и содержат по сравнению с другими такими д. н. ф. наименьшее число символов переменных. Среди них выделяются все те д. н. ф., к-рые, во-первых, не содержат конъюнкций и, во-вторых, содержат все конъюнкции удовлетворяющие условию

Если для всех из конъюнкция входит во все выделенные д. н. ф., то отметка ( ) над заменяется на отметку -и шаг алгоритма заканчивается. Если не входит ни в одну из выделенных д. н. ф., то отметка заменяется на отметку и -и шаг алгоритма заканчивается. В остальных случаях описанная процедура применяется ко второй по порядку конъюнкции и т. д. Если ни у одной из конъюнкций не удается изменить отметку, то на -м шаге работа алгоритма заканчивается. Все конъюнкции, получившие в кольцевом алгоритме над сокращенной д. н. ф. функции отметки (соответственно ), входят во все минимальные д. н. ф. (соответственно не входят ни в одну минимальную д. н. ф.) функции f. Результат применения описанных выше алгоритмов не зависит от способа упорядочения конъюнкций в д. н. ф.

Задача выделения всех конъюнкций, входящих хотя бы в одну и не входящих ни в одну минимальную д. н. ф., не может быть решена алгоритмами, работающими с при k, ограниченных пли недостаточно быстро растущих с ростом пчисла переменных. Ситуация не изменится, если к запоминаемым в алгоритме свойствам P 1 , Р 2 добавить ограниченное или недостаточно быстро растущее с ростом пмножество свойств.

Лит.:[1] Яблонский С. В., Функциональные построения в k-значной логике, 1958 ("Тр. Матем. ин-та АН СССР", т. 51); [2] Журавлев Ю. И., "Проблемы кибернетики", 1962, в. 8, с. 5-44; [3] Quine W. V., "Amer. Math. Monthly", 1959, т. 66, № 9, p. 755-60. Ю. И. Журавлев.

Математическая энциклопедия. — М.: Советская энциклопедия . И. М. Виноградов . 1977—1985 .

Читайте также: