Свойства операций над высказываниями
п.1. Переместительные, сочетательные и распределительные законы алгебры высказываний
При определении конъюнкции и дизъюнкции (см. §31 данного справочника), мы указали, что конъюнкция является логическим умножением, а дизъюнкция – логическим сложением.
Ещё из курса арифметики, нам известно, что операции умножения и сложения для чисел обладают коммутативностью (переместительный закон), ассоциативностью (сочетательный закон) и дистрибутивностью (распределительный закон) (см. §2 справочника для 7 класса). Эти же законы справедливы в алгебре высказываний.
Коммутативность (переместительный закон)
A ∨ B = B ∨ A
Ассоциативность (сочетательный закон)
(A ∨ B) ∨ C = A ∨ (B ∨ C)
Коммутативность (переместительный закон)
A ∧ B = B ∧ A
Ассоциативность (сочетательный закон)
(A ∧ B) ∧ C = A ∧ (B ∧ C)
Дистрибутивность (распределительный закон)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
п.2. Законы идемпотентности
В логике высказываний идемпотентность наблюдается при повторении объектов (высказываний) и при повторных операциях с логическими 0 и 1:
A ∨ A = A, A ∨ 1 = A ∨ 1 ∨ 1 = ... 1, A ∨ 0 = A ∨ 0 ∨ 0 = ... = A
п.3. Законы поглощения
При операциях с константами 0 и 1 происходят следующие поглощения:
A ∨ 1 = 1, A ∨ 0 = A
При повторе высказываний происходят следующие поглощения:
Доказательство этих двух формул – см. пример 1 к этому параграфу.
п.4. Закон силлогизма (замыкания)
Транзитивность импликации:
Силлогизмы были впервые осмыслены и классифицированы Аристотелем.
В данной формуле представлена «первая фигура» аристотелевского силлогизма, наиболее совершенная.
Например:
Пусть A: Вася, B: студент, C: человек
Получаем рассуждение: «Вася – студент» и «Студент – человек».
Значит, «Вася – человек».
п.5. Закон контрапозиции
$$ \mathrm{ (A \rightarrow B) \rightarrow (\overline{B}\rightarrow\overline{A}) } $$Например:
Пусть A: Вася, B: студент
Получаем рассуждение: «Вася – студент»
Значит, «Если некто – не студент, то он – не Вася».
п.6. Другие законы алгебры высказываний
Эти законы нам уже встречались. Приведём их здесь ещё раз для полного списка:
Закон тождества
$$\mathrm{A = A}$$
Закон отрицания отрицания
$$\mathrm{\overline{\overline{A}} = A}$$
Закон противоречия
$$\mathrm{A \wedge\overline{A} = 0}$$
Закон исключенного третьего
$$\mathrm{A \vee\overline{A} = 1}$$
Законы де Моргана
$$\mathrm{\overline{A\wedge B}=\overline{A}\vee\overline{B}}$$ $$\mathrm{\overline{A\vee B}=\overline{A}\wedge\overline{B}}$$
п.7. Приоритет логических операций
1. При отсутствии скобок логические операции выполняются в следующей последовательности:
- Отрицание
- Конъюнкция
- Дизъюнкция
- Импликация
- Эквиваленция
2. Если без скобок последовательно записаны несколько одинаковых операций, то они выполняются последовательно слева направо.
3. Если необходимо изменить обычный порядок выполнения операций, часть формулы заключают в скобки.
п.8. Примеры
Пример 1. Докажите с помощью таблиц истинности законы поглощения
0
0
0
0
0
1
1
0
1
0
1
1
1
1
1
1
Крайний левый и крайний правый столбцы равны, значит A ∧ (A ∨ B) = A
0
0
0
0
0
1
0
0
1
0
0
1
1
1
1
1
Крайний левый и крайний правый столбцы равны, значит A ∨ (A ∧ B) = A
Что и требовалось доказать.
Пример 2. Докажите, что импликацию можно заменить дизъюнкцией:
$$ \mathrm{ (A\rightarrow B) = (\overline{A}\vee B) } $$0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
0
1
1
Столбцы совпадают. Значит, импликация и рассмотренная дизъюнкция эквивалентны.
Что и требовалось доказать.
Пример 3. Докажите, что эквиваленцию можно заменить следующей комбинацией дизъюнкций и конъюнкции: $$ \mathrm{ (A\leftrightarrow B)=(\overline{A}\vee B)\wedge (A\vee\overline{B}) } $$
\(\wedge\)
\(\mathrm{(A\vee\overline{B})}\)
0
0
1
1
1
1
1
1
0
1
0
1
1
0
0
0
1
0
0
0
0
1
1
0
1
1
1
0
1
0
1
1
Выделенные столбцы совпадают. Значит, соответствующие формулы эквивалентны.
Что и требовалось доказать.
Пример 4*. Запишите с помощью формул логики рассуждение:
«Глупец мог бы это сделать. Я не могу этого сделать. Значит, я не глупец».
Является ли данная формула логическим законом?
A – я, B – глупец, C – действие, о котором речь. $$ \mathrm{ (B\rightarrow C) \wedge (\overline{A\rightarrow C})\rightarrow (\overline{A\leftrightarrow B}) } $$
\(\wedge\)
\(\mathrm{(\overline{A\rightarrow C})}\)
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
0
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
0
0
1
0
1
1
0
1
1
1
0
1
1
1
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
1
1
1
1
0
0
1
0
1
Это – тавтология, т.е. закон логики.
