5.2.4 Основы булевой алгебры

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

Как и обычная алгебра, булева алгебра оперирует с тремя типами множеств: множеством констант, множеством операций и множеством теорем.

5.2.4.1 Булевы переменные и основные операции булевой алгебры

Булева алгебра называется еще алгеброй логики, так как первоначально была предложена английским математиком Джорджем Булем в 1854 году для математического описания теории логических высказываний, которые всегда или «истинны», или «ложны», а третьего – не может быть.

В последующем времени, когда оказалось, что эта алгебра имеет техническое применение, «истинность» стали считать логической единицей (лог.1), а «ложность» – логическим нулем (лог.0).

В связи с этим множество констант, которые использует булева алгебра, содержит всего две константы: лог.0 и лог.1.

Переменных в булевой алгебре может быть сколько угодно, но каждая переменная в любой момент времени принимает одно из двух возможных значений, а именно

(2)

Таким образом, булевы переменные – дискретные переменные, равные лог.0 или лог.1. В дальнейшем при их записи слово «логический» будем опускать.

В случае булевых переменных их нумерацию выгоднее начинать с нуля, то есть записывать

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

Логическое сложение (дизъюнкция, операция ИЛИ (OR)) определяется так: результат операции равен единице, если или первая, или вторая переменная, или все переменные =1. Результат операции равен нулю только в одном случае, когда все переменные =0.

Логическое умножение (конъюнкция, операция И (AND)) определяется так: результат операции равен единице только в одном случае, когда и первая, и вторая, и все переменные =1. Во всех остальных случаях результат равен нулю.

Логическое отрицание (инверсия, операция НЕ (NOT)) выполняется всегда над одной переменной и преобразует ее в противоположное логическое значение: 0 в 1, или 1 в 0.

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

Таблица 1

Название функции

Функциональное обозначение

Логическое сложение

Дизъюнкция

ИЛИ (OR)

Логическое умножение

Конъюнкция

И (AND)

Логическое отрицание

Инверсия

НЕ (NOT)

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

Таблица 2