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

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

которое справедливо при условии i ф j . Операция неполного конъюнктивного склеивания состоит в дописывании в исходной КНФ в виде дополни­тельных конъюнктивных членов всевозможных элементарных дизъюнкций А. Последние можно получить переходом от левой части тождества (40) к правой. Операцию неполного конъюнктивного склеивания сначала применяем к конституэнтам нуля исходной СКНФ, затем к элементарным дизъюнкциям, состоящим из узнаваний букв, n(k-1)-2 узнаваний букв и т.д., наконец, к элементарным дизъюнкциям, состоящим из одного узнавания буквы. В нашем примере имеем

f = (x\ v xf v    v x2 v x'b v x\)(x\ v xf v    v x2 v x'b v

vx3)(xa v xf v    v xc2 v x'b v x3)(x'a v xf v    v xc2 v x'b v

vxf)(xa v x\ v xaa v xbb v xbb v xl)(xa v x\ v xaa v xbb v xaa v

vxl)(xa v    v xaa v xbb v xaa v xbb)(x\ v xf v xL2 v xbb v

vxf )(xf vxaa vx2 vxbb vxf )(xa vxf vv xbb vxl)Л

vx\ vxaa vxbb vxf )(xa vvxaa vxbb vxaa)л

v xf v xbb v xf )(xa v x\ v xaa v x^) .

2) Применяем к конъюнктивным членам полу­ченной формулы операцию элементарного конъюн­ктивного поглощения:

(A v x° )A = A . (42)

В результате получаем сокращенную КНФ. В нашем примере имеем:

f = (xa vx\ v xaa vxbb)(xf vvxbb v xf).

В примере сокращенная КНФ совпадает с ми­нимальной КНФ. В более сложных случаях про­цесс минимизации продолжатся.

3) Составляем имплицентную таблицу. Импли-центная таблица конечного предиката f представ­ляет собой матрицу, строки которой обозначены всевозможными простыми имплицентами преди­ката f, а столбцы — конституэнтами нуля того же предиката. Каждая ячейка таблицы соответству­ет паре предикатов, один из которых представлен конституэнтой нуля, другой — некоторой элемен­тарной дизъюнкцией. Если элементарная дизъ­юнкция, соответствующая некоторой строке та­блицы, является имплицентой для конституэнты нуля, соответствующей некоторому столбцу, то в ячейку, образуемую пересечением строки и столб­ца, заносим звездочку, в противном случае ячейку оставляем незаполненной.

4) По имплицентной таблице находим конъ-юктивное ядро предиката. Для этого находим те столбцы таблицы, в которых содержится только по одной звездочке. Соответствующие звездочкам простые имплиценты образуют конъюнктивное ядро предиката.

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

6) По имплицентной таблице методом полного перебора отыскиваем все приведенные системы простых имплицент, накрывающих своими нуля­ми все конституэнты нуля системы, найденной на пятом шаге алгоритма.

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

8) Строим все тупиковые КНФ предиката. Приведем описание алгоритма минимизации

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

f = (xf v xf v xa v xha )(xa v xf v xa v xbb)

(xa v x{ v x2)(xja v    v xbf v x2).

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

(A v xa )(B v xaj) =

= (A v xa )(B v xaj)(A v B), справедливого в случае, когда їф]. Результатом опе­рации обобщенного конъюнктивного склеивания является множество всех не равных единице эле­ментарных дизъюнкций вида AvB. В нашем при­мере получаем следующее множество элементарных дизъюнкций:

{xf v x{ v xaa v xbf,  xa v    v xaa v xbf,  xf v xaa v xbf,

xa v xf v xf v xc2,  x'a v x\ v xf,  xa v xf v xf v x2,

xa v xbf v }.

Заметим, что тождество (43), лежащее в основе операции обобщенного конъюнктивного склеи­вания, в алгебре конечных предикатов выглядит несколько иначе, чем соответствующее тождество в алгебре логики. В частном случае при к=2 тожде­ство (41) переходит в известное тождество алгебры логики

(Avx)(Bv x )=(Avx)(Bv x )(AvB),

используемое в алгоритме Порецкого-Блейка. До­кажем справедливость тождества (41): (A v xai )(B v xa]) = (A v xai)(A v xa v B)(B v xa]) л

a(B v xa] v A) = (A v xai )(B v xa])(A v B v xa'x"]) =

= (A v xai )(B v xa])(A v B).

2) Исходную КНФ пополняем конъюнктивны­ми членами из системы, полученной на первом шаге алгоритма. В нашем примере имеем

f = (xf v x{ v xaa v xf )(xa v xf v xaa v xf) л

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

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

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

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

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