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

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

Если некоторая булева функция φ равна нулю на тех же наборах, на которых равна нулю другая функция F, а также и на некоторых других наборах, то говорят, что функция φ входит в функцию F и является ее импликантой. Условие вхождения записывается следующим образом: jÌF. Например, рассмотрим функцию F=XÅY. Ее импликантами являются функции

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

Например, для Значит и являются простыми импликантами функции F.

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

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

Метод Квайна. Этот метод основан на преобразовании СДНФ с помощью операции неполного склеивания и поглощения.

Операция склеивания (полного) определяется соотношением

+ =X.

Говорят, что два члена XY и склеиваются по переменной Y.

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

+ =X+XY+ .

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

Операция поглощения определяется соотношением

X+XY=X.

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

Действительно, пусть F задана в ДНФ; например, F=F₁+F₂+F₃. Предположим, что F₁, F₂, и F₂, F₃ попарно склеиваются, т.е. F₁+F₂=G₁, F₂+F₃=G₂, тогда G₁+G₂= F₁+F₂+F₃=F.

Покажем, что G₁, G₂ÌF. Действительно, из того, что F=0 следует, что G₁=0 и G₂=0. Если F=1, то может быть либо G₁=0 и G₂=1, либо G₁=1 и G₂=0, либо G₁=1 и G₂=1. Значит G₁ и G₂ равны нулю на всех тех наборах, на которых равна нулю функция F и на некоторых других наборах.

Практически сокращенную ДНФ удобно находить в такой последовательности.

Провести в СДНФ все возможные операции неполного склеивания конституент единицы и все возможные операции поглощения.

Затем провести все возможные операции неполного склеивания и поглощения членов с (n-1) буквой.

Провести все возможные операции неполного склеивания и поглощения членов с числом букв, равным (n-2) и т. д.

Пример.

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

Номера склеиваемых Результат

конъюнкций склеивания

1 - 2

1 - 3

2 - 4

3 - 4

4 - 6 5 - 6

Записываем сокращенную формулу, в которую должны войти конъюнкции, полученные в результате склеивания, и те исходные конституенты единицы, которые не склеились:

В полученном выражении выполняем снова все возможные операции склеивания и поглощения:

1 - 4

2 - 3

Первый и четвертый, второй и третий члены попарно склеиваются. Пятый и шестой члены остаются. Таким образом, получим:

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

Таблица 5.

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

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

.

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

Карты Карно (Вейча). Карта Карно представляет собой прямоугольник, разделенный на клетки, число которых равно числу всех возможных наборов независимых переменных заданной логической функции. Для функции двух переменных карта содержит 4 клетки, для функции 3 переменных - 8 клеток и т.д.

Рассмотрим карту для двух переменных (рис. 21). Каждая клетка карты соответствует конституенте единицы.

Рис. 21. Карта Карно для Рис. 22. Карта Карно для

функции 2-х переменных функции 3-х переменных

С добавлением переменной карта удваивается. На рис. 22 показана карта Карно для функции 3 переменных.

При построении карты можно пользоваться следующим правилом: карта Карно для функции n переменных получается из карты для функции n-1 переменных, если последнюю удвоить путем добавления к ней точно такой же, расположенной симметрично относительно длинной грани. При этом одна половина новой карты помечается новой буквой в утвердительной форме, а вторая половина - той же буквой, но с отрицанием. На рис. 23 показана карта Карно для функции 4-х переменных, полученной из карты, изображенной на рис. 22. В правильно размеченной карте любые две рядом расположенные клетки соответствуют

Рис. 23. Карта Карно для функции 4-х переменных

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

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

1. Заданная функция преобразуется в СДНФ.

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

3. Единицы, расположенные рядом, или симметрично на краях карты, покрываются правильными прямоугольниками. При этом выполняются следующие требования:

- число единиц, покрываемых одним прямоугольником, должно быть равно 2^k, гдеk - целое число;

- каждый прямоугольник должен покрывать как можно больше единиц, а количество покрывающих прямоугольников должно быть как можно меньше;

- одна и та же единица может быть покрыта несколько раз разными прямоугольниками.

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

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

6. Если есть возможность, сокращаем полученную формулу путем вынесения общих членов за скобки.

Пример. Рассмотрим функцию четырех переменных. Пусть СДНФ заданной функции имеет вид:

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

Рис. 24. Карта Карно для функции 5-ти переменных

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

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

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

При выписывании импликанты, получающейся в результате покрытия единиц в карте Карно, можно для контроля пользоваться следующими зависимостями: l=n-k, m=2^k, где l- число букв в импликанте, полученной в результате покрытия, m – число единиц, покрытых данным прямоугольником, k - число букв, поглощенных в результате склеивания, n - число независимых переменных в функции.

Рис. 25. Карта Карно для функции 6-ти переменных