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

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

Присвоим каждой конституэнте едини­цы x"1 x"2...x"n свой номер. Для этого составим n-разрядный k-ичный код ст1ст2...стп из показателей ее узнаваний, рассматривая буквы а1, а2,..., ак ал­фавита А как k-ичные цифры 0, 1, к-1. Число, соответствующее коду ст1ст2...стп, будем считать но­мером данной конституэнты единицы. Например, номером конституэнты единицы x1bx2ax3c служит число 11 (в десятичной записи), соответствующее троичному коду 102. Всего имеется kn различных конституэнт единицы.

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

Общий вид СДНФ сле­дующий:

,-"11 V- "12

h x2

,-"21 v "22 Ч     X2 .

{■"In

Y"m1v "m 2 \Л2

V x1i1 x"i2...x"in = V A x"ij i=1  12      n    i=1 j=1 1

Здесь "j некоторые фиксированные буквы ал-

m

фавита А; знак V обозначает операцию логическо­го суммирования m членов; m число конституэнтединицы в СДНФ; i, j индексы, изменяющиеся в пределах соответственно от 1 до m и от 1 до n, по которым ведутся логическое суммирование и ло­гическое перемножение.

Присвоим каждой СДНФ свой номер. Для этого каждой СДНФ поставим в соответствие не­который двоичный код длины kn. Длина кода со­впадает с числом всех различных конституэнт единицы. Если в рассматриваемой СДНФ консти­туэнта единицы с номером i отсутствует, то в i-том разряде ее двоичного кода записываем 0, если при­сутствует, то записываем 1. Нумерацию разрядов двоичного кода в данном случае начинаем с нуля и ведем слева направо. Число, соответствующее полученному таким способом двоичному коду, будем считать номером СДНФ. В качестве СДНФ с номером 0 принимаем формулу 0. Например, номер СДНФ x1ax2bvx1bx2c в алгебре с алфавитами A={a, b, c}, B={x1, x2} будет число 13610 , соответ­ствующее двоичному коду 010001000. Всего име­ется 2kn различных СДНФ, то есть ровно столько, сколько существует всех различных конечных пре­дикатов. Вместе с тем, каждой формуле соответ­ствует единственный конечный предикат, каждому же конечному предикату соответствует некоторая своя СДНФ. Следовательно, между конечными предикатами и совершенными дизъюнктивными нормальными формами существует взаимно одно­значное соответствие.

Важно выяснить вопрос: можно ли с помощью приведенных выше тождеств преобразовать произ­вольную формулу алгебры конечных предикатов к СДНФ. Если да, то отсюда будет следовать, что си­стема этих тождеств полна. Действительно, сравни­вая между собой СДНФ двух формул, всегда мож­но, в силу единственности представления любого конечного предиката в виде СДНФ, решить вопрос о тождестве этих формул. Если СДНФ совпадают, то исходные формулы тождественны, если не со­впадают, то они соответствуют различным преди­катам. Такое преобразование существует. Следо­вательно, система тождеств (4) — (19) [1] алгебры конечных предикатов полна.

Ниже приводится описание алгоритма преоб­разования произвольной формулы к СДНФ. Ал­горитм сопровождается примером: A={a, b}, B={x1, x2, x3}, требуется преобразовать к СДНФ формулу

/=(x1avx2b)(x1avx1bx3a)v(x1avx2a)(x2bx3bvx2ax3a).

1) Пользуясь тождествами (5), (7) и (8) [1], рас­крываем в формуле все скобки:

/=x1a(x1avx1bx3a)vx2b(x1avx1bx3a)v vx1a(x2bx3bvx2ax3a)vx2a(x2bx3bvx2ax3a)= =(x1avx1bx3a)x1av(x1avx1bx3a)x2bv(x2bx3bvx2ax3a)x1av v(x2bx3bvx2ax3a)x2a=x1ax1avx1bx3ax1avx1ax2bvx1bx3ax2bv

\ /-V" b-%/* b-%/* ci\ /-%/*-\Г a-v*    r-\r b-\/* b-v" a* /-v* a-v* a-v* a x2 x3 x1     x2 x3 x1     x2 x3 x2    x2 x3 x2 .

В результате получаем некоторую дизъюнкцию конъюнкций узнаваний предмета.

2) Пользуясь тождествами (4)-(7), (10), (11), (15), (17) и (19) [1], производим упрощения в фор­муле:

y=x1av0-x3avx1ax2bvx1bx2bx3avx1ax2bx3bvx1ax2ax3av v0-x3bvx2ax3a=x1av0vx1ax2bvx1bx2bx3avx1ax2bx3bv vx1ax2ax3av0vx2ax3a=x1avx1ax2bv

b       b       a a       b       b a       a       a a a

x1 x2 x3     x1 x2 x3    x1 x2 x3     x2 x3

В результате получаем некоторую дизъюнктив­ную нормальную формулу предиката.

3) Пользуясь тождествами (16) и (18) [1], во все конъюнкции вводим недостающие переменные:

/=x1a(x2avx2b)(x3avx3b)vx1ax2b(x3avx3b)vx1bx2bx3av vx1ax2bx3bvx1ax2ax3av(x1avx1b)x2ax3a.

4) Пользуясь тождествами (4)-(8) и (10) [1], сно­ва раскрываем скобки и производим упрощения:

a       a       a a       a       b a       b       a a       b       b a       b a

j1   2   3      1   2   3      1   2   3      1   2 3

a       b       b b       b       a b       b       a a       b       b a       a a

x1 x2 x3    x1 x2 x3     x1 x2 x3     x1 x2 x3    x1 x2 x3

a       a       a b       a       a a       a       a a       a       b a       b a

x1 x2 x3    x1 x2 x3    x1 x2 x3     x1 x2 x3    x1 x2 x3

a       b       b b       a       a b       b a

x1 x2 x3    x1 x2 x3     x1 x2 x3

В результате получаем искомую СДНФ.

От совершенной дизъюнктивной нормальной формы нетрудно перейти к таблице обозначаемого ею конечного предиката. Для этого нужно выделить в таблице все наборы значений аргументов, совпа­дающие с наборами показателей узнаваний букв конституэнт единицы, фигурирующих в СДНФ. Против выделенных наборов надо выписать зна­чение предиката 1, против остальных наборов — значение 0. Рассмотрим пример. Пусть A={a, b, c}, B={x1, x2}. Предикат задан совершенной дизъюн­ктивной нормальной формой t=x1ax2bvx1ax2cvx1bx2a. Этому предикату соответствует табл. 1.

Таблица 1

х1

а

a

a

b

b

b

c

c

с

 

а

b

c

a

b

c

a

b

с

t

0

1

1

1

0

0

0

0

0

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

Таблица 2

x1

0

0

0

1

1

1

2

2

2

 

0

1

2

0

1

2

0

1

2

t

1

0

0

0

1

0

0

1

0

X1°X2°vX11X21 vX1"2X21— t.

Заметим, что таблицу значений предиката мож­но легко построить также и по его произвольной дизъюнктивной нормальной форме. Для этого нужно выделить в таблице те наборы значений аргументов, в состав которых входят наборы по­казателей узнаваний элементарных конъюнкций ДНФ. Против выделенных наборов проставляем значения 1, против остальных наборов значение 0. Рассмотрим пример. Пусть А={а, в}, B={x, y, z}. Предикат задан следующей ДНФ:

t—xayвvxвza.

Ему соответствует табл. 3.

Таблица 3

X

a

a

a

a

в

в

в

в

У

a

a

в

в

a

a

в

в

z

a

в

a

в

a

в

a

в

t

0

0

1

1

1

0

1

0

В ряде случаев бывает полезно, отправляясь от задания конечного предиката в виде произвольной формулы алгебры конечных предикатов, получить какую-нибудь по возможности акономную ДНФ. С этой целью можно воспользоваться первыми двумя шагами описанного выше алгоритма приведения к СДНФ. Полученную ДНФ следует попытаться упростить, применяя первый закон поглощения (12) и первый закон идемпотентности (10) [1]. Подчеркнем, что по данному методу мы находим формулу, не обязательно простейшую среди все­возможных ДНФ. Однако она, как правило, ока­зывается не намного сложнее самой простой ДНФ. На отыскание такой экономной формулы затрачи­вается гораздо меньше усилий. Для примера про­изведем упрощение ДНФ, полученной на втором шаге в примере только что упомянутого алгоритма преобразования к СДНФ:

bb

123

12

bb

bb

aaa

, ax a 3 vx2 x3 .

aa

x2 x3 =

i-1 V.A.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 самых важных уроков библии

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

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

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

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