Интернет-энциклопедия по школьным предметам от Maximum Education. Учебник поможет решить домашнее задание, подготовиться к контрольной и вспомнить прошлые темы.
Законы алгебры логики
В данном теоретическом блоке разобраны основные преобразования, правила математической логики.
| Формула | Описание |
|---|---|
| A B = –A \/ B | Разложение импликации |
| A ≡ B = (A /\ B) \/ (–A /\ –B) | Разложение эквиваленции |
| A ≡ B = (–A \/ B) /\ (A \/ –B) | |
| – (A /\ B) = – A \/ –B | Законы Де-Моргана |
| – (A \/ B) = – A /\ –B | |
| 0 /\ A = 0 | Правила 0 |
| 0 \/ A = A | |
| 1 /\ A = A | Правила 1 |
| 1 \/ A = 1 | |
| A /\ A = A | Тавтология |
| A \/ A = A | |
| A \/ –A = 1 | Свойства инверсии |
| A /\ –A = 0 | |
| – (–A) = A | |
| A \/ B = B \/ A | Коммутативность |
| A /\ B = B /\ A | |
| A \/ (B \/ C) = (A \/ B) \/ C | Ассоциативность |
| A /\ (B /\ C) = (A /\ B) /\ C | |
| A /\ (B \/ C) = (A /\ B) \/ (A /\ C) | Дистрибутивность |
| A \/ (B /\ C) = (A \/ B) /\ (A \/ C) | |
| A \/ (A /\ B) = A | Закон поглощения |
| A /\ (A \/ B) = A | |
| A ≡ –B = –(A ≡ B) | Работа с эквиваленцией |
| –(A ≡ B) = C A ≡ B = –C |
Ниже рассмотрим подробнее некоторые из законов и разберём как доказывать равносильностьь выражений в булевой алгебре.
Формулы де-Моргана. Два главных выражения
Формулами де-Моргана называются две формулы, которые выглядят следующим образом:
¬(A /\ B) = ¬A \/ ¬B и ¬(A \/ B) = ¬A /\ ¬B
Эти выражения справедливы абсолютно всегда и используются, чтобы раскрывать инверсию перед скобкой. Чтобы убедиться, что эти формулы равносильны, достаточно построить для них таблицы истинности.
Для первой формулы:
| A | B | ¬(A /\ B) | ¬A \/ ¬B |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
Для второй формулы:
| A | B | ¬(A \/ B) | ¬A /\ ¬B |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Свойства констант:
A /\ 1 = А
| A | 1 | A /\ 1 |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 1 | 1 |
A \/ 1 = 1
| A | 1 | A \/ 1 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 1 |
A /\ 0 = 0
| A | 0 | A /\ 0 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
A \/ 0 = A
| A | 0 | A \/ 0 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Закон двойного отрицания:
¬(¬А) = А
| A | ¬А | ¬(¬А) |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 1 |
Законы поглощения:
А /\ (A \/ B) = A
| A | B | A \/ B | А /\ (A \/ B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
А \/ (A /\ B) = A
| A | B | A /\ B | А \/ (A /\ B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Законы алгебры логики помогают упрощать сложные логические выражения. Рассмотрим два примера.
Пример упрощения выражения.
–(–A P) /\ (Q –A) = 1 #раскрываем импликацию
–(A \/ P) /\ –(Q /\ A) = 1 #используем закон де-Моргана для двух скобок
–( A \/ P \/ Q /\ A) = 1 #раскрываем отрицание
A \/ P \/ Q /\ A = 0 #используем правило тавтологии
P \/ Q /\ A = 0
Пример упрощения выражения.
– (X1 ≡ X2) /\ (X1 \/ X3 ) /\ ( –X1 \/ –X3 ) = 0 #свернем вторую и третью скобки в эквиваленцию
# (–X1 \/ X3 ) /\ ( X1 \/ –X3 ) = X1 ≡ X3 # (–(–X1 )\/ X3 ) /\ ( –X1 \/ –X3 ) = –X1 ≡ X3
– (X1 ≡ X2) /\ (–X1 ≡ X3) = 0 #вынесем отрицание из второй скобки
– (X1 ≡ X2) /\ – (X1 ≡ X3) = 0 #используем закон де-Моргана
– ((X1 ≡ X2) \/ (X1 ≡ X3)) = 0 #раскрываем отрицание
(X1 ≡ X2) \/ (X1 ≡ X3) = 1