Законы де Моргана: как правильно отрицать «и» и «или»

Законы де Моргана это два правила отрицания связок. Первый: «неверно, что оба» равно «хотя бы один не», то есть ¬(A ∧ B) равносильно ¬A ∨ ¬B. Второй: «ни то, ни другое» равно «не то и не это», то есть ¬(A ∨ B) равносильно ¬A ∧ ¬B. Оба доказываются таблицей в четыре строки и нужны не логике, а вам, притом ежедневно.

Доказательство

Возьмём второй закон, ¬(A ∨ B) и ¬A ∧ ¬B. Слева: «или» ложно только в последней строке, где A и B оба ложны, и отрицание переворачивает столбец в Л Л Л И. Справа: «и» истинно только там, где истинны обе части, а ¬A и ¬B вместе истинны тоже только в последней строке. Столбцы совпали во всех четырёх строках, закон доказан.

Первый закон проверяется так же: ¬(A ∧ B) ложно только в первой строке, где оба истинны, и ¬A ∨ ¬B ложно тоже только там. Огастес де Морган был английским математиком (1806-1871), но сами законы были известны и раньше: их знал, в частности, Уильям Оккам в четырнадцатом веке.

Зачем это в жизни

Законы отвечают на вопрос, как правильно отрицать «и» и «или». «Гарантия действует, если товар не вскрыт и есть чек». Когда гарантия не действует? Не «когда вскрыт и нет чека», а «когда вскрыт или нет чека»: достаточно одного нарушения. Продавец, требующий обоих условий сразу для отказа, читает договор в вашу пользу, и это редкость.

Обратный случай. «Я не был ни в среду, ни в четверг» это ¬(среда ∨ четверг), и оно равносильно «не был в среду и не был в четверг». Проверять алиби нужно по каждому дню отдельно, отрицание перечня превращается в перечень отрицаний.

Где ошибаются

Самая частая ошибка это отрицать конъюнкцию, отрицая обе части: из «неверно, что он умён и честен» выводят «глуп и нечестен». Закон говорит другое: хотя бы одно неверно, а какое именно, из отрицания не следует.

Вторая ошибка касается неклассических логик. В интуиционистской логике из ¬(P ∧ Q) не следует ¬P ∨ ¬Q: чтобы утверждать «хотя бы один не», надо указать который, а отрицание целого этого не даёт. Один закон де Моргана там работает, встречный нет. В классической логике оба верны без оговорок.

Вопросы

Как звучат законы де Моргана словами?

Отрицание «и» это «или» отрицаний, отрицание «или» это «и» отрицаний. «Неверно, что оба» значит «хотя бы один не», «ни то, ни другое» значит «не то и не это».

Работают ли законы де Моргана для множеств?

Да, в той же форме: дополнение пересечения равно объединению дополнений, дополнение объединения равно пересечению дополнений. Это та же таблица, только «истинно» означает «принадлежит».

Как применять законы де Моргана в программировании?

Условие !(a && b) равносильно !a || !b, а !(a || b) равносильно !a && !b. Так упрощают отрицания в проверках и избавляются от вложенных «не».