§ 2.2. Логические операции и логические выражения

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

Поэтому в алгебре логики высказывания заменяют буквами: A, B, C, X и так далее. Буква, которой обозначено высказывание, называется логической переменной. Значение у логической переменной одно из двух. Истину записывают единицей, ложь — нулём: если высказывание A истинно, пишут A = 1, если высказывание B ложно, пишут B = 0. Сами символы 0 и 1 в этой роли называют логическими значениями. Не путайте их с числами: единица здесь означает не «один предмет», а «правда».

Возьмём высказывание «Число 21 делится на 7» и обозначим его буквой D. Оно истинно, значит, D = 1. Высказывание «Число 21 чётное» обозначим буквой E; оно ложно, и E = 0. Какие слова стояли за буквами, для дальнейших вычислений уже неважно: алгебра логики работает только со значениями.

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

Логические операции. Когда высказывания заменены переменными со значениями 0 и 1, связки НЕ, И, ИЛИ можно считать действиями над этими переменными — так же, как сложение и умножение считают действиями над числами. Такие действия называют логическими операциями, а значения, над которыми операция выполняется, — операндами.

Каждую операцию удобно описать таблицей истинности (рис. 1). В её левых столбцах перечислены все возможные наборы значений операндов, а в последнем столбце записан результат операции на каждом наборе. Для двух операндов A и B наборов четыре, и выписывают их по порядку, как двоичные числа по возрастанию: 00, 01, 10, 11. Для одного операнда наборов два: 0 и 1. Операцию можно описать и квадратной таблицей, как таблицу умножения: во главе строк стоит первый операнд, во главе столбцов — второй, а на пересечении — результат.

Операция И. В таблице истинности результат равен 1 в одной-единственной строке — там, где оба операнда равны 1. Квадратная таблица операции И (на рис. 1 внизу слева) клетка в клетку совпадает с таблицей двоичного умножения из § 1.2: произведение равно единице, только если оба множителя — единицы. Поэтому операцию И часто называют логическим умножением. Её третье название — конъюнкция.

Конъюнкция (логическое умножение) — логическая операция, которая из двух высказываний строит новое высказывание; оно истинно в единственном случае — когда истинны оба исходных высказывания. Во всех остальных случаях конъюнкция ложна.

Операция ИЛИ. Здесь всё наоборот: результат равен 0 в одной строке — там, где оба операнда равны 0. Квадратная таблица операции ИЛИ очень похожа на таблицу двоичного сложения: три клетки из четырёх у них одинаковы. Различается одна — та, где складывают две единицы: в двоичной арифметике выходит 10, а в логике 1 ИЛИ 1 = 1, потому что других значений, кроме нуля и единицы, нет. За это сходство операцию ИЛИ называют логическим сложением, а ещё — дизъюнкцией.

Дизъюнкция (логическое сложение) — логическая операция, которая из двух высказываний строит новое высказывание; оно ложно в единственном случае — когда ложны оба исходных высказывания. Если истинно хотя бы одно из них, дизъюнкция истинна.

Операция НЕ. У неё один операнд, и таблица истинности состоит из двух строк: НЕ 0 = 1, НЕ 1 = 0. Эту операцию называют логическим отрицанием, или инверсией.

Инверсия (логическое отрицание) — логическая операция над одним высказыванием, которая даёт новое высказывание с противоположным значением: из истинного получается ложное, из ложного — истинное.

Как у сложения есть знак «+», а у вычитания знак «−», так и у логических операций есть свои знаки, причём у каждой не один. Инверсию обозначают знаком ¬ или чертой над буквой. Для конъюнкции применяют знаки ∧, · и &, для дизъюнкции — знаки ∨, + и |. В этом уроке будем писать ¬, ∧ и ∨: запись ¬A читается «не A», A ∧ B — «A и B», A ∨ B — «A или B». Высказывания о числе X, как и в прошлом параграфе, иногда удобнее записывать словами: (X > 3) И НЕ (X > 8).

Операции над множествами. С конъюнкцией и дизъюнкцией тесно связаны две операции над множествами, знакомые вам по математике.