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

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

=(01У0) x"1 x2"2...x"t ((v) x^f^, "2,-, "t, "t+1,

(°1,°2,..,°t) ("t+1)

v xn))= (    v    ) x1a1 x2"2 ...xt"+tl1 А"Ъ "2v v

(°1,°2,..,°t+1)

"t+1, Xt+2,.••, xn).

Таким образом, теорема доказана для любых к, l, n.

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

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

Axb X2,-, Xn)= x\lf(ax, X2,-, Xn)v 2Aa2,

X2,...,Xn)v...v Xlak Aak, X2,-, Xn). (2)

Следствие 2. Любой конечный предикат f(x1, x2,..., xn) может быть представлен в виде: fx1,x*...,Xn)= (  v     x"1 X2"2...x"n . (3)

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

Тождество (2) может быть использовано в ка­честве эффективного средства упрощения формул алгебры конечных предикатов. Рассмотрим при­мер такого упрощения. Пусть A={a, b}, B={x1, x2, x3,}. Требуется упростить формулу:

Axb x2, x3)=

=(x1avx2b)(x1avx1bx3a)v(x1avx1a)(x2bx3bvx2ax3a).

Производим разложение функции f по пере­менной x1:

Ax\, X2, x3)=X1af(a, X2, X3)vxfb, X2, X3), Aa, x2, x3)=(aavx2b)(aavabx3a)v(aavx2a)(x2bx3bv vx2ax3a)=(1 vx2b)(1 v0-x3a)v(1 vx2a)(x2bx3bvx2ax3a)= 1, f{b, x2, x3)=(bavx2b)(bavbbx3a)v(bavx2a)(x2bx3bvx2ax3a)=

V a,,-v a/V bx/V- a-Y a\—v ax/V- a-v a— —Xr2 X3 VX2 (X2 X3 VX2 X3 )=X2 X3 VX2 X3 =

=(x2avx2b)x3a=x3a. Окончательно:

f=x1avx1bx3a=(x1avx1b)(x1avx3a)=x1avx3a.

Из второго следствия теоремы о разложении вытекает полнота алгебры конечных предикатов: любой конечный предикат можно записать в виде формулы алгебры конечных предикатов. Тожде­ство (3) можно использовать для получения СДНФ предиката, заданного какой-нибудь произвольно выбранной формулой алгебры конечных предика­тов. Пример: A={a, b}, B={x1, x2, x3,}, дан предикат:

f(x1, ^ x3)=

=(x1avx1b)(x1avx1bx3a)v(x1avx2a)(x2bx3bvx2ax3a).

Требуется отыскать СДНФ указанного преди­ката. Имеем:

Aa, a, a)=(aavab)(aavabaa)v(aavaa)(ababvaaaa)=1.

Аналогично находим: f(a, a, b)=1, f(a, b, a)=1, Aa, b, b)=1, Ab, a, a)=1, f(b, a, b)=1, f(b, b, a)=1, f(b, b, b)=0. СДНФ предиката fимеет вид:

fx 1, Xr2, X3~)=X1aX2aX3avX1aX2aX3bv

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

VX1 X2 X3 VX1 X2 X3 VX1 X2 X3 VX1 X2 X3 .

2. Совершенная конъюнктивная нормальная форма

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

Операция отрицания предиката - это одномест­ная функция, заданная на множестве всех к-ичных n-местных предикатов со значениями в том же множестве. Если A - аргумент и B значение опе­рации отрицания, то условимся писать (—A)=B или, в сокращенной форме A =В. Отрицанием пре­диката f(x1, x2,..., xn) назовем предикат

g(x1, x2,.••, xn)= f        X^-v xn),

принимающий значение 0 для всех тех наборов значений аргументов (x1, x2,..., xn), при которыхAx1, x2,., xn)=1, и принимающий значение 1 для всех тех наборов значений аргументов, при которых^^, x2,., xn)=0.

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

(4) (5)

Действительно,

A v B = AB ,

AB = A v B,

Здесь A и B - произвольные формулы, х - произ­вольная буквенная переменная, ai - произвольная буква алгебры конечных предикатов, индекс i при­нимает значения в пределах от 1 до к. Тождества (4) и (5) совпадают по форме с известными в алге­бре логики законами де Моргана, которые, однако, применяются теперь не к булевым переменным, а к переменным предикатам. Тождество (6) назовем законом отрицания. Заметим, что при к=1 закон от­рицания теряет смысл.

Справедливость законов де Моргана доказыва­ется проверкой тождеств для всех возможных вари­антов значений предикатов Aи B. Например, убеж­даемся при A=0 и B=1, что 0v 1 = 0-Ї и 0-1 = 0v 1. Легко устанавливается также справедливость зако­на отрицания. Действительно, если x=a,, то преди­каты, стоящие слева и справа от знака тождества в (6), обращаются в 0, если же x£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 самых важных уроков библии

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

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

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

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