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

Страницы:
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 

/"V" 0-v" а    -V" Д-v" С   -V" b-v b    -V" C-v" b   -V" C-v" C-v" сі

{X1 X2 , X1 X2 , X1 X2 , X1 X3 , X1 X2 X3 }.

5) По импликантной таблице отыскиваем си­стему всех конституэнт единицы предиката, кото­рые не накрываются единицами его дизъюнктив­ного ядра. С этой целью отмечаем все столбцы, в которых содержатся звездочки, соответствующие простым импликантам, вошедшим в состав дизъ­юнктивного ядра. Столбцы, оставшиеся неотме­ченными, соответствуют искомым конституэнтам единицы. В нашем примере разыскиваемая систе­ма имеет в своем составе единственную конститу­энту единицу {x1ax2bx3b}.

6) По импликантной таблице методом полного перебора отыскиваем все приведенные системы простых импликант, накрьшающих своими едини­цами все конституэнты единицы системы, найден­ной на пятом шаге алгоритма. В примере имеем две такие системы: {x1ax3b}, {x2bx3b}, каждая из которых состоит из одной конституэнты единицы.

7) Объединяя дизъюнктивное ядро предиката с каждой из систем, полученных на шестом шаге алгоритма, формируем все приведенные системы простых импликант предиката. В нашем примере имеем две системы:

а       а а       C b       b C       b C       C       C а b

{X1 X2 , X1 X2 , X1 X2 , X1 X3 , X1 X2 X3 , X1 X3 },

а   а     а   C     b   b     C   b     C   C   C     b b

(Х1   Х2   і Х^   Х^   , Х1  Х2   і Х Ц Х3   , Х^ Х^ Х^   , Х^ Х3 |.

8) Строим все тупиковые ДНФ предиката. В примере имеем две такие формы:

v a-y а V y а C V v bY b V v сх b V v cy cy C V v aY b X1 X2     X1 X2     X1 X2     X1 X3     X1 X2 X3     X1 X3 ,

Y aY a V Y aY с V -y bv b V -y Cv b V v сх сх с V v b-r b x1 x2     x1 x2     x1 x2     x1 Л3     Л1 Л2 Л3     ^1 Л3 .

9) Из числа тупиковых ДНФ выбираем ми­нимальную ДНФ, имеющую наименьшее число узнаваний букв. В нашем примере обе тупиковые ДНФ имеют одинаковое число узнаваний букв — 13, любая из них может быть принята в качестве минимальной ДНФ. Исходная СДНФ предиката f имеет 42 узнавания буквы. В результате минимиза­ции число узнаваний букв в формуле сократилось более чем в три раза.

в) Обобщение методов Порецкого-Блейка и Нель­сона. Ниже приводится описание алгоритма мини­мизации формул алгебры конечных предикатов, обобщающего алгоритм Порецкого-Блейка дизъ­юнктивной минимизации формул алгебры логики. Исходной информацией при минимизации для этого алгоритма служит произвольно выбранная ДНФ предиката, для которого отыскивается мини­мальная ДНФ. Рассмотрим пример. Пусть А={а, b, c}. Предикат f задан следующей ДНФ:

f X1 X2 V X1 X2 V X1 X3 V X1 X2 X3 V X1 X2 X3 .

1) Применяем к дизъюнктивным членам исхо­дной ДНФ всюду, где возможно, операцию группи­ровки узнаваний букв:

Ax01 V Ax°2 V... V Ax°r A(x4 v2 v ... vx°'). (39)

Указанная операция не используется в методе Порецкого-Блейка при минимизации формул ал­гебры логики, она становится необходимой только в алгебре конечных предикатов при дизъюнктив­ной минимизации в случае, когда k>2. В результа­те выполнения операции группировки узнавания букв получаем дизъюнкцию некоторых скобочных форм. В нашем примере:

f ( )x2a v ()x2b v (xa )x3a v (xxb v x{ )x2x3a V vxxa (xa v   ) v x\ (xC )xaa v xxC (xC )xaa v (xa) ормальные формы формул алгебры конечных предикатов

2) К скобочным формам всюду, где возможно, применяем операцию обобщенного дизъюнктивного склеивания, основанную на использовании тожде­ства:

A(x01 vx"2 v... vr) v

vB(xvx"r+2 v... vx"s) (40)

A(x01 vx"2 v... v x"r) v

vB(xvx°r+2 v... v x"s) v AB. Это тождество справедливо лишь в том случае, когда множество {ст1, ст2,..., ^совпадает с алфави­том А, причем в записи множества допускаются повторения букв. Результатом операции обобщен­ного дизъюнктивного склеивания является мно­жество всех ненулевых конъюнкций вида А2?. В на­шем примере получаем множество, состоящее из единственного произведения {x2Cx3a}. Заметим, что тождество (40), лежащее в основе операции обоб­щенного дизъюнктивного склеивания в алгебре конечных предикатов, выглядит сложнее, чем со­ответствующее тождество в алгебре логики. В част­ном случае при k=2 тождество (40) переходит в из­вестное тождество алгебры логики: AxvBx —AxvBx vAB, используемое в алгоритме Порецкого-Блейка. Докажем справедливость тождества (40):

A(x01 v x"2 v... v x"r ) v B(xv x°r+2 v... v x°s)

Страницы:
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 самых важных уроков библии

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

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

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

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