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

Класс (множество) К булевых функций называется функционально замкнутым, если вместе с функциями из этого класса он содержит и все их суперпозиции.

Очевидно, что для доказательства замкнутости класса достаточно показать, что элементарные суперпозиции не выводят из этого класса (т.е. элементарные суперпозиции функций данного класса также принадлежат этому классу).

Рассмотрим некоторые функционально замкнутые классы булевых функций.

1. Через Т₀ обозначается класс функций, сохраняющих 0, т.е. функций удовлетворяющих условию f(0,0,…,0)=0.

2. Через Т₁ обозначается класс функций, сохраняющих 1, т.е. функций, удовлетворяющих условию f(1,1,…,1)=1.

Заметим, что х₁х₂ Т₀, а х₁х₂  Т₁, х₁+х₂  Т₀, а х₁+х₂  Т₁, т.е. эти классы функций различны и не совпадают с классом всех булевых функций.

Поскольку элементарные суперпозиции не выводят из классов Т₀ и Т₁ соответственно, то они функционально замкнуты.

3. Пусть f(x₁, x₂, …, x_n) – булева функция. Функция f*(x₁, x₂,…,x_n) называется двойственной f(x_1, x₂, …, x_n), если f*(x_1, x₂, …, x_n)=f(x_1, x₂, …, x_n).Функция f(x₁, …, x_n) называется самодвойственной, если f(x₁, …, x_n)=f*(x₁, …, x_n).

Класс самодвойственных функций обозначается через S; он функционально замкнут.

4. Функция f(x₁, x₂, …, x_n) называется линейной, если f(x₁, x₂, …, x_n)=a₀+a₁x₁+a₂x₂+ … + a_nx_n, где a_i {0;1}.

Класс линейных функций обозначается через L. Класс L. Функционально замкнут.

5. Введем отношение частичного порядка на множестве наборов значений переменных.

Говорят, что набор =(₁, …, _n) предшествует набору  =(_{1, …,} _n) , где _i {0,1}, _i {0,1}, i=1, …, n, если _i  _i для любого i. Обозначается   .

Например, (0, 1, 0, 1)  (0, 1, 1, 1), а наборы (0, 1, 1) и (1,0,1) несравнимы. Введенное отношение  есть отношение частичного порядка.

Функция f(x₁, x₂, …, x_n) называется монотонной, если для любых наборов значений переменных  и  от таких, что   , имеем f()  f().

Класс монотонных функций обозначается через М.

Класс М функционально замкнут.

Классы Т₀, Т₁, S, L, M неполные и попарно различные, поскольку можно привести примеры булевых функций, не принадлежащих ни одному из этих классов, и примеры функций, принадлежащих одному из любых двух классов, но не принадлежащих другому. Кроме перечисленных классов можно указать и много других функционально замкнутых классов. Оказывается, что для проверки полноты системы булевых функций можно ограничиться рассмотренными пятью функциональными классами.

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

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

Теорема Поста: Для того, чтобы система булевых функций {f₁, …, f_n} была полной необходимо и достаточно, чтобы для каждого из классов Т₀, Т₁, L, M и S нашлась функция f_i из системы, не принадлежащая этому классу.