Логические схемы и булевы функции

Что такое логические схемы

Логическая схема — это устройство, которое преобразует входные двоичные сигналы (0 и 1) в выходные по правилам алгебры логики. На таких схемах построены процессоры, оперативная память и все цифровые устройства. В основе лежат булевы функции — функции, аргументы и значения которых принимают только два состояния: ложь (0) и истина (1).

Алгебру логики разработал английский математик Джордж Буль, поэтому функции и называют булевыми. Школьный курс одиннадцатого класса опирается на эти понятия и при изучении логики, и при подготовке к экзамену, где встречаются задачи на построение таблиц истинности и упрощение выражений.

Базовые логические элементы

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

• Инвертор (операция НЕ) — меняет сигнал на противоположный: из 0 делает 1 и наоборот.
• Конъюнктор (операция И) — выдаёт 1 только тогда, когда оба входа равны 1.
• Дизъюнктор (операция ИЛИ) — выдаёт 1, если хотя бы один вход равен 1.

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

Таблица истинности

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

Разбор примера

Построим значение для выражения F = (A или B) и (не C). Сначала вычисляем скобку с операцией ИЛИ, затем отрицание переменной C, потом перемножаем результаты конъюнкцией:

A=1, B=0, C=0 -> (1 или 0)=1, (не 0)=1, F = 1 и 1 = 1 A=0, B=0, C=1 -> (0 или 0)=0, (не 1)=0, F = 0 и 0 = 0

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

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

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

Упрощать выражения помогают законы: переместительный, сочетательный, распределительный и законы де Моргана. Например, по закону де Моргана отрицание конъюнкции равно дизъюнкции отрицаний: не (A и B) = (не A) или (не B). Упрощение позволяет собрать ту же функцию из меньшего числа элементов, что удешевляет и ускоряет схему. Также полезны законы поглощения и склеивания, убирающие лишние слагаемые.

Кратко о главном

• Логическая схема преобразует двоичные сигналы по правилам алгебры логики.
• Базовые элементы — НЕ, И, ИЛИ; из них собирают любую функцию.
• Таблица истинности перечисляет все наборы входов и результат.
• Порядок операций: сначала НЕ, потом И, затем ИЛИ; скобки его меняют.
• Законы де Моргана и другие позволяют упрощать схемы.