Законы логики: как упростить выражение и схему

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

Какие выражения считают равными

Мама говорит: «Гулять пойдёшь, когда сделаешь уроки и уберёшь в комнате». Вы уточняете: «То есть не пойду, если не сделаю уроки или не уберу?» Слова разные, а правило одно: в любой ситуации обе фразы дают один и тот же ответ.

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

Законы в одной таблице

Почти у каждого закона есть пара: поменяйте И на ИЛИ, а 0 на 1 — и получится второй закон.

Ещё один закон пары не имеет — двойное отрицание: НЕ НЕ A = A.

Что законы значат на обычном языке

• Переместительный и сочетательный. Порядок проверок не важен: «пароль верный и код верный» — то же самое, что «код верный и пароль верный».
• Распределительный. Общую часть выносят за скобки, как в арифметике. «Беру зонт и иду пешком или беру зонт и еду на самокате» — это «беру зонт и (иду пешком или еду на самокате)». Вторая форма закона в арифметике не работает, а в логике верна.
• Действия с 0 и 1. Условие, которое всегда истинно, в операции И ничего не меняет: A И 1 = A. А в операции ИЛИ оно решает всё: A ИЛИ 1 = 1.
• Повторение. Сказать одно и то же дважды — не значит сказать больше.
• Высказывание и его отрицание. Дверь не бывает сразу и открытой, и не открытой: A И НЕ A = 0. Зато одно из двух верно всегда: A ИЛИ НЕ A = 1.
• Двойное отрицание. «Не могу не согласиться» означает «согласен».
• Поглощение. «В кино пустят, если есть билет или если есть билет и попкорн». Попкорн ничего не решает: пустят всех, у кого билет.
• Законы де Моргана. Отрицание входит в скобки, а операция меняется на противоположную. «Неверно, что в рюкзаке лежат и учебник, и тетрадь» — значит, нет учебника или нет тетради. «Неверно, что завтра контрольная или диктант» — значит, не будет ни контрольной, ни диктанта. Законы названы в честь британского математика Огастеса де Моргана, современника Джорджа Буля.

Как доказать закон

В арифметике правило нельзя проверить на всех числах: их бесконечно много. В логике можно: у двух букв всего четыре сочетания значений. Составим таблицу для обеих частей первого закона де Моргана.

Четвёртый и последний столбцы совпали во всех строках — закон доказан. Так проверяют любой закон и любое упрощение. Совпали столбцы — выражения равны. Нашлась хотя бы одна строка с разными значениями — не равны.

Упрощаем по шагам

Пример 1. Программист записал, когда показывать значок «Новое» в мессенджере: «сообщение не прочитано и чат закреплён или сообщение не прочитано и чат не закреплён». Пусть A — «сообщение не прочитано», B — «чат закреплён».

A И B ИЛИ A И НЕ B
= A И (B ИЛИ НЕ B)       вынесли A за скобки
= A И 1                  B ИЛИ НЕ B = 1
= A                      A И 1 = A

Закреплён чат или нет — неважно. Четыре вентиля заменил один провод.

Пример 2. Условие входа записали так: «неверно, что пароль неверный или код неверный». Пусть A — «пароль верный», B — «код верный».

НЕ (НЕ A ИЛИ НЕ B)
= НЕ НЕ A И НЕ НЕ B      закон де Моргана
= A И B                  двойное отрицание

Пример 3. В кафе скидку дают тем, у кого есть карта школьника, а ещё тем, у кого карты нет, но сегодня день рождения. Пусть A — «есть карта», B — «сегодня день рождения».

A ИЛИ НЕ A И B
= (A ИЛИ НЕ A) И (A ИЛИ B)     распределительный закон
= 1 И (A ИЛИ B)                A ИЛИ НЕ A = 1
= A ИЛИ B                      действия с 1

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

Зачем это инженеру

Каждый вентиль — это несколько транзисторов: они занимают место на кристалле и расходуют энергию. К тому же вентиль срабатывает не мгновенно: сигнал задерживается в нём на крошечную долю секунды. Чем меньше вентилей стоит на пути сигнала, тем быстрее схема даёт ответ.

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

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

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

• В законе де Моргана забывают сменить операцию. НЕ (A И B) — это НЕ A ИЛИ НЕ B, а не НЕ A И НЕ B.
• Путают действия с 0 и 1. A ИЛИ 1 равно 1, а не A. A И 0 равно 0, а не A.
• Выносят за скобки и теряют единицу. A ИЛИ A И B — это A И (1 ИЛИ B), то есть A И 1. От вынесенной буквы в скобках остаётся 1, а не пустое место.
• Проверяют упрощение на одной-двух строках. Выражения равны, только если совпали все строки таблицы.

Коротко

• Выражения равны, если их таблицы истинности совпадают во всех строках.
• Любой закон логики можно доказать таблицей истинности.
• При упрощении чаще всего помогают вынесение за скобки, поглощение, законы де Моргана и правила A ИЛИ НЕ A = 1, A И НЕ A = 0.
• По законам де Моргана отрицание входит в скобки, а И и ИЛИ меняются местами.
• Чем меньше вентилей, тем схема дешевле, быстрее и экономнее.

Теперь у нас есть всё, чтобы собрать из вентилей что-то полезное. Начнём со схемы, которая складывает числа, — урок Сумматор: как сложить два числа проводами.