2.3. Произвольные функции и логические схемы

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

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

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

СДНФ состоит из элементарных конъюнкций, соединенных знаками дизъюнкции.

Конъюнкцию называют элементарной, если в нее не входит несколько одинаковых букв. Число элементарных конъюнкций в СДНФ обязательно равно числу единичных значений функции в таблице истинности. В каждую элементарную конъюнкцию СДНФ входят обязательно все аргументы функции. С помощью набора функций НЕ, И, ИЛИ можно выразить любую логическую функцию, сколь бы сложной она ни была. Пример: построить логическую схему, реализующую функцию, заданную таблицей. Для решения удобнее пользоваться аналитическим выражением

,

(2.1)

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

Рис. 2.4. Логическая схема, реализованная по СДНФ

Трехъярусные схемы элементов НЕ–И–ИЛИ широко распространены, но они громоздки. Обычно элементы И, ИЛИ, НЕ расположены в одном корпусе микросхемы. Поэтому на схемах используют более компактное изображение (рис. 2.5).

Рис. 2.5. Сокращенное условное изображение схемы по рис. 2.4

По логической схеме можно воспроизвести аналитическую форму реализуемой ею логической функции.

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

4. Законы булевой алгебры

Булева алгебра базируется на нескольких аксиомах.

Аксиомы операции отрицания:

Аксиомы операций
конъюнкции	И	дизъюнкции
0 · 0 = 0		1  1 = 1
1 · 0 = 0 · 1 = 0		0  1 = 1 0 = 1
1 · 1 = 1		0  0 = 0

Законы булевой алгебры вытекают из аксиом и имеют две формы выражения: для конъюнкции и дизъюнкции. Их правильность легко проверить по таблицам истинности либо путем подстановки 0 и 1 вместо соответствующих значений переменных.

	Для конъюнкции	Для дизъюнкции
1. Переместительный закон:
2. Закон повторения (тавтологии):
3. Закон нулевого множества:
4. Закон универсального множества:
5. Закон дополнительности:
6. Закон поглощения:
7. Закон склеивания:
8. Закон инверсии (закон де Моргана):
или после инвертирования правых и левых частей:
9. Закон обращения: если , то
10. Закон двойной инверсии:
11. Сочетательный закон:
12. Распределительный закон:

Для примера преобразуем на основе законов булевой алгебры функцию

(2.2)

Раскроем скобки:.

Так как (закон дополнительности), то.

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

Рис. 2.6. Схемы примера: а – по исходному уравнению (2.2);

б – после преобразования

Аналогично можно минимизировать рассмотренное ранее выражение (2.1):

. (2.3)

Для минимизации были использованы соотношения:

(закон дополнительности);

(закон универсального множества).

Схема, реализующая полученную функцию, представлена на рис. 2.7.

Рис. 2.7. Схема, полученная в результате минимизации уравнения (2.1)

Выражение (2.3) существенно проще, чем исходное уравнение (2.1). Построив для уравнения (2.3) таблицу истинности, можно убедиться, что она совпадает с данными табл. 2.3.

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

Преобразование исходной логической функции выполняют с целью нахождения минимальной ДНФ. Специального правила, приводящего к минимальной ДНФ, не существует. Можно исследовать различные варианты и сравнить их результаты. Процедуру поиска облегчают специально разработанные методы минимизации, с которыми можно ознакомиться, например, по учебному пособию [7].