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

Объектный язык и метаязык

Сначала несколько общих замечаний. В логике важно различать два языка: тот, который является объектом нашего изучения, и тот, который мы используем, чтобы говорить об этом объекте. Первый называется объектным языком, второй – метаязыком. В нашем изложении логики высказываний объектный язык – это формальный язык пропозициональных формул, а метаязык – обычный неформальный язык математики – смесь русского и математических обозначений.

Пропозициональные формулы будут определены как конечные последовательности символов, взятых из определенного алфавита. Можно развить теорию конечных последовательностей на строго аксиоматической основе, но мы не будем здесь делать это. В доказательствах метатеорем мы будем свободны использовать любые хорошо известные свойства натуральных чисел которые нам могут потребоваться, не доказывая их на основе аксиом арифметики (из части 1).

Пропозициональные формулы

Пропозициональная сигнатура – это множество символов, называемых атомами. Символы (отрицание), & (конъюнкция), Ú(дизъюнкция) и É (импликация) называются пропозициональными связками; – унарная связка, а другие – бинарные.

Возьмём непустую пропозициональную сигнатуру s, которая не содержит ни пропозициональных связок, ни скобки (,). Алфавит пропозициональной логики состоит из атомов сигнатуры s, пропозициональных связок и скобок. Под строкой мы понимаем конечную последовательность (строку) символов в этом алфавите.

Чтобы определить понятие пропозициональной формулы, нам требуется следующее вспомогательное определение.

Определение 7. Множество X строк замкнуто относительно правил построения (для логики высказываний), если

• каждый атом принадлежит X,
• для любой строки F, если F принадлежит X, то F тоже принадлежит,
• для любых строк F, G и любой бинарной связки Ä, если F и G принадлежат X, то также принадлежит (F Ä G).

2.1 Укажите два примера множества строк: одно замкнутое, другое не замкнутое относительно правил построения.

Определение 8 (Формула). Строка F называется пропозициональной формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

2.2 Множество формул замкнуто относительно правил построения.

Определение формулы показывает, что множество формул является наименьшим множеством строк, замкнутых относительно правил построения; то есть, любое другое такое множество включает в себя множество формул.

В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура – это { p, q }.

2.3 Является ли формулой (p & q)?

2.4 Является ли формулой (p)?

Следующие два раздела обосновывают корректность понятий, вводимых ниже.

Доказательство свойств формул по индукции

 

Разбор формул

 

Семантика

В этом и следующем разделах мы работаем с булевыми функциями, которые используются в интерпретациях формул логики высказываний.^*

Определение 10 (Интерпретация). Символы л,и (``ложь'', ``истина'') называются истиностными значениями. Интерпретация пропозициональной сигнатуры s есть функция из s в {л,и}.

Если s конечна, тогда интерпретация может быть определена таблицей её значений, например:

p q л и

(3)

Семантика логики высказываний, которую мы собираемся ввести, определяет какие истиностные значения назначены формуле F интерпретацией I.

Прежде всего нам надо связать функцию с каждой пропозициональной связкой – функцию из {л,и} в {л,и} с унарной связкой и функцию из {л,и}´ {л,и} в {л,и} с каждой бинарной связкой. Функции определяются следующими таблицами:

x (x) л и и л

x y &(x, y) Ú(x, y) É(x, y) л л л л и л и л и и и л л и л и и и и и

^*

Для любой формулы F и любой интерпретации I истиностное значение F^I, назначенное формуле F интерпретацией I, определяется как значение суперпозиции соответствующих булевых функций, а именно, следующим образом:

• F^I = I (F) если F – атом,
• (F) ^I = (F^I),
• (F Ä G) ^I = Ä(F^I,G^I) для каждой бинарной связки Ä.

Заметим, что это определение рекурсивно: (F) ^I определяется через F^I и (F Ä G) ^I – через F^I и G^I.

Если F^I = и, мы говорим, что формула F истинна при интерпретации I (символически I |= F).

2.10 Найдите формулу F такую, что (3) – единственная интерпретация, при которой F истинна.

Если рассматриваемая сигнатура конечна, тогда множество интерпретаций тоже конечно, и значения F^I для всех интерпретаций можно представить в виде конечной таблицы. Эта таблица называется таблицей истинности формулы F. Например, предыдущая задача может быть сформулирована следующим образом: найти формулу, таблицей истинности которой является

p	q
л	л	л
л	и	и
и	л	л
и	и	л

2.11 Для любых формул F 1 ,...,F_n (n ³ 1) и любой интерпретации I

(F 1 & ··· &F_n) ^I = и тогда и только тогда, когда F^I 1 = ··· = F^I_n = и.

2.12 Сформулируйте и докажите подобный факт для дизъюнкции F 1 Ú ··· Ú F_n.

В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура конечна: s = { p 1 ,..., p_n }.

2.13 Для любой интерпретации I существует формула F такая, что I – единственная интерпретация, при которой F истинна.

2.14 Для любой функции a из интерпретаций в истинстные значения существует формула F такая, что для всех интерпретаций I: F^I = a(I).

Другими словами, любая таблица истинности может быть представлена пропозициональной формулой. В этом смысле множество пропозициональных связок, которое мы ввели ``полно''.

Нормальные формы

Определение 11 (Эквивалентность). Формула F эквивалентна формуле G, если F^I = G^I для любой интерпретации 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, содержит по крайней мере одно отрицание. см. Указания

Литерал – это атом или отрицание атома. Элементарная конъюнкция – это формула вида L 1 & ··· &L_n (n ³ 1), где L 1 ,...,L_n – литералы. Будем говорить, что формула находится в дизъюнктивной нормальной форме, если она имеет вид C 1 Ú ··· Ú C_m (m ³ 1), где C 1 ,..., C_m – элементарные конъюнкции.

2.18 Любая формула эквивалентна некоторой формуле в дизъюнктивной нормальной форме.

Элементарная дизъюнкция – это формула вида L 1 Ú ··· Ú L_n (n ³ 1), где L 1 ,...,L_n – литералы. Будем говорить.что формула находится в конъюнктивной нормальной форме, если она имеет вид D 1 & ··· &D_m (m ³ 1), где D 1 ,..., D_m – элементарные дизъюнкции.

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''.

2.22 Предполагая, что p и q – атомы, определите

• следует ли q из (множества состоящего из) p и p É q,
• следует ли q из p и p É q.

2.23 G влечёт F тогда и только тогда, когда G È { F } не выполнимо.

Определение 14 (Тавтология). Формула F называется тавтологией, или тождественно истинной формулой, если F истинно при любой интерпретации.^*

Понятие тавтологии ``двойственно'' понятию выполнимой формулы: F – тавтология тогда и только тогда, когда F не выполнима. Определение эквивалентных формул, данное выше, может быть переформулировано следующим образом: F эквивалентна G, если F º G – тавтология.

2.24 Определить, какие из следующих формул являются тавтологиями: (p É q) Ú (q É p), ((p É q) É p) É p, ((p º q) º r) º (p º (q º r)).

2.25 Для любых формул F, G 1 ,...,G_n (n ³ 1): F следует из { G 1 ,..., G_n } тогда и только тогда, когда (G 1 & ··· &G_n) É F – тавтология.