Это – алгебра лотки. На рисунке проиллюстрированы пять основных логических утверждении. Для любого из них, если А верно, то в таблице появляется «1». Если А ложно, появляется «О». В утверждении типа «И» С верно (т.е. в таблице имеется 1), когда верны А и В, но ложно, если и А, и В ложны. В утверждении «ИЛИ» С верно, если верно либо А, либо В, и ложно только в том случае, если и А, и В ложны. Утверждение «НЕТ» имеет один вход и один выход, его функция заключается в перемене местами «верного» и «ложного»; применение его к выражениям «И» и «ИЛИ» дает соответственно «НЕ» и «НИ». Утверждения Булевой алгебры,показанные здесь, можно также изобразить как элементы электрического контура (ввод слева, выход справа) или, по способу и, как в теории множеств (результат обозначен на рисунке закрашиванием соответствующих участков).
1.3 Булева алгебра и теория множеств
Будем рассматривать двухэлементное множество , элементы которого не являются числами в полном смысле этого слова, а интерпретируются как «ложь» и «истина». Считая их логическими переменными, определим следующие функции алгебры двузначной логики.
Определение:
Отрицанием x назовем функцию , которая значению аргументаx = 0 ставит в соответствие ; а значению аргументаx = 1 ставит в соответствие .
Определение:
Конъюнкцией элементов и назовем функцию , которая имеет значение 1, только если. В остальных случаях конъюнкция равна 0.
Определение:
Дизъюнкцией элементов и назовем функцию , которая принимает значение 1, если хотя бы один из ее аргументовили (то есть только , или только ,или и одновременно) равны 1. Дизъюнкция равна нулю тогда и только тогда, когда .
Определенные так логические функции носят название логических связок «не», «и», «или».
Связь между ними описывается с помощью набора эквивалентностей:
1) ; 2) ;
3) ; 4) ;
5); 6);
7) ; 8);
9) ; 10);
11) ; 12);
13) ; 14);
.
Любые операции, подчиняющиеся свойствам 1-14, называются булевыми операциями. F алгебры с данным набором операций называются булевыми алгебрами. Так, например, свойства 1-14 будут выполняться и для операций объединения, пересечения и дополнения множеств, если сопоставить:
– объединение – дизъюнкции;
– пересечение – конъюнкции;
дополнение – отрицанию, а вместо иподставить некоторые множества А и В изU (универсального множества).
Заметим важный факт, что если применить данные операции к логическим функциям , где, то результатами тоже будут логические функции. Поэтому связки &, также можно считать и операциями над множеством всех логических функций двузначной логики, обозначаем .
Тогда алгебра тоже будет булевой алгеброй (булевой алгеброй логических функций), так как для ее операций тоже выполняются соотношения 1-14, где вместо переменныхиподставлены логические функции.
Если U – некоторое множество элементов мощности n: .
Определение: B-булеан U – это множество (совокупность) всех подмножеств множества U.
Определение: Алгебра (B,), несущим множеством которой является множествоB, а операциями – пересечение, объединение и дополнение множеств, называетсябулевой алгеброй множества U или алгеброй Кантора. Ее тип (2,2,1).
Общий термин ”булева алгебра” для алгебр множеств и логических функций не случаен.
Определение: Всякая алгебра типа (2,2,1) называется булевой алгеброй, если ее операции удовлетворяют основным свойствам булевых операций 1-14.
В алгебре множеств элементами являются подмножества фиксированного (”универсального”) множества U, операции & соответствует пересечение , операции– объединение, операции (отрицание) соответствует дополнение; единицей является само множество U, нулем – . Справедливость соотношений 1-14 для алгебры множеств можно доказать непосредственно их проверкой. Для этого нужно рассмотреть переменные в них как множества, знаки & изаменить наи, и показать, что, если какой-либо элемент принадлежит множеству из левой части равенства, то он принадлежит и правой части, и наоборот.
В пункте 4.2. (в теореме о числе подмножеств конечного множества) отмечалось и использовалось взаимно однозначное соответствие между множествомдвоичных векторов длиныn и множеством B, где: каждому подмножествусоответствует двоичный вектор, где.
Булева алгебра на множестве(двоичных векторов) определяется следующим образом: для любыхи
