АППАРАТ БУЛЕВОЙ АЛГЕБРЫ

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

Высказывание — некоторое предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

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

Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами.

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

Логическое выражение - это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).

В булевой алгебре простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Обозначаются логические переменные буквами латинского алфавита.

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

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

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

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

Элементы. Схемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и управляющие.

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

Во всех случаях сигналы двух различных уровней могут представляться бинарными символами {0,1} или логическими значениями {Истина, Ложь}. Поэтому сама алгебра называется бинарной, или переключательной. Ее элементы называются константами, или логическими 0 и 1 , которым в ряде случаев соответствуют бинарные цифры, в других случаях – логические значения, соответственно ложь (False)и истина (True).

Для обозначения булевых переменных используются буквы латинского алфавита - x, y, z … .

Операции. Основными, или базовыми, операциями булевой алгебры служат: И (AND), ИЛИ (OR) и НЕ (NOT).

Операция И называется логическим умножением или конъюнкцией и обозначается знаком умножения {•, ^}.

Операция ИЛИ называется логическим сложением или дизъюнкцией и обозначается знаком сложения { + , v}.

Операция НЕ называется логическим отрицанием или инверсией и обозначается знаком {', ¯.}.

При выполнении операций применяются отношение эквивалентности «=» и скобки «()», которые определяют порядок выполнения операций. Если скобок нет, то операции выполняются в следующей последовательности: логическое отрицание, логическое умножение и логическое сложение.

Аксиомы (постулаты) алгебры логики

Дизъюнкция двух переменных равна 1, если хотя бы одна из них равна 1:

0 + 0 = 0; 0+1 = 1; 1+0=1;1 + 1 = 1.

Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0:

0x0 = 0; 0x1=0; 1x0 = 0; 1x1 = 1.

Инверсия одного значения переменной совпадает с ее другим значением:

ī = 0; ō = 1.