В каждой из следующих задач представьте данное предложение русского языка предикатной формулой.

Когда мы намереваемся рассмотреть подстановки вместо переменной v в некоторую формулу, удобно обозначать эту формулу выражением F(v), и обозначать результат подстановки терма t вместо v в этой формуле через F(t) .

3.11 Если v не является свободной переменной F(v), тогда F(t) равно F(v).

Пусть F(x) обозначает формулу

" y (P(y) Й Q(x, y)),

предложенную выше как перевод условия ``все простые числа больше чем x'' (задача 3.5). Формула вида F(t), где t – терм, обыкновенно выражает то же условие применённое к значению t. Например, F(a) есть " y (P(y) Й Q(a, y)), что значит ``все простые числа больше чем 10'', F(z₂) есть " y (P(y) Й Q(z₂, y)), что значит ``все простые числа больше чем z<sub>2</sub>''. Существует, однако, одно исключение. Формула F(y), то есть, " y (P(y) Й Q(y, y)), выражает (неправильное) утверждение ``каждое простое число меньше чем оно само''. Проблема с этой подстановкой в том, что, когда мы подставляем переменную y вместо x в F(x), y ``захватывается'' квантором. Чтобы выразить утверждение ``все простые числа больше чем y'' предикатной формулой, мы будем использовать связанную переменную отличную от y и писать, например,

" z(P (z) Й Q(y, z))

Чтобы различать ``плохие'' подстановки, как в последнем примере, от ``хороших'', мы определим, когда терм t является подстановочным для переменной v в формуле F.

• Если F – атомарная, тогда t является подстановочным для переменной v в F,
• t является подстановочным для переменной v в F тогда и только тогда, когда t является подстановочным для v в F,
• t является подстановочным для v в (F Д G) тогда и только тогда, когда t является подстановочным для v и в F и в G,
• t является подстановочным для v в Kw F тогда и только тогда, когда

9. t не содержит w и является подстановочным для v в F, или

10. v не является свободной переменной формулы Kw F.

3.12 Терм, не содержащий ни одной связанной переменной формулы F, является подстановочным в F для любой переменной.

Определение 26 (Универсальное замыкание). Универсальное замыкание формулы F – это предложение

" v₁ ··· v_n F,

где v₁, ... , v_n – все свободные переменные F.

Выводы в логике предикатов

В логике предикатов вывод определяется так же, как и в исчислении высказываний и секвенции имеют тот же синтаксис. Аксиомы тоже определяются так же, как в логике высказываний. Все правила вывода логики высказываний – правила введения и удаления для пропозициональных связок, правила противоречия и сведения к противоречию – включены в множество правил вывода логики предикатов, с метапеременными для формул понимаемыми теперь как предикатные формулы. В дополнение, есть четыре новых правил вывода: правила введения и удаления для кванторов.

Правила для кванторов всеобщности

G |– F(v)

G |– " v F(v)

(В")

(У")

G |– " v F(v)

G |– F (t)

где v не является свободной

где t является

Переменной для любой формулы в G

подстановочным для v в F(v)