Нормальные формы
Определение 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 выполнима.
Эта терминология применима также к множествам формул: множество формул выполнимо, если существует интерпретация, при которой истинны все формулы .
2.21 Пусть – множество литералов. Покажем, что выполнимо тогда и только тогда, когда не существует атома A, для которого и A и ¬A принадлежат .
Для любого атома A литералы A, ¬A называются дополнительными друг к другу. Так, утверждение последней задачи может быть выражено следующим образом: множество литералов выполнимо тогда и только тогда, когда оно не содержит дополнительных пар.
Логическое следование
Мы сейчас определим в контексте логики высказываний, когда формула F ``следует'' из множества формул . Идея следования центральна в логике: в любой формальной аксиоматической теории ``теорема'' – это формула, которая следует из аксиом.
Определение 13 (Логическое следование). Формула F (логически) следует из множества формул (или множество формул влечёт формулуF, символически, |= F ), если для каждой интерпретации, при которой все формулы истинны, формула F также истинна.*
Про формулы, которые логически следуют из будем говорить ``логическое следствие ''.
2.22 Предполагая, что p и q – атомы, определите
следует ли q из (множества состоящего из) p и p q,
следует ли ¬q из ¬p и p q.
2.23 влечёт F тогда и только тогда, когда { ¬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, G1,...,Gn (n 1) : F следует из { G1,..., Gn } тогда и только тогда, когда (G1 & ··· & Gn) F – тавтология.