Перейти к содержанию

Булева алгебра

В булевой алгебре переменная принимает только два значения, а сложение и умножение означают ИЛИ и И. Из этого следуют странные на первый взгляд правила вроде 1 + 1 = 1 и A + AB = A — и именно они позволяют сократить схему из десятка элементов до двух.

Обновлено Редакция GAW

Содержание

Булева алгебра (Boolean algebra, алгебра логики) — математика величин, принимающих только два значения: 0 и 1, «ложь» и «истина». В ней три операции: логическое сложение (ИЛИ), логическое умножение (И) и дополнение (НЕ), которое записывают штрихом или чертой: A'. По Kuphaldt, Джордж Буль изложил её в трактате 1854 года, придав символическую форму двузначной логике Аристотеля; в цифровой технике она описывает работу логических элементов.

Арифметика двух значений

Сложение (ИЛИ)Умножение (И)Дополнение (НЕ)
0 + 0 = 00 · 0 = 00' = 1
0 + 1 = 10 · 1 = 01' = 0
1 + 1 = 11 · 1 = 1

Последняя строка сложения смущает больше всего, но она лишь повторяет таблицу истинности элемента ИЛИ. Отрицательных чисел, вычитания и деления нет. Булевы величины не надо путать с двоичными числами: двоичная запись — способ записать обычные числа, и в ней 1 + 1 = 10.

Тождества и правила упрощения

  • С константами: A + 0 = A, A + 1 = 1, A · 0 = 0, A · 1 = A.
  • С самой переменной: A + A = A, A · A = A, A + A' = 1, A · A' = 0, (A')' = A.
  • Поглощение: A + AB = A, A(A + B) = A.
  • Сокращение дополнения: A + A'B = A + B.
  • Распределительный закон в обе стороны: A(B + C) = AB + AC и (A + B)(A + C) = A + BC — второй вид в обычной алгебре не работает.
  • Законы де Моргана: (AB)' = A' + B', (A + B)' = A'B'.

Пример Kuphaldt: выражение AB + BC(B + C) раскрывается в AB + BC + BC, затем в AB + BC и выносится B(A + C). Вместо нескольких элементов И и ИЛИ остаются один элемент ИЛИ и один И.

Где применяется

Любую логическую функцию можно задать таблицей истинности, записать по ней булево выражение и упростить — алгебраически, картой Карно или методом Куайна — Мак-Класки. От числа слагаемых и множителей зависит число элементов и корпусов микросхем, а в программах — число операций с битами. Поиграть с выражениями и сразу увидеть минимальную форму позволяет симулятор логических схем, а последовательное изложение — на странице «Цифровая логика».

Частые вопросы

Почему в булевой алгебре 1 + 1 = 1?

Потому что «+» здесь означает логическое ИЛИ, а не арифметическое сложение. Результат ИЛИ равен 1, если хотя бы один операнд равен 1, — значит, и 1 + 1 = 1. Kuphaldt сравнивает это с двумя параллельными контактами: замкнутая цепь остаётся замкнутой, сколько контактов ни замкни. Вычитания и деления в булевой алгебре вообще нет.

Чем булевы числа отличаются от двоичных?

Двоичная запись — просто другой способ записать обычные числа, в ней 1 + 1 = 10. Булева алгебра — отдельная математика, где значений всего два и других не бывает. Путаница возникает из-за того, что обе используют цифры 0 и 1.

Какие правила булевой алгебры чаще всего нужны для упрощения?

Поглощение A + AB = A, правило A + A'B = A + B, распределительный закон в виде (A + B)(A + C) = A + BC и законы де Моргана для переноса инверсии. С их помощью Kuphaldt сворачивает выражение AB + BC(B + C) в B(A + C).

Источники

  1. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 7 «Boolean Algebra» (CC BY) — разд. «Introduction»: Джордж Буль (1815–1864) в 1854 г. издал трактат «An Investigation of the Laws of Thought», придав символическую форму двузначной логике Аристотеля; булевы числа — не двоичные числа; разд. «Boolean arithmetic»: сложение соответствует ИЛИ и параллельным контактам, 1 + 1 = 1, вычитания и деления нет, умножение соответствует И; разд. «Boolean algebraic identities», «properties», «rules for simplification»: A + 0 = A, A + 1 = 1, A + A = A, A + A' = 1, A·0 = 0, A·1 = A, A·A = A, A·A' = 0, A + AB = A, A + A'B = A + B, (A + B)(A + C) = A + BC; разд. «Circuit simplification examples»: AB + BC(B + C) = B(A + C)
  2. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 3 «Logic Gates» (CC BY) — элементы AND, OR, NOT и производные от них; таблица истинности как стандартное описание элемента; универсальность NAND и NOR

Нашли ошибку?

Смотрите также