Использование булевой алгебры может показаться излишним для доказательства очевидного факта (особенно учитывая то, что Сократ доказал собственную смертность 2400 лет назад), однако ее можно использовать для того, чтобы определить, удовлетворяет ли что-то определенному набору критериев. Возможно, однажды вы зайдете в зоомагазин и скажете продавцу: «Мне нужен стерилизованный кот белого или рыжего окраса, или стерилизованная кошка любого окраса, кроме белого, или я возьму любую из имеющихся у вас черных кошек». И продавец скажет, что вам нужна кошка из множества, описываемого следующим выражением:
(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.
Верно? И вы ответите: «Да! Точно!»
Проверяя, правильно ли продавец вас понял, можно отказаться от понятий объединения и пересечения, вместо них использовать слова ИЛИ и И. Я пишу эти слова заглавными буквами, потому что они не только соответствуют понятиям в обычном языке, но и могут представлять собой операции в булевой алгебре. Когда вы формируете объединение двух множеств, вы фактически берете элементы из первого ИЛИ второго множества. А когда вы формируете пересечение, то берете только те элементы, которые одновременно принадлежат первому И второму множествам. Кроме того, вы можете использовать слово НЕ везде, где встречается символ 1, за которым следует знак «минус». Таким образом:
символ «+» (ранее обозначавший объединение) теперь означает ИЛИ;
символ «×» (ранее обозначавший пересечение) теперь означает И;
выражение «1 –» (ранее обозначавшее множество всех элементов, за исключением чего-то) теперь означает НЕ.
Именно поэтому приведенное выше выражение также может быть записано:
(М И С И (Б ИЛИ Р)) ИЛИ (Ж И С И (НЕ Б)) ИЛИ Ч.
Как видите, это соответствует тому, что вы сказали. Обратите внимание, как скобки уточняют ваши пожелания. Вам нужна кошка, принадлежащая одному из трех множеств.
(М И С И (Б ИЛИ Р))
ИЛИ
(Ж И С И (НЕ Б))
ИЛИ
Ч
С помощью этой формулы продавец может выполнить то, что называется проверкой условия. Незаметно мы перешли к несколько иной форме булевой алгебры, в которой буквы не обозначают множества. Вместо этого буквы теперь могут соответствовать числам. Однако буквам может быть присвоено только значение 0 или 1. Число 1 означает «да», «истина», данная конкретная кошка удовлетворяет этим критериям, число 0 — «нет», «ложь», данная кошка не удовлетворяет этим критериям.
Сначала продавец приносит нестерилизованного рыжего кота. Вот выражение, описывающее множество приемлемых кошек:
(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.
Вот как оно выглядит после подстановки значений 0 и 1:
(1 × 0 × (0 + 1)) + (0 × 0 × (1 – 0)) + 0.
Обратите внимание: единственными символами, которым было присвоено значение 1, являются М и Р, поскольку речь идет о рыжем коте.
Теперь нужно упростить данное выражение. Если оно упрощается до 1, то кошка удовлетворяет вашим критериям; если оно упрощается до 0, то кошка критериям не удовлетворяет. Имейте в виду, что в процессе упрощения выражения мы на самом деле ничего не складываем и не умножаем, хотя обычно можем сделать вид, что выполняем эти операции. Большинство тех же правил применяются тогда, когда символ «+» означает ИЛИ, а символ «×» — И. Иногда в современных текстах для обозначения И и ИЛИ используются символы «∧» и «∨» вместо «×» и «+». Однако именно здесь символы «+» и «×», вероятно, имеют наибольший смысл.
Когда символ «×» означает И, возможны результаты:
0 × 0 = 0;
0 × 1 = 0;
1 × 0 = 0;
1 × 1 = 1.
Другими словами, результат равен 1 только в том случае, если левый И правый операнды равны 1. Эта операция соответствует обычному умножению и называется конъюнкцией, и ее можно описать с помощью небольшой таблицы, аналогичной таблицам сложения и умножения, приведенным в главе 8.
Когда символ «+» означает ИЛИ, возможны следующие результаты.
0 + 0 = 0;
0 + 1 = 1;
1 + 0 = 1;
1 + 1 = 1.
Результат равен 1, если левый ИЛИ правый операнд равен 1. Исход этой операции похож на результаты обычного сложения, за исключением того, что в данном случае 1 + 1 равно 1. Результаты операции ИЛИ, которая называется дизъюнкцией, можно представить в виде другой таблицы.
Мы готовы использовать эти таблицы для вычисления:
(1 × 0 × 1) + (0 × 0 × 1) + 0 = 0 + 0 + 0 = 0.
Результат 0 — «нет», «ложь», этот котенок не подходит.
Затем продавец приносит стерилизованную белую кошку. Исходное выражение выглядело так:
(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.
Снова подставим в него значения 0 и 1:
(0 × 1 × (1 + 0)) + (1 × 1 × (1 – 1)) + 0.
И упростим его:
(0 × 1 × 1) + (1 × 1 × 0) + 0 = 0 + 0 + 0 = 0.
Еще один несчастный котенок отвергнут.
Затем продавец приносит стерилизованную серую кошку. (Серый соответствует критерию «другой окрас», то есть не белый, не черный и не рыжий.) Вот соответствующее выражение:
(0 × 1 × (0 + 0)) + (1 × 1 × (1 – 0)) + 0.
Теперь упростим его:
(0 × 1 × 0) + (1 × 1 × 1) + 0 = 0 + 1 + 0 = 1.
Результат вычисления, равный 1, означает «да», «истина», котенок нашел свой дом. (Кроме того, он оказался самым милым!)
Позже в тот же вечер, пока котенок спит у вас на коленях, вы спрашиваете себя, нельзя ли подключить несколько переключателей к лампочке для облегчения процесса проверки котят на соответствие вашим критериям. (Да, вы весьма странный ребенок.) Сами не зная того, вы вплотную приблизились к решающему концептуальному прорыву. Вы вот-вот проведете некоторые эксперименты, которые объединят алгебру Джорджа Буля с электричеством и сделают возможным проектирование и сборку компьютеров, работающих с двоичными числами. Однако пусть вас это не пугает.
Чтобы поставить такой эксперимент, вы, как обычно, соединяете лампочку и батарейку, но используете два переключателя вместо одного.
Считается, что переключатели, подключенные друг за другом, соединены последовательно. Если вы замыкаете левый переключатель, ничего не происходит.
Если вы оставляете левый переключатель разомкнутым, а замыкаете правый, также ничего не произойдет. Лампочка загорается, когда и левый, и правый переключатели оказываются замкнутыми.
Ключевым в данном случае является союз «и». Левый и правый переключатели должны быть замкнуты, чтобы ток шел по цепи.
Эта схема решает небольшую логическую задачу. Фактически лампочка отвечает на вопрос: «Замкнуты ли оба переключателя?» Мы можем суммировать результаты работы этой схемы в следующей таблице.
Левый переключатель
Правый переключатель
Лампочка
Разомкнут
Разомкнут
Не горит
Разомкнут
Замкнут
Не горит
Замкнут
Разомкнут
Не горит
Замкнут
Замкнут
Горит
В предыдущей главе мы говорили о том, как с помощью двоичных цифр, или битов, можно представить любую информацию, начиная от чисел и заканчивая направлением большого пальца Роджера Эберта. Мы могли сказать, что ноль бит означает, что палец направлен вниз, а один бит — что палец направлен вверх. Переключатель может находиться в двух положениях, поэтому для его описания достаточно одного бита. Можно сказать, что 0 — это «переключатель разомкнут», а 1 — «переключатель замкнут». Лампочка также имеет два состояния, следовательно, для их описания достаточно одного бита. Можно сказать, что 0 — «лампочка не горит», а 1 — «лампочка горит». Теперь мы просто переписываем приведенную выше таблицу.
Левый переключатель
Правый переключатель
Лампочка
0
0
0
0
1
0
1
0
0
1
1
1
Обратите внимание: если мы поменяем местами левый и правый переключатели, результаты останутся прежними. Нам не обязательно различать переключатели. Именно поэтому таблицу можно переписать так, чтобы она напоминала приведенные И/ИЛИ.
Последовательное соединение переключателей
0
1
0
0
0
1
0
1
Действительно, это соответствует таблице с результатами выполнения булевой операции И.
Эта простая схема фактически выполняет операцию И в булевой алгебре.
Теперь попробуйте соединить два переключателя иначе.
Переключатели соединены параллельно. Разница между этим и предыдущим способом соединения заключается в том, что эта лампочка загорится, если вы замкнете верхний переключатель.
Или нижний переключатель.
Можно также замкнуть оба переключателя.
Лампочка загорается, если замкнуть верхний или нижний переключатель. Ключевым словом в данном случае является союз «или».
Опять же, данная схема решает логическую задачу. Лампочка отвечает на вопрос: «Замкнут ли хотя бы один переключатель?» В следующей таблице показаны результаты работы этой схемы.
Левый переключатель
Правый переключатель
Лампочка
Разомкнут
Разомкнут
Не горит
Разомкнут
Замкнут
Горит
Замкнут
Разомкнут
Горит
Замкнут
Замкнут
Горит
Теперь снова используем 0 для обозначения разомкнутого переключателя или негорящей лампочки и 1 — для обозначения замкнутого переключателя или горящей лампочки, в результате чего получим следующую таблицу.
Левый переключатель
Правый переключатель
Лампочка
0
0
0
0
1
1
1
0
1
1
1
1
Опять же ничего не изменится, если переключатели поменять местами, поэтому таблицу можно заполнить следующим образом.
Параллельное соединение переключателей
0
1
0
0
1
1
1
1
Вероятно, вы уже догадались, что эта таблица соответствует результатам булевой операции ИЛИ.