Теоретический минимум по Computer Science

Программистам приходится иметь дело с логическими задачами так часто, что у них от этого ум за разум заходит. Однако на самом деле многие из них логику не изучали и пользуются ею бессознательно. Освоив формальную логику, мы сможем осознанно использовать ее для решения задач.

Рис. 1.4. Логика программиста[7]

Для начала мы поэкспериментируем с логическими высказываниями и операторами. Затем научимся решать задачи с таблицами истинности и увидим, как компьютеры опираются на логику.

Операторы

В математике переменные и операторы (+, ×, −, …) используются для моделирования числовых задач. В математической логике переменные и операторы указывают на достоверность. Они выражают не числа, а истинность (true) или ложность (false). Например, достоверность выражения «Если вода в бассейне теплая, то я буду плавать» основывается на достоверности двух вещей, которые можно преобразовать в логические переменные A и B:

A: Вода в бассейне теплая.

B: Я плаваю.

Они либо истинны (true), либо ложны (false)[8]. A = True обозначает теплую воду в бассейне, B = False обозначает «Я не плаваю». Переменная B не может быть наполовину истинной, потому что я не способен плавать лишь отчасти. Зависимость между переменными обозначается символом , условным оператором. A B выражает идею, что A = True влечет за собой B = True:

AB: если вода в бассейне теплая, то я буду плавать.

При помощи других операторов можно выражать другие идеи. Для отрицания идеи используется знак! оператор отрицания.!A противоположно A:

!A: Вода в бассейне холодная.

!B: Я не плаваю.

Противопоставление. Если дано A B, и я при этом не плаваю, что можно сказать о воде в бассейне? Теплая вода влечет за собой плавание, потому, если его нет, вода в бассейне не может быть теплой. Каждое условное выражение имеет противопоставленный ему эквивалент:

Для любых двух переменных A и B

AB тождественно! B !A.

Еще пример: если вы не умеете писать хороший код, значит, вы не прочли эту книгу. Противопоставлением данному суждению является такое: если вы прочли эту книгу, значит, вы умеете писать хороший код. Оба предложения сообщают одно и то же, но по-разному[9].

Двусторонняя условная зависимость. Обратите внимание, что высказывание «Если вода в бассейне теплая, то я буду плавать» не означает: «Я буду плавать только в теплой воде». Данное высказывание ничего не говорит насчет холодных бассейнов. Другими словами, A B не означает B A. Чтобы выразить оба условных суждения, используйте двустороннюю условную зависимость:

A <—> B: Я буду плавать, если и только если вода в бассейне теплая.

Здесь теплая вода в бассейне равнозначна тому, что я буду плавать: знание о воде в бассейне означает знание о том, что я буду плавать, и наоборот. Опять же, остерегайтесь обратной ошибки: никогда не предполагайте, что B A следует из A B.

AND, OR и XOR. Эти логические операторы — самые известные, поскольку они часто записываются в исходном коде в явном виде — AND (И), OR (ИЛИ) и XOR (исключающее ИЛИ). AND возвращает True, если все идеи истинны; OR возвращает True, если любая идея истинна; XOR возвращает True, если идеи взаимоисключающие. Представим вечеринку, где подают водку и вино:

A: Вы пили вино.

B: Вы пили водку.

A OR B: Вы пили.

A AND B: Вы пили и то и другое.

A XOR B: Вы пили, не смешивая.

Проверьте, правильно ли вы понимаете, как работают эти операторы. В табл. 1.1 перечислены все возможные комбинации двух переменных. Обратите внимание, что A B тождественно! A OR B, а A XOR B тождественно!(A <—> B).

Таблица 1.1. Логические операции для четырех возможных комбинаций A и B

Булева алгебра

Булева алгебра[10] позволяет упрощать логические выражения точно так же, как элементарная алгебра упрощает числовые.

Ассоциативность. Для последовательностей, состоящих только из операций AND или OR, круглые скобки не имеют значения. Так же, как последовательности только из операций сложения или умножения в элементарной алгебре, эти операции могут вычисляться в любом порядке.

A AND (B AND C) = (A AND B) AND C;

A OR (B OR C) = (A OR B) OR C.

Дистрибутивность. В элементарной алгебре мы раскрываем скобки: a × (b + c) = (a × b) + (a × c). Точно так же и в логике выполнение операции AND после OR эквивалентно выполнению операции OR над результатами операций AND и наоборот:

A AND (B OR C) = (A AND B) OR (A AND C);

A OR (B AND C) = (A OR B) AND (A OR C).