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

Страницы:
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), можно доказать, что:

0 = 1, (7)

1 =0. (8)

а\  а г—   aix/   а 2= ci2,

x   v x  v x

v... v

at

=1,

1 =- xa1 vxa2 v...v= xa1 xVj^

=(

a 2 v   а з

x   v x

v... v

at

x   )(x

v...v

at

).

...(xai v.

a 2

v v...v

at-i

)=0.

Любая формула с отрицаниями может быть преобразована с помощью зависимостей (4) — (8) в тождественную ей формулу без отрицаний. Дей­ствительно, применяя многократно законы де Моргана, мы всегда сможем все знаки отрицания, стоящие над формулой или ее частями, опустить непосредственно на узнавания букв или на 0 и 1. Затем, пользуясь тождествами (6) — (8), исключаем отрицания из формулы. Рассмотрим пример ис­ключения знаков отрицания из формулы. Пусть A={a, b, c}. Тогда:

X1 v X1 X2 X1 X1 X2 X1 (X1 v X2 )

=(x1bvx1c)(x1avx1cvx2avx2b).

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

В ряде случаев процесс исключения знаков от­рицания из формул существенно упрощается, если использовать следующие тождества:

X i X

-.xa

(9)

xai (xaj v A) = xai . (10)

Тождества справедливы при условии, что Щ, индексы i и j принимают значения в пределах от 1 до к. Буквой A обозначена произвольная формула алгебры конечных предикатов. Тождество (9) на­зовем законом поглощения отрицания, тождество (10) - обобщенным законом поглощения отрицания. Докажем справедливость тождества (10):

xai (xaj vA)= xai (xa1 vxa2 v...vxai v... v xaj-1 v xaj+1 v...v     vA)= xai v xai A= xa .

Рассмотрим пример, иллюстрирующий при­менение только что приведенных тождеств. Пусть A={a, b, c}, требуется упростить формулу

f= (xa xxb v xf v x2a) x1bx2c,

0

a 3

v

x

x

x

x

xпредварительно исключив из нее отрицания. При­меняя тождество (10), непосредственно получаем искомый результат f=x1bx2c. Без использования законов поглощения отрицания тот же результат достигается более длинным путем:

„/=((x1bvx1c)(x1avx1c)vx1avx1bvx2bvx2c)x1bx2c=

=(x1cvx1avx1bvx2bvx2c)x1bx2c=x1bx2cvx1bx2c=x1bx2c.

Для операции отрицания также справедливы следующие тождества: закон двойного отрицания

A = A, (11) закон исключенного третьего

A v A = 1, (12)

закон противоречия

AA = 0. (13)

Эти тождества по форме совпадают с одноимен­ными законами алгебры логики. Тождества (11) — (13) можно получить из ранее выведенных тож­деств.

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

xai = xa1 vxa2 v... vx"i-1 vxai+1 v...vx"k =

= xa1 xa2     xai-1 xai+1     xak =

(xa2 v... v xai v... v x"k )(xa1 v xa3 v... v vxa v... v x"k )...(xa1 v... v xai v xa,+2 v... v vx"k )...(x"1 v... v xai v... v x"k-1) = xai.

Предположим, что закон двойного отрицания справедлив для формул А и В, и установим, что он выполняется также для формул AvB и AB:

A v B = AB = A v B = A v B,

AB=A v B = AB=ab.

Таким образом, закон двойного отрицания справедлив для всех формул.

Докажем тождество (12). Оно выполняется для формул 0 и 1, а также для всех узнаваний букв: 0v 0 =0v1=1, 1v 1 =1v0=1,

xai v X" =

= xai vx"1 vx"2 v... vx"i-1 vxai+1 v... vxak = 1. Если тождество (40) справедливо для формул A и B, то оно справедливо и для формул AvB и AB:

AvBv A v B =AvBv AB =

=(Av A )(Av B )v(Bv A )(Bv B)=Av B vBv A = 1,

ABv AB =ABv A v B =(Av A )(Bv A )(Av B )(Bv B )= = Bv A vAv B =1.

Аналогично доказывается закон противоречия.

Итак, мы видим, что в алгебре конечных пре­дикатов наряду с операциями дизъюнкции и конъ­юнкции существует операция отрицания со всеми свойствами, которыми наделяет ее булева алгебра (тождества (4), (5), (7), (8), (11) — (13)). Поэтому ал­гебру конечных предикатов можно рассматривать как разновидность булевой алгебры. Основным множеством в ней служит система всех к-ичных n-местных предикатов с алфавитом букв {a1, a2,

ak} и алфавитом переменных {x1, x2, xn}, роль нуля выполняет тождественно ложный предикат, роль единицы - тождественно истинный предикат, в роли базисных операций выступают дизъюнк­ция, конъюнкция и отрицание.

В качестве системы тождеств алгебры конечных предикатов, задающей в ней структуру булевой ал­гебры (и только эту структуру), можно использо­вать, к примеру, следующий набор аксиом [1]: (10), (4), (6), (8), (39), (32) и тождество:

(A v A )B = B. (14)

Подчеркнем еще раз, что алгебра конечных пре­дикатов не есть только булева алгебра, она имеет и свои специфические тождества: закон истинности (18) [1], закон ложности (19) [1] и закон отрицания (6), не вытекающие из аксиом булевой алгебры.

Законы истинности и ложности можно запи­сать в модифицированном виде без использования символов 0 и 1:

x"1 vx"2 v...vx"k =Av A , (15) xai xai =AA , (iVj) (16)

Тождество (16) может быть выведено из тож­деств булевой алгебры и тождеств (6), (15). Дей­ствительно, пусть Щ. Тогда:

xai x"j = xa,x"j = X" v x"j = =( x"1 v x"2 v^v x"i-1 v x"i+1 v^v x"k v x"1 v v x"2 v^v x"j-1 v x"^1 v^v x"k )=( x"1 v x"2 v^v x"k )=

= A v A = AA.

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

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

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

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

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