§ 3. Элементы исчисления высказываний Язык логики высказываний

Алфавит – содержит все символы языка;

Синтаксис - определяет, каким образом из символов формируются высказывания;

Семантика – определяет правила интерпретации высказываний путем приписывания значений символам алфавита.

Алфавит языка логики высказываний состоит:

1) из пропозициональных символов: ;

2) из логических связок: ;

3) из запятой и скобок: , ().

Синтаксис

Выражение - произвольная последовательность символов, принадлежащих алфавиту языка

Определение 1. (высказывания) или формулы.

1. Пропозициональные символы являются высказываниями и называются атомами.

2. Если  и  — высказывания, то выражения (), (), (), (), () – также являются высказываниями (их называют составными высказываниями).

3. Выражения, построенные в соответствии с пунктами 1 и 2, и только они являются высказываниями.

Пример

1. Выражение (((АB))C) является высказыванием.

2. Следующие выражения не являются высказываниями:



A

(AB

Приоритет логических связок (по убыванию слева-направо): ,  , , 

Семантика

t, f – истинностные значения. Семантика описывает способы определения истинностных значений высказываний.

Определение 2. Означиванием назовем произвольную функцию F: Q  {t, f}

где Q — множество атомов языка.

Булева алгебра

Пусть  ,  ,  ,  ,  - алгебраические операции, определенные над значениями {t,f}. Результат выполнения операций определяется таблицами истинности:

					
t	t	t	t	t	t
t	f	t	f	f	f
f	t	t	f	t	f
f	f	f	f	t	t

Структура ({t,f}, , , ) называется двузначной булевой алгеброй.

Определение 3. (Истинностного означивания) Пусть S — множество высказываний. Истинностным означиванием называется функция

V: S  {t,f}

такая, что для произвольных ,   S верно:

а) если  - атом, то V(){t, f}

б) V() = V()

в) V() = V()V()

г) V() = V()V()

д) V() = V()V()

е) V() = V()V()

Т.о. означивание приписывает истинностное значение (t или f) атомам языка. Истинностное означивание является расширением означивания на множество высказываний языка.

Классификация высказываний по истинностным значениям

Определение. Высказывание  называется логически истинным или тавтологией ( ), если для каждого истинностного означивания V верно, что V()=t.

Определение. Высказывание  не является тавтологией ( ), если существует истинностное означивание V, такое, что V() = f.

Определение. Высказывание  называется выполнимым или подтверждаемым, если существует истинностное означивание V: V() = t.

Определение. Высказывание  называется логически ложным (невыполнимым или противоречием), если для любого истинностного означивания V верно, что V() = f.

Определение. Высказывания  и  называются логически эквивалентными (), если для любого истинностного означивания V верно, что V() = V().

Следствия.

( )   - является противоречием

( )   - выполнимо (обратное неверно)

Таблицы истинности (Использование таблиц истинности для классификации высказываний)

Пример. Классифицировать следующее высказывание: ((AB)A)A

A	B	(AB)	(AB)A	((AB)A)A
t	t	t	t	t
t	f	f	t	t
f	t	t	f	t
f	f	t	f	t

Ответ. Высказывание ((AB)A)A является тавтологией

Задание 1. Классифицировать следующие высказывания

(A  B)(A  B) (A  B)(A  B) (A)  A (AB)  (B  A) (A(BC))  ((AB) C) (BC)((AB)(AC))

(AB)((BC)(AC)) (AB)  (A  B) (AB)  (A  B) (AB)  (AB)(BA) (AB)  (A  B) (AB)  (A  B)

Классификация множеств высказываний по истинностным значениям

Определение. S – множество высказываний. Высказывание  называются логическим следствием S (S ), если для любого истинностного означивания V такого, что S и V()=t, верно, что V() = t.

Определение. Множество высказываний S непротиворечиво (подтверждаемо, выполнимо), если существует истинностное означивание V такое, что S V()=t.

Определение. Множество высказываний S противоречиво (неподтверждаемо, невыполнимо), если для любого истинностного означивания V существует S такое, что V()=f.

Полнота множеств логических связок и нормальные формы

Определение. Множество логических связок Q называется полным, если для каждого высказывания логики высказываний существует логически эквивалентное ему высказывание, содержащее только связки из Q.

Теорема. Множество {, , } является полным.

Следствие. Для любого высказывания можно построить логически эквивалентное ему высказывание в дизъюнктивной или конъюнктивной нормальной форме (ДНФ или КНФ).

Дизъюнктивная нормальная форма. Пусть F — высказывание, содержащее атомы A₁, … , A_n. В общем случае ДНФ формулы F имеет вид

ДНФ(F): ,

где – атом или отрицание атома F, причем в конъюнктивную компоненту входит либо атом либо его отрицание.