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

Представьте, что вам нужно объяснить машине правило: «дверь открывается, если приложена карта сотрудника и сейчас рабочее время, или если нажата кнопка охраны». Машина не понимает слов «и», «или», «если». Она умеет одно: пропускать или не пропускать ток.

Вопрос, на который отвечает эта тема, звучит так: как превратить рассуждение в устройство? Как записать правило формулой, проверить, что формула верна во всех случаях, сократить её до минимума и собрать из проводов.

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

В ЕГЭ тема отвечает за задания 2 и 15, а по сути за гораздо большее: без неё не понять ни условия в программе, ни устройства процессора, ни того, почему if a and b выполняется быстрее, чем кажется.

Может показаться странным, что в курсе информатики изучают раздел математики, придуманный за сто лет до первой ЭВМ. История объясняет всё.

В 1854 году английский математик Джордж Буль (1815–1864) опубликовал работу «Исследование законов мышления». Он предложил записывать рассуждения так же, как записывают арифметику: высказывания обозначать буквами, а связки «и», «или», «не» — операциями. В этой алгебре всего два значения, 0 и 1, и потому её называют двузначной, или булевой.

Почти сто лет идея оставалась математической игрушкой. В 1937 году американский инженер Клод Шеннон (1916–2001) в своей магистерской работе показал: контакты реле ведут себя точно так же, как переменные булевой алгебры. Замкнут — 1, разомкнут — 0; последовательное соединение контактов даёт «И», параллельное — «ИЛИ». А значит, любую логическую формулу можно превратить в электрическую схему, и наоборот — любую схему упростить алгебраически.

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

Полезно помнить и то, что в алгебре логики важны не сами высказывания, а только их истинность. «Волга впадает в Каспийское море» и «2 + 2 = 4» для этой алгебры — одно и то же: два высказывания со значением 1. Поэтому формула работает одинаково и для суждений о мире, и для сигналов в микросхеме.

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

Джордж Буль родился в 1815 году в Линкольне, в семье сапожника. Отец, Джон Буль, чинил обувь без особого усердия, зато увлечённо шлифовал линзы, собирал телескопы и состоял в местном научном обществе. Систематического образования сын не получил: латынь он выучил сам, греческий — сам, математику — тоже сам, по книгам, которые доставал где мог. В шестнадцать лет он пошёл работать помощником учителя, потому что семья разорилась, а в девятнадцать открыл собственную школу.

Человек без диплома, зарабатывающий преподаванием арифметики, начал печатать статьи в математических журналах — и в 1844 году получил за них золотую медаль Лондонского королевского общества. В 1849-м его без учёной степени взяли первым профессором математики в новый колледж в ирландском Корке.

Умер он в 1864 году, сорока девяти лет: прошёл под дождём три мили до колледжа и отчитал лекцию в мокрой одежде; началось воспаление лёгких. Он так и не узнал, что через семьдесят лет его алгебра станет основанием всей вычислительной техники.

Одна деталь для памяти: младшая дочь Буля, Этель Лилиан Войнич, написала роман «Овод» — книгу, которую в Советском Союзе издавали миллионными тиражами. Фамилия Буль в России была известна по роману задолго до того, как стала известна по алгебре.

Вопрос, который редко задают вслух: почему машина считает в двух значениях? Десятичная арифметика привычнее, и первые счётные машины — от арифмометра до Марк I — были именно десятичными.

Причина не в математике, а в физике сигнала. Любой электрический сигнал зашумлён: напряжение плавает от нагрева, от помех, от старения деталей. Если вы условились кодировать десять цифр десятью уровнями напряжения от 0 до 5 вольт, то на каждую цифру приходится половина вольта, и помеха в четверть вольта уже превращает «семь» в «восемь». Схема будет ошибаться постоянно.

Если же значений два, то весь диапазон делится пополам: ниже определённого порога — ноль, выше — единица. Между ними остаётся широкая зона запаса: чтобы ноль прочитался как единица, помеха должна быть размером почти во всё питание. Такого не бывает.

Отсюда и вся конструкция: два значения выбраны не потому, что так красивее, а потому, что двухуровневый сигнал восстанавливается после каждой ступени и ошибка не накапливается. Сигнал проходит через миллион вентилей и на выходе остаётся таким же чётким, каким был на входе.

А как только значений стало два, готовая математика для них уже существовала — булева алгебра, лежавшая без дела восемьдесят лет.

Высказывание — повествовательное предложение, о котором можно определённо сказать, истинно оно или ложно.

Проверка на экзамене простая:

• • — «Москва — столица России» — высказывание, истинно;
• • — «5 больше 7» — высказывание, ложно;
• • — «Который час?» — не высказывание: вопрос;
• • — «Закройте дверь» — не высказывание: побуждение;
• • — «x больше 3» — не высказывание, а высказывательная форма (предикат): истинность зависит от значения x. Это важно для задания 15, где как раз работают с предикатами вида ДЕЛ(n, m).

Логическая переменная обозначает высказывание и принимает значения 0 или 1. Логическая функция (формула) строится из переменных с помощью операций.

Число различных наборов значений для n переменных равно 2ⁿ. Отсюда размер таблицы истинности: для двух переменных 4 строки, для трёх — 8, для четырёх — 16. Это нужно знать не ради формулы, а чтобы оценивать объём перебора: для пяти переменных строк уже 32, и таблицу целиком в задании 2 никто не строит — работают с фрагментом.

Наборы в таблице принято выписывать в порядке возрастания двоичного числа: 000, 001, 010, 011, 100, 101, 110, 111. Такой порядок гарантирует, что ни один набор не потерян и не повторён.

Отрицание ¬A (инверсия, НЕ). Меняет значение на противоположное. В речи — «неверно, что A».

Конъюнкция A∧B (логическое умножение, И). Истинна только когда истинны оба операнда. Легко запомнить через умножение: 1·1=1, всё остальное даёт 0. В речи — «A и B», «как A, так и B».

Дизъюнкция A∨B (логическое сложение, ИЛИ). Ложна только когда ложны оба. В речи — «A или B», причём это неисключающее «или»: если верны оба, дизъюнкция истинна.

Импликация A→B (следование). Ложна в единственном случае: A истинно, B ложно. Это место вызывает больше всего вопросов, поэтому разберём его на бытовом примере.

Обещание: «Если сдам экзамен, куплю торт». Когда обещание нарушено? Только в одном случае: экзамен сдан (A=1), а торта нет (B=0). Если экзамен не сдан, обещание не нарушено независимо от того, куплен торт или нет, — поэтому 0→0 и 0→1 дают 1. Логика не спрашивает, «связаны ли» A и B по смыслу: она смотрит только на значения.

Тождество, которым импликацию заменяют при упрощении: A→B = ¬A∨B. Проверьте по таблице — совпадает во всех четырёх строках.

Эквивалентность A≡B (тождество). Истинна, когда значения совпадают. Тождество: A≡B = (A→B)∧(B→A), а также A≡B = (A∧B)∨(¬A∧¬B).

Приоритет операций (от старшего к младшему): ¬, ∧, ∨, →, ≡. Скобки, как в арифметике, старше всего. Поэтому запись ¬A∧B∨C читается как ((¬A)∧B)∨C, а A∨B→C — как (A∨B)→C.

Самая частая ошибка в задании 2 — посчитать импликацию раньше дизъюнкции. Помните: импликация почти самая слабая операция, слабее неё только эквивалентность.

На импликации спотыкаются все, и спотыкаются в одном и том же месте: почему 0 → 1 = 1 и 0 → 0 = 1? Разберём это не заклинанием, а по сути, потому что в задании 15 импликация стоит почти в каждой формуле.

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

Возьмём правило: «Если число делится на 4, то оно делится на 2». Проверим его на числах.

Число 8: делится на 4 (A = 1) и делится на 2 (B = 1). Правило соблюдено, 1 → 1 = 1. Число 6: на 4 не делится (A = 0), на 2 делится (B = 1). Нарушено ли правило? Нет: правило ничего не обещало про числа, не делящиеся на 4. 0 → 1 = 1. Число 7: не делится ни на 4, ни на 2. Правило снова не нарушено — оно про такие числа молчит. 0 → 0 = 1. Число, которое делится на 4, но не делится на 2, не существует, и именно поэтому правило верно. Если бы такое число нашлось, комбинация 1 → 0 дала бы 0 и опровергла бы правило целиком.

Отсюда рабочая формулировка для экзамена: импликация ищет контрпример. Она равна нулю ровно там, где посылка сработала, а следствие подвело.

И отсюда же главный приём: A → B = ¬A ∨ B. «Либо A не выполнилось, либо B выполнилось» — третьего не дано. Этой заменой начинается решение почти каждого задания 15.

Таблица истинности перечисляет все возможные наборы значений переменных и значение формулы на каждом наборе. Для n переменных наборов ровно 2ⁿ: две переменные — четыре строки, три — восемь, четыре — шестнадцать.

Порядок строк. Наборы записывают в порядке возрастания двоичного числа: 000, 001, 010, 011, 100, 101, 110, 111. Это не прихоть: такой порядок гарантирует, что вы ничего не пропустите и не повторите. Практический приём: в первом столбце половина нулей, потом половина единиц; во втором — четверти; в третьем — чередование через один. Получается «лесенка», которую невозможно сбить.

Промежуточные столбцы. Не пытайтесь вычислить всю формулу в уме. Разбейте её на части и заведите столбец на каждую. Для (A ∧ ¬B) ∨ (B → C) столбцы будут такие: A, B, C, ¬B, A ∧ ¬B, B → C, и только потом результат.

Проверка. Сосчитайте, сколько единиц получилось в итоговом столбце, и подумайте, правдоподобно ли это. У дизъюнкции двух переменных единиц три из четырёх, у конъюнкции — одна. У импликации — три. Если у вас в формуле снаружи стоит импликация, а нулей получилось больше, чем единиц, это повод перепроверить.

Тождественно истинная формула (тавтология) — та, у которой в итоговом столбце все единицы. Тождественно ложная — все нули. Эти понятия прямо нужны в задании 15, где спрашивают, при каких значениях параметра выражение истинно при любых значениях переменных.

Логическая операция — не абстракция: в процессоре ей соответствует физическая схема из транзисторов.

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

Вентиль НЕ (инвертор) собирается из двух транзисторов: когда на входе единица, выход притягивается к нулю, и наоборот.

Вентиль И в простейшем виде — два выключателя последовательно: ток дойдёт до конца, только если замкнуты оба.

Вентиль ИЛИ — два выключателя параллельно: достаточно одного.

Именно это и увидел Шеннон в 1937 году в релейных схемах телефонной станции.

Сколько их в процессоре. В современном процессоре несколько миллиардов транзисторов, то есть сотни миллионов вентилей. Сложение двух 64-битных чисел — это работа схемы из нескольких тысяч вентилей, срабатывающих за доли наносекунды.

Зачем упрощать формулы. Каждый лишний оператор в булевом выражении — это лишние транзисторы, лишняя площадь кристалла, лишнее тепло и лишние наносекунды. Поэтому законы алгебры логики (следующий урок) — не математическое упражнение, а способ сделать процессор меньше и быстрее. Когда вы в задании 15 сворачиваете A ∨ (A ∧ B) в A, вы делаете ровно то, что делает инженер, убирающий из схемы половину деталей.

На экзамене программу пишут на Python, и логические операции там выглядят словами: and, or, not. Но ведут они себя чуть хитрее, чем в учебнике алгебры логики, и это надо знать.

Тип bool наследуется от int. В Python True — это единица, False — ноль, и с ними можно считать: True + True даёт 2, sum([True, False, True]) даёт 2. Приём рабочий: чтобы посчитать, сколько элементов списка удовлетворяют условию, достаточно сложить результаты проверок.

Вычисление сокращённое (ленивое). Выражение a and b вычисляет a, и если оно ложно, к b даже не обращается: результат уже ясен. Так же a or b не смотрит на b, если a истинно. Отсюда безопасная запись x != 0 and 10 / x > 1 — деления на ноль не произойдёт, потому что до него дело не дойдёт.

Возвращается не True/False, а операнд. 2 and 3 даёт 3, 0 or 5 даёт 5. Операция возвращает то значение, на котором остановилась. В условии if это незаметно, но при печати результата удивляет.

Поразрядные операции — другие. Знаки &, |, ^, ~ работают с каждым битом числа отдельно: 12 & 10 даёт 8, потому что 1100 и 1010 совпадают единицами только в старшем разряде. В задачах на логику нужны and/or/not, в задачах на двоичное кодирование — &/|. Перепутать их легко, и ошибка тихая: программа отработает и выдаст неверный ответ.

Руками таблицу на шестнадцать строк строить долго и легко ошибиться. На экзамене разрешён компьютер, и таблицу проще напечатать.

``` from itertools import product

```

Разберём, что здесь написано.

product([0, 1], repeat=4) выдаёт все шестнадцать наборов из нулей и единиц, причём в том же порядке, в каком их пишут в таблице истинности: 0000, 0001, 0010 и так далее. Перебор гарантированно полный.

Эквивалентность y ≡ w записывается как w == y, импликация x → z — как x <= z. Второе неочевидно, но проверяется по таблице: x <= z ложно только при x = 1, z = 0 — ровно там же, где ложна импликация. Это самая удобная запись импликации в Python.

if F == 0 печатает только строки, где функция ложна, — а именно такой фрагмент и дают в задании 2.

Что важно понять про машину. Программа не «понимает» формулу: она честно перебирает все 2ⁿ наборов и для каждого вычисляет выражение. Для четырёх переменных это 16 шагов — мгновение. Для тридцати переменных было бы больше миллиарда наборов, и та же программа считала бы минуты. Рост 2ⁿ — та самая причина, по которой в следующем уроке мы учимся упрощать формулу вместо перебора.