9.4. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

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

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

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

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

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

Пример. Булева функция задана табл. 9.11. Там же приведены все ее вмяли каити. При записи функции и ее импликант в СДНФ имеем:

Таблица 9.11

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

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

1. Дизъюнкция любого числа импликант булевой функции также является импликантой этой функции.

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

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

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

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

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

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

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

Метод Квайна

Метод Квайна основывается на применении двух основных соотношений.

1. Соотношение склеивания

где А — любое элементарное произведение.

2. Соотношение поглощения

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

Для доказательства достаточно показать, что произвольная простая импликанта может быть получена. В самом деле, применяя к операцию развертывания (обратную операции склеивания):

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

Пример. Пусть имеется булеаа функция, заданная таблицей истинности (табл. 9.12). Ее СДНФ имеет вид

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

Таблица 9.12

(произвольно). Выполняем склеивания. Конституента I склеивается только с конституентой 2 (по переменной и с конституентой (по переменной конституента 2 с конституентой 4 и т. д. В результате получаем

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

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

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

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

Пример (продолжение). Имплнкантиая матрица имеет вид (табл. 9.13).

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

Таблица 9.13

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

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Пример (продолжение). Ядром нашей функция являются импликанты Импликанта — лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

Следует отметить, что число крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что

где — число букв, содержащихся в простой импликанте.

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

Пример Минимизировать булеву функцию методом Квайна:

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

2. Восстанавливаем СДНФ функции применяя операцию развертывания

3. Найдем сокращенную ДНФ функция производя в СДНФ все возможные склеивания:

4. Ищем минимальную ДНФ функции по импликантной матрице (табл. 9.14). Ядро булевой функции: Минимальные ДНФ;

Таблица 9.14

Метод Квайна—Мак-Класки

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

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

2. Все номера разбиваются на непересекающиеся группы. Признак образования группы: единиц в каждом двоичном номере конституенты единицы,

3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием).

4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Таблица 9.15

Таблица 9.16

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

1. В СДНФ функции заменим все конституенты единицы их двоичными номерами:

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

3. Склеим номера из соседних групп табл. 9 15. Склеиваемые номера вычеркнем. Результаты склеивания занесем в табл. 9.16.

Склеим номера из соседних групп табл. 9.16 Склеиваться могут только номера, имеющие зиездочки в одинаковых позициях. Склеиваемые номера вычеркнем. Результаты склеивания занесем в табл. 9.17.

4. Имеем три простые импликанты:

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

Табдица 9.17

Таблица 9.18

соответствуют сохранившимся двоичным цифрам:

Заметим, что разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.

Метод Блейка—Порецкого

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

справедливость которой легко доказать. Действительно,

Следовательно,

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

Пример. Булева функция задана произвольной ДНФ.

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

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

После склеивания по имеем

Второй и третий Л элемент ДНФ допускают обобщенное склеивание по переменной После склеивания получаем

Выполнив последнее обобщенное склеивание, приходим к ДНФ:

После выполнения поглощений получаем

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

Метод Нельсона

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

Пример. Булева функция задана ДНФ.

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

После проведения всех поглощений имеем Получена сокращенная ДНФ функции

Метод диаграмм Вейча

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

Таблица 9.19

Таблица 9.20

Таблица 9.21

Таблица 9.22

т. е. приписыванием еще одной диаграммы 3-х переменных к только что рассмотренной, можно получить диаграмму для функции переменных ит. д., однако диаграммы для функций с числом переменных больше 4-х используются редко. Для приведенных диаграмм характерно следующее:

1) каждой клетке диаграммы соответствует свой набор;

2) соседние наборы расположены рядом в строке либо в столбце.

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

О парс единиц правой части диаграммы можно сказать то же самое:

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

Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения ни тех склеиваемых наборах. Число оставшихся переменных, и элементарном произведении определяется легко:

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

Таблица 9.23

навык определения минимальной ДНФ по диаграмме «с первого взгляда». Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Вейча 4-х переменных примыкает к ее правому краю, а верхний «рай диаграммы примыкает к нижнему ее краю. После получения минимального накрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме. Рассмотрим несколько примеров.

Пример. Булева функция имеет следующую СДНФ:

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

Очевидно, простая импликанта не нужна для получения минимальной ДНФ.

Пример. Булевы функции заданы диаграммами Вейча (табл. 9.24; 9.25; 9,26; 9.27; 9.28; 9.29). Найти их минимальные ДНФ. Минимальные покрытия единиц показаны в таблицах. Там же выписаны конъюнкции,

Таблица 9.24

Таблица 9.25

Таблица 9,26

Таблица 9.27

Таблица 9.28

Таблица 9.29

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

Метод самопонижающихся циклов

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

Последнее означает, что если В таблице истинности произвольной булевой функции

Рис. 9.3

Таблица 9.30

Таблица 9.31

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

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

Таблица 9.32

Таблица 9.33

Пример. Найти самопонижающиеся циклы рангов

3, 2, 1 для функции заданной таблицей истинности (табл. 9.32). Каждому циклу поставить в соответствие конъюнкцию из соращенной ДНФ функции по этому циклу.

Цикл № 1. Ранг цикла 3. Склеенные переменные: Сокращенная ДНФ: Фрагмент представлен в табл. 9.33.

Цикл № 2. Ранг цикла 2. Склеенные переменные: Сокращенная ДНФ: — Фрагмент представлен в табл. 9.34.

Цикл № 3. Ранг цикла 2. Склеенные переменные: Сокращенная ДНФ: Фрагмент представлен в табл. 9.35.

Цикл № 4. Ранг цикла 1. Склеенные переменные: Сокращенная ДНФ: . Фрагмент представлен в табл. 9.36.

Таблица 9.34

Таблица 9.35

Таблица 9 36

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

1. Установить Перейти к 2.

2. Найти все самопонижающпеся циклы ранга Если циклы всех найденных рангов накрывают все единицы булевой функции в ее таблице истинности, то перейти к иначе к 3.

3. Исключить из рассмотрения все самопонижающиеся циклы ранга включаемые полностью в один или несколько самопонижающихся циклов ранга Установить Перейти к 4.

4. Если то перейти к 5, иначе к 2.

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

Пример. Найти сокращенную ДНФ нужной функции методом самопонижающихся циклов. Таблица истинности функции задана (табл. 9.32). Ищем цикли максимального ранга Имеется тольки один такой цикл: № 1. Цикл описывается конъюнкцией Найденный цикл накрывает не все единицы таблицы истинности функции Поэтому рассматриваем циклы меньших рангов. Ищем циклы ранга Имеется 2 таких цикла: № 2, 3. Цикл № 2 описывается конъюнкцией Цикл № 3 описывается конъюнкцией Он полностью содержится в цикле № 1, поэтому цикл № 3 не рассматриваем. Поиск циклов меньших рангов не нужен, так как циклы № 1,2 полностью покрывают ту часть таблицы истинности функции в которой она принимает единичные значения. Результирующая сокращенная ДНФ функции имеет вид Циклы № 1, 2, 3 приведены в табл. 9,33, 9.34 , 9.35 соответственно.

Минимизация монотонных функций

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

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

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

Минимизация конъюнктивных нормальных форм

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

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

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

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

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

Что касается первого этапа — поиска всех простых имплицент, то практически все методы минимизации ДНФ имеют свои аналоги для КНФ. Расссмотрим это подробнее.

Соотношение склеивания по Квайну

Соотношение склеивания по Блейку

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

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

Таблица 9.87

функции, заданной диаграммой (табл. 9.37) минимальной КНФ, является

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

Метод Петрика

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

Примеп. Задана импликантная матрица (табл. 9.13). Найти методам Петрика все тупиковые ДНФ булевой функции описываемой данной матрицей. Имеющиеся простые импликанты обозначим буквами:

Тогда конъюнктивное представление матрицы имеет вид

Упростим его

Тупиковая ДНФ содержит две простые импликанты: и имеем вид Например. Задана импликантная матрица (табл. 9.14). Найти методом Петрика все тупиковые ДНФ булевой функции описываемой данной матрицей. Имеющиеся простые импликанты обозначим буквами:

Тогда конъюнктивное представление матрицы имеет вид

После упрощения получим

Две тупиковые ДНФ являются минимальными:

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

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

Таблица 9.38

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

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

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

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

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

Для функции, представленной табл. 9.39:

ДНФ:

КНФ:

Для функции, представленной табл. 9.41

ДНФ:

КНФ:

Для функции, представленной табл. 9.42

ДНФ:

КНФ:

Для функции, представленной табл. 9.43

Таблица 9.39

Таблица 9.40

Таблица 9.41

Таблица 9.42

Таблица 9.43

ДНФ:

КНФ:

Минимизация функций в базисах И-НЕ и ИЛИ-НЕ

Как уже отмечалось, функции «стрелка Пирса» и «штрих Шеффера» обладают функциональной полнотой. Напомним, что связь этих функций с операциями дизъюнкции и конъюнкции проста:

или, обобщая их для переменных, получаем]

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

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

заменить в КНФ все операции конъюнкции и дизъюнкции стрелкой Пирса, сохранив скобки и отрицания на своих местах.

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

где — элементарные дизъюнкции.

Используя приведенные соотношения, получим

Утверждение доказано. Таким образом, минимизацию функции можно осуществлять в базисе И, ИЛИ, НЕ, а затем осуществить переход к стрелке Пирса. Операция отрицания легко реализуется через стрелку Пирса:

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

справедливость которых легко проверяется.

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

откуда

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

Таблица 9.44

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

Пример. В качестве примера рассмотрим ту же функцию (табл. 9.44). Ее минимальная ДНФ

откуда получаем

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