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

Определение 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

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

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

.

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

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

.

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