Представление логических функций

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

Таблица 2 – Представление Y

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

Выражение (12) называется совершенной дизъюнктивной нормальной формой ЛФ (СДНФ). mi - минтерм или логическое произведение всех переменных i-го двоичного набора, входящих в прямом виде, если значение этой переменной в наборе равно 1, и в инверсном виде, если ее значение равно 0. fi - значение ЛФ на i - ом наборе. Доказательство (12) базируется на теореме разложения, в соответствии с которой любую ЛФ f(..) от n-переменных можно разложить по переменной xi в виде: f(x(n-1),...,xi,...,x0) = ~xi*f(x(n-1),...,0,..,x0) + xi*f(x(n-1),..,1,..,x0). Это выражение для xi=0 равно ~0*f(x(n-1),...,0,..,x0) + 0*f(x(n-1),..,1,..,x0) = f(x(n-1),...,0,..,x0). При xi=1 оно будет равно ~1*f(x(n-1),..,1,..,x0) + 1*f(x(n-1),..,1,..,x0) = f(x(n-1),...,1,..,x0), т.е. при любых значениях xi теорема разложения справедлива. Теорему разложения можно применить n раз и тогда ЛФ будет разложена по всем своим переменным.

В виде примера рассмотрим функцию 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). (12.1)

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

Рассмотрим разложение функций 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). На основании аксиомы (8), выражение в скобке равно "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 (функция неравнозначности).

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

Пример представления логических функций в виде СДНФ (СКНФ).

Будем использовать логическую функцию “эквивалентность”, записанную в виде х^у. Напомним, что 0⁰= 1; 0¹=0; 1⁰= 0; 1¹= 1.Таким образом, х^у = 1 тогда и только тогда, когда х = у.

Лемма. Любая логическая функция f (x ₁, x ₂, …, x_n) может быть представлена в виде дизъюнкции 2 ^п дизъюнктных слагаемых, причем дизъюнкция берется по всевозможнымнаборам из Eⁿ. Этот факт будем записывать следующим образом:

(*)

где дизъюнкция проводится по всевозможным наборам (s₁, s₂, …, s _п) из Е^п.

Доказательство леммы.

а) Пусть f (x ₁, x ₂, …, x_n)= 1. Тогда слева в формуле (*) стоит 1. Докажем, что и справа в этом случае стоит 1, для чего достаточно указать одно дизъюнктное слагаемое, равное 1. Но среди всех наборов (s₁, s₂, …, s _п) имеется набор s₁ = х ₁, s₂ = х ₂, …, s _п = х_п. Очевидно, что для этого набора слагаемое равно 1 (так как и.

б) Пусть f (x ₁, x ₂, …, x_n) = 0. Предположим, что справа стоит не ноль, а единица, тогда какое-то слагаемое тоже должно равняться 1, т. е. для некоторого набора

Это означает (по свойствам конъюнкции), что, откуда следует, что х ₁=s₁, х ₂=s₂, …, х_п =s_n, но в этом случае f (s₁, s₂,..., s_n) f (x _1, x ₂, …, x_n) = 0 и, значит, справа нет слагаемого, равного 1, т. е. в этом случае и справа и слева в формуле (*) стоит 0. Лемма доказана.

Теорема. Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборыпеременных (х ₁, х _2, …, х_n ₎, для которых f (х ₁, х ₂, …, х_n)=1, и составляем простую конъюкцию для этого набора так: если х_i = 0, то берем в этой конъюнкции, если х_i = 1, то берем х_i _. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ.

Доказательство. Пусть f (x _1, x ₂, …, x_n) не равна тождественному нулю, тогда в дизъюнкции можно не записывать слагаемые, равные нулю, а из формулы (*) следует следующее представление для данной функции

Запись означает, что дизъюнкция берется по всем наборам (s₁, s₂,..., s_n), для которых f (s₁, s₂,..., s_n) = 1. Так как (если s₁=0), из формулы (**) следует утверждение теоремы.

Следствие. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание.

Из предыдущей теоремы видно, что следствие верно для любой функции, не равной тождественному нулю. Однако если f (x ₁, x ₂, …, x_n _{) =}0, то ее также можно выразить через конъюнкцию, дизъюнкцию и отрицание, например, так: f (x ₁, x ₂, …, x_n _{) = x1},и, несмотря на то, что последнее выражение не является простой конъюнкцией (и, значит, не является СДНФ), тем не менее тождественный ноль также выражен через нужные три функции.

Набор функций, через которые можно выразить любые другие функции, называется полным набором (более точные формулировки даны в разд. 7). Таким образом, конъюнкция, дизъюнкция и отрицание являются полным набором.

По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х ₁, х ₂, …, х_п), для которых f (x ₁, x ₂, …, x_n) =0, причем если х_i =1, то в этой дизъюнкции берем _, если же х_i = 0, то берем х_i.