Основные сведения

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

Любую функцию алгебры логики можно представить в виде формулы через конъюнкцию, дизъюнкцию или отрицание в виде

z=f(х₁,х₂,…,х_k,…,х_n)= V х₁^s1 х₂^s2 …..х_к^sк ……х_n^sn,

где х_к^sк – общее обозначение для аргумента х_k и его отрицания ,

х_к^sк при=1

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

Конъюнкция p=х1 х2 …хk называется элементарной , если число ее членов меньше некоторого множества переменных n, причем любая переменная хi входит в конъюнкцию только один раз. То же самое относится и к элементарной дизъюнкции.

Импликантная булева функция f(х1,х2,…,хn) – это такая булева функция f1(х1,х2,…,хn),которая на любом наборе значений переменных х1,х2,…,хn, при f1 равном единице, принимает значение, также равное единице.

Простая импликантная булева функция f(х1,х2,…,хn) – это элементарная конъюнкция наименьшего ранга, входящая в данную булеву функцию.

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

Процесс минимизации состоит из следующих этапов:

1. Нахождение сокращенной ДНФ.

2. Определение всех тупиковых ДНФ.

3. Выбор из всех тупиковых ДНФ минимальной ДНФ.

Существуют несколько алгоритмов минимизации булевой функции.

Метод Квайна

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

2. Далее проводятся операции склеивания и элементарного поглощения по соответствующим законам.

Пример 1:

Дана функция z=f(х1,х2,х3,х4)= х4Vх1х3V Vх1 х2 .

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

Решение.

1. Приведем данную функцию к СДНФ.

х4= х4(х2Vх2)(х3Vх3)

а) х1х4=х1х4(х2V )(х3V )= х2х3х4 V х2 х4 V х1 х3х4 V х1 х4

б) х1 х3=х1 х3 (х2 V )(х4 V )=(х1 х2 х3 Vх1 х3 )(х4 V )=х1 х3 х2 х4 V х1 х3 х4 Vх1 х3 V х1 х3 )

в) = (х1 V )(х2 V )=х1 х2 V х2 V х1 V

г) х2 = х2 (х4 V )= х2 х4 V х2

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

z= х2 х3 х4 V х2 х4 V х1 х3 х4 V х1 х4 Vх1 х2 х3 х4 V х1 х3 х4 V х1 х3 V х3 V х1 х2 V х2 х3 х4 V х1 V V х2 х4 V х2

2. Операция склеивания и поглощения выполняется по следующему принципу:

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

1) первый член со всеми остальными

2) второй член со всеми остальными, кроме первого

3) третий член с остальными, кроме первого и второго, и т.д.

3)Операция склеивания сначала выполняется для дизъюнктивных членов ранга n (количество аргументов равно n).После выполнения первой операции ранг дизъюнктивных членов понижается до n-1.Затем выполняются все возможные операции склеивания для дизъюнктивных членов ранга n-1, описанные выше.

Выполним операцию склеивания для нашего примера.

После первого склеивания получим функцию z в виде

z= х4 V Vх1 х3 Vх1 х3 х4 V х4 Vх1 V х3 х4 V х2 х3 х4 Vх2 V V х2 V V х1 х3 V х1 х2 х3 V х2 х3 V х4 V х1 V х1 х2

В функции z ранг дизъюнктивных членов равен 3.

Следующая операция склеивания и поглощения даст результаты:

z= V х4 V х1 х3 V х1 V х3 х4 V

В результате дальнейших сокращений получим:

z= V x4 V x1 x3 V x1

Диаграммы Вейча

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

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

Диаграммы Вейча для функций имеющих две, три и четыре переменные представлены соответственно на Рис.11, Рис.12, Рис. 13.

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

Процесс минимизации заключается в следующем:

- На основе заданной булевой функции создаем диаграмму Вейча.

- Находим все склеивающиеся конституенты единицы.

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

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

При склеивании необходимо придерживаться следующих правил:

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

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

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

Пример 2:

Дана функция z=x1 x4 V x3 x2 V x1 x3 V x1 x3 V x1 x2 x3