Пример 2.6.

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

Пример 2.7.

Ф ункции, заданной таблицей истинности (рис. 2.2), соответствует СДНФ.

Функции, заданной этой же таблицей истинности, соответствует СКНФ.

Представление в виде СДНФ или СКНФ для функции является единственным.

Свойства СНФ.

I. 1. Дизъюнкция всех конституент 1 равна единице

.

2. Конъюнкция всех конституент 0 равна нулю

.

II. 1. Дизъюнкция каких-то k конституент единицы равна отрицанию дизъюнкций оставшихся конституент единицы.

2. Конъюнкция каких-то k конституент нуля равна отрицанию конъюнкций оставшихся конституент нуля

Пример 2.8.

Для функции двух переменных a и b имеем следующее множество конституент 1: . Отрицание функции легко может быть найдено путём использования свойства II.1. Действительно, , и следовательно, .

2.5. Задача минимизации булевых функций.

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

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

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

Канонический метод синтеза логических схем заключается в следующем.

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

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

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

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

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

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

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

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

Таким образом, задача минимизации сводится к получению минимальных нормальных форм (МДНФ или МКНФ).