И, или, не

В меню «суп или салат» обычно означает одно из двух. В логике «p или q» остаётся истинным, когда истинны оба, и это правило разрешает большинство споров о слове «или».

И: обе части должны выполняться

Возьмём два высказывания: p «Магазин продаёт хлеб» и q «Магазин продаёт молоко». Конъюнкция p ∧ q, читаемая «p и q», утверждает оба сразу. Она истинна лишь в одной ситуации: когда p и q оба истинны. Если в магазине есть хлеб, но нет молока, предложение «Магазин продаёт хлеб и молоко» ложно: половина обещанного отсутствует. Для двух высказываний есть четыре ситуации (TT, TF, FT, FF), и конъюнкция истинна ровно в одной из них.

В английском и корейском много слов, выполняющих ту же логическую роль, что и «и». «Квартира маленькая, но светлая» утверждает и то, что она маленькая, и то, что светлая; «но» добавляет противопоставление, поэтому forall x рассматривает его как конъюнкцию. «Хотя», «однако», «также» и «тогда как» обычно работают подобным образом. Логика сохраняет условия истинности, отбрасывая оттенок речи.

Или: выполняется хотя бы одна часть

Дизъюнкция p ∨ q, читаемая «p или q», истинна, когда хотя бы одно из p и q истинно. Она ложна только тогда, когда оба ложны. Это неисключающее «или», и символ ∨ всегда означает именно его. Допустим, объявление о работе говорит: «Соискатель должен владеть японским или китайским». Того, кто владеет обоими, явно не отвергнут. Здесь действует неисключающее прочтение.

Иногда мы действительно имеем в виду «одно или другое, но не оба». Комплексный обед с выбором «кофе или чай» редко позволяет взять оба напитка. Это исключающее «или». В forall x для него нет отдельного основного символа; оно строится из остальных как (p ∨ q) ∧ ¬(p ∧ q), то есть хотя бы одно, но не оба. При неоднозначности безопаснее уточнить замысел говорящего и при необходимости записать исключающий вариант полностью.

Не и законы де Моргана

Отрицание меняет одно значение истинности. Интереснее то, что происходит при отрицании целой конъюнкции или дизъюнкции. «Неверно, что квартира дешёвая и рядом со станцией» истинно, когда хотя бы одна часть не выполняется: квартира не дешёвая, или не рядом со станцией, или и то и другое. Символически ¬(p ∧ q) имеет то же значение истинности, что ¬p ∨ ¬q, в каждой строке. Аналогично «Неверно, что можно заплатить наличными или картой» означает невозможность обоих способов: ¬(p ∨ q) совпадает с ¬p ∧ ¬q. Эти два равносильных выражения называются законами де Моргана в честь логика девятнадцатого века Огастеса де Моргана.

Частая ошибка: перенести «не» внутрь и забыть поменять связку. «Не (дешёвая и рядом)» не означает «не дешёвая и не рядом». Дешёвая квартира далеко от станции делает первое предложение истинным, второе ложным. При переносе отрицания внутрь скобок «и» превращается в «или», а «или» в «и».

Скобки важны по той же причине, что и в арифметике. ¬p ∧ q означает «не p, и q», а ¬(p ∧ q) означает «не оба». В первом случае отрицание относится лишь к p. Переводя обычное предложение в символы, сначала определи область действия «не», затем расставь скобки.