Логические операции И, ИЛИ, НЕ и таблицы истинности

Логическая операция — это действие над высказываниями, каждое из которых либо истинно, либо ложно. Главных операций три: И, ИЛИ и НЕ. Из них составляют любое условие — от «пускать ли человека в аккаунт» до правил, по которым процессор складывает числа.

Высказывание: правда или ложь

Высказывание — это утверждение, о котором можно сказать, истинно оно или ложно. «Сегодня суббота», «В рюкзаке лежит сменка», «Пароль введён верно» — высказывания. А вопрос «Который час?» и просьба «Закройте окно» — нет: они не бывают ни правдой, ни ложью.

Значений у высказывания всего два, поэтому оно помещается в один бит: истину записывают единицей, ложь — нулём. Чтобы не переписывать длинные фразы, высказывания обозначают буквами: A, B, C.

Операция И

Когда Вы входите в аккаунт с двойной защитой, сайт проверяет два высказывания: A — «пароль верный», B — «код из СМС верный». Пускают, только если верны оба. Это операция И: результат равен 1, только когда оба высказывания равны 1.

Такую таблицу называют таблицей истинности: слева в ней перечислены все сочетания значений, справа стоит результат для каждого.

Операция ИЛИ

Телефон можно разблокировать двумя способами: приложить палец или ввести код. Пусть A — «отпечаток подошёл», B — «код верный». Экран откроется, если верно хотя бы одно из двух. Это операция ИЛИ: результат равен 0, только когда оба высказывания равны 0.

Посмотрите на последнюю строку. В разговоре «или» часто значит «что-то одно»: чай или сок. В логике ИЛИ истинно и тогда, когда верны оба высказывания сразу.

Операция НЕ

Третья операция работает с одним высказыванием и переворачивает его значение. Пусть A — «телефон в беззвучном режиме». Мелодия звонка играет, когда это неправда: мелодия = НЕ A.

Как это записывают

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

операция   название      в математике   в программах
И          конъюнкция    A ∧ B          A && B
ИЛИ        дизъюнкция    A ∨ B          A || B
НЕ         отрицание     ¬A             !A

Значки &&, || и ! приняты в C++, Java, JavaScript и многих других языках. В Python операции пишут словами: and, or, not. В этом учебнике мы пишем по-русски: И, ИЛИ, НЕ.

Порядок действий

В выражении из нескольких операций есть порядок — как в арифметике, где умножение выполняют раньше сложения:

1. сначала НЕ;
2. затем И;
3. в последнюю очередь ИЛИ.

Скобки меняют порядок: то, что в них стоит, считают первым.

НЕ A И B       означает   (НЕ A) И B
A ИЛИ B И C    означает   A ИЛИ (B И C)

Сходство с арифметикой не случайно. Перемножьте нули и единицы — получится таблица операции И: 1 · 1 = 1, а остальные произведения равны нулю. Поэтому И называют логическим умножением, а ИЛИ — логическим сложением, с одной оговоркой: 1 ИЛИ 1 равно 1, а не 2.

Таблица истинности для трёх высказываний

Дверь подъезда открывают ключом от домофона. Курьерам выдали код, но он действует только днём. Обозначим: K — «приложен ключ», C — «набран код», N — «сейчас ночь». Дверь открыта, когда истинно выражение K ИЛИ C И НЕ N.

Построим его таблицу по шагам.

1. Считаем строки. Высказываний три, каждое равно 0 или 1, значит, сочетаний 2³ = 8. Это то же правило 2ⁿ, что и для сочетаний битов.
2. Заполняем левые столбцы. Чтобы не пропустить ни одного сочетания, записываем их как двоичные числа по порядку: от 000 до 111.
3. Считаем по порядку действий. Сначала НЕ N, затем C И НЕ N, в конце — ИЛИ с K. Для каждого шага заводим свой столбец.

Дверь открывается в пяти случаях из восьми. Четвёртая строка — курьер с кодом ночью: дверь закрыта. Шестая — жилец с ключом ночью: ключ работает всегда.

Теперь поставим скобки иначе: (K ИЛИ C) И НЕ N. В шестой строке получится 0: ночью дверь не откроет даже ключ. Одна пара скобок — и жильцы остались на улице.

Откуда взялась алгебра логики

В середине XIX века английский математик Джордж Буль заметил, что рассуждения можно записывать как уравнения, только вместо чисел в них стоят истина и ложь. Свои идеи он изложил в книгах «Математический анализ логики» (1847) и «Исследование законов мышления» (1854). В его честь правила действий с нулём и единицей называют булевой алгеброй, а во многих языках программирования есть тип данных bool.

Долгое время булева алгебра оставалась занятием математиков. В 1937 году американец Клод Шеннон — тот самый, в чьей статье позже появилось слово «бит», — показал в магистерской работе «Символический анализ релейных и переключательных схем», что формулы Буля описывают электрические цепи: замкнутый контакт — единица, разомкнутый — ноль. С тех пор схемы из переключателей рассчитывают по формулам.

Частые ошибки

• Понимают ИЛИ как «что-то одно». В логике 1 ИЛИ 1 равно 1.
• Забывают порядок действий. НЕ A И B — это (НЕ A) И B. Чтобы отрицать всё выражение, нужны скобки: НЕ (A И B).
• Пропускают строки таблицы. Проверьте их число: для двух высказываний строк 4, для трёх — 8, для четырёх — 16.
• Считают длинное выражение в уме. Заведите столбец для каждого шага, и ошибок станет меньше.

Коротко

• Высказывание либо истинно (1), либо ложно (0).
• A И B равно 1, только когда оба равны 1. A ИЛИ B равно 0, только когда оба равны 0. НЕ A переворачивает значение.
• Порядок действий: НЕ, затем И, затем ИЛИ; скобки его меняют.
• Таблица истинности перечисляет все сочетания значений; для n высказываний в ней 2ⁿ строк.
• Правила действий с истиной и ложью называют булевой алгеброй — по имени Джорджа Буля.

Пока нули и единицы живут только на бумаге. Как заставить электрическую цепь считать их по-настоящему — в уроке От выключателя к транзистору.