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

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

ПРИМЕР:

Сложность булевой функции

равна 15, а сложность функцииравна 3. В то же время обе эти формулы описывают одну и ту же булеву функцию.

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

Определение:

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

Определение:

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

Определение:

Булева функция является импликантом функции, если для всякого наборазначений аргументов выполнено неравенство:. Данное условие может быть записано в эквивалентном виде:=.

Определение:

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

Лекция 14 Стандартные формулы преобразования булевых функций

1) – правило поглащения;

2) – правило поглащения;

3) – правило склеивания;

4) – правило вычеркивания.

Теорема:

МДНФ функции, отличной от 0 или 1, является дизъюнкция некоторых простых импликантов.

Доказательство:

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

Геометрическая интерпретация

Любой двоичный набор можно рассматривать как вершину единичногоn-мерного гиперкуба. Тогда любую функциюможно задать множеством вершин куба, на которых она принимает значение 1. Функцияявляется импликантом для функцииf, если соответствующее ей множество вершин содержится во множестве вершин дляf. Всякая конъюнкциязадает вершины (n-p)-мерного гиперкуба, для которого,,…,, а значение остальных (n-p) компонент могут быть выбраны произвольно. Простой импликант определяет подкуб, все вершины которого принадлежат множеству единичных вершин функций. При этом он не содержится ни в каком большем подкубе, обладающим этим свойством. Такие подкубы называютсямаксимальными.

Всякая ДНФ задает некоторое покрытие множества единичных вершин множества подкубами в соответствии с ее формулами.

ПРИМЕР:

Рассмотрим 3-х мерный случай: ,максимальные подкубы:

,.