Фактор-алгебра алгебры формул

Обозначим через Фn множество всех формул алгебры логики с переменными из множества {х1, х2, ... , хn}.

На множестве Фn определены двухместные операции конъюнкции и дизъюнкции — : , : — и одноместная операция отрицания : .

Выделим на множестве Фn две константы и . Так получается алгебра формул Fn = .

Отношение ~ эквивалентности формул является конгруэнцией на алгебре Fn, и поэтому можно задать фактор-алгебру Fn/~.

На фактор-множестве Фn/~ операции , и определяются следующим образом:

~(φ)~(ψ) = ~( φψ),

~(φ)~(ψ) = ~( φψ),

~(φ) = ~( φ),.

На множестве Фn/~ выделяются две константы: 0 = ~() и 1 = ~(). Полученная система является фактор-алгеброй Fn/~.

Теорема. Фактор-алгебра Fn/~ изоморфна алгебре булевых функций Bn

Доказательство.

Искомый изоморфизм ξ: Fn/~ → Bn определяется по следующему правилу: классу эквивалентности ~(φ) сопоставляется функция fφ, имеющая таблицу истинности произвольной формулы из множества ~(φ). Поскольку разным классам эквивалентности соответствуют различные таблицы истинности, отображение ξ инъективно, а так как для любой булевой функции f из Вп найдется формула , представляющая функцию f, то отображение ξ сюръективно. Сохранение операций , 0, 1 при отображении ξ проверяется непосредственно. ЧТД.

По теореме о функциональной полноте каждой функции , не являющейся константой 0, соответствует некоторая СДНФ ψ, принадлежащая классу ~(φ) = ξ-1(f) формул, представляющих функцию f. Возникает задача нахождения в классе ~(φ) дизъюнктивной нормальной формы, имеющей наиболее простое строение.

Контрольные вопросы

1. Что такое булева функции? Понятие «булева функция», булевы функции одной переменной. Булевы функции двух переменных.

2. Что называется высказыванием? Понятие «высказывание». Приведите примеры высказываний. Какие высказывания называются истинными, а какие ложными?

3. Что называется составным высказыванием?

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

5. Какие основные операции используются в теории высказываний? Простейшие связки. Назовите другие связки.

6. Что такое таблица истинности высказывания и как она строится?

7. Сформулируйте основные законы алгебры высказываний. Как их доказать?

8. Булевы функции: понятия формула, подформула, базис. Равносильные формулы. Принцип двойственности.

Лекция № 9

Так как здание всего мира совершенно и возведено премудрым Творцом, то в мире не происходит ничего, в чем не было бы виден смысл какого-нибудь максимума или минимума.

Эйлер