- •Раздел 4. Математическая логика и формальные системы.
- •4.1. Введение в формальные системы
- •4.2. Принципы построения формальных теорий.
- •4.3. Исчисление высказываний. Аксиомы и правила вывода.
- •2) Правило заключения (Modus Ponens). Если u и u β – выводимые формулы, то β выводима:
- •4.4. Исчисления предикатов и теории первого порядка.
- •3. Аксиомы исчисления предикатов делятся на две группы:
- •1) Аксиомы исчисления высказываний ( можно взять любую из систем или );
- •2) Две следующие предикатные аксиомы:
- •4.Правила вывода:
- •3) Правило - введения:
- •4.5.Предмет математической логики
- •4.6. Аксиоматический метод
- •1.4 Такое число m единственно.
- •1.20 Если k ј m и m ј n, то k ј n.
- •4.7. Логика высказываний
- •2.1 Укажите два примера множества строк: одно замкнутое, другое не замкнутое относительно правил построения.
- •2.2 Множество формул замкнуто относительно правил построения.
- •2.3 Является ли формулой ¬(p & q)?
- •2.4 Является ли формулой (p)?
- •2.10 Найдите формулу f такую, что (3) – единственная интерпретация, при которой f истинна.
- •2.11 Для любых формул f1,...,Fn (n і 1) и любой интерпретации I
- •2.12 Сформулируйте и докажите подобный факт для дизъюнкции f1 ъ ··· ъ Fn.
- •2.13 Для любой интерпретации I существует формула f такая, что I – единственная интерпретация, при которой f истинна.
- •2.15 Покажите, что для атомов p и q
- •2.22 Предполагая, что p и q – атомы, определите
- •2.23 G влечёт f тогда и только тогда, когда g и { ¬f } не выполнимо.
- •2.24 Определить, какие из следующих формул являются тавтологиями: (p й q) ъ (q й p), ((p й q) й p) й p, ((p є q) є r) є (p є (q є r)).
- •2.25 Для любых формул f, g1,...,Gn (n і 1) : f следует из { g1,..., Gn } тогда и только тогда, когда (g1 & ··· & Gn) й f – тавтология.
- •2.26 Найдите вывод q & p из p & q.
- •2.29 Найдите вывод p й r из p й q и q й r.
- •2.43 Правило удаления отрицания корректно.
- •2.44 Правило введения отрицания корректно.
- •2.45 Правило противоречия корректно.
- •2.52 Оба правила введения дизъюнкции корректны.
- •2.53 Правило удаления дизъюнкции корректно.
- •3.1 Является ли " X формулой?
- •3.2 Если формула содержит квантор, тогда она содержит переменную. Верно или нет ?
- •3.3 Если формула содержит квантор, тогда она содержит скобки. Верно или нет ?
- •3.4 Найдите свободные переменные и связанные переменные формулы
- •3.5 Все простые числа больше чем X.
- •3.10 Найдите результат подстановки константы a вместо X в формулу из задачи 3.4.
- •3.11 Если V не является свободной переменной f(V), тогда f(t) равно f(V).
- •V не является свободной переменной формулы Kw f.
- •3.12 Терм, не содержащий ни одной связанной переменной формулы f, является подстановочным в f для любой переменной.
- •3.23 Каждый терм содержит объектную константу или объектную переменную. Верно или нет ?
- •3.38 Модель арифметики первого порядка (7) стандартна.
- •3.39 G непротиворечива.
- •3.40 Арифметика первого порядка имеет нестандартную модель.
3.1 Является ли " X формулой?
Как и в логике высказываний можно доказать, что множество формул замкнуто относительно правил построения. Теоремы возможности и единственности разбора подобны соответствующим теоремам для пропозициональных формул.
В случае предикатных формул доказательство по структурной индукции имеет следующий вид. Для данного свойства формул мы проверяем, что
каждая атомарная формула обладает этим свойством,
для любой формулы F, обладающей этим свойством, ¬F также обладает этим свойством,
для любых формул F, G, обладающих этим свойством, и любой бинарной связки Д, (F Д G) также обладает этим свойством,
для любого квантора K, любой переменной v и любой формулы F, обладающей этим свойством, Kv F также обладает этим свойством.
Тогда это свойство выполняется для всех формул.
3.2 Если формула содержит квантор, тогда она содержит переменную. Верно или нет ?
3.3 Если формула содержит квантор, тогда она содержит скобки. Верно или нет ?
При записи предикатных формул мы будем опускать некоторые скобки и применять другие сокращения, введённые в части 2. Строку вида
" v1 ··· " vn (n і 0)
будем писать как " v1 ··· vn, и подобным образом для квантора существования.
Свободные и связанные переменные
Множество свободных переменных формулы 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.7 x равно 2.
3.8 x равно 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.