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

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

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

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается повествовательное предложение, о кото­ром можно сказать, истинно оно или ложно (третьего не дано). Вы­сказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА (обозна­чим 1).

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

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

Операции. Основными, или базовыми, операциями булевой ал­гебры служат (табл. 3.1): И (AND), ИЛИ (OR) и НЕ (NOT). Опе­рация И называется логическим умножением, или конъюнкцией, и обозначается знаком умножения {•, Ù }. Операция ИЛИ называется логическим сложением, или дизъюнкцией, иобозначается знаком сложения {+, Ú }. Операция НЕ называется логическим отрицани­ем, или инверсией (дополнением), и обозначается знаком {—, }.

Сложное высказывание можно построить из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации и логических выражений, представляющих собой комбинации логи­ческих операций. Рассмотрим их подробней.

Операцией отрицания А называют высказывание Ā (или -А, го­ворят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно.

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, ког­да истинны оба высказывания, записывается С = А Ù В или С = А & В (при этом говорят С равно А и В).

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A Ú В (при этом говорят: С равно А ИЛИ В).

Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, кото­рое ложно только тогда, когда посылка истинна, а заключение лож­но, записывается С = А ® В (при этом говорят: из А следует В).

Эквиваленцией двух высказываний А и В является новое выска­зывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А «В (С = А º В).