Автор неизвестен - Информация, язык, интеллект - страница 58

Страницы:
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  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 

Пусть P — отношение, заданное на дека­ртовом произведении A = A x A2 x...x An, где A1,A2,...,An єU. Отношение P можно формально выразить любым предикатом P , заданным на Un, который удовлетворяет условию: P (x1, x2,..., xn) = 1, если (x1,x2,...,xn)єP ; P(x1,x2,...,xn) = 1, если (x1, x2,..., xn) є A x A2 x ... x An \ P . За предела­ми области A x A2 x...x A значения предика­та P можно выбрать произвольно. Факт зада­ния отношения P на декартовом произведении A формально выражается системой уравнений A (x1 ) = 1, A2 (x2 ) = 1,..., An (xn ) = 1, ограничивающих значения переменных x1,x2,...,xn множествами

A1,A2,.■■,An .

Пытаясь описать на языке алгебры предикатов отношение равенства D , заданное на U , мы обна­руживаем, что этому отношению соответствует не один предикат D , а целое семейство предикатов D(xj,Xj) (іф j; i,j є{1,2,...,п}) , зависящих от все­возможных пар аргументов. Таким образом, мы вынуждены различать отношения равенства в за­висимости от того, на каких местах в n -компонен­тном наборе стоят элементы, связываемые данным отношением равенства.

Отношению равенства D , связывающему эле­менты, стоящие в n -компонентном наборе на D -м и D -м местах, соответствует предикат D, значе­ния которого определяются формулой:

D(Xi,x,) = v xaxa. (98)

 

Если универсум конечен (U = {ах,а2,..,ак}), то формулу (98) можно записать в виде

 

D(xt, xj) = xa1 xa1 v xa2 x]2 v . v xak xak. (99)

Назовем множества однотипными, если соот­ветствующие им предикаты зависят от одной и той же переменной. Пусть однотипным множествам A и B соответствуют предикаты A(xt) и B(xt) (iє{1,2,^,n}). Тогда объединению AuB этих мно­жеств соответствует предикат

(AuB)(xt) = A(xt)vB^). (100)

Пересечению A n B множеств A и B соответс­твует предикат

(AnB)(xt) = A^B^). (101)

Дополнению A множества A соответствует предикат

(A)(xi) = A~(XX7). (102)

Мы видим, что объединение, пересечение и дополнение предикатов совпадает соответствен­но с их дизъюнкцией, конъюнкцией и отрица­нием (см. (83)-(85)). Точно так же объединению, пересечению и дополнению отношений отвечает дизъюнкция, конъюнкция и отрицание предика­тов, соответствующих этим отношениям. Можно показать, что при таком определении операций u, n и ~ для множеств и отношений они будут удовлетворять всем основным тождествам булевой алгебры. Заметим, что пустому множеству 0 соот­ветствует предикат 0(xi) = 0 (103) для всех x, єU . Универсальному множеству U соответствует пре­дикат U(xi) = 1 (104) для всех X/ єU . Точно так же пустому и полному отношениям соответствуют предикаты тождественно ложный и тождественно истинный.

5. Операции над предикатами

Пусть P(x1,x2,...,xn) — произвольный преди­кат, заданный на Un. Утверждение "Для всех xt выполняется равенство P (x1, x2,..., x,xn) = 1" связывает предикат некоторым унарным отноше­нием, которое формально можно записать в виде равенства

л P(X1,x2,..,xtxn) = 1. (105)

Здесь iє{1,2,...,п} . Выражение, стоящее в ле­вой части равенства (105) можно понимать как некую операцию, отображающую множество всех предикатов., заданных на Un, в себя. Называется эта операция квантором общности по переменной X/ и записывается в виде Ух, (P(x1, x2,..., x{,..., xn)). Символ У читается «для всех». Таким образом:

Ух1 (P (^ x2,..., x       xn )) =

P(                         ) (106)

=   P(x1,x2,. ,x ,. ,xn).

 

Утверждение «Существует X/, для которого вы­полняется равенство P(x1,x2,^,х{,..,хп) = 1» свя­зывает предикат P другим отношением, которое формально выражается равенством

v P(X1,X2,^,x{xn) = 1. (107)

Xj єU

Операция, стоящая в левой части равенства (107) и отображающая множество всех предикатов, заданных на Un, в себя, называется квантором су­ществования по переменной xt. Она записывается в виде 3xt (P (x1, x2,..., xxn)). Символ 3 читается «существует». Имеем:

 

= у p(xl, x2,^, xi       xn ) = 1. (108)

x j gU

Кванторы общности и существования исполь­зуются для формальной записи различных ма­тематических высказываний. При переводе на формальный язык слова "для всех" (или "для каж­дого", "при любом" и т.п.) заменяются символом V, слова "существует" ("найдется") — символом 3; отношения, фигурирующие в высказывании, заменяются соответствующими им предикатами; слова "или", "и" (запятая), "не" ("ложно, что", "неверно, что"), "влечет" ("если — то", "когда — тогда"), "равносильно" ("если и только если — то", "тогда и только тогда — когда", "в том и только том случае — если") заменяются булевыми операциями

V , Л ,     , з , ~.

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

1) «При любых

x1, x2,.■■, xn  (x1, x2,.■■, xn )є A1 X A2 X     X An

Страницы:
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  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

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

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

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

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