Отрицание условий
Отрицание составного условия меняет не только знак «не»: нужно правильно преобразовать каждую логическую связку и каждое сравнение. В этой статье разобраны законы де Моргана, отрицание «и», «или», сравнений и условий в программах.
Составное высказывание — это высказывание, полученное из простых с помощью логических связок. Отрицание высказывания \(A\) обозначают \(\neg A\) и читают «не \(A\)». Если \(A\) истинно, то \(\neg A\) ложно, и наоборот.
Законы де Моргана
Главное правило: при отрицании составного условия связка меняется на противоположную, а каждое простое условие также отрицается. Связка «и» превращается в «или», а «или» — в «и».
Для любых логических высказываний \(A\) и \(B\) верны два равенства: отрицание конъюнкции равно дизъюнкции отрицаний, а отрицание дизъюнкции равно конъюнкции отрицаний.
Первое равенство означает: «неверно, что выполнены оба условия» равносильно «хотя бы одно условие не выполнено». Второе: «неверно, что выполнено хотя бы одно условие» равносильно «не выполнено ни одно условие», то есть не выполнены оба.
| Исходная связка | После отрицания | Смысл |
|---|---|---|
| \(A\land B\) | \(\neg A\lor\neg B\) | не оба сразу |
| \(A\lor B\) | \(\neg A\land\neg B\) | ни одно |
| \(\neg A\) | \(A\) | двойное отрицание исчезает |
Отрицание «и» даёт «или», отрицание «или» даёт «и». Само отрицание каждого условия сохраняется: \(\neg\neg A\equiv A\).
Как отрицать сравнения
В условии программы простое высказывание часто является сравнением. Чтобы получить его отрицание, знак сравнения заменяют на противоположный.
- Строгое неравенство \(>\) меняется на нестрогое \(\le\).
- Строгое неравенство \(<\) меняется на нестрогое \(\ge\).
- Нестрогое \(\ge\) меняется на строгое \(<\), а \(\le\) — на \(>\).
- Равенство \(=\) меняется на неравенство \(\ne\), и наоборот.
Нельзя просто поменять направление стрелки и оставить тот же тип знака. Например, отрицание \(x\ge5\) — это \(x<5\), а не \(x\le5\). Граница \(5\) должна перейти только в одну из частей.
Пошаговый алгоритм
Для отрицания длинного условия удобно действовать слева направо. Сначала найти внешнюю связку, затем применить закон де Моргана, после этого заменить отрицание каждого сравнения.
- Поставьте скобки вокруг всего исходного условия и знак отрицания перед скобками.
- Определите главную связку: «и» или «или».
- Замените её на противоположную по законам де Моргана.
- Отрицайте каждое простое условие, изменяя знак сравнения.
- Уберите двойные отрицания и проверьте скобки.
Исходное условие описывает числа отрезка \((2;7]\). Его отрицание описывает все числа вне этого отрезка: \(x\le2\) или \(x>7\). Обратите внимание: точка \(2\) вошла в отрицание, а точка \(7\) — нет.
Чему равносильно отрицание условия \(x\ge3\lor x<10\)?
Отрицание условий в программах
В языках программирования логические связки обычно записывают как and, or, not или соответствующими символами. Например, условие «\(x\) находится в отрезке \([a;b]\)» можно записать как \(x\ge a\land x\le b\).
Это правило особенно полезно при замене условия в операторе if. Если программа должна выполнить действие, когда число не принадлежит отрезку \([a;b]\), достаточно проверить \(x<a\) или \(x>b\).
Сначала мысленно разделите запись \(a\le x\le b\) на два условия: \(a\le x\) и \(x\le b\). Затем отрицайте их по отдельности и соединяйте через «или».
Разобранный экзаменационный пример
Найти условие, равносильное отрицанию выражения: «\(x\) — целое число, при этом \(x\ne0\) и \(x\le12\), или \(x>20\)». Обозначим \(A\): «\(x\) — целое», \(B\): «\(x\ne0\), \(C\): «\(x\le12\), \(D\): «\(x>20\)». Исходное выражение имеет вид \((A\land B\land C)\lor D\).
Показать решение 4 шага
Чтобы исходное выражение стало ложным, одновременно должны быть ложны обе его части: первая тройка условий не должна выполняться, а условие \(x>20\) также должно быть ложным. Поэтому обязательно \(x\le20\).
Проверка закона таблицей истинности
Если есть сомнения, равносильность можно проверить таблицей истинности. Для закона де Моргана достаточно рассмотреть четыре сочетания значений \(A\) и \(B\).
| A | B | \(\neg(A\land B)\) | \(\neg A\lor\neg B\) |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
Два последних столбца совпадают во всех строках, значит выражения равносильны. Аналогично проверяется второй закон: \(\neg(A\lor B)\equiv\neg A\land\neg B\).
Первая: отрицать только одно условие, например превращать \(\neg(A\land B)\) в \(\neg A\land B\). Вторая: путать отрицание «хотя бы одного» с отрицанием «ровно одного». Законы де Моргана относятся к связкам «и» и «или», а не к количеству совпавших условий.
Связь с множествами и диаграммами
Логические условия можно понимать как принадлежность множествам. Связка «и» соответствует пересечению, «или» — объединению, а отрицание — дополнению. Поэтому закон де Моргана работает и для множеств: дополнение пересечения равно объединению дополнений.
Такой взгляд помогает при работе с диаграммами Венна и кругами Эйлера и при подсчёте элементов по диаграмме Венна. В задачах на условия полезны также классификация логических связок и логические приёмы решения задач.
Быстрая проверка
Главное
- При отрицании «и» заменяется на «или»: \(\neg(A\land B)\equiv\neg A\lor\neg B\).
- При отрицании «или» заменяется на «и»: \(\neg(A\lor B)\equiv\neg A\land\neg B\).
- Каждое сравнение нужно отрицать отдельно: \(>\) ↔ \(\le\), \(<\) ↔ \(\ge\), \(=\) ↔ \(\ne\).
- Для двойного неравенства сначала разделите его на два условия, затем примените закон де Моргана.
- После преобразования проверьте границы и при необходимости используйте таблицу истинности.