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

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

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

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

f (x1, x2, xi,xi+1, xn)-

v

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

x1 1 x2 2 .

.xi l f(si, s2      si, xi

l+1

(1)

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

Докажем теорему о дизъюнктивном разложе­нии. Доказательство будем вести индукцией по к, l и n.

1. При k=l=n=1 равенство (1) принимает вид:

fx)— v x"f "1).

Оно является тождеством. Действительно, пе­ременная х1 принимает единственное возможное значение а1, поэтому f(x1)—f(a1) и

v x1 1

("1) 1

f "1)— X1 1f(a^— 1f>1).

Таким образом, k=l=n=1, теорема о разложении справедлива.

2. Пусть l=n=1. Предположим, что при k=t ра­венство (1) является тождеством и выведем отсю­да, что при k=t+1 равенство (1) тоже будет тожде­ством. По индуктивному предположению имеем тождество

x"1        x? 2f(a2)v...v x^f^), (a)

которое является частным случаем тождества (1) при l=n=1 и k=t. Для каждого предиката/^) заданного на множестве At={a1, a2,..., at}, построим два пре­диката: f'(x1) иf"(x1), определенных на множестве At+1={a1, a2,..., at, at+1}, задавая их следующими условиями:

0,если x1

f'( X1) =

f "( X,):

*t+1'

f (x1), если x1 ф a 1, если x1 = at+1,

t+1

f (x1), если x1 ф at+1.

Докажем, что для указанных предикатов спра­ведливо тождество (1), то есть:

f '(X1)— v x"f'("1)— x?1 f '(al)v    2f'(a^v...

...v x"tf'(a^)v x1t+1f' (at+l), f "(x)— v x"f "("1)— x?1 f "(а>x/V"(а>...

...vX1 'f"(a)vx f^).

(б)

Действительно, если x1Фat+1, то f (x1)=f"(x1)=f(x1) и x1 t+1 —0. В этом случае, согласно (а), равенства (б) обращаютсяв тождества. Е сли же х?=at+1, тоf (x1)—0,

f"(X1)—1,   X11 X1

X t 0,  x t+11, f'(at+1)—0,

f"(at+1)=l, поэтому равенства (б) также обраща­ются в тождества типа 0=0 или 1=1. Заметим, что предикатами f '(x1) и f исчерпывается класс возможных одноместных предикатов, заданных на множестве At+1. Таким образом, при l=n=1 теорема о разложении справедлива для любого к.

3. Пусть 1=1 и к произвольным образом зафик­сировано. Предположим, что при n=t равенство (1) является тождеством, и выведем отсюда, что и при n=t+1 равенство (1) будет тождеством. По предпо­ложению, согласно (1), имеет место тождество

fX1, Х2,..., Xt)= V x^f^, хъ..., Xt).

Поэтому при любом a, (1<ї<к)

f(xx, X2,..., Xt, a,)= V x^f^, X2,-, Xt, a,). Следовательно,

АХЪ Х^-^ xt, Xt+1)= (V) Х\1А®Ъ X2,—, xt, Xt+1).

Заметим, что предикатами, для которых спра­ведливо записанное выше тождество, исчерпывает­ся весь класс всевозможных t+1-местных предика­тов. Таким образом, при l=1 теорема о разложении справедлива для любых к и n.

4. Пусть к и n произвольно фиксированы. Пред­положим, что при l=t равенство (1) является тож­деством, и выведем отсюда, что и при l=t+1, если l<n, равенство (1) будет тождеством. По предполо­жению, согласно (1), имеем тождество:

Axb X^-v xt, З^Ь-^ xn)= = (   V   ) x"1 X"2 ...X^f^, "2,-, "t, Xt+1,-, Xn).

Пользуясь им, а также результатом, получен­ным в пункте 3 настоящего доказательства, имеем:

Axb x2,.••, xb xt+1, Xt+2,.••, xn)= = (   V   ) X"1 X2"2...Xtatf(CT1, "2,-, "t, Xt+1, Xt+2,-, Xn)=

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

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

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

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

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