Синтез обратных логических функций
ЛЕКЦИЯ 12
Синтез обратных логических функций.
Если логическое уравнение вида z=f(x1,x2,x3,...,xi,...xn) решает-
ся относительно одной из своих переменных,например,отыскивается обрат-
ная функция x1=fi(z,x2,x3,...,xi,...,xn),то можно воспользоваться бо-
лее простым алгоритмом "Селигер-С" решения задачи.
Алгоритм "Селигер-С".
1.Построить таблицу истинности для уравнения z=f(x1,x2,..,xn)
2.По исходной таблице истинности построить таблицу истинности для
обратной функции вида x1=fi(z,x2,...,xn) простой перестановкой
столбцов z и x1.
3.По полученной таблице истинности построить обратную функцию
x1=fi(z,x2,...,xn) и провести ее минимизацию.
Пример 1.
Дано: z = xy,v = x+y.
Найти: y = z/x,y = v-x.
Решение.
На основе формулы эквивалентности преобразуем исходную формулу
z=xy.Тогда получим (z=xy) = zxy+z'(x'+y').В соответствии с пп.4,5 ал-
горитма "Селигер" получим y = xz+ix'z'+jx'z.
Решим ту же задачу посредством алгоритма "Селигер-С".Исходные
уравнения представим в виде таблицы истинности (табл.12).Тогда в соот-
ветствии с п.2 алгоритма "Селигер-С" построим частные таблицы истин-
ности для y = z/x и y = v-x.
Табл.12 Табл.13 Табл.14
-----T-----T-----¬ -----T-------¬ -----T-------¬
¦ xy ¦ z ¦ v ¦ ¦ xz ¦ y=z/x ¦ ¦ xv ¦ y=v-x ¦
+----+-----+-----+ +----+-------+ +----+-------+
¦ 00 ¦ 0 ¦ 0 ¦ ¦ 00 ¦ i ¦ ¦ 00 ¦ 0 ¦
¦ 01 ¦ 0 ¦ 1 ¦ -----> ¦ 01 ¦ j ¦ ¦ 01 ¦ 1 ¦
¦ 10 ¦ 0 ¦ 1 ¦ ¦ 10 ¦ 0 ¦ ¦ 10 ¦ j ¦
¦ 11 ¦ 1 ¦ 1 ¦ ¦ 11 ¦ 1 ¦ ¦ 11 ¦ i ¦
L----+-----+------ L----+-------- L----+--------
В соответствии с п.3 алгоритма "Селигер-С" проведем минимизацию
искомых функций в комплементарной логике(рис.9 и 10).
x\z 0 1 x\v 0 1
\----T----¬ \----T----¬
0 ¦ i ¦ j ¦ 0 ¦ 0 ¦ 1 ¦
+----+----+ +----+----+
1 ¦ 0 ¦ 1 ¦ 1 ¦ j ¦ i ¦
L----+----- L----+-----
Рис.9 Рис.10
Для комплементарной логики получим:
y = z/x = xz + ix'z' + jx'z
y = v-x = x'v + ixv + jxv'
Используя алгоритмы "Селигер" или "Селигер-С",можно получить пол-
ную систему обратных функций для двоичной логики.В табл.15 приведена
полная система функций двоичной логики.
Табл.15
-----T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---¬
¦ xy ¦ z0¦ z1¦ z2¦ z3¦ z4¦ z5¦ z6¦ z7¦ z8¦ z9¦z10¦z11¦z12¦z13¦z14¦z15¦
+----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
¦ 00 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 01 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 10 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦
¦ 11 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦
L----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
Перестановкой столбцов y и z табл.15,строим таблицы истинности
для полной системы обратных функций (табл.16).
Табл.16
-----T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---¬
¦ xz ¦ y0¦ y1¦ y2¦ y3¦ y4¦ y5¦ y6¦ y7¦ y8¦ y9¦y10¦y11¦y12¦y13¦y14¦y15¦
+----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
¦ 00 ¦ i ¦ i ¦ i ¦ i ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ j ¦ j ¦ j ¦ j ¦
¦ 01 ¦ j ¦ j ¦ j ¦ j ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ i ¦ i ¦ i ¦ i ¦
¦ 10 ¦ i ¦ 0 ¦ 1 ¦ j ¦ i ¦ 0 ¦ 1 ¦ j ¦ i ¦ 0 ¦ 1 ¦ j ¦ i ¦ 0 ¦ 1 ¦ j ¦
¦ 11 ¦ j ¦ 1 ¦ 0 ¦ i ¦ j ¦ 1 ¦ 0 ¦ i ¦ j ¦ 1 ¦ 0 ¦ i ¦ j ¦ 1 ¦ 0 ¦ i ¦
L----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
Из табл.16 получаем полную симметричную систему обратных функций:
y0 = iz'+jz
y1 = xz+ix'z'+jx'z
y2 = xz'+ix'z'+jx'z
y3 = i(xz+x'z')+j(xz'+x'z)
y4 = x'z+ixz'+jxz
y5 = z
y6 = xz'+x'z
y7 = x'z+ixz+jxz'
y8 = x'z'+ixz'+jxz
y9 = xz+x'z'
y10 = z'
y11 = x'z'+ixz+jxz'
y12 = i(xz'+x'z)+j(xz+x'z')
y13 = xz+ix'z+jx'z'
y14 = xz'+ix'z+jx'z'
y15 = iz+jz'
Заменив z на 1,а z' - на 0,мы получим перечисленные функции,зави-
сящие от одного аргумента.
y0 = j
y1 = x+jx'
y2 = jx'
y3 = ix+jx'
y4 = x'+jx
y5 = 1
y6 = x'
y7 = x'+ix
y8 = jx
y9 = x
y10 = 0
y11 = ix
y12 = ix'+jx
y13 = x+ix'
y14 = ix'
y15 = i
Решая задачу Порецкого,мы заметили аналогию между рекурсивным y и
комплементарным i.Резонно предположить,что такая же аналогия существу-
ет между комплементарным j и рекурсивным y'.Проверим это предположение
на полученных одноаргументных функциях и убедимся в их обратимости с
помощью формулы эквивалентности.
0) (y = j) = (y = y')
M = (y=y') = yy'+y'y = 0
1) (y = x+jx') = (y = x+x'y') = (y = x+y')
M = (y=x+y') = y(x+y'0+y'(x+y')' = xy+y'x'y = xy
2) y = jx' = x'y'
M = (y=x'y') = yx'y'+y'(x'y')' = y'(x+y) = xy'
3) y = ix+jx' = xy+x'y'
M = (y=xy+x'y') = y(xy+x'y')+y'(xy'+x'y) = xy+xy' = x
4) y = x'+jx = x'+xy' = x'+y'
M = (y=x'+y') = y(x'+y')+y'(x'+y')' = x'y
5) y = 1
M = (y=1) = y&1+y'&0 = y
6) y = x'
M = (y=x') = xy'+x'y
7) y = x'+ix = x'+xy = x'+y
M = (y=x'+y) = y(x'+y)+y'(x'+y)' = y+xy' = x+y
8) y = jx = xy'
M = (y=xy') = yxy'+y'(xy')' = x'y'
9) y = x
M = (y=x) = x'y'+xy
10)y = 0
M = (y=0) = y&0+y'&1 = y'
11)y = ix = xy
M = (y=xy) = yxy+y'(xy)' = xy+y' = x+y'
12)y = ix'+jx = x'y+xy'
M = (y=x'y+xy') = y(x'y+xy')+y'(x'y'+xy) = x'y+x'y' = x'
13)y = x+ix' = x+x'y = x+y
M = (y=x+y) = y(x+y)+y'(x+y)' = y+x'y' = x'+y
14)y = ix' = x'y
M = (y=x'y) = yx'y+y'(x'y)' = x'y+y' = x'+y'
15)y=i = y
M = (y=y) = y&y+y'&y' = y+y' = 1
После обращения были получены все 16 прямых функций от двух аргу-
ментов без какого-либо искажения.Это подтверждает правильность всех
алгоритмов решения логических уравнений и корректность комплементарной
логики.
Домашнее задание ДЗ6
1.Решить уравнение v = xyzu+x'y'z'u' относительно у.
2.Построить систему обратных функций для 3-х переменных.
------T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---¬
¦ uxy ¦z0 ¦z1 ¦z2 ¦z3 ¦z4 ¦z5 ¦z6 ¦z7 ¦z8 ¦z9 ¦z10¦z11¦z12¦z13¦z14¦z15¦
+-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
¦ 000 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦
¦ 001 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦
¦ 010 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦
¦ 011 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦
¦ 100 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 101 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 110 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦
¦ 111 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦
L-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----