Логика предикатов с одним переменным
Рефераты >> Логика >> Логика предикатов с одним переменным

Легко видеть, что имеет место следующая равносильность:

(х) ~ ((х)).

Действительно, (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), то получим равносильное выражение:


Страница: