Способы представления логических функций. Совершенная дизъюнктивная нормальная форма логических функций.

Целью проектирования цифрового устройства является получение его логической функции (ЛФ) и соответствующей ей схемной реализации. ЛФ могут иметь различные формы представления:

1) словесное, 2) графическое, 3) табличное, 4) алгебраическое, 5) на алгоритмическом языке (например VHDL) и 6) схемное.

В качестве примера, рассмотрим функцию Y от двух переменных x1 и x0, заданную словесным описанием: Y=1, если переменные НЕ РАВНЫ и Y=0, если x1=x0. Такую ЛФ удобно назвать функцией НЕРАВНОЗНАЧНОСТИ. Переходим к табличному представлению Y (таблица 2).

Табличное представление значений ЛФ для всех наборов входных переменных называется таблицей истинности. В общем виде переход от табличного представления к алгебраическому может осуществляться по формуле (1.12), одной из основных в алгебре логики.

Выражение (1.12) называется совершенной дизъюнктивной нормальной формой ЛФ (СДНФ). mi - минтерм или логическое произведение всех переменных i-го двоичного набора, входящих в прямом виде, если значение этой переменной в наборе равно 1, и в инверсном виде, если ее значение равно 0. fi - значение ЛФ на i - ом наборе.

В виде примера рассмотрим функцию F=f(x1,x0) от двух переменных.

Разложение этой функции по переменной x1 даст: F= ~x1∙f(0,x0) + x1∙f(1,x0). Продолжая эту операцию для переменной x0, получим:

F =~x1∙(~x0∙(f(0,0) + x0∙(f(0,1)) + x1∙(~x0∙(f(1,0) + x0∙(f(1,1)) =

~x1∙~x0∙f(0,0) + ~x1∙x0∙f(0,1) + x1∙~x0∙f(1,0) + x1∙x0∙f(1,1). (1.13)

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

Рассмотрим разложение функций F7-"ИЛИ" и F1-"И", для чего необходимо обратиться к соответствующим строчкам таблицы 1. Функция И на двоичных наборах входных переменных x1 и x0 (00,01,10,11) принимает значения 0,0,0,1. Записывая выражение (12.1) для этих значений получим: F1(x1,x0 ) = ~x1∙~x0∙0 + ~x1∙x0∙0 + x1∙~x0∙0 + x1∙x0∙1 = x1∙x0, что соогласуется с ее определением.

Таким же образом, находим алгебраическое выражение функции F7-"ИЛИ", которая, соответственно, на тех же входных наборах принимает значения: 0,1,1,1.

Тогда, в соответствии с (12.1), F7(x1,x0) = ~x1∙~x0∙0 + ~x1∙x0∙1 + x1∙~x0∙1 + x1∙x0∙1. Вынося за скобки в двух последних слагаемых x1, получим F7 = ~x1∙x0∙1 + x1∙(~x0∙1 + x0∙1). Выражение в скобке равно "1" и F7 = ~x1∙x0∙1 + x1. Применяя распределительный закон, найдем (~x1+x1) ∙ (x0+x1) = x1+x0.

Возвращаясь к таблице 2, получим Y = 0∙~x1∙~x0 + 1∙~x1∙x0 + 1∙x1∙~x0 + 0∙x1∙x0 = ~x1∙x0 + x1∙~x0 = x1 (+) x0 = F6 (функцияия неравнозначности).

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