Законы алгебры логики

Вот формула из настоящего задания 15: ДЕЛ(x, A) → (¬ДЕЛ(x, 21) ∨ ДЕЛ(x, 35)). Сколько строк в её таблице истинности?

Ответ: бесконечно много. Переменная x пробегает все натуральные числа, и таблицу построить нельзя в принципе. Перебор здесь не инструмент, а тупик.

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

Это ровно то, чем занимается обычная школьная алгебра. Никто не проверяет (a + b)² = a² + 2ab + b² подстановкой чисел — формулу преобразуют по правилам. Разница в том, что в булевой алгебре правил меньше, они проще, и есть несколько таких, аналогов которым в арифметике нет вовсе. Их-то и надо выучить.

Таблицу истинности для пяти переменных придётся строить на 32 строки, для десяти — на 1024. Законы алгебры логики позволяют свернуть формулу и решить задачу без перебора. Это не украшение курса: в заданиях 2 и 15 упрощение экономит большую часть времени.

Переместительный (коммутативный) закон: A∧B = B∧A, A∨B = B∨A. Сочетательный (ассоциативный): (A∧B)∧C = A∧(B∧C), (A∨B)∨C = A∨(B∨C). Распределительный (дистрибутивный): — A∧(B∨C) = (A∧B)∨(A∧C) — привычен, он как раскрытие скобок в алгебре; — A∨(B∧C) = (A∨B)∧(A∨C) — непривычен, второго такого в арифметике нет. Именно он чаще всего нужен.

Законы де Моргана — главный инструмент при работе с отрицанием: — ¬(A∧B) = ¬A∨¬B; — ¬(A∨B) = ¬A∧¬B.

Словами: отрицание меняет операцию на противоположную и переносится внутрь на каждый операнд. «Неверно, что идёт дождь и холодно» означает «нет дождя или не холодно».

Законы идемпотентности: A∧A = A, A∨A = A. Законы поглощения: A∨(A∧B) = A, A∧(A∨B) = A. Законы склеивания: (A∧B)∨(A∧¬B) = A, (A∨B)∧(A∨¬B) = A. Двойное отрицание: ¬¬A = A. Законы противоречия и исключённого третьего: A∧¬A = 0, A∨¬A = 1. Операции с константами: A∧1 = A, A∧0 = 0, A∨1 = 1, A∨0 = A.

Два последних набора — самые полезные на практике: как только в формуле появилось A∧¬A, всё выражение обнуляется, а A∨1 сразу даёт единицу.

Любое тождество проверяется механически: строим таблицу для левой части, строим для правой, сравниваем столбцы. Если они совпали во всех строках — тождество верно.

Проверим закон де Моргана ¬(A ∨ B) = ¬A ∧ ¬B.

При A=0, B=0: слева ¬(0∨0) = ¬0 = 1; справа 1 ∧ 1 = 1. Совпало. При A=0, B=1: слева ¬(0∨1) = ¬1 = 0; справа 1 ∧ 0 = 0. Совпало. При A=1, B=0: слева ¬1 = 0; справа 0 ∧ 1 = 0. Совпало. При A=1, B=1: слева ¬1 = 0; справа 0 ∧ 0 = 0. Совпало.

Четыре строки — закон доказан.

Почему это работает. В алгебре логики переменных конечное число значений, поэтому полный перебор является строгим доказательством. В обычной алгебре так нельзя: проверить (a+b)² = a² + 2ab + b² на четырёх парах чисел не значит доказать.

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

И обратный приём. Иногда проще не преобразовывать формулу, а подставить конкретные значения и посмотреть, что получится. Если при A=1 выражение становится тождественно истинным независимо от остальных переменных, значит, в нём есть кусок вида A ∨ ….

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

Огастес де Морган родился в 1806 году на юге Индии, где служил его отец; в младенчестве он потерял зрение на один глаз. Учился в Кембридже, но кафедры там не получил: занять место преподавателя можно было, только принеся религиозную присягу, а де Морган отказался. В 1828 году, двадцати двух лет, он стал первым профессором математики только что открытого Университетского колледжа Лондона — единственного заведения в Англии, где для этого ничего подписывать не требовалось.

Из этого колледжа он дважды уходил в отставку в знак протеста против решений руководства. Он отказался от почётной учёной степени и от избрания в Королевское общество, считая и то и другое несправедливо устроенным. На похоронах его почти никого не было — он сам просил, чтобы не было.

При этом именно он учил математике Аду Лавлейс — ту самую, которая написала первую программу для аналитической машины Бэббиджа. И именно он в книге «Формальная логика» 1847 года — в том же году, что и Буль свою первую работу, — сформулировал два равенства, которые вы будете применять чаще всех остальных.

Де Морган и Буль переписывались и читали друг друга. Из их двух книг, вышедших одна за другой, и выросла современная математическая логика.

Формулы ¬(A ∧ B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A ∧ ¬B запоминаются быстрее, если один раз понять их смысл.

Возьмём утверждение: «Идёт дождь и холодно». Когда оно ложно? Когда нарушено хотя бы одно из двух условий: либо дождя нет, либо не холодно (или и то и другое). Опровергнуть «и» легко — достаточно опровергнуть одну половину. Это и есть первый закон.

Теперь: «Я поеду на поезде или на автобусе». Когда это ложно? Только если оба варианта отпали: и на поезде не поехал, и на автобусе. Опровергнуть «или» тяжело — нужно опровергнуть всё. Это второй закон.

Отсюда правило в одну строку: отрицание проходит внутрь скобки и по дороге переворачивает связку. И наоборот, если вы «сворачиваете» выражение обратно, связка переворачивается снова.

Где это нужно каждый день. Программист пишет условие if not (age >= 18 and has_passport). Читать такое неудобно, и его переписывают: if age < 18 or not has_passport — «либо несовершеннолетний, либо без паспорта». Это буквально закон де Моргана, применённый вручную. Компилятор делает то же самое автоматически, чтобы схема получилась короче.

И типичная ошибка экзамена. Отрицая скобку, забывают поменять операцию: пишут ¬(A ∧ B) = ¬A ∧ ¬B. Проверьте на наборе A = 1, B = 0: слева ¬(1 ∧ 0) = ¬0 = 1, справа 0 ∧ 1 = 0. Не совпало — значит, равенство неверно. Тридцать секунд проверки спасают всю задачу.

Два закона выглядят похоже и оба экономят больше всего работы.

Поглощение: A ∨ (A ∧ B) = A. Почему? Если A = 1, то левая часть равна 1 сразу, по первому слагаемому. Если A = 0, то первое слагаемое 0, а второе 0 ∧ B = 0, и вся дизъюнкция равна 0. Итого левая часть всегда равна A, что бы ни делало B. Второе слагаемое лишнее — оно «поглощается».

Парный вариант: A ∧ (A ∨ B) = A. Проверяется так же.

Склеивание: (A ∧ B) ∨ (A ∧ ¬B) = A. Здесь общий множитель A, а B встречается и с отрицанием, и без. Выносим: A ∧ (B ∨ ¬B) = A ∧ 1 = A. Иначе говоря, если значение B не влияет на результат, переменную B выбрасывают.

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

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

Порядок, который почти всегда приводит к результату:

Шаг 1. Избавиться от импликаций и эквивалентностей. Заменяем A→B на ¬A∨B, а A≡B на (A∧B)∨(¬A∧¬B) либо на ¬(A⊕B), если так удобнее. После этого в формуле остаются только ¬, ∧, ∨ — и все законы применимы.

Шаг 2. Опустить отрицания вниз по де Моргану, пока каждое отрицание не встанет перед отдельной переменной. Заодно убираем двойные отрицания.

Шаг 3. Раскрыть скобки или, наоборот, вынести общий множитель — смотря что короче. Ориентир: если после раскрытия появляются пары вида X и ¬X, раскрывать стоит, дальше сработают законы противоречия.

Шаг 4. Применить поглощение и склеивание. Ищите фрагменты A∨(A∧B) и (A∧B)∨(A∧¬B) — они схлопываются в один член.

Шаг 5. Проверить результат на одном-двух наборах значений. Подставьте, например, все нули и все единицы в исходную и упрощённую формулы. Если значения совпали, вероятность ошибки резко падает; если нет — ошибка точно есть.

Пример разбора. Упростим ¬(A→B)∨(A∧B).

Шаг 1: A→B заменяем на ¬A∨B, получаем ¬(¬A∨B)∨(A∧B). Шаг 2: по де Моргану ¬(¬A∨B) = A∧¬B. Формула принимает вид (A∧¬B)∨(A∧B). Шаг 4: это в точности закон склеивания — общий A, а второй множитель встречается и с отрицанием, и без. Результат: A.

Проверка: при A=1, B=0 исходная формула равна ¬(1→0)∨(1∧0) = ¬0∨0 = 1, и A=1. При A=0, B=1 исходная равна ¬(0→1)∨(0∧1) = ¬1∨0 = 0, и A=0. Совпало.

Упростим (A → B) ∧ (A → ¬B).

Шаг 1. Избавляемся от импликаций: A → B = ¬A ∨ B. Получаем (¬A ∨ B) ∧ (¬A ∨ ¬B).

Шаг 2. Замечаем общий член ¬A и применяем распределительный закон в обратную сторону: (¬A ∨ B) ∧ (¬A ∨ ¬B) = ¬A ∨ (B ∧ ¬B).

Шаг 3. По закону противоречия B ∧ ¬B = 0. Получаем ¬A ∨ 0.

Шаг 4. По закону с константой X ∨ 0 = X. Итог: ¬A.

Проверка таблицей. При A = 0 исходное выражение: (0→B) ∧ (0→¬B) = 1 ∧ 1 = 1. И ¬A = 1. При A = 1: (1→B) ∧ (1→¬B) = B ∧ ¬B = 0. И ¬A = 0. Совпало на всех наборах.

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

Второй пример. Упростим ¬(¬A ∧ B) ∨ B. По де Моргану: (A ∨ ¬B) ∨ B. По сочетательному закону: A ∨ (¬B ∨ B). По закону исключённого третьего: A ∨ 1. По закону с константой: 1. Выражение тождественно истинно: оно верно при любых значениях переменных.

Посмотрим, что даёт алгебра на настоящем экзаменационном сюжете.

Пусть требуется, чтобы выражение (x ∈ A) → ((x ∈ P) → (x ∈ Q)) было истинно при любом x. Перебирать нечего: x пробегает всю числовую прямую.

Шаг 1. Убираем импликации, начиная с внутренней: (x ∈ P) → (x ∈ Q) превращается в ¬(x ∈ P) ∨ (x ∈ Q). Внешняя импликация даёт ¬(x ∈ A) ∨ (¬(x ∈ P) ∨ (x ∈ Q)).

Шаг 2. Скобки внутри дизъюнкции не нужны — по сочетательному закону: ¬(x ∈ A) ∨ ¬(x ∈ P) ∨ (x ∈ Q).

Шаг 3. Читаем результат словами. Выражение ложно только тогда, когда все три слагаемых ложны, то есть когда x одновременно принадлежит A, принадлежит P и не принадлежит Q.

Шаг 4. Требование «истинно при любом x» означает, что такого x не существует. Значит, пересечение A и P целиком лежит внутри Q.

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

Общее правило, которое стоит запомнить. Импликация (x ∈ P) → (x ∈ Q) тождественно истинна тогда и только тогда, когда P ⊆ Q: всякий элемент P лежит в Q. Это не отдельный факт, а прямое следствие того, что импликация ложна лишь при «истинно → ложно».

Операций в алгебре логики пять, вентилей в схемотехнике десятки. Но для того, чтобы выразить любую логическую функцию, достаточно трёх: И, ИЛИ, НЕ. Такой набор называют функционально полным.

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

Дальше — удивительное. Полон даже один элемент: И-НЕ, то есть ¬(A ∧ B) (его называют штрихом Шеффера). Убедимся:

отрицание — ¬A = ¬(A ∧ A), то есть подаём A на оба входа; конъюнкция — A ∧ B = ¬(¬(A ∧ B)), то есть И-НЕ и следом ещё один И-НЕ в роли инвертора; дизъюнкция — по де Моргану A ∨ B = ¬(¬A ∧ ¬B), то есть два инвертора и один И-НЕ.

Всё выражается. То же верно для одного только элемента ИЛИ-НЕ (стрелка Пирса).

Зачем это на производстве. Микросхему проще и дешевле делать, когда на кристалле повторяется одна и та же ячейка. Поэтому целые семейства логики строились на одних вентилях И-НЕ: технология отлажена под единственный элемент, а из него собирается всё остальное.

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

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

• • СДНФ (совершенная дизъюнктивная нормальная форма). Алгоритм:
• • выбрать все строки, где функция равна 1;
• • для каждой такой строки написать конъюнкцию всех переменных: переменная берётся без отрицания, если в строке она равна 1, и с отрицанием, если 0;
• • соединить полученные конъюнкции дизъюнкциями.

Пример. Функция от двух переменных равна 1 в строках (A=0, B=1) и (A=1, B=1). Первая строка даёт ¬A ∧ B, вторая — A ∧ B. СДНФ: (¬A ∧ B) ∨ (A ∧ B). Её, кстати, можно упростить по распределительному закону: (¬A ∨ A) ∧ B = 1 ∧ B = B. Действительно, функция равна единице ровно тогда, когда B = 1.

• • СКНФ (совершенная конъюнктивная нормальная форма). Алгоритм зеркальный:
• • выбрать все строки, где функция равна 0;
• • для каждой написать дизъюнкцию всех переменных: переменная берётся с отрицанием, если в строке она равна 1, и без отрицания, если 0 (всё наоборот по сравнению с СДНФ);
• • соединить дизъюнкции конъюнкциями.

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

На экзамене СДНФ прямо не спрашивают, но понимание её алгоритма помогает в задании 2: вы видите, как строка таблицы соответствует набору значений, и наоборот.

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

``` from itertools import product

```

Если программа ничего не напечатала, равенство верно на всех наборах, то есть верно вообще: переменных конечное число, перебор полный, и это строгое доказательство.

Чем это отличается от обычной алгебры. Проверить (a + b)² = a² + 2ab + b² на восьми парах чисел ничего не докажет: чисел бесконечно много. В булевой алгебре наборов ровно 2ⁿ, поэтому полный перебор является доказательством. Это редкая роскошь, и ею надо пользоваться.

На экзамене. В заданиях 2 и 15 компьютер под рукой. Разумная тактика: упростить формулу на бумаге, а потом проверить своё упрощение перебором. Если расхождение нашлось — вы узнали об этом за десять секунд, а не после объявления баллов.