Покажите, что для атомов p и q

каждая из формул p & q, p Й q эквивалентна формуле, не содержащей связок, кроме Ъ и ,
каждая из формул p Ъ q, p Й q эквивалентна формуле, не содержащей связок, кроме & и ,
каждая из формул p & q, p Ъ q эквивалентна формуле, не содержащей связок, кроме Й и .

2.16 Любая формула эквивалентна

формуле, не содержащей связок, кроме Ъ и ,

формуле, не содержащей связок, кроме & и ,

формуле, не содержащей связок, кроме Й и .

В сочетании с результатом задачи 2.14 этот факт показывает, что множества { Ъ, }, { &, } и { Й, } – ``полные'' множества связок – они достаточны для выражения любой таблицы истинности. С другой стороны, множество { Ъ, &, Й } не ``полное'':

2.17 Предполагая, что p – атом, покажите что любая формула, эквивалентная p, содержит по крайней мере одно отрицание.

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

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

Элементарная дизъюнкция – это формула вида L₁ Ъ ··· Ъ L_n (n і 1), где L₁,...,L_n – литералы. Будем говорить. что формула находится в конъюнктивной нормальной форме, если она имеет вид D₁ & ··· & D_m (m і 1), где D₁, ..., 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₁,...,G_n (n і 1) : F следует из { G₁,..., G_n } тогда и только тогда, когда (G₁ & ··· & G_n) Й F – тавтология.

Пропозициональный вывод

Существует другое определение следования, которое выглядит совершенно отличающимся от данного выше, но в действительности эквивалентное ему. В соответствие с этим определением, G влечёт F, если F может быть выведено из G с использованием определенного набора ``правил вывода''. Первое определение, основанное на интерпретации, – ``семантическое'', второе, основанное на понятии вывода – ``синтаксическое'' или ``дедуктивное''.

Выводы в логике высказываний – наш основной объект изучения до конца данной части.

Вывод строятся из конструкций, которые называются ``секвенциями''.

Определение 15 (Секвенция). Секвенция – это выражение вида G |– F (``F при посылках G'') или G |– ^ (``посылки G противоречивы''), где F – формула и G – конечное множество формул.

Мы определим, какие секвенции рассматриваются ``начальными'', и опишем несколько ``правил вывода'' для порождения новых секвенций из секвенций, порождённых ранее. Начальные секвенции называются аксиомами.

Определение 16 (Аксиомы). Аксиомы в исчислении высказываний имеют вид

{ F } |– F.

<8 9 101112 13 14 >

Дата добавления: 2015-10-05; просмотров: 708;