Основы булевой алгебры -- AND / OR / NOT / XOR
Булева алгебра — математическая основа всех цифровых схем; комбинации четырёх базовых логических операций позволяют строить сколь угодно сложные схемы.
Аналогия из жизни: автоматические двери и системы контроля доступа
При входе в здание с высоким уровнем безопасности вы столкнётесь с различными правилами контроля доступа. Эти правила как раз точно соответствуют базовым операциям булевой алгебры; давайте разберём их на повседневных примерах.
Элемент И — чтобы войти, две двери должны быть открыты одновременно: В одном хранилище для открытия нужно одновременно повернуть два ключа. Только когда оба ключа вставлены и повёрнуты (оба входа равны 1), дверь откроется (выход равен 1). Если хотя бы одного ключа нет, дверь остаётся неподвижной.
Элемент ИЛИ — если открыта хотя бы одна дверь, можно войти: В офисном здании есть два входа; если открыта передняя или задняя дверь, можно войти. Если открыт любой вход (хотя бы один вход равен 1), можно пройти (выход равен 1).
Элемент НЕ — кнопка переключает состояние: У входа в туалет есть перекидная табличка «Свободно/Занято»; нажатие кнопки переключает текущее состояние. При входе 0 (свободно) выход равен 1 (занято), и наоборот.
Элемент XOR (исключающее ИЛИ) — две лампы в комнате должны быть в состояниях: одна включена, другая выключена: В комнате есть две лампы, и правило таково: две лампы должны находиться в противоположных состояниях (одна включена, другая выключена); иначе срабатывает система сигнализации. Следовательно, когда два входа различаются, выход равен 1; когда они одинаковы, выход равен 0.
Краткая история булевой алгебры
Булева алгебра была разработана британским математикомДжорджем БулемВ 1854 году булева алгебра была впервые систематически изложена в работе «Исследование законов мышления». Целью Буля было математизировать человеческое логическое рассуждение; он создал метод использования алгебраических символов для представления «истины» и «лжи».
В 1938 годуКлод ШеннонВ своей магистерской диссертации в MIT он доказал, что булеву алгебру можно использовать для описания и упрощения релейных переключательных схем. Эта работа, известная как «самая важная магистерская диссертация в истории», заложила теоретическую основу для всего проектирования цифровых схем.
Можно сказать, что без булевой алгебры не было бы цифровых схем, а без цифровых схем не было бы современных компьютеров. Внутри устройства, на котором вы читаете этот текст, каждую секунду выполняются сотни миллионов логических операций.
Подробное объяснение четырёх основных логических операций
Операция AND
Правило операции AND состоит всего из одного предложения:Выход равен 1 только тогда, когда все входы равны 1.; в противном случае выход равен 0. Это можно представить как последовательно соединённые переключатели — оба переключателя должны быть замкнуты, чтобы лампочка загорелась.
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Логическое выражение:Y = A · B(Иногда точку опускают и записывают прямо как Y = AB). Мнемоническое правило: выход равен 1 только тогда, когда все входы равны 1.
Операция OR
Правила операции OR:Если хотя бы один вход равен 1, выход равен 1; выход равен 0 только тогда, когда все входы равны 0. Аналогично параллельно соединённым переключателям — если любой переключатель замкнут, лампочка загорается.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Логическое выражение:Y = A + B(Обратите внимание, что это не арифметическое сложение; в булевой алгебре 1+1 всё равно равно 1). Мнемоническое правило: любая 1 даёт 1.
Операция NOT
NOT — единственная базовая операция, которая принимает ровно один вход, и её правило самое простое:Выход является инверсией входаЕсли вход равен 1, выход равен 0; если вход равен 0, выход равен 1.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Логическое выражение:Y = A'илиY = NOT AВ схемах на входной линии небольшой кружок обычно используется для обозначения инверсии. Мнемоника: 0 становится 1, 1 становится 0.
Операция XOR (исключающее ИЛИ)
Правила XOR:Когда два входа различаются, выход 1; когда они одинаковы, выход 0. XOR реализуется комбинацией AND, OR, NOT. Реализация: A XOR B = (A' · B) + (A · B').
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Логическое выражение:Y = A XOR BXOR имеет множество применений в таких областях, как проектирование сумматоров, проверка чётности и шифрование данных. Мнемоника: разные входы дают 1.
Символы логических элементов
На схемах цифровых устройств каждой базовой логической операции соответствует стандартное условное обозначение логического элемента:
Элемент AND: символ имеет D-образную форму — прямая сторона плюс полукруглая дуга, две входные линии слева и одна выходная линия справа.
Элемент OR: символ имеет форму щита — вогнутая дуга, сходящаяся к заострённому кончику сзади, отражающая логический смысл «или».
Элемент NOT (инвертор): треугольник, за которым следует маленький кружок — треугольник обозначает буферизацию/усиление, а кружок обозначает инверсию сигнала.
Элемент XOR: по форме похож на элемент OR, но перед дугой со стороны входов добавлена дополнительная дуга, чтобы отличать «исключающее ИЛИ».
Любая сложная цифровая схема — включая арифметическое устройство и устройство управления внутри CPU — в конечном счёте может быть разложена на комбинации этих четырёх базовых логических элементов. Это фундаментальная причина, по которой булева алгебра является теоретической основой цифровых схем.
Приложение: SVG-значки логических элементов и интерактивные таблицы истинности (пример демонстрации)
Ниже приведены стандартные обозначения четырёх базовых логических элементов, а также интерактивная таблица истинности — нажимайте кнопки A и B, чтобы переключать входы и наблюдать изменение выходов в соответствующих строках.
Стандартные обозначения четырёх логических элементов
Интерактивная таблица истинности — нажимайте кнопки, чтобы переключать входы
Нажимайте кнопки A и B ниже, чтобы переключаться между 0/1, и наблюдайте, как соответствующие строки входов в таблице подсвечиваются
| A | B | AND | OR | NOT A | NOT B | Исключающее ИЛИ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Интерактивная демонстрация
Нажмите кнопки ниже, чтобы переключить значения входов A и B (0 или 1), и наблюдайте, как выходы каждого логического элемента изменяются в реальном времени:
Интерактивная демонстрация логического элемента (пример демонстрации)
Нажмите кнопки ниже, чтобы переключить значения входов A и B
| Логический элемент | Логические выражения | Текущий выход | Мнемоника |
|---|---|---|---|
| Элемент AND | A AND B | - | 1 только если все 1 |
| Элемент OR | A OR B | - | 1, если хотя бы одна 1 |
| Элемент NOT | NOT A | - | 0 становится 1, 1 становится 0 |
| Элемент NOT | NOT B | - | 0 становится 1, 1 становится 0 |
| Логический элемент XOR | A XOR B | - | Различие — это 1 |
Демонстрация кода Python
Ниже Python используется для реализации функций четырёх базовых логических операций, автоматически генерируя полные таблицы истинности и также проверяя законы де Моргана:
Пример
def AND(a, b):
"""Операция AND: все 1, тогда 1"""
return 1 if a == 1 and b == 1 else 0
def OR(a, b):
"""Операция OR: если есть хотя бы одна 1, результат 1"""
return 1 if a == 1 or b == 1 else 0
def NOT(a):
"""Операция NOT: инвертировать"""
return 1 if a == 0 else 0
def XOR(a, b):
"""Операция XOR: разные значения дают 1"""
return 1 if a != b else 0
def print_truth_table(title, func, inputs):
"""Универсальная функция вывода таблицы истинности"""
print(f"\n{'='*40}")
print(f" {title}")
print(f"{'='*40}")
if func.__code__.co_argcount == 1:
print(f" {'A':>4} | {'выход':>4}")
print(f" {'-'*13}")
for a in inputs:
print(f" {a:>4} | {func(a):>4}")
else:
print(f{'A':>4} | {'B':>4} | {'Выход':>4})
print(f" {'-'*20}")
for a in inputs:
for b in inputs:
print(f" {a:>4} | {b:>4} | {func(a, b):>4}")
# Главная программа: вывести все таблицы истинности
inputs = [0, 1]
print("пример полной демонстрации таблицы истинности булевой алгебры")
print_truth_table("Операция AND", AND, inputs)
print_truth_table("OR (операция OR)", OR, inputs)
print_truth_table("Операция NOT", NOT, inputs)
print_truth_table("операция XOR", XOR, inputs)
# Проверка закона де Моргана
print(f"\n{'='*40}")
print(" Проверка закона де Моргана")
print(f"{'='*40}")
print(Закон 1: NOT(A AND B) = NOT A OR NOT B)
print(Закон 2: NOT(A OR B) = NOT A AND NOT B)
for a in inputs:
for b in inputs:
left1 = NOT(AND(a, b))
right1 = OR(NOT(a), NOT(b))
left2 = NOT(OR(a, b))
right2 = AND(NOT(a), NOT(b))
print(f" A={a}, B={b}:")
print(f" Проверка закона1: {left1} = {right1} -> {'OK' if left1 == right1 else 'FAIL'}")
print(f" Проверка закона2: {left2} = {right2} -> {'OK' if left2 == right2 else 'FAIL'}")