- •Раздел 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.11 Для любых формул f1,...,Fn (n і 1) и любой интерпретации I
(F1 & ··· & Fn)I = и тогда и только тогда, когда FI1 = ··· = FIn = и.
2.12 Сформулируйте и докажите подобный факт для дизъюнкции f1 ъ ··· ъ Fn.
В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура конечна: s = { p1, ..., pn}.
2.13 Для любой интерпретации I существует формула f такая, что I – единственная интерпретация, при которой f истинна.
2.14 Для любой функции a из интерпретаций в истинные значения существует формула F такая, что для всех интерпретаций I: FI = a(I).
Другими словами, любая таблица истинности может быть представлена пропозициональной формулой. В этом смысле множество пропозициональных связок, которое мы ввели ``полно''.
Нормальные формы
Определение 11 (Эквивалентность). Формула F эквивалентна формуле G, если FI = GI для любой интерпретации I.
В задачах 2.16, 2.18 и 2.20 мы вводим несколько ``нормальных форм'' таких, что любая пропозициональная формула может быть эквивалентно трансформирована в любую из этих форм.
2.15 Покажите, что для атомов p и q
каждая из формул p & q, p Й q эквивалентна формуле, не содержащей связок, кроме Ъ и ¬,
каждая из формул p Ъ q, p Й q эквивалентна формуле, не содержащей связок, кроме & и ¬,
каждая из формул p & q, p Ъ q эквивалентна формуле, не содержащей связок, кроме Й и ¬.
2.16 Любая формула эквивалентна
формуле, не содержащей связок, кроме Ъ и ¬,
формуле, не содержащей связок, кроме & и ¬,
формуле, не содержащей связок, кроме Й и ¬.
В сочетании с результатом задачи 2.14 этот факт показывает, что множества { Ъ, ¬ }, { &, ¬ } и { Й, ¬ } – ``полные'' множества связок – они достаточны для выражения любой таблицы истинности. С другой стороны, множество { Ъ, &, Й } не ``полное'':
2.17 Предполагая, что p – атом, покажите что любая формула, эквивалентная ¬p, содержит по крайней мере одно отрицание.
Литерал – это атом или отрицание атома. Элементарная конъюнкция – это формула вида L1& ··· & Ln (n і 1), где L1,...,Ln – литералы. Будем говорить, что формула находится в дизъюнктивной нормальной форме, если она имеет вид C1 Ъ ··· Ъ Cm (m і 1), где C1, ..., Cm – элементарные конъюнкции.
2.18 Любая формула эквивалентна некоторой формуле в дизъюнктивной нормальной форме.
Элементарная дизъюнкция – это формула вида L1 Ъ ··· Ъ Ln (n і 1), где L1,...,Ln – литералы. Будем говорить. что формула находится в конъюнктивной нормальной форме, если она имеет вид D1 & ··· & Dm (m і 1), где D1, ..., Dm – элементарные дизъюнкции.
2.19 Пусть F – формула в дизъюнктивной нормальной форме. Покажите, что ¬F эквивалентно некоторой формуле в конъюнктивной нормальной форме.
2.20 Любая формула эквивалентна некоторой формуле в конъюнктивной нормальной форме.
Выполнимость
Определение 12 (Выполнимость). Если существует интерпретация, при которой формула F истинна, мы говорим, что F выполнима.
Эта терминология применима также к множествам формул: множество G формул выполнимо, если существует интерпретация, при которой истинны все формулы G.
2.21 Пусть G – множество литералов. Покажем, что G выполнимо тогда и только тогда, когда не существует атома A, для которого и A и ¬A принадлежат G.
Для любого атома A литералы A, ¬A называются дополнительными друг к другу. Так, утверждение последней задачи может быть выражено следующим образом: множество литералов выполнимо тогда и только тогда, когда оно не содержит дополнительных пар.
Логическое следование
Мы сейчас определим в контексте логики высказываний, когда формула F ``следует'' из множества формул G. Идея следования центральна в логике: в любой формальной аксиоматической теории ``теорема'' – это формула, которая следует из аксиом.
Определение 13 (Логическое следование). Формула F (логически) следует из множества формул G (или множество формул G влечёт формулу F, символически, G |= F ), если для каждой интерпретации, при которой все формулы G истинны, формула F также истинна. Про формулы, которые логически следуют из G будем говорить ``логическое следствие G''.