Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 26

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

 

 

 

1

 

 

1

 

 

ху 00 01

10

zt 00

01 11

10

г

1 >

 

 

, 1

1

1

 

 

1

 

 

 

)

 

 

Задачи только что рассмотренного типа можно решать также и чисто аналитически без привле­чения диаграмм Вейча. Рассмотрим пример. Дано уравнение:

x1 x2 x3    x1 x2 x3    x1 x3    x1 x2 x3    x1 x2 x3 =1.

Переменные x1, x2, x3 троичные со значения­ми а, b, c. Требуется заменить это уравнение равно­сильной ему системой возможно более коротких уравнений. Ищем первое уравнение системы, от­правляясь от предиката:

x1cx2xx3xvx1cx2xx3bvx1bx2bvx1cx2cx3bvx1bx2bx3cv

vx1 ax2 ax3 a vx1 ax2 bx3 a vx1 ax2cx3 a vx1 ax2 ax3 b V

vx1xx2bx3bvx1xx2cx3bvx1xx2xx3cvx1xx2bx3cv

vx1 ax2 cx3 cvx1 bx2 ax3 a vx1 bx2 bx3 a vx1 bx2 cx3 a V

x1 bx2 ax3 cvx1 bx2 cx3 cvx1 cx2 bx3 a vx1 cx2cx3 a V

vx1 cx2 bx3 b vx1 cx2 ax3 cvx1 cx2 bx3 cvx1 cx2 cx3 c.

В указанном предикате сохранена вся левая часть исходного уравнения. Кроме того, в него вве­дены в роли дополнительных членов конституэнты единицы для всех наборов (x1, x2, x3), не являющих­ся решениями исходного уравнения. Эти консти­туэнты единицы заключены в квадратные скобки. Производим такую минимизацию полученной формулы, при которой разрешается использовать любые дополнительные члены, но не все одновре­менно. Все дизъюнктивные члены, не охваченные квадратными скобками, в процессе минимизации должны быть использованы обязательно.

После минимизации получаем левую часть пер­вого уравнения x1bvx1c. В процессе минимизации были использованы следующие дополнительные конституэнты единицы:

b       a       a b       b       a b       С       a b       a       С b       С С

Л1      Л3 , Л1      Л3 , Л1 Л2 Л3 , , Л3 ,

123

С       С        a С       b        b С       a        С С       b        С С        С С

Л1 Л2 Л3 , Л1 Л2 Л-3 , Л1 Л2 Л3 , Л1 Л2 Л3 , Л1 Л2 Л-3 .

Далее, отправляясь от того же предиката, ищем второе уравнение системы. Теперь в процессе ми­нимизации не должны использоваться все консти­туэнты единицы из только что приведенного пе­речня. Все те конституэнты единицы, которые не приведены в этом перечне и охвачены квадратны­ми скобками, могут использоваться или не исполь­зоваться по нашему усмотрению. Получаем левую часть второго уравнения x1bvx2avx2c. При миними­зации не использовались из нашего перечня сле­дующие конституэнты единицы: x1cx2bx3a, x1cx2bx3b, x1cx2bx3c. Повторяем процесс минимизации для еще более сокращенного перечня конституэнт едини­цы:

у b a-y a -v bv bv a у by Су a у by ay c x1 x2 x3 , x1 x2 x3 , x1 x2 x3 , x1 x2 x3 ,

v by Су Су Су Су a у Су a-y Су Су Су c Л1 Л2 Л3 , Л1 Л2 Л3 , Л1 Л2 Л3 , Л1 Л2 Л3 .

Получаем левую часть третьего уравнения x1cx2avx3bvx3c. Перечень оставшихся конституэнт единицы становится еще меньшим:

b      a      С b      С      С С      a      С С      С С

1   2   3 '   1   2   3 '   1   2   3 '   1   2   3 *

Наконец, получаем левую часть четвертого уравнения x1bx2bvx3avx3b. Перечень конституэнт единицы превращается в пустое множество, что служит признаком окончания процесса построе­ния системы уравнений. Итак, мы заменили ис­ходное уравнение

x1cx2ax3avx1cx2ax3bvx1bx2bvx1cx2cx3bvx1bx2bx3c=1 (д)

системой равносильных ему уравнений:

x1bvx1c=1, x1bvx2avx2c=1, x1cx2avx3bvx3c=1, x1bx2bvx3avx3b=1.

Суммарное число букв в системе осталось почти тем же, что и в исходном уравнении (13 узнаваний буквы против 14), зато максимальная сложность уравнений резко уменьшилась (с 14 до 4 узнаваний буквы).

Рассмотрим один специальный, но важный ме­тод декомпозиции уравнений алгебры конечных предикатов, основанный на применении теоремы о конъюнктивном разложении. Пусть требуется произвести декомпозицию произвольно выбран­ного уравнения f(x1, x2,..., xn)=1, где переменная x1 определена на множестве букв {a1, a2,..., xk}. Тогда согласно первому следствию теоремы о конъюн­ктивном разложении имеем:

Axb xb.., xn)=(vAah x2,.., x„))...

(x(k vAab xb.., xn)).

Таким образом, исходное уравнение заменяется системой, состоящей из k уравнений

x1a1 V f ((1, x2,..., xn ) 1,

.............................. (е)

x1ak v f (ak, x2,...,xn) 1.

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

Для иллюстрации метода приведем декомпози­цию уравнения (д), рассмотренного в предыдущем примере. Производим разложение левой части уравнения (д) по переменной x1. В результате по­лучаем следующую систему уравнений: x1 1, x1 V x3 V x2 x3 1, x1 V x2      V x2 x3 V x2x3 1.

Согласно закону отрицания:

Окончательно имеем:

x1bvx1c=1, x1avx1cvx3bvx2bx3c=1, x1avx1bvx2ax3avx2ax3bvx2cx3b=1.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа