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

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

Дизъюнкция любого числа импликант конеч­ного предиката есть импликанта этого предиката. Систему S импликант конечного предиката f на­зовем полной, если любая единица из таблицы зна­чений предиката f накрывается единицами хотя бы одной импликанты системы S. Тому или иному конечному предикату может соответствовать, во­обще говоря, несколько различных полных систем импликант. Дизъюнкция всех импликант полной системы импликант каждого конечного преди­ката выражает собой этот предикат. Система всех простых импликант любого конечного предиката является его полной системой. Дизъюнкция всех простых импликант конечного предиката выра­жает собой этот предикат; назовем ее сокращенной дизъюнктивной нормальной формой данного конеч­ного предиката.

Во многих случаях (однако далеко не всегда) сокращенная дизъюнктивная нормальная форма представляет собой более экономное средство за­писи конечных предикатов, чем СДНФ. Однако сокращенная форма, как правило, не совпадает с минимальной дизъюнктивной нормальной фор­мой, сложнее ее. Дизъюнктивным ядром конечного предиката назовем множество всех таких его про­стых импликант, исключение каждой из которых из системы всех простых импликант делает эту си­стему неполной. Элементы дизъюнктивного ядра входят в состав любой полной системы простых импликант. Систему простых импликант конечно­го предиката назовем приведенной, если она полна и никакое ее собственное подмножество не явля­ется полной системой. Дизъюнкцию всех простых импликант приведенной системы назовем тупико­вой дизъюнктивной нормальной формой предиката. Отметим, что предикат может иметь много тупи­ковых дизъюнктивных нормальных форм.

Любая минимальная дизъюнктивная нормаль­ная форма является, вместе с тем, и тупиковой ДНФ. Многие конечные предикаты имеют не­сколько различных минимальных ДНФ, содержа­щих одинаковое число узнаваний букв. Выбирая из числа тупиковых ДНФ одну с наименьшим чис­лом узнаваний букв, получаем минимальную ДНФ предиката. Сформулированные понятия и поло­жения позволяют наметить ход действий, лежащих в основе всех описываемых ниже методов мини­мизации формул алгебры конечных предикатов. Вначале нужно отыскать все простые импликанты заданного конечного предиката и составить из них сокращенную ДНФ. Затем следует найти все тупи­ковые ДНФ и из их числа выбрать минимальную дизъюнктивную нормальную форму конечного предиката.

Ниже рассматриваются три алгоритма миними­зации формул алгебры конечных предикатов. Ал­горитмы сопровождаются примерами. В частном случае при к=2 они превращаются в известные алгоритмы канонической минимизации формул алгебры логики Квайна-Мак-Класки, Порецкого-Блейка и Нельсона [6].

б) обобщение метода квайна-Ыак-Еласки. Рас­смотрим метод дизъюнктивной минимизации фор­мул алгебры конечных предикатов, обобщающий известный метод Квайна-Мак-Класки миними­зации формул алгебры логики. Исходной инфор­мацией при минимизации служит совершенная дизъюнктивная нормальная форма предиката, для которого отыскивается минимальная ДНФ. Рас­смотрим пример. Пусть A={a, b, c}, B={x1, x2, x3}. Предикат задан следующей СДНФ:

і—— у' d-\r d-\r "\ r-\/* d-\r d-\r b\ /-V" "-V" d-\r      /-v* d-\r b-v* b\ *

J—X1 Xr2 X3 VX1 X2 X3 VX1 X2 X3 VX1 X2 X3 V

a       c       a a       c       b a       c       c b       b a

VX1 X2 X3 VX1 X2 X3 V X1 X2 X3 VX1 X2 X3 V

b      b      b b      b      c c      a      b c      b b

1   2   3      1   2   3      1   2   3      1   2 3

c       c       b c       c c

x1 x2 x3    x1 x2 x3 .

Ниже описывается алгоритм минимизации, включающий в себя 9 шагов.

1) Всюду, где это возможно, применяем опера­цию неполного дизъюнктивного склеивания, осно­ванную на тождестве:

Ax"1 v Ax"2 v... v Ax"k = (37)

= Ax"1 v Ax"2 v... v Ax"k v A. Здесь A некоторая элементарная конъюнкция, x одна из буквенных переменных. Операция неполного дизъюнктивного склеивания состоит в дописывании к исходной ДНФ в виде дополни­тельных дизъюнктивных членов всевозможных элементарных конъюнкций, которые можно по­лучить переходом от левой части тождества (37) к правой. Операцию неполного дизъюнктивного склеивания сперва применяем к конституэнтам единицы исходной СДНФ, затем к элементарным конъюнкциям, состоящим из n-1 узнаваний букв, n-2 узнаваний букв и т.д. и, наконец, к элементар­ным конъюнкциям, состоящим из одного узнавания буквы. В нашем примере имеем:

a       a       a a       a       b a       a       c a       b       b a       c a

f x1 x2 x3     x1 x2 x3    x1 x2 x3    x1 x2 x3    x1 x2 x3

a      c      b a      c      c b      b      a b      b      b b      b c

c       a       b c       b       b c       c       b c       c       c a a

vx1ax2сvx1bx2bvx1ax3bvx1cx3bvx2bx3b.

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

Ax°vA—A, (38)

где xP некоторый предикат узнавания буквы. В результате получаем сокращенную ДНФ. В при­мере имеем:

/—— у' a-v au /-V" a-v I)\ /-V" a-v с* ^-v" b-\i* b\ /-\/* b-v b\ /-\/* с-v b\ /-v с-v с-v с

y=xXVxi  Л3  Vxi  Л^Лі Л3   VXXVxi Л3  Vxi X2 Л3 .

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

Таблица 7

Простая импликанта

а

3

C

3

C

3

b

3

а

b

3

C

3

$

а

3

b b

C b

b

3

b b

b

3

C

д-у- а x1 x2

*

*

*

 

 

 

 

 

 

 

 

 

 

 

-v- а-v- b

X1 X3

 

*

 

*

 

*

 

 

 

 

 

 

 

 

х1ах2с

 

 

 

 

*

*

*

 

 

 

 

 

 

 

 

 

 

 

*

 

 

 

 

*

 

 

*

 

 

bv b

x1 x2

 

 

 

 

 

 

 

*

*

*

 

 

 

 

v cv b

Хц Л3

 

 

 

 

 

 

 

 

 

 

*

*

*

 

v Cv Cv С

x1 x2 x3

 

 

 

 

 

 

 

 

 

 

 

 

 

*

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

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

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

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

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

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