Полные системы функций

1.9.1. Система функций { }

Теорема. Всякая булева функция порождается некоторой формулой, в которой есть только операции .

Доказательство. Пусть некоторая булева функция. Для нее можно поострить таблицу истинности, в которой будет 2ⁿ строк. Каждую строку можно представить в виде конъюнкции переменных х₁,…х_n, куда входит либо , либо . Если значение конъюнкции будет равно 1, то всю функцию можно представить в виде дизъюнкции этих конъюнкций.

Пример.

Получим СДНФ, используя таблицу истинности.

Возникает вопрос: Существуют ли другие системы булевых функций, с помощью которых можно выразить все другие функции?

Замкнутые классы

Пусть множество булевых функций от n переменных.

Замыканием F ([F]) называется множество всех булевых функций, реализуемых формулами над F.

Множество функций (класс) называется замкнутым, если [F]=F.

Рассмотрим следующие классы функций.

1. Класс функций, сохраняющих 0:

.

2. Класс функций, сохраняющих 1:

3. Класс самодвойственных функций:

, где .

4. Класс монотонных функций

где .

5. Класс линейных функций

, где + - означает сложение по модулю 2, а знак конъюнкции опущен.

Теорема. Классы Т₀, Т₁, Т_*, Т_М, T_L – замкнуты.

Доказательство. Чтобы доказать, что некоторый класс F замкнут достаточно показать, что, если формула реализована в виде формулы над F, то она принадлежит F.

Рассмотрим доказательство для одного класса функций Т₀.

Пусть и . Тогда .

Аналогичные доказательства можно привести для остальных классов.

Не нашли, что искали? Воспользуйтесь поиском: