Лекция № 3. Основные вопросы, рассматриваемые на лекции

Тема: АЛГЕБРА ВЫСКАЗЫВАНИЙ

Основные вопросы, рассматриваемые на лекции:

1. Отношение равносильности формул

2. Законы алгебры высказываний

3. Дизъюнкции и конъюнкции n высказываний

Краткое содержание лекционного материала

Предположим, что в состав формул A и B входят пропозициональные переменные p ₁,…, p_n. Формулы A и B называются равносильными (A º B), если при любых истинностных значениях переменных p ₁,…, p_n формулы A и B принимают одно и тоже истинностное значение. Легко увидеть, что A º B тогда и только тогда, когда формула A Û B является тавтологией.

Отношение равносильности обладает такими же свойствами, как и отношение равенства чисел или равенства множеств: рефлексивно (A º A), симметрично (из A º B следует B º A), транзитивно (из A º B и B º A следует A º C). Имеет место правило подстановки для логических операций: например, из A º C и B º D следует A Þ B º C Þ D.

Равносильность формул – это отношение между формулами. Знаки Û (и ему подобные знаки «, º, ~) на практике применяются и для обозначения операций над высказываниями (эквивалентность A Û B), и для отношений между высказываниями (равносильность A º B), и для краткой записи последовательного выполнения отношения равносильности (в доказательствах или в решениях задач, например, при решении уравнений и систем уравнений).

Законы алгебры высказываний (или логические законы, или булевы законы) для логических связок Ø, Ú, Ù и с константами 0 и 1 напоминают законы арифметики для действий - (нахождения противоположного числа), +, × и констант (чисел) 0, 1. (Когда-то дизъюнкция и конъюнкция назывались логическим сложением и логическим).

Следующие булевы законы аналогичны арифметическим законам:

P Ú Q º Q Ú P, P Ù Q º Q Ù P (законы коммутативности);

(P Ú Q)Ú R º Q Ú(P Ú R), (P Ù Q)Ù R º Q Ù(P Ù R) (законы ассоциативности);

P Ù(Q Ú R)º(P Ú Q)Ù(P Ú R) (закон дистрибутивности Ù относительно Ú);

ØØ P º P (закон двойного отрицания);

P Ú0º P; P Ù1º P; P Ù0º0 (свойства констант 0 и 1).

А следующие булевы законы не аналогичны арифметическим законам:

P Ú P º P, P Ù P º P (законы идемпотентности);

P Ú(Q Ù R)º(P Ú Q)Ù(P Ú R) (закон дистрибутивности Ú относительно Ù)

(P Ù Q)Ú Q º Q, (P Ú Q)Ù Q º Q (законы поглощения);

Ø(P Ú Q)ºØ P ÙØ Q, Ø(P Ù Q)ºØ P ÚØ Q (законы де Моргана);

P ÚØ P º1 (законы исключенного третьего);

P ÙØ P º0 (закон о противоречии); P Ú1º1.

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

Дизъюнкцией A ₁Ú…Ú A_n от n высказываний A ₁, …, A_n называется новое высказывание, истинное, если хотя бы одно из A ₁, …, A_n истинно, и ложное, если все A ₁, …, A_n ложны. Конъюнкцией A ₁Ù…Ù A_n от n высказываний A ₁, …, A_n называется новое высказывание, истинное, если все A ₁, …, A_n истинны, и ложное, если хотя бы одно из A ₁, …, A_n ложно.

Законы дистрибутивности и де Моргана обобщаются и для n -местных операций дизъюнкции и конъюнкции:

B Ù(A ₁Ú…Ú A_n)º(B Ù A ₁)Ú…Ú(B Ù A_n);

B Ú(A ₁Ù…Ù A_n)º(B Ú A ₁)Ù…Ù(B Ú A_n);

Ø(A ₁Ú…Ú A_n)º(Ø A ₁)Ú…Ú(Ø A_n);

Ø(A ₁Ù…Ù A_n)º(Ø A ₁)Ù…Ù(Ø A_n).