Свободные и связанные переменные

Множество свободных переменных^* формулы F определяется рекурсивно, следующим образом:

Определение 22 (Свободные переменные).

Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
свободные переменные формулы F являются свободными переменными формулы F,
переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.

Определение 23 (Замкнутая формула).Формула без свободных переменных называется замкнутой формулой, или предложением.

Определение 24 (Связаная переменная).Переменная v связана в формуле F, если F содержит вхождение Kv, где K – квантор.

3.4Найдите свободные переменные и связанные переменные формулы

$ y P(x, y) & $ x P (x, x)

Представление предложений русского языка предикатными формулами

Перед тем как мы продолжим изучение синтаксиса логики предикатов, полезно потренироваться в переводе предложений с русского языка в язык предикатных формул. ^*

В этих упражнениях для перевода рассматривается сигнатура (4). Мы предполагаем, что объектные переменные служат для обозначения натуральных чисел и интерпретируем сигнатуру следующим образом:

a представляет число 10,
P(x) выражает условие ``x является простым числом'',
Q(x, y) выражает условие ``x меньше чем y''.

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

3.5Все простые числа больше чем x.

Ответ: " y(P (y) Й Q(x, y)).

3.6Существует простое число, которое меньше чем 10.

3.7x равно 2. см. Указания

3.8x равно 11. см. Указания

3.9Существует бесконечно много простых чисел.

Подстановка

Определение 25 (Подстановка терма).Пусть F – формула и v – переменная. Результат подстановки терма t вместо v в F – формула, определённая рекурсивно следующим образом:

результат подстановки t вместо v в атомарную формулу F получается из F одновременной заменой всех вхождений v на t,
если результат подстановки t вместо v в F есть F' тогда результат подстановки t вместо v в F есть F',
если результат подстановки t вместо v в F и G есть F' и G' тогда результат подстановки t вместо v в (F Д G) есть (F'Д G'),
если результат подстановки t вместо v в F есть F' и w – переменная, отличающаяся от v, тогда результат подстановки t вместо v в Kw F есть Kw F',
результат подстановки t вместо v в Kv F есть Kv F.

3.10Найдите результат подстановки константы a вместо x в формулу из задачи 3.4.

Когда мы намереваемся рассмотреть подстановки вместо переменной 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₂''. Существует, однако, одно исключение. Формула 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 тогда и только тогда, когда

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

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

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

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

" v₁ ··· v_n F,

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

Семантика

Выполнимость

Логическое следование

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

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

Дата добавления: 2018-02-28; просмотров: 680; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 345 6 Следующая ⇒

Мы поможем в написании ваших работ!