Булева алгебра функций.

Выше мы обозначили множество всех логических операций на двухэлементном множестве , как .

Определение. Булевой алгеброй логических функций называется алгебра вида , основным множеством которой является всё множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание.

Замечание. На практике мы имеем дело не самими функциями, а с представляющими их формулами, то есть с алгеброй формул, которая значительно шире, поскольку каждую функцию представляет бесконечное множество формул. Чтобы “синхронизировать” их алгебре формул придаётся следующий вид. Элементами алгебры формул объявляются не сами формулы, а классы эквивалентности формул, то есть классы формул, представляющих одну и ту же функцию. Определённая таким образом, алгебра формул называется алгеброй Линденбаума - Тарского. Она изоморфна булевой алгебре функций.

Теперь рассмотрим основные свойства булевых операций (частично уже знакомые по теме “Элементы математической логики”).

1. Ассоциативность: а) ; б) .

2. Коммутативность: а) ; б) .

3. Дистрибутивность конъюнкции относительно дизъюнкции: .

4. Дистрибутивность дизъюнкции относительно конъюнкции:

.

5. Идемпотентность: а) ; б) .

6. Двойное отрицание: .

7. Свойства констант: а) ; б) ; в) ; г) ; д) ; е) .

8. Правила де Моргана: а) ; б) . Очень важные соотношения, которые часто будут использоваться в дальнейшем. С их помощью (а также с помощью соотношения 6) дизъюнкция заменяется конъюнкцией и наоборот.

9. Закон противоречия: .

10. Закон “исключённого третьего”: .

Все соотношения 1 – 10 можно проверить указанным ранее стандартным методом – вычислением обеих частей равенств на всех наборах значений переменных. Эти равенства остаются справедливыми и в случае подстановки вместо переменной любой логической функции и, следовательно, любой формулы, представляющей эту функцию. Важно лишь соблюдать следующее правило подстановки формулы вместо переменной.

При подстановке формулы вместо переменной все вхождения данной переменной в исходное соотношение должны быть одновременно заменены формулой .

Правило подстановки позволяет получать из соотношений 1 – 10 новые эквивалентные соотношения. Заметим, что равенство означает в данном контексте, что формулы и описывают одну и ту же логическую функцию. Следовательно, если какая-то формула содержит в качестве подформулы, то замена её на не изменит значения формулы . Это утверждение представляет собой правило замены подформул, которое позволяет, используя эквивалентные соотношения, получать формулы, эквивалентные данной. Практическое применение описанных правил будет рассмотрено ниже.

Замечание. Есть существенная разница между подстановкой и заменой. При подстановке переменная заменяется формулой; при этом формула может быть любой, лишь бы производилась одновременная замена ею всех вхождений переменной. При замене подформул может быть заменена любая подформула, однако, не на любую другую, а только на подформулу, эквивалентную ей. При этом замена всех вхождений исходной подформулы не обязательна.