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

 

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

Пример. Составить для импликации и сложения по модулю 2 СДНФ и СКНФ.

х	у	х у	х + у
0	0	1	0
0	1	1	1
1	0	0	1
1	1	1	0

 

       Тогда СДНФ для этих функций:

СКНФ для этих функций:

Законы алгебры логики

 

Любая формула алгебры логики зависит от переменных высказываний x₁, x₂... x_n, полностью определяющих значение входящих в неё простых высказываний, следовательно, её можно рассматривать как функцию этих высказываний. Такие функции, которые как и их переменные принимают значение “0” или “1”, называют функциями алгебры логики или логическими функциями. Эти функции обозначаются f(x₁... x_n).

Логическая переменная может принимать два значения, тогда из n-переменных можно составить N= 2ⁿ комбинаций из “0” и “1”, которые принято называть наборами переменных, и говорят, что функция f определена на множестве наборов. Посколько функция принимает два значения, то на N наборов можно построить M= m^Nразличных функций.

Пример. Если n=1, то наборов N=2, а функций M=4

n=2 N=4 M=16

n=4 N=8 M=256                                                                                                 

Элементарные функции - логические функции одной или двух переменных.

Построим при n=1 функцию f(x).

Таблица 3 - Логические функции одной или двух переменных

X	f1	f2	f3	f4
0	0	1	0	1
1	0	1	1	0

 

Здесь f₁(x)=0 – константа “0”;

f₂(x)= 1 – константа “1”;

f₃(x)= x – функция x

f₅(x)= Øx – отрицание.

Аналогично, при n=2 получаем:

f₅(x,y)=xÈy

f₆(x,y)=x×y

f₇(x,y)=x®y

f₈(x,y)=y®x

f₁₀(x,y)= Øf₉(x,y)=xÅy – суммапомодулю “два”.

f₁₁(x,y)=Øf₁₀(x,y)=x½y – ШтрихШеффера.

f₉(x,y)=x~yf₁₂(x,y)=Øf₅(x,y)=x¯y – стрелкаПирса.

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

Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Введем обозначение x⁰=Øx, x¹=x. Пусть а - параметр, равный 0 или 1. Тогда x^A=1, если x=а, и x^A=0, если х¹а.

Теорема. Всякая логическая функция f(x₁,..., x_n) мо-жет быть представлена в следующем виде:

где n³m, а дизъюнкция берется по всем 2^m наборам значений переменных х₁,..., х_m.

Это равенство называется разложением по переменным х₁,..., х_т. Например, при n=4, m=2 разложение имеет вид:

f(x₁, x₂, x₃, x₄)= Øx₁ Øx₂ f(0, 0, x₃, x₄) ÈØx₁ x₂ f & (0,1,x₃,x₄)È x₁ Øx₂ f(1,0,x₃,x₄)È x₁ x₂ f(1,1,x₃,x₄)

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

При m=1 из получаем разложение функции по одной переменной

Ясно, что аналогичное разложение справедливо для любой из п переменных. Другой важный случай — разложение по всем п переменным (т=п). При этом все переменные в правой части (3.4) получают фиксированные значения и функции в конъюнкциях правой части становятся равными 0 или 1, что дает:

где дизъюнкция берется по всем наборам на которых f=1. Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f; каждому единичному набору  соответствует конъюнкция всех переменных, в которой Xi взято с отрицанием, если s_i = 0, и без отрицания, если s_i = l. Таким образом, существует взаимно од­нозначное соответствие между таблицей функции

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

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

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

Действительно, для всякой функции, кроме константы 0, таким представлением может служить её СДНФ. Константу 0 можно представить булевой формулой Ø xx.

А почему же формула называется “совершенной”? Совершенной называется потому, что она имеет 4 свойства совершенства.

1. В формуле все конъюнкции разные.

2. В конъюнкции все переменные разные.

3. В одной конъюнкции не встречаются переменные вместе с их отрицанием.

4. В конъюнкции столько переменных, сколько в исходной функции f, то есть n. (Число переменных в функции есть ранг этой функции).

В таблице истинности определяют единичные наборы. Из переменных образуют конъюнкции следующим образом: если переменная = 1, то пишем x, если ¹ 1, то пишем Øx. Полученные конъюнкции объединяем знаком дизъюнкции.

x	y	Z	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

В результате получаем следующую СДНФ:

f(x, y, z) = (Øxyz) È (xØyz) È (xyØz) È (xyz)