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

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

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

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

Например, для Минимизация булевых функций - student2.ru Значит Минимизация булевых функций - student2.ru и Минимизация булевых функций - student2.ru являются простыми импликантами функции F.

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

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

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

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

Минимизация булевых функций - student2.ru + Минимизация булевых функций - student2.ru =X.

Говорят, что два члена XY и Минимизация булевых функций - student2.ruсклеиваются по переменной Y.

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

Минимизация булевых функций - student2.ru + Минимизация булевых функций - student2.ru =X+XY+ Минимизация булевых функций - student2.ru .

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

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

X+XY=X.

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

Действительно, пусть F задана в ДНФ; например, F=F1+F2+F3. Предположим, что F1, F2, и F2, F3 попарно склеиваются, т.е. F1+F2=G1, F2+F3=G2, тогда G1+G2= F1+F2+F3=F.

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

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

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

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

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

Пример.

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

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

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

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

1 - 2 Минимизация булевых функций - student2.ru

1 - 3 Минимизация булевых функций - student2.ru

2 - 4 Минимизация булевых функций - student2.ru

3 - 4 Минимизация булевых функций - student2.ru

4 - 6 Минимизация булевых функций - student2.ru 5 - 6 Минимизация булевых функций - student2.ru

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

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

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

1 - 4 Минимизация булевых функций - student2.ru

2 - 3 Минимизация булевых функций - student2.ru

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

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

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

Таблица 5.

Простые импликанты Конституенты единицы Минимизация булевых функций - student2.ru Минимизация булевых функций - student2.ru Минимизация булевых функций - student2.ru Минимизация булевых функций - student2.ru Минимизация булевых функций - student2.ru Минимизация булевых функций - student2.ru
Минимизация булевых функций - student2.ru + + + +    
Минимизация булевых функций - student2.ru       +   +
Минимизация булевых функций - student2.ru         + +

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

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

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

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

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

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

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

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

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

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

Минимизация булевых функций - student2.ru   Рис. 23. Карта Карно для функции 4-х переменных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  Минимизация булевых функций - student2.ru Рис. 24. Карта Карно для функции 5-ти переменных

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

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

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

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

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

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

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

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

Наши рекомендации