Логика предикатов
Категория реферата: Рефераты по философии
Теги реферата: bestreferat ru, роботы реферат
Добавил(а) на сайт: Пондяков.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 | Следующая страница реферата
, , ..., .
Некоторые из этих классов могут оказаться пусты, так как может случиться, что для некоторой последовательности 1, 2, ...,n не существует такого элемента, для которого предикаты , , ..., принимают соответствующие значения 1, 2, ...,n . Вместе с тем каждый элемент множества M принадлежит одному из классов , и различные классы общих элементов не имеют. Число всех классов (пустых и непустых) равно числу последовательностей 1, 2, ...,n, т. е. . Следовательно, число q непустых классов не превышает . Выберем из каждого непустого класса по одному элементу и обозначим эти элементы
a1, a2, ..., aq.
Множество всех этих элементов обозначим .докажем, что если формула U(, ..., ) истинна на поле M, то она истинна и на поле (так как – часть поля M, то предикаты определены на ). каждому элементу x поля M поставим в соответствие элемент из , принадлежащий тому же классу, что и х. В существует один и только один такой элемент. Элемент из , поставленный в соответствие х, обозначим (х). Можно сказать, что мы построили функцию, определённую на множестве M и принимающую значения из множества .
Легко видеть, что имеет место следующая равносильность:
(х) ~ ((х)).
Действительно, (x) принадлежит тому же классу , что и x. Но, по определению, для элементов одного и того же класса каждый предикат принимает одно и то же значение. Отсюда следует, что если в формуле U(, ..., ) для каждого предметного переменного t заменить каждое выражение (t) через ((х)), то формула U(, ..., ) перейдёт в формулу (, ..., ), равносильную первой. Написание формулы отличается от U только тем, что все предметные переменные x, y, z, …, u формулы U замещены соответственно через (х), (y), ..., (u). Это следует из того, что по условию формула U(, ..., ) содержит только предикаты , и поэтому всякое предметное переменное входит только под знаком одного из этих предикатов.
Пусть R (x, y, ..., u) – предикат, определённый на поле M. Введём обозначение
R (x, y..., u).
Под этим выражением мы будем понимать предикат, зависящий от y, z, ..., u (или высказывание, если, y, z, ..., u отсутствуют) и принимающий значение И, когда R (y, z, ..., u) имеет значение И для данных y, z, ..., u и для всех x, принадлежащих полю , и принимающий значение Л в противоположном случае. Введём также выражение
R (x, y..., u),
которое представляет собой предикат от y, ..., u и принимает значение И, когда R (x, y, ..., u) имеет значение И для y, ..., u и по крайней мере для одного значения x из поля , и значение Л в противоположном случае. Знаки и будем называть ограниченными кванторами. Если мы все переменные предиката R (x, y, ..., u) свяжем ограниченными кванторами, например
... R (x, y, ..., u),
то получим формулу, отнесённую к полю . покажем, что выражение
("x) R ((х), y, ..., u)
равносильно выражению
R (x, y..., u).
Пусть ("x) R ((х), y, ..., u) имеет значение И. В таком случае R ((х), y, ..., u) имеет значение И для данных y, ..., u и для каждого x. Но так как функция (х) пробегает всё поле , когда x пробегает поле M, то R (x, y, ..., u) имеет значение И для данных y, ..., u и для всех x из . В силу определения R (x, y..., u) также принимает значение И. Обратно, если R (x, y..., u) принимает значение И, то R (x, y, ..., u) имеет значение И для данных y, ..., u и для каждого x из . В таком случае выражение R ((х), y, ..., u) имеет значение И для данных y, ..., u и для каждого x из M, так как (х) для любого x принадлежит .
Аналогичным образом можно показать, что выражения
() R ((х), y, ..., u) и () R (x, y, ..., u)
также равносильны.
Рассмотрим формулу U(, ..., ), которую можно представить в форме
(s x1)(s x2)...(s xp) B(, ..., , x1, ..., xp).
B(, ..., , x1, ..., xp)
представляет собой предикат, определённый на поле M и зависящий от p переменных x1..., xp. Каждое из этих переменных входит в формулу B только через предикаты , ..., . С другой стороны, мы видели, что предикаты (х) и ((х)) равносильны. Поэтому если в формуле B(, ..., , x1, ..., xp) мы заменим xi на (хi), то получим равносильное выражение:
Рекомендуем скачать другие рефераты по теме: сочинение изложение, курсовые работы бесплатно.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 | Следующая страница реферата