Основные тождества алгебры Буля

Алгебра логики (АЛ) является основным инструментом синтеза и анализа дискретных автоматов всех уровней. АЛ называют также Булевой алгеброй. АЛ базируется на трёх функциях, определяющих три основные логические операции.

1. Функция отрицания (НЕ). f1 =`X читается, как f1 есть (эквивалентна) НЕ Х. Элемент, реализующий функцию НЕ, называется элементом НЕ (инвертором).

Элемент НЕ имеет два состояния.

2. Функция логического умножения (конъюнкции). Функция логического умножения записывается в виде f2=X₁·X₂. Символы логического умножения &, L, < × >, ´. Функция конъюнкции читается так: f2 есть (эквивалентна) Х₁ и Х₂, поскольку функция истинна тогда, когда истинны 1-й и 2-й аргументы (переменные). Конъюнкцию называют функцией И, элемент, реализующий эту функцию, элементом И.

В общем случае функцию логического умножения от n переменных записывают так:

Количество переменных (аргументов), участвующих в одной конъюнкции, соответствует количеству входов элемента И.

3. Логическое сложение (дизъюнкция). Функция логического сложения записывается в виде f3=X1 + X2, и читается так: f3 есть Х1 или Х2, поскольку функция истинна, когда истинна одна или другая переменная (хотя бы одна). Поэтому функцию дизъюнкции часто называют функцией ИЛИ. Символы логического сложения +, V.

В общем случае функция ИЛИ записывается:

Используя операции (функции) И, ИЛИ, НЕ можно описать поведение любого комбинационного устройства, задав сколь угодно сложное булево выражение. Любое булево выражение состоит из булевых констант и переменных, связанных операциями И, ИЛИ, НЕ.

Пример булева выражения:

.

Основные законы алгебры логики. Основные законы АЛ позволяют проводить эквивалентные преобразования функций, записанных с помощью операций И, ИЛИ, НЕ, приводить их к удобному для дальнейшего использования виду и упрощать запись.

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ Таблица 1.1

N	а	б	Примечание
	=1 X+0=X X+1=1 X+X=X X+ =1	=0 X*1=X X*0=0 X*X=X X* =0	Аксиомы (тождества)
	=X		Закон двойного отрицания
	X+Y=Y+X	X*Y=Y*X	Закон коммутативности
	X+X*Y=X	X =X	Закон поглощения
	= *		Правило де-Моргана (закон дуальности)
	+Z=X+Y+Z		Закон ассоциативности
	X+ *Z= X+ Z		Закон дистрибутивности

Булевой алгебре свойственен принцип двойственности, что наглядно иллюстрирован в табл. 1.1. Как следует из табл. 1.1, только закон двойного отрицания не подчиняется этому принципу.

Используя законы алгебры логики, можно упростить булевы выражения, в частности, правило склеивания позволяет упростить выражение типа

.

Действительно, используя законы 2, 5 и 11 можно записать исходное выражение в виде Х₂(Х₁ +`Х<sub>1</sub>) =Х<sub>2</sub>. Так как логическая операция Х<sub>1</sub> +`Х₁ = 1 (см. з-н 5), а Х₂× 1 = Х₂ (см. з-н 2б), полученное выражение истинно.