Логика предикатов (стр. 3 из 7)

Пусть 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 x₁)(s x₂)...(s x_p) B(

, ..., , x₁, ..., x_p).

B(

, ..., , x₁, ..., x_p)

представляет собой предикат, определённый на поле M и зависящий от p переменных x₁, ..., x_p. Каждое из этих переменных входит в формулу B только через предикаты

, ..., . С другой стороны, мы видели, что предикаты (х) и ( (х)) равносильны. Поэтому если в формуле B( , ..., , x₁, ..., x_p) мы заменим x_i на (х_i), то получим равносильное выражение:

B(

, ..., , x₁, ..., x_p) ~ B( , ..., , (x₁), ..., (x_p)).

Отсюда следует, что

(s x_p) B(

, ..., , x₁, ..., x_p) ~ (s x_p) B( , ..., , (x₁), ..., (x_p)).

Далее можно заключить, что

(s x_p) B(

, ..., , (x₁), ..., (x_p)) ~

~

B( , ..., , (x₁), ..., (x_p-1), x_p).

Рассуждая аналогичным образом, мы получим

(s x_p-1) (s x_p) B(

, ..., , x₁, ..., x_p-1 , x_p) ~

~

B( , ..., , (x₁), ..., (x_p-2), x_p-1, x_p)

и, наконец, придём к следующему:

(s x₁)(s x₂)...(s x_p) B(

, ..., , x₁, ..., x_p) ~

~

B( , ..., , x₁, ..., x_p).