Законы де моргана

Законы де Моргана – это логические правила, установленные шотландским математиком Огастесом де Морганом, связывающие пары логических операций при помощи логического отрицания.

Огастес де Морган заметил, что в классической логике справедливы следующие соотношения:

not (А and В) = (not А) or (not В)

not (А or В) = (not А) and (not В)

В более привычной для нас форме данные соотношения можно записать в следующем виде:

Законы де Моргана можно сформулировать следующим образом:

I закон де Моргана: Отрицание дизъюнкции двух простых высказываний равносильно конъюнкции отрицаний этих высказываний.

II закон де Моргана: Отрицание конъюнкции двух простых высказываний равносильно дизъюнкции отрицаний этих высказываний.

Рассмотрим применение законов де Моргана на конкретных примерах.

Пример 1. Преобразовать формулу так, чтобы не было отрицаний сложных высказываний.

Воспользуемся первым законом де Моргана, получим:

,

к отрицанию конъюнкции простых высказываний В и С применим второй закон де Моргана, получим:

,

таким образом:

.

В итоге мы получили равносильное высказывание, в котором нет отрицаний составных высказываний, а все отрицания относятся только к простым высказываниям.

Проверить справедливость решения можно с помощью таблиц истинности. Для этого составим таблицы истинности для исходного высказывания:

,

и для высказывания, полученного в результате преобразований, выполненных с помощью законов де Моргана:

.

Таблица 1.

А

В

С

В/\С

А\/В/\С

0

0

0

0

0

1

0

0

1

0

0

1

0

1

0

0

0

1

0

1

1

1

1

0

1

0

0

0

1

0

1

0

1

0

1

0

1

1

0

0

1

0

1

1

1

1

1

0

Как видим из таблиц, исходное логическое высказывание и логическое высказывание, полученное с помощью законов де Моргана – равносильны. Об этом говорит тот факт, что в таблицах истинности мы получили одинаковые наборы значений.

Пример 2. Преобразовать формулу так, чтобы в ней не использовались знаки логического умножения.

Применим второй закон де Моргана к отрицанию конъюнкции простых высказываний В и С:

,

Раскроем скобки, применив закон дистрибутивности, получим:

,

применим закон двойного отрицания к образовавшимся конъюнкциям:

,

снова применим второй закон де Моргана к отрицанию конъюнкций

,

учитывая закон двойного отрицания:

.

Таким образом, можем записать:

.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *