- •Раздел 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) Правило заключения (Modus Ponens). Если u и u β – выводимые формулы, то β выводима:
u, u β
u: ——— .
β
В этом описании исчисления высказываний аксиомы являются формулами исчисления (соответствующими определению формулы); формулы же использованные в правилах вывода (u, u β и т. д.), это ”метаформулы“ или схемы формул. Схема формул, например u β обозначает множество всех тех формул исчисления, которые получаются, если её метапеременные заменить формулами исчисления: скажем, если u заменить на А, а β – на A&B и, то из схемы формул u β получим формулу АA&B.
4.4. Исчисления предикатов и теории первого порядка.
Аксиомы и правила вывода.
1.Алфавит исчисления предикатов состоит из предметных переменных x1, x2, … , предметных констант a1, a2, … , предикатных букв P11, P21, P31 , … ,Pkj и функциональных букв f11, f11, … , fkj, а также знаков логических связок , , ¯, , кванторов , и скобок (, ).
Верхние индексы предикатных и функциональных букв указывают число аргументов, их нижние индексы служат для обычной нумерации букв. Переменные высказывания в исчисление предикатов вводятся либо как о – местные предикаты Р10, Р20, . . . , то есть как предикаты без предметных переменных.
2.Формулы. Понятие формулы определяется в два этапа.
1)Термы:
а) предметные переменные и константы являются термами;
б) если fn – функциональная буква, а t1, ... , tn – термы, то fn( t1, ... ,tn) –
терм.
2)Формулы :
а) если Рn – предикатная буква, а t1, . . . , tn – термы, то Рn( t1, . . . , tn) – формула; все вхождения предметных переменных в формулу вида Рn ( t1, . . . , tn) называются свободными;
б) если F1, F2 - формулы, то формулами являются ┐F1, (F1& F2), (F1 F2), ( F1 → F2); все вхождения переменных, свободные в F1, F2 являются свободными в указанных четырех видах формул;
в) если F(х) –формула, содержащая свободные вхождения переменной х, то xF(х) и хF(х) –формулы; в этих формулах все вхождения переменной х называются связанными; вхождения остальных переменных в F остаются свободными.
3. Аксиомы исчисления предикатов делятся на две группы:
1) Аксиомы исчисления высказываний ( можно взять любую из систем или );
2) Две следующие предикатные аксиомы:
Р1. х F ( х ) F ( у );
Р2. F ( у ) х F ( х ).
В этих аксиомах F (х) - любая формула, содержащая свободные вхождения х, причем ни одно из них не находится в области действия квантора по у; формула F ( у ) получена из F ( х ) заменой всех свободных вхождений х на у.
Чтобы пояснить существенность требования к вхождениям х в F, рассмотрим в качестве F ( х ) формулу у Р ( у, х ), где это требование нарушено: свободное вхождение х находится в области действия у. Подстановка этой формулы в аксиому Р1 дает формулу х у Р ( у, х ) у Р ( у, у ). Если ее проинтерпретировать на множестве N натуральных чисел с предикатом Р „ быть больше“, то получим высказывание: „ если для всякого х найдется у больший, чем х, то найдется у, больший самого себя. “ Посылка этой импликации истинна на N, а ее заключение ложно, и, следовательно, само высказывание ложно.