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

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

Таким образом, при наличии операции отрица­ния, заданной аксиоматически тождествами (4)-(6), законы ложности можно исключить из числа аксиом алгебры конечных предикатов.

Заметим, что введение операции отрицания в алгебре конечных предикатов не расширяет ее вы­разительных возможностей. Ведь мы знаем, что алгебра конечных предикатов полна и без опера­ции отрицания. Таким образом, введением опера­ции отрицания достигается лишь консервативное расширение [3] алгебры конечных предикатов. В дальнейшем мы не раз будем вводить в алгебре ко­нечных предикатов новые операции. Хотя они и не расширяют выразительных возможностей алгебрыконечных предикатов, однако делают более гибким ее язык, повышают уровень его абстрактности.

Рассмотрим понятие инверсного предиката, ко­торое нам понадобится при введении совершенной конъюнктивной нормальной формы. Предикат g(x1, x2,.., xn) назовем инверсным по отношению к предикатуf(x1, x2,.., xn), если

fy^-^ xn)= f (xb fy^-^ xn).

Предикат, инверсный предикату f, будем запи-співать в видеf*, так что:

f *(X\, X2,.~, Xn)= f (X1, X2,.., Xn). (17)

Таблица инверсного предиката может быть получена из таблицы исходного предиката заме­ной в ее последней строке значений предиката на обратные: 0 на 1 и 1 на 0. Для каждого предиката существует инверсный ему предикат. Предикат, инверсный инверсному предикату, совпадает с ис­ходным предикатом:

f**(X1, X2,.., Xn)=f(X1, X2,.., Xn). (18)

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

f = X1 X2 v X3 ,

тогда

a *=(X v X] к.

Рассмотрим теперь конъюнктивное разложе­ние предиката. Для этого применим тождество (1) к предикату f     X2,.., x^)\

f (xh x2,.■■, xh xl+1,.■■, xn)= = (   v   ) X1a1 X2a2...Xl"' Д"^ "2,-, "l, Xl+1,-, xn).

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

Любой конечный предикат f(x1, x2,., xn) может быть представлен в виде:

f (x1, x2v, xl, xlxn ) =

v   x"1 vx"2 v... vx"1 (19)

("1,"2,..,"l)   12 l

уДсУ^ "2,•••, "l, XlXn)).

Представление предиката f(x1, x2,., xn) в виде правой части тождества (19) назовем его конъюн­ктивным разложением по переменным x1, x2,., xn. Буквенные переменные 1, 2,., l играют роль индексов при образовании многократной конъ­юнкции. Запись ( 1, 2,., l) под знаком конъ­юнкции означает, что логическое перемножение ведется по всевозможным наборам индексов 1, 2,., l. Таким образом, в правой части тождества (19) присутствуют kl конъюнктивных членов.

Из теоремы о конъюнктивном разложении вы­текают следующие два следствия.

Следствие 1. Любой конечный предикат f (x1, x2, ., xn) может быть представлен в виде

f (xj, X2Xn ) = (X"1 v f ("j, X2Xn )) Л

л(x"2 v f (a2, x2, .., xn))..(x"k v (20)

v f (ak, X2v-v Xn )).

Следствие 2. Любой конечный предикат f (x1, x2,..., xn) может быть представлен в виде

AX1, X2,.., Xn)= f(   v      (x"1 vX2"2 v... vXf ). (21)

Тождества (20) и (21) находим, полагая в виде (19) соответственно l=1 и l=n. Запись f( 1, 2,., n)=0 в (21) под знаком конъюнкции означает, что логиче­ское перемножение ведется только по тем наборам индексов (ст1, ст2,..., которые обращают предикат f в 0. Если предикат f тождественно истинный, то, согласно теореме о конъюнктивном разложении, в правой части тождества (21) нужно ставить 1.

Представление предиката fв виде формулы, по­лучаемой в результате исключения из первой ча­сти тождества (21) знаков отрицания с помощью законов отрицания, назовем совершенной конъюн­ктивной нормальной формой предиката f (СКНФ). Рассмотрим пример получения СКНФ предиката. Пусть A={a, b, c}, B={x1, x2}. Найти СКНФ преди­ката:

Значения f( 1, 2) равны 0 для всех наборов ( 1, 2), кроме (a, b), (a, c) и (b, a). По формуле (49) на­ходим:

f (Xj, x2) = (x" v x")(x\ v x])(x] v x2) Л

л(x[ v x") (x[ v x] )(x[ v x2).

Избавляясь от отрицаний с помощью тождеств (34), выводим СКНФ предиката f

f (x1,x2) = (x] vxf vx2 vx2)(xa vxf vx" vx2)л л(xa v xf v x" v x])(xa v x] v x] v x2)л л(x" v x] v x" v x2)(x" v x] v x" v x]).

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

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

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

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

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