Построение логической схемы по выражению: алгоритм

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

Из чего состоит логическая схема

В курсах информатики и по ГОСТ 2.743-91 логические элементы обозначаются не привычными по формулам символами $\wedge$, $\vee$, $\neg$, а короткими значками внутри прямоугольника:

• & (конъюнктор) - элемент И, на выходе 1 только если на всех входах 1;
• 1 (дизъюнктор) - элемент ИЛИ, на выходе 1, если хотя бы на одном входе 1;
• 1 с кружком на выходе (инвертор) - элемент НЕ, меняет значение входа на противоположное.

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

Приоритет операций как порядок сборки

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

1. Сначала строятся элементы, которые берут на вход только исходные переменные, - это операции с самым высоким приоритетом в своей части выражения.
2. Затем строятся элементы, которые берут на вход выход уже собранных гейтов.
3. Так продолжается, пока не будет собран последний гейт, - его выход и есть результат всего выражения F.

Возьмём выражение $F = (A \wedge B) \vee \neg C$. Внутри него нет вложенных скобок, поэтому первый шаг - сразу два независимых гейта: конъюнктор для $A \wedge B$ и инвертор для $\neg C$. Оба они не зависят друг от друга, поэтому их можно рисовать в любом порядке между собой, но обязательно раньше финального элемента. Второй шаг - дизъюнктор, который объединяет выходы этих двух гейтов и выдаёт F. Всего два шага сборки и три элемента: это ровно то, что показывает калькулятор выше на первом пресете.

Рассчитать для своей задачи

Как схема вычисляет значение выражения

Когда схема полностью собрана, она работает как калькулятор: подставляем значения на входы, и сигнал бежит по проводам через гейты к выходу. У каждого провода в любой момент есть конкретное значение - 0 или 1, - а не абстрактная переменная, и именно это значение красят зелёным (1) или красным (0) на калькуляторе выше. Такой пошаговый просчёт удобно проверять руками: возьмём $A = 1$, $B = 0$, $C = 0$. Конъюнктор $A \wedge B$ получает на входы 1 и 0 и выдаёт 0. Инвертор $\neg C$ получает 0 и выдаёт 1. Финальный дизъюнктор получает 0 и 1 и выдаёт итоговое значение F = 1. Ровно эти же числа встают на провода в анимации выше: сигнал последовательно проходит через уже построенные гейты, и результат на выходе совпадает со значением формулы, посчитанным вручную.

Разбор примера со вложенным отрицанием

Второй пресет калькулятора, $F = \neg(A \wedge B) \vee (C \wedge \neg D)$, показывает более сложный случай: отрицание стоит не у одной переменной, а у целой скобки $(A \wedge B)$. Порядок сборки здесь такой:

1. Шаг 1: конъюнктор $A \wedge B$ и инвертор $\neg D$ - оба берут только исходные переменные.
2. Шаг 2: инвертор, который берёт на вход уже готовый выход конъюнктора $A \wedge B$ (это и есть $\neg(A \wedge B)$), и второй конъюнктор, который берёт переменную C и выход инвертора $\neg D$.
3. Шаг 3: финальный дизъюнктор объединяет результаты двух веток шага 2 и выдаёт F.

Частая ошибка - попытаться сразу инвертировать переменные A и B по отдельности вместо того, чтобы сначала собрать конъюнктор, а потом инвертировать уже его выход. $\neg(A \wedge B)$ и $\neg A \wedge \neg B$ - это разные функции (первая равна $\neg A \vee \neg B$ по правилу де Моргана), и схема для них будет собрана по-разному: во втором случае инверторы стояли бы сразу на входах A и B, а не после конъюнктора.

Как из И, ИЛИ, НЕ собрать исключающее ИЛИ

Базовых элементов И, ИЛИ и НЕ достаточно, чтобы собрать любую логическую функцию, включая те, для которых на схемах иногда рисуют отдельный значок, например исключающее ИЛИ (XOR). Третий пресет калькулятора использует тождество $A \oplus B = (A \vee B) \wedge (\neg A \vee \neg B)$: сначала два независимых гейта первого шага - дизъюнктор $A \vee B$ и два инвертора $\neg A$, $\neg B$; на втором шаге инверторы объединяются дизъюнктором; на третьем шаге результат первого дизъюнктора и результат второго дизъюнктора соединяются конъюнктором, который и даёт исключающее ИЛИ.

Рассчитать для своей задачи

Проверить тождество легко на конкретных значениях: при $A = 1$, $B = 0$ дизъюнктор $A \vee B$ даёт 1, инверторы дают $\neg A = 0$ и $\neg B = 1$, их дизъюнкция равна 1, а финальный конъюнктор $1 \wedge 1 = 1$ - ровно то, что даёт исключающее ИЛИ для несовпадающих значений A и B.

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

• Перепутать элемент НЕ с ИЛИ. Внутри обоих прямоугольников пишут цифру 1, а различает их только маленький кружок-инверсия на выходном проводе. Пропустили кружок - прочитали схему неверно.
• Собирать гейты в произвольном порядке, а не по приоритету. Пока не построен гейт для операции с более высоким приоритетом, строить гейт, который берёт его выход, нельзя, - просто не с чего брать сигнал.
• Инвертировать переменные по отдельности вместо целой скобки. $\neg(A \wedge B)$ - это инвертор ПОСЛЕ конъюнктора, а не два инвертора ДО него на входах A и B.
• Забыть, что один и тот же провод может идти на несколько входов. Если переменная входит в выражение дважды, от неё проводят два провода к разным гейтам, а не дублируют саму переменную.
• Перепутать число входов у гейта. У элементов И и ИЛИ на схеме может быть больше двух входов, если операция применяется сразу к трём и более переменным подряд без скобок; у элемента НЕ всегда ровно один вход.

FAQ

Сколько логических элементов нужно для выражения $F = (A \wedge B) \vee \neg C$? Три: один конъюнктор для $A \wedge B$, один инвертор для $\neg C$ и один дизъюнктор, который объединяет их выходы в F.

Как понять, в каком порядке рисовать гейты по выражению? Смотреть на приоритет операций: отрицание сильнее конъюнкции, конъюнкция сильнее дизъюнкции. Сначала строятся гейты для операций с самым высоким приоритетом в своей части выражения, а гейты, объединяющие их результаты, - позже.

Можно ли собрать любую логическую функцию только из И, ИЛИ и НЕ? Да, набор {И, ИЛИ, НЕ} функционально полон: любую логическую функцию, включая исключающее ИЛИ, импликацию и эквивалентность, можно выразить через эти три элемента.

Коротко

Логическая схема собирается снизу вверх по дереву выражения: сначала гейты, которые берут только исходные переменные, затем гейты, которые берут выходы уже построенных элементов, и так до финального гейта, чей выход равен F. Обозначения по ГОСТ - & для И, 1 для ИЛИ, 1 с кружком-инверсией на выходе для НЕ, и именно кружок отличает инвертор от дизъюнктора. Любое логическое выражение, сколь угодно длинное, раскладывается на такую последовательность шагов, если строго следовать приоритету операций.