Основы булевой алгебры -- AND / OR / NOT / XOR

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


Аналогия из жизни: автоматические двери и системы контроля доступа

При входе в здание с высоким уровнем безопасности вы столкнётесь с различными правилами контроля доступа. Эти правила как раз точно соответствуют базовым операциям булевой алгебры; давайте разберём их на повседневных примерах.

Элемент И — чтобы войти, две двери должны быть открыты одновременно: В одном хранилище для открытия нужно одновременно повернуть два ключа. Только когда оба ключа вставлены и повёрнуты (оба входа равны 1), дверь откроется (выход равен 1). Если хотя бы одного ключа нет, дверь остаётся неподвижной.

Элемент ИЛИ — если открыта хотя бы одна дверь, можно войти: В офисном здании есть два входа; если открыта передняя или задняя дверь, можно войти. Если открыт любой вход (хотя бы один вход равен 1), можно пройти (выход равен 1).

Элемент НЕ — кнопка переключает состояние: У входа в туалет есть перекидная табличка «Свободно/Занято»; нажатие кнопки переключает текущее состояние. При входе 0 (свободно) выход равен 1 (занято), и наоборот.

Элемент XOR (исключающее ИЛИ) — две лампы в комнате должны быть в состояниях: одна включена, другая выключена: В комнате есть две лампы, и правило таково: две лампы должны находиться в противоположных состояниях (одна включена, другая выключена); иначе срабатывает система сигнализации. Следовательно, когда два входа различаются, выход равен 1; когда они одинаковы, выход равен 0.


Краткая история булевой алгебры

Булева алгебра была разработана британским математикомДжорджем БулемВ 1854 году булева алгебра была впервые систематически изложена в работе «Исследование законов мышления». Целью Буля было математизировать человеческое логическое рассуждение; он создал метод использования алгебраических символов для представления «истины» и «лжи».

В 1938 годуКлод ШеннонВ своей магистерской диссертации в MIT он доказал, что булеву алгебру можно использовать для описания и упрощения релейных переключательных схем. Эта работа, известная как «самая важная магистерская диссертация в истории», заложила теоретическую основу для всего проектирования цифровых схем.

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


Подробное объяснение четырёх основных логических операций

Операция AND

Правило операции AND состоит всего из одного предложения:Выход равен 1 только тогда, когда все входы равны 1.; в противном случае выход равен 0. Это можно представить как последовательно соединённые переключатели — оба переключателя должны быть замкнуты, чтобы лампочка загорелась.

ABA AND B
000
010
100
111

Логическое выражение:Y = A · B(Иногда точку опускают и записывают прямо как Y = AB). Мнемоническое правило: выход равен 1 только тогда, когда все входы равны 1.

Операция OR

Правила операции OR:Если хотя бы один вход равен 1, выход равен 1; выход равен 0 только тогда, когда все входы равны 0. Аналогично параллельно соединённым переключателям — если любой переключатель замкнут, лампочка загорается.

ABA OR B
000
011
101
111

Логическое выражение:Y = A + B(Обратите внимание, что это не арифметическое сложение; в булевой алгебре 1+1 всё равно равно 1). Мнемоническое правило: любая 1 даёт 1.

Операция NOT

NOT — единственная базовая операция, которая принимает ровно один вход, и её правило самое простое:Выход является инверсией входаЕсли вход равен 1, выход равен 0; если вход равен 0, выход равен 1.

ANOT A
01
10

Логическое выражение:Y = A'илиY = NOT AВ схемах на входной линии небольшой кружок обычно используется для обозначения инверсии. Мнемоника: 0 становится 1, 1 становится 0.

Операция XOR (исключающее ИЛИ)

Правила XOR:Когда два входа различаются, выход 1; когда они одинаковы, выход 0. XOR реализуется комбинацией AND, OR, NOT. Реализация: A XOR B = (A' · B) + (A · B').

ABA XOR B
000
011
101
110

Логическое выражение:Y = A XOR BXOR имеет множество применений в таких областях, как проектирование сумматоров, проверка чётности и шифрование данных. Мнемоника: разные входы дают 1.


Символы логических элементов

На схемах цифровых устройств каждой базовой логической операции соответствует стандартное условное обозначение логического элемента:

Элемент AND: символ имеет D-образную форму — прямая сторона плюс полукруглая дуга, две входные линии слева и одна выходная линия справа.

Элемент OR: символ имеет форму щита — вогнутая дуга, сходящаяся к заострённому кончику сзади, отражающая логический смысл «или».

Элемент NOT (инвертор): треугольник, за которым следует маленький кружок — треугольник обозначает буферизацию/усиление, а кружок обозначает инверсию сигнала.

Элемент XOR: по форме похож на элемент OR, но перед дугой со стороны входов добавлена дополнительная дуга, чтобы отличать «исключающее ИЛИ».

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

Приложение: SVG-значки логических элементов и интерактивные таблицы истинности (пример демонстрации)

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

Стандартные обозначения четырёх логических элементов

Логический элемент И (D-форма: прямая сторона + полукруглая дуга)
A B Y
Логический элемент И
1 только когда все равны 1 · D-образный символ
Логический элемент ИЛИ(дуга: вогнутые внутрь линии сходятся в острие)
A B Y
Логический элемент ИЛИ
1, если хотя бы один равен 1 · щитообразный символ
Логический элемент НЕ (треугольник + маленький кружок на выходном выводе обозначает инверсию)
A Y
Логический элемент НЕ
Отрицание · Треугольник + Круг
Вентиль XOR (вентиль OR с добавленной дугой со стороны входа)
XOR-specific extra arc on the input sideOR gate body A B Y
Вентиль XOR
1, если различаются · OR+дуга

Интерактивная таблица истинности — нажимайте кнопки, чтобы переключать входы

Нажимайте кнопки A и B ниже, чтобы переключаться между 0/1, и наблюдайте, как соответствующие строки входов в таблице подсвечиваются

Вход A
0
Вход B
0
Сейчас выбрано:A=0, B=0
ABANDORNOT ANOT BИсключающее ИЛИ
0000110
0101101
1001011
1111000

Интерактивная демонстрация

Нажмите кнопки ниже, чтобы переключить значения входов A и B (0 или 1), и наблюдайте, как выходы каждого логического элемента изменяются в реальном времени:

Интерактивная демонстрация логического элемента (пример демонстрации)

Нажмите кнопки ниже, чтобы переключить значения входов A и B

Вход 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 используется для реализации функций четырёх базовых логических операций, автоматически генерируя полные таблицы истинности и также проверяя законы де Моргана:

Пример

# пример теста: Полная реализация булевой алгебры на 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'}")
Другие расширения