Автор неизвестен - Информация, язык, интеллект - страница 61
Кванторы по предикатной переменной 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);
Похожие статьи
Автор неизвестен - 13 самых важных уроков библии
Автор неизвестен - Беседы на книгу бытие
Автор неизвестен - Беседы на шестоднев
Автор неизвестен - Божественность христа