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

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

Пример 2.8.

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

Пример 2.7.

Пример 2.6.

Пример 2.5.

.

Конъюнкция конституент нуля носит название совершенной конъюнктивной нормальной формы (СКНФ).

.

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

N	c	b	a	F

Таблица 2.2

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

.

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

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

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

.

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

.

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

.

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

.

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

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

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

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

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

При использовании многовходовых логических элементов схема

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

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

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

Дальнейшего упрощения схемы можно добиться путём получения

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

зованная по нормальной форме, но обладает меньшим быстродействи

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

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

Существуют следующие методы минимизации:

1. Ручные методы минимизации.

2. Машинные методы минимизации.

Ручные методы минимизации используют, если число переменных не больше 7.

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

Ручные методы минимизации делятся на:

1. Аналитические;

2. Топологические.

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

- минимальная форма.

С использованием правила введения и исключения лишних связок нет необходимости в переходе к совершенным формам:

.

Дата добавления: 2014-10-15