- •Раздел 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 Арифметика первого порядка имеет нестандартную модель.
2.26 Найдите вывод q & p из p & q.
В двух следующих задачах выведите данную формулу из пустого множества посылок.
2.27 (p & p) Й p.
2.28 (p & p) є p.
Правило удаления посылки
Мы построили несколько примеров простых выводов. Однако, используя только правила для конъюнкции и импликации, мы не сможем построить вывод формулы p & q из множества посылок {p, q}. Действительно, формулу {p, q} |– p & q мы можем получить с помощью правила (В&) из формулу {p, q} |– p и формулу {p, q} |– q. Однако ``очевидные'' формулы {p, q} |– p и {p, q} |– q мы не сможем вывести. У нас нет правила, позволяющего выводить формулу из некоторого множества посылок, если она выводится из более узкого множества. Это правило вывода назовём правилом удаления посылки.
|
G И {G} |– F |
(УП) |
|
|
G |– F |
Пример вывода. Мы приводим вывод p Й ((p Й q) Й (p & q)) из пустого множества посылок:
|
|
|
{p} |– p |
|
|
|
{p} |– p |
|
{p Й q} |– p Й q | |||
|
|
(УП) |
|
(УП) |
| |||||||
|
|
|
{p,p Й q} |– p |
|
{p,p Й q} |– p Й q | |||||||
(УП) |
|
(УЙ) |
| |||||||||
|
{p,p Й q} |– p |
|
{p,p Й q} |– q | |||||||||
(В&) |
| |||||||||||
|
|
|
|
|
{p,p Й q} |– p & q |
| ||||||
|
|
(ВЙ) |
| |||||||||
|
|
|
{p} |– (p Й q) Й (p & q) | |||||||||
|
(ВЙ) |
| ||||||||||
|
|
Ж |– p Й ((p Й q) Й (p & q)) |
2.29 Найдите вывод p й r из p й q и q й r.
2.30 Найдите вывод r из p & q и p Й (q Й r).
В каждой из следующих задач выведите данную формулу из пустого множества посылок.
2.31 p Й (q Й p).
2.32 p Й ((p & q) є q).
2.33 ((p & q) Й r) є (p Й (q Й r)).
Корректность правил вывода
Определение 19 (Истинность секвенций). Секвенция G |– F тождественно истинна, если G влечёт F.
Определение 20 (Корректность правил вывода). Правило вывода корректно, если для каждого примера этого правила посылки которого являются тождественно истинными, его заключение также тождественно истинно.
2.34 Правило удаления посылки корректно.
2.35 Оба правила удаления конъюнкции корректны.
2.36 Правило введения конъюнкции корректно.
2.37 Правило удаления импликации корректно.
2.38 Правило введения импликации корректно.
Правила для отрицания и правила противоречия
Следующие четыре правила вывода – правила введения и удаления отрицания ``правило сведения к противоречию'' и ``правило противоречия''.
|
|
G И { F } |– ^ |
|
|
G И { ¬F } |– ^ | |
(В¬) |
|
|
(У¬) |
| ||
|
G |– ¬F |
|
G |– F | |||
|
|
G |– F G |– ¬F |
|
|
G |– ^ |
|
(В^) |
|
|
(У^) |
|
| |
|
G |– ^ |
|
G |– F |
|
Выведите секвенции:
2.39 {¬¬p} |– p.
2.40 {p} |– ¬¬p.
В каждой из следующих задач выведите данную формулу из пустого множества посылок.
2.41 ¬(p & ¬p).
2.42 (p & ¬p) Й q.
Определение 21 (Истинность секвенций). Секвенция G |– ^ тождественно истинна, если G не выполнима.