Пусть B - множество высказываний с обычными логическими операциями конъюнкции, дизъюнкции и отрицания и равенство высказываний интерпретируется как их равносильность.
Во второй главе показано, что операции Ú и Ù ассоциативны, коммутативны, и каждая из них дистрибутивна относительно другой. Если мы обозначим любое противоречие через Л, а любую тавтологию через И, то мы можем считать, что И и Л являются элементами B (так как все тавтологии равносильны, и все противоречия также равносильны). Легко проверить, что множество B с логическими операциями является булевой алгеброй, а элементы И и Л будут нейтральными элементами.
Теоретико-множественная модель
Пусть A - непустое множество, тогда множество-степень P(A) является моделью булевой алгебры, если условиться о следующем.
Элементы этой булевой алгебры - это различные подмножества множества A.
Операция Ù определяется как пересечение множеств, операция Ú обозначает объединение множеств и операция Ø является абсолютным дополнением (до A). Нетрудно убедиться, что все аксиомы булевой алгебры при таких определениях выполнены и множества A и Æ являются соответственно единичным и нулевым элементом алгебры.
Кроме конъюнкции и дизъюнкции особенно важны с точки зрения технической реализации переключательных функций следующие операции:
f¯g = Ø(fÚg) (функция Пирса);
f | g = Ø(fÙg) (штрих Шеффера);
f É g = ØfÚg (импликация);
f g = fÙØg (разность, теоретико-множественная разность в P(A));
f~g = (fÙg)Ú(ØfÙØg) (эквивалентность);
f + g = (fÙØg)Ú(ØfÙg) (симметрическая разность, исключающее "или", неэквивалентность).
Для произвольного элемента f булевой алгебры имеем:
Î É f = Ë , Ë É f = f,
f É Ë = Ë , f É Î = Øf.
Кроме того, f g = Ø(f É g).
Для симметрической разности имеем также
f + g = (fg)Ú(gf)
f + g = Ø(f~g)
Î + Î = Î Î + Ë = Ë
Ë + Î = Ë Ë + Ë = Î
При отождествлении Î с 0, а Ë с 1, получаем операцию сложения по модулю 2:
0+0 = 0 1+0 = 1
1+1 = 0 0+1 = 1
Возможно, теперь стало понятным, почему основные равносильности логики высказываний и основные тождества алгебры множеств так похожи - они просто законы булевой алгебры.
На основании законов булевой алгебры можно доказывать утверждения о тождественности (эквивалентности) выражений с булевыми операциями. Например, (fÙg)Ú(ØfÙb)Ú(fÙØg) = gÚf. Действительно,
(fÙg)Ú(ØfÙb)Ú(fÙØg) =
((fÙg)Ú(ØfÙg))Ú(fÙØg) =
((f Ú Øf)Ùg)Ú(fÙØg) =
(Ë Ù g)Ú(fÙØg) =
gÚ(fÙØg) =
(gÚf)Ù(gÚØg) =
(gÚf)Ù Ë =
gÚf.
Докажем, что все булевы выражения можно выразить через функцию Пирса. Для этого достаточно показать представимость с помощью функции Пирса базисных операций Ù, Ú, Ø.
Имеем
Øf = Ø(fÚf) = f¯f.
Далее, по определению,
f¯g = Ø(fÚg) Þ f Úg = Ø( f¯g) Þ fÚg = ( f¯g) ¯ ( f¯g).
И, наконец,
fÙg = Ø(ØfÚØg) = (Øf)¯(Øg) =(f¯f)¯(g¯g).