Функции, сохраняющие константу

Определение 26. Функция f (x₁,…,x_n) называется функцией, сохраняющей ноль, если f (0 ,…, 0)=0.

Определение 27. Функция f (x₁,…,x_n) называется функцией, сохраняющей единицу, если f (1 ,…, 1)=1.

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

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

Пример 5.15. Рассмотрим классический базис {Ø, Ù, Ú}. Здесь “Ø” не монотонна, не сохраняет ноль и единицу, “Ù“ и “Ú“– не линейные и не самодвойственные.

Пример 5.16. Можно показать, что функции Шеффера и Пирса (каждая сама по себе) являются базисом, т.е. через любую из них могут быть выражены все возможные булевы функции.

Данный факт нашел широкое применение в технике, например, элемент И-НЕ, реализующий функцию Шеффера, является базовым для ряда серий интегральных микросхем, т.е. является тем основным “кирпичиком”, из которых воздвигаются здания и города аппаратных средств вычислительных систем и комплексов.

Вопросы для самоконтроля

1. К каким классам относится функция эквивалентности?

2. Докажите полноту базиса Жегалкина .

 

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

 

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

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

В основе всех методов минимизации лежат правила склеивания и поглощения:

1) правило полного склеивания: ,

2) правило неполного склеивания: ,

3) правило обобщенного склеивания: ,

4) правило поглощения: .

 

Метод Блейка

Метод основан на использовании правила обобщенного склеивания и правила поглощения. Для применения метода необходимо выполнить следующие шаги:

1) пополнить ДНФ новыми членами с использованием правила обобщенного склеивания;

2) произвести элементарные поглощения, в результате которых появится новая ДНФ;

3) считая новую ДНФ исходной, перейти к п. 1;

4) повторять пп. 1-3 пока ДНФ будет пополняться новыми членами.

Пример. 5.17. .

1 2 3

Применим правило обобщенного склеивания:

 

1 2 1-2 3 1-3

.

1 2 3 4 5

Произведем поглощения:

2-5

3-4

.

Метод Блейка позволяет получить минимальную ДНФ из произвольной ДНФ, не обязательно совершенной.

 

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

 

Минимизация функции основывается на использовании правила поглощения, позволяющего вычислить все множество 1-, 2-, … n - кубов, образующих комплекс K (f). Из этого комплекса выделяются кубы наибольшей размерности, покрывающие все множество вершин функции, определяя покрытие Z (f) функции. Покрытие Z (f) упрощается с целью получения минимального.

Здесь 0-куб есть вершина, т.е. булев вектор, или набор аргументов типа «0100», «0000». 1-куб можно рассматривать как вектор, одна координата которого безразлична. Очевидно, что 1-куб может быть образован 0-кубами, различающимися только на одну единицу. Например, «0100» и «0000» образуют 1-куб «0x00». Аналогично 2-кубы образуются из 1-кубов, отличающихся только на 1 единицу (и имеющих «x» в одинаковых позициях), например «0x01» и «0x11» дадут 2-куб «0xx1» и т.д.

В задачах минимизации булевых функций используется понятие простой импликанты. Некоторый куб z Î K называется простой импликантой, если он не содержится ни в каком другом кубе комплекса К, т.е. не является гранью никакого другого куба из этого комплекса. Совокупность всех таких кубов образует множество Z ={ z } простых импликант данного комплекса. Любой куб минимального покрытия С _min является простой импликантой; следовательно, С_minÍ Z. Минимизация функции состоит из последовательных этапов.

1. Нахождение простых импликант. Все 0-кубы сравниваются попарно между собой на предмет образования 1-кубов. Если 0-кубы образуют 1-куб, они помечаются. Для упрощения данной операции удобно множество 0-кубов разбить на группы, содержащие равное число единиц, 1-кубы могут быть образованы объединением 0-кубов только из смежных групп. Множество полученных 1-кубов записывается в столбик и подразделяется на группы, содержащие одинаковое количество единиц. На базе данных множеств строится множество 2-кубов, при этом 1-кубы, участвовавшие в образовании 2-кубов, также помечаются. Этап заканчивается, когда ни один куб более высокого порядка не может быть построен. Все неотмеченные кубы комплекса K (f) являются простыми импликантами и образуют покрытие Z (f) функции f, которое в общем случае не является минимальным.

2. Составление таблицы покрытий. Задача данного этапа – удалить все лишние простые импликанты. Составляется так называемая таблица покрытий. Строки данной таблицы помечаются простыми импликантами, полученными на шаге 1, столбцы - 0-кубы(термы) минимизированной функции. На пересечении i -й строки и j -го столбца ставится метка 1, если i -я импликанта покрывает j -й 0-куб, т.е. соответствующие символы совпадают или покрываются символом “ x ” со стороны импликанты.

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

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

5. Вычеркивание лишних простых импликант. Если в остаточной таблице имеются строки, не имеющие ни одной метки, импликанты, соответствующие данным строкам, вычеркиваются.

6. Нахождение минимального покрытия. В остаточной таблице, полученной после выделения существенных импликант, выбирается совокупность простых импликант, позволяющих покрыть все столбцы с минимальными затратами. То есть по возможности предпочтение отдается импликантам, содержащим больше “x” (сокращается сложность применяемых для реализации логических элементов), и импликантам, содержащим больше “1”, чем “0” (при этом в некоторых случаях уменьшается число необходимых инверторов). С учетом проведенных вычислений записывается минимальное покрытие как объединение множества существительных импликант и простых импликант, отобранных на данном этапе.

Записывается минимальная ДНФ как дизъюнкция элементов минимального покрытия.

Пример 5.18.

х₁ х₂ х₃ х₄

0 0 0 0 0 Запишем минимизируемую фун-

1 0 0 0 1 кцию в виде комплекса К ⁰, при этом

2 0 0 1 0 для удобства разобьем на группы, со-

3 1 0 0 0 держащие одинаковое число единиц, и

4 0 0 1 1 пронумеруем каждый 0-куб. В про-

5 0 1 1 0 цессе вычислений будем также поме-

6 1 0 0 1 чать кубы.

7 0 1 1 1

8 1 1 1 0

9 1 1 1 1

Определение простых импликант.

Построим комплекс K ¹, помечая, посредством слияния каких 0-кубов или импликант создана текущая импликанта.

 

1 0 0 0 х 0 – 1

2 0 0 х 0 0 – 2

3 х 0 0 0 0 – 3

4 0 0 х 1 1 – 4

5 х 0 0 1 1 – 6

6 0 0 1 х 2 – 4

7 0 х 1 0 2 – 5

8 1 0 0 х 3 – 6

9 0 х 1 1 4 – 7

10 0 1 1 х 5 – 7

11 х 1 1 0 5 – 8

12 х 1 1 1 7 – 9

13 1 1 1 х 8 – 9

Построим комплекс :

 

0 0 х х 1 – 6

х 0 0 х 1 – 8

0 х 1 х 6 – 10

х 1 1 х 10 – 13

 

Будем также помечать «» все импликанты, покрываемые кубами более высокого порядка.

Таким образом, имеем набор простых импликант:

 

0 0 х х

х 0 0 х

0 х 1 х.

х 1 1 х

 

Составляем таблицу покрытий (табл. 5.3).

Таблица 5.3

0-куб   Импликанта
0 0 х х
х 0 0 х				1			1
0 х 1 х
х 1 1 х									1

 

По таблице покрытий находим две существенные импликанты х00х и х11х (соответствующие единицы подчеркнуты), покрывающие все 0-кубы, кроме 0011. Таким образом, в данном случае можно построить два минимальных покрытия:

х 0 0 х х 0 0 х

х 1 1 х х 1 1 х

0 0 х х 0 х 1 х

 

Запишем результат в виде ДНФ:

и

 

.

 

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

Замечание 1. Очевидно, что нахождение простых импликант связано со значительным объемом вычислений. При увеличении числа переменных количество столбцов резко возрастает. С целью упрощения процедуры нахождения простых импликант Мак-Класки предложил использовать числовые представления булевых функций для выполнения операций по методу Квайна. Данный метод подробно изложен в [3].

Замечание 2. Для решения задачи минимального покрытия может быть использован алгоритм Петрика (см., например, [9]).

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

Пример 5.19.

	a	b	c	d
А
В
С
D

 

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

Для нашего примера имеем:

.

Далее раскрываются скобки и выражение преобразуется в ДНФ:

 

 

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

 

.

 

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