Логика с нуля LOGIC · 01 · 02

И, ИЛИ, НЕ: таблицы истинности, де Морган и искусство отрицать условия

AND, OR, NOT и XOR полностью заданы таблицами истинности. Законы де Моргана: NOT (a AND b) превращается в (NOT a) OR (NOT b). Короткое замыкание в коде — та же таблица, исполняемая в рантайме. Большинство багов в составных условиях — это неверно раскрытое отрицание.

LOGIC Основы ◷ 17 min

Уровень

ОсновыJuniorMiddleSenior

Спецификация умещалась в одно предложение: «Блокировать запрос, если пользователь не является верифицированным и активным». Разработчик рассуждал вслух — блокируем при НЕ (верифицирован и активен), то есть НЕ верифицирован И НЕ активен — и закоммитил if (!user.verified && !user.active) block(req). Ревью одобрило. Через три месяца аудит нашёл, что деактивированный бывший сотрудник, всё ещё с подтверждённой почтой, сохранял полный доступ. Условие блокировало лишь тех, кто провалил обе проверки; один провал проскальзывал. Исправление — один символ, && на ||, а урок двухсотлетний: когда отрицание проходит сквозь И, оно обязано его перевернуть в ИЛИ.

Цель

После этого урока ты умеешь читать таблицы истинности для И, ИЛИ, НЕ и XOR; применять оба закона де Моргана для переписки отрицания составного условия; объяснять, что делает короткое замыкание; и называть три эквивалентных способа записать «блокировать, если не (верифицирован И активен)».

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

`p`	`q`	`p AND q` (`&&`)	`p OR q` (`\|\|`)	`p XOR q`
И	И	И	И	Л
И	Л	Л	И	И
Л	И	Л	И	И
Л	Л	Л	Л	Л

NOT (!) — одновходовая таблица: НЕ И = Л, НЕ Л = И. Таблицы — вся дефиниция.

AND строгое; OR включающее; XOR исключающее. AND истинно ровно в одной строке — когда истинны обе части. OR включающее: истинно, когда истинна хотя бы одна часть, включая строку, где обе истинны. XOR истинно, когда части различаются. Бытовое «или» часто означает XOR («суп или салат» — не оба), но || в коде всегда включающее OR. Ключевого слова XOR в большинстве языков нет; для булей — a !== b.

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

!(a && b)  ===  (!a || !b)   // НЕ (оба)         = хотя бы один не выполнен
!(a || b)  ===  (!a && !b)   // НЕ (хотя бы один) = оба не выполнены

Паттерн: когда ! распределяется по частям, связка переворачивается. Баг из пролога, исправленный тремя эквивалентными способами:

if (!(user.verified && user.active)) block(req);   // прямое отрицание
if (!user.verified || !user.active) block(req);    // де Морган — правильно
if (!user.verified && !user.active) block(req);    // БАГ: только если ОБА провалены

Короткое замыкание исполняет таблицу слева направо и останавливается досрочно. Рантайм не вычисляет обе стороны && и не сверяется с таблицей. Если левая сторона && ложна, результат уже Л и правая не вычисляется. Если левая сторона || истинна, результат уже И и правая пропускается. Это короткое замыкание. Оно позволяет левой стороне охранять правую от падений — user && user.name.length > 0, — но любой побочный эффект справа молча не происходит, когда левая уже решила.

Таблицы истинности четырёх основных связок
p	q	p И q	p ИЛИ q	p XOR q	НЕ p
И	И	И	И	Л	Л
И	Л	Л	И	И	Л
Л	И	Л	И	И	И
Л	Л	Л	Л	Л	И

Разбор примера

Примените закон де Моргана, чтобы переписать !(loggedIn && hasPaid) без внешнего отрицания.

Условие !(loggedIn && hasPaid) означает «НЕ (залогинен И оплатил)».

Первый закон де Моргана: !(a && b) === (!a || !b). Подставим:

!(loggedIn && hasPaid)
// a = loggedIn, b = hasPaid
!loggedIn || !hasPaid

Проверим смешанную строку: loggedIn = И, hasPaid = Л — залогиненный, но не оплативший:

Оригинал: !(И && Л) → !(Л) → И — правильно заблокирован.
Переписка: !И || !Л → Л || И → И — тот же результат.

Неверная версия !loggedIn && !hasPaid даёт Л || Л → Л — этот пользователь проходит. Это и есть баг.

▸Почему это работает

Зачем языкам короткое замыкание, раз в нём есть ловушка? Две причины. Производительность: правая сторона может быть дорогой (запрос к базе, сетевая проверка), и пропускать её, когда левая уже решила, — бесплатная скорость. Безопасность: идиома-охранник (проверка на null слева, разыменование справа) работает только потому, что правая сторона гарантированно не выполнится. Цена: порядок начинает иметь значение. У a && b и b && a одинаковые таблицы истинности, но разное поведение при побочных эффектах. Правило: держите правые операнды чистыми, дешёвые проверки ставьте слева, дорогие — справа.

Практика 0 / 5

Чему равно (И И Л)? Напишите И или Л.

Чему равно (Л ИЛИ И)? Напишите И или Л.

Чему равно НЕ (И И И)? Напишите И или Л.

Применим де Моргана к !(a || b). Что равно: (!a && !b) или (!a || !b)?

При user = null упадёт ли (user && user.name) в JavaScript? Напишите да или нет.

Проверь себя

Викторина

Нужно отрицание условия (loggedIn && hasPaid). Какая переписка верна?

Итог

Связки строят составные высказывания, истинность которых зависит только от частей, а таблицы истинности — их полная дефиниция: AND истинно ровно в одной строке из четырёх (обе части истинны), включающее OR ложно ровно в одной (обе ложны), XOR истинно при различии частей, NOT меняет единственное значение. Бытовое «или» часто исключающее, но || в коде — включающее; когда важно «не оба сразу», это XOR, для булей — a !== b. Отрицанием правят законы де Моргана: НЕ (a И b) равно (НЕ a) ИЛИ (НЕ b), а НЕ (a ИЛИ b) равно (НЕ a) И (НЕ b) — связка переворачивается, когда отрицание заходит внутрь. Распределить НЕ без переворота — канонический баг составных условий: он совпадает с правильным условием на однородных строках, которые гоняют ревью и happy-path-тесты, и расходится на смешанных строках, которыми полон продакшен. Лечится перебором четырёх строк или именованием позитивного условия с отрицанием имени. В рантайме таблица исполняется с коротким замыканием: держите правые операнды чистыми, дешёвые проверки ставьте слева.

Практика

Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.

вспомнитьприменитьуглубить0 из 5 завершено

Что-то непонятно?

Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.

Примени это

Примени этот урок в реальном проекте.

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