Сравнение булевских выражений
Введено| English | Значение |
|---|---|
| equivalent/ɪˈkwɪvələnt/ | Эквивалентность |
| De Morgan's Laws/də ˈmɔːɡənz lɔːz/ | Законы де Моргана |
Один контрпример опровергает булево преобразование
- Предложенное преобразование меняет !(a && b) на !a && !b. Задайте a = true и b = false.
- Исходное выражение истинно, а предложенное преобразование ложно. Де Моргана требует !a || !b, что совпадает с исходным.
Когда два условия означают одно и то же
- Два булевых выражения эквивалентны, если они дают одинаковый результат для любого входа. Для целого числа
x,x >= 5и!(x < 5)эквивалентны — оба истинны ровно тогда, когдаxне менее5. - Для булевых переменных без побочных эффектов эквивалентные выражения имеют одинаковый результат. Также проверяйте порядок вычисления, если выражения вызывают методы или изменяют состояние. Таблица истинности доказывает эквивалентность: тот же вывод в каждой строке.
Законы де Моргана
- Законы Де Моргана переписывают НЕ над AND/OR:
!(a && b)равно!a || !b. !(a || b)равно!a && !b. Паттерн: внесите!внутрь и переверните&&↔||.
Упрощение условий
- Используйте законы Де Моргана и правила логики, чтобы написать более короткое, понятное эквивалентное выражение. Для целочисленного счета
!(score < 60)становитсяscore >= 60— то же значение, легче читать. - Устранение двойного отрицания или внешнего
!часто проясняет намерение. Проверьте точную область ввода и поведение вычисления; меньшее количество символов не гарантирует меньшее количество ошибок.
По закону Де Моргана, !(a && b) эквивалентен...
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
Внесите ! внутрь и переверните && на ||.
По закону Де Моргана, !(a || b) эквивалентен...
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
Внесите ! внутрь и переверните || на &&.
Для целочисленного счета, что является эквивалентом !(score < 60)?
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
не-меньше-чем-60 означает-как-минимум-60.
Два булевских выражения эквивалентны, если они дают одинаковый результат для любого входного значения.
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
Одинаковый вывод в каждой строке таблицы истинности = эквивалентность.
Применение закона Де Моргана превращает !(a && b) в !a && !b.
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
Он становится !a || !b — оператор должен быть перевернут.
Проверка с помощью таблицы истинности
- Чтобы проверить, являются ли два выражения эквивалентными, составьте таблицу для обоих на всех входах. Если каждая строка совпадает, они эквивалентны; одно несовпадение означает, что они нет.
- Для двух чистых булевых переменных существуют четыре строки входа, которые полностью определяют функцию истинности. Это не перечисляет эффекты произвольных вызовов методов и не доказывает каждое преобразование сравнения чисел с плавающей точкой.
Применяя закон де Моргана, вы должны также инвертировать оператор, а не просто распределить !. !(a && b) превращается в !a || !b (AND становится OR) — запись !a && !b является неверной. Мнемоническое правило: внесите NOT внутрь и поменяйте местами && ↔ ||. При сомнениях таблица истинности решает вопрос за четыре строки.
При a=true и b=false, каковы значения !(a && b), !a && !b и !a || !b по порядку?
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
The mismatching middle expression is a counterexample to the proposed equivalence.
Для двойного сравнения, равного NaN, !(score < 60) and score >= 60) возвращает тот же логический результат.
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
Сравнения score < 60 and score >= 60 оба ложны для NaN, поэтому инвертированное первое выражение истинно, а второе — ложно.
Если f() возвращает false, сколько раз будет вызвана g() при вычислении !(f() && g())?
Сложность 2/5 · 140 монет + небольшой бонус за первое выполнение сегодня
Ложное первое операнд коротко замыкает оператор &&, поэтому g не вызывается. Эквивалентное выражение !f() || !g() также пропускает вызов g.
Перезапись !(a && b):
- Неверно:
!a && !b. - Верно (де Морган):
!a || !b— AND меняется на OR. - Проверка: если
a = true, b = false, то!(true && false) = !false = true, и!a || !b = false || true = true. ✓
Перенесите рассуждения на новый случай
- Для чистых булевых переменных все четыре пары входов доказывают эквивалентность. Формы Де Моргана сохраняют левостороннюю оценку с коротким замыканием:
!(f() && g())и!f() || !g()пропускают g, когда f ложно. - Обмен операндами — это другое преобразование. Хотя
a && bиb && aимеют одну и ту же таблицу истинности для чистых переменных,f() && g()иg() && f()могут вызывать разные методы. Для double score=NaN,!(score < 60)истинно, ноscore >= 60ложно; правило сравнения целых чисел не распространяется на NaN.
Два булевых выражения являются эквивалентными, если они совпадают для любого входа (что можно доказать с помощью таблицы истинности). Законы де Моргана: !(a && b) = !a || !b и !(a || b) = !a && !b — внесите ! внутрь и поменяйте местами && ↔ ||. Используйте их для упрощения условий до более явных эквивалентных форм.