3. Основные законы математической логики.
В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.
Закон двойного отрицания:
не (не А) = A.
Двойное отрицание исключает отрицание.
Переместительный (коммутативный) закон:
- для логического сложения:
А v B = B v A;
- для логического умножения:
A & B = B & A.
Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.
Сочетательный (ассоциативный) закон:
- для логического сложения:
(A v B) v C = A v (B v C);
- для логического умножения:
(A & B) & C = A & (B & C).
При одинаковых знаках скобки можно ставить произвольно или вообще опускать.
Распределительный (дистрибутивный) закон:
- для логического сложения:
(A
B)
& C = (A & C)
(B
& C);
- для логического умножения:
(A & B) v C = (A v C) & (B v C).
Определяет правило выноса общего высказывания за скобку.
Закон общей инверсии (законы де Моргана):
- для логического сложения:
;
- для логического умножения:
.
Закон идемпотентности ( от латинских слов idem - тот же самый и potens -сильный; дословно - равносильный):
- для логического сложения:
A v A = A;
- для логического умножения:
A & A = A.
Закон означает отсутствие показателей степени.
Законы исключения констант:
- для логического сложения:
A v 1 = 1, A v 0 = A;
- для логического умножения:
A & 1 = A, A & 0 = 0.
Закон противоречия:
A & (не A)= 0.
Невозможно, чтобы противоречащие высказывания были одновременно истинными.
Закон исключения третьего:
A v (не A) = 1.
Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе - ложно, третьего не дано.
Закон поглощения:
- для логического сложения:
A v (A & B) = A;
- для логического умножения:
A & (A v B) = A.
Закон исключения (склеивания):
- для логического сложения:
(A & B) v ( & B) = B;
- для логического умножения:
(A v B) & (v B) = B.
Закон контрапозиции (правило перевертывания):
(A
B)
= (B
A).
Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.
Пример.
Упростить
логическое выражение:
Заключение
Стоит отметить, что на практике множество элементарных логических операций является обязательной частью набора инструкций всех современных микропроцессоров и соответственно входит в языки программирования. Это является одним из важнейших практических приложений методов математической логики, изучаемых в современных учебниках информатики.
Контрольные вопросы
1. Предмет изучения математической логики.
2. Понятия высказывания, его значений.
3. Содержание операций над высказываниями. Таблицы истинности.
4. Понятие логического выражения (составного высказывания). Примеры.
5. Основные законы математической логики. Примеры.