Синтез обратных логических функций

                            ЛЕКЦИЯ 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-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
Hosted by uCoz