2.3.1. Полнота и замкнутость. Полные системы функций и замкнутые классы

Определение. Система булевых функций {F1, F2, …, Fn} называется Полной, если любая булева функция может быть представлена в виде композиции функций из данной системы.

Так, например, из результатов §2 следует, что система функций {‾, } (отрицание, конъюнкция и дизъюнкция) является полной, так как всякая функция может быть представлена в виде СДНФ или СКНФ. Из теоремы Жегалкина следует, что полной является также система функций {} (конъюнкция, сумма по модулю 2, константа 1).

Понятно, что не всякая система функций полная. Например, совокупность констант {0, 1} не является полной системой функций (все композиции, которые можно получить в данном случае – это те же константы 0 и 1).

Отметим следующие очевидные Свойства:

1. Если к полной системе функций добавить ещё какую-либо функцию, то получим полную систему функций.

2. Если каждая функция Fi полной системы функций {F1, F2, …, Fn} является композицией функций системы {G1, G2, …, Gm}, то система функций {G1, G2, …, Gm} также является полной.

Определение. Пусть М некоторое множество булевых функций. Замыканием [M] множества М называется множество функций, представимых в виде формул (композиций) функций из множества М. Класс (множество) функций М называется Замкнутым, если [M] = M.

Примеры. 1. Пусть M = {0, 1}, тогда [M] = {0, 1}= M.

2. Пусть M = {‾, }, тогда [M] -- множество всех булевых функций.

Понятно, что система булевых функций является полной тогда и только тогда, когда её замыкание совпадает с множеством всех булевых функций.

Справедливы также следующие Свойства замыкания.

1.

2.

3. Если , то

4.

< Предыдущая		Следующая >