Модель исчисления высказываний

Пусть 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 = (f\g)Ú(g\f)

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).