Покажите, что для атомов 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''.
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, G1,...,Gn (n і 1) : F следует из { G1,..., Gn } тогда и только тогда, когда (G1 & ··· & Gn) Й F – тавтология.
Пропозициональный вывод
Существует другое определение следования, которое выглядит совершенно отличающимся от данного выше, но в действительности эквивалентное ему. В соответствие с этим определением, G влечёт F, если F может быть выведено из G с использованием определенного набора ``правил вывода''. Первое определение, основанное на интерпретации, – ``семантическое'', второе, основанное на понятии вывода – ``синтаксическое'' или ``дедуктивное''.
Выводы в логике высказываний – наш основной объект изучения до конца данной части.
Вывод строятся из конструкций, которые называются ``секвенциями''.
Определение 15 (Секвенция). Секвенция – это выражение вида G |– F (``F при посылках G'') или G |– ^ (``посылки G противоречивы''), где F – формула и G – конечное множество формул.
Мы определим, какие секвенции рассматриваются ``начальными'', и опишем несколько ``правил вывода'' для порождения новых секвенций из секвенций, порождённых ранее. Начальные секвенции называются аксиомами.
Определение 16 (Аксиомы). Аксиомы в исчислении высказываний имеют вид
{ F } |– F.
Дата добавления: 2015-10-05; просмотров: 751;