Статьи

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

Страницы:

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

Кванторы по предикатной переменной Pj (j є {1,2,—,r}) вычисляются по формулам:

VPR (x1, x2,—, xn ЛА—Р,-,Рг ) =

(132)

pi ЛunR (X1, x2, —, xn ,Р1,Р2,...,Р,.,РГ ),

ЗРЯ (x1, x2,..., xn ,Р1,Р2 — .,Р],...,РГ ) =

j у 1' 2' ' II' 1' 2' 'j'

(133)

= V R (x1, x2, —, x„ ,Р1,Р2, — ,Р;,Р.).

Аналогичным способом можно определить операцию взятия кванторов по предикатным переменным второго и более высокого порядков.

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

(134)

1) «Для всех a и b a = b в том и только том случае, когда a є A равносильно b є A при любом A »: VAVaVb (D (a,b) ~ (A (a) ~ A (b)));

2) «Для всех A и B A = B в том и только том случае, когда a є A равносильно a є B при любом a »: VAVBVa (D (A,B) ~ (A (a) ~ B (a)));

3) «Существует множество M такое, что для всех x x єМ »: 3MVxM(x). Заметим, что предикат равенства от предикатов первого порядка определяется формулой

= V PAPA.

AcUn j

аналогичной выражению (93).

Мы рассмотрели ряд операций над предикатами, отображающих множество всех предикатов, заданных на Un, в себя. Это — конъюнкция, дизъюнкция и отрицание предикатов, а также кванторы общности и существования по переменным xt (і = 1,2,—,n). Введём ещё семейство всех предикатов, соответствующих отношениям A с Un, каждый из которых рассматривается как константная операция A, принимающая на всех наборах предикатов одно и то же значение A. Введём также операцию узнавания предиката A по предикатной переменной Р] (j є{1,2,...,?}), определяемую следующим образом:

(135)

I" 1, если Р = A, [0, если Р} ф A.:Здесь символы 1 и 0 обозначают тождественно истинный и тождественно ложный предикаты.

Любую t -местную операцию F над предикатами P1,P2,..,Pt можно следующим образом выразить в виде суперпозиции уже введенных операций:

F (Р1,Р2,..,Р ) =

v B(A1,A2,...,АР1^2,-^ (136).

A1,A2,..,,A, cUn

Здесь B (A1, A2,..., A ) = F (A1, A2,..., A) — фиксированный предикат, представляющий собой значение операции F на наборе предикатов (A1,A2,...,At). Таким образом, система операций, состоящая из дизъюнкции, конъюнкции, узнаваний всевозможных предикатов по переменным Р1,Р2, ..,Р1 и всех константных операций, полна.

Узнавание каждого предиката A по любой из предикатных переменных Р,(j = 1,2,...,t) выражается в виде следующей суперпозиции кванторов общности, операции равнозначности предикатов и фиксированного (индивидуального) предиката A:

PA =VxxVx2 ..*xn (Р] (x1, x2,-, xn) ~ A (x1, x2,-, xn)) (137) Операция равнозначности предикатов

Р ~Q = PQ v PQ (138) выражается через дизъюнкцию, конъюнкцию и отрицание предикатов. Пусть x = (x1, x2,..., xn) — набор предметных переменных. Квантором общности по набору x назовем операцию

VxP (x ) = Vx1Vx2... VxnP (x1, x2,..., xn). (139)

Мы видим, что любую операцию над предикатами можно выразить суперпозицией операций Vx, v , л , и всех константных операций (т.е. индивидуальных предикатов). Такая система операций несократима.

Операции над предикатами, которые принимают значения только из множества 0,1, называются предикатами от предикатов. Каждому предикату T от предикатов P[,P2,..,Pt соответствует некоторое отношение T, связывающее отношения P1,P2, . .,Pt. Любой t -арный предикат T от предикатов Р1,Р2,..,Р1 можно выразить формулой вида:

T(Р,,Р2,...,Р.)= v Р/1 P2A2 ...PtA (140) Выводы

Мы видим, что система всех узнаваний предикатов, вместе с операциями дизъюнкции и конъюнкции предикатов, полна при выражении с ее помощью любого предиката от предикатов. Если желательно обойтись без узнаваний предикатов, то для выражения любых предикатов от предикатов можно воспользоваться описанной в предыдущем абзаце системой, состоящей из операций v , л , , Vx и всех константных операций.

Предикаты от предикатов используются для формальной записи математических утверждений. Если предикат от предикатов принимает значение 1, то ему соответствует истинное утверждение, если 0 — ложное. Приводим примеры перевода истинных и ложных утверждений на формальный язык:

1) "Для любого множества М существует элемент x такой, что x єМ ": VM3xM (x);

Страницы:

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

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