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

Произвольная булева функция может быть представлена полиномом по mod2 в виде суммы по mod2 монотонных конъюнкций (полинома Жегалкина). Пусть Говорят, что функция f линейна, если ее полином Жегалкина не содержит конъюнкций, ранг которых превышает 1 и имеет вид

где коэффициенты . Такая функция называется симметрической.

Множество всех линейных функций обозначается

Терема. Класс L замкнут и неполон, т.е. [L]=LP₂.

► Так как тождественная функция линейна, то для доказательства замкнутости класса L достаточно показать, что суперпозиция линейных функций есть линейная функция. Доказывается записью соответствующей суперпозиции.

Неполнота L следует из существования нелинейных функций. 

Очевидно, что мощность класса n-местных линейных функций равна .

Лемма о нелинейной функции. Из произвольной нелинейной функции с помощью подстановки констант, тождественной функции и функции отрицания и, возможно, навешиванием отрицания на всю функцию, можно получить конъюнкцию и дизъюнкцию.

Пусть . Тогда ее полином по mod2 содержит монотонные элементарные конъюнкции ранга выше 1. Выберем среди этих элементарных конъюнкций конъюнкцию минимального ранга (>1). Для удобства рассуждений положим, что выбранная конъюнкция содержит переменные x₁ и x₂. Выполним следующие подстановки: всем переменным, участвующим в выбранной конъюнкции, кроме переменных x₁ и x₂, присвоим значение1. А всем переменным, не вошедшим в выбранную конъюнкцию, присвоим значение 0. В силу единственности полинома, представляющего данную функцию, после выполнения равносильных преобразований полином примет вид:

.

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

0 1 2	Полином	Функция
000	x1x2	F(x1x2)=x1x2
001	x2x1x2=
010
011
100
101
110
111

Доказано, что из нелинейной функции могут быть получены конъюнкция и дизъюнкция.

Теорема Поста

Теорема. Чтобы множество DP₂ было полным, необходимо и достаточно, чтобы среди функций этого множества нашлась хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна не самодвойственная функция, хотя бы одна немонотонная и хотя бы одна нелинейная функции.

Следствие 1. В любом полном множестве существует полное подмножество, состоящее не более, чем из пяти функций.

Следствие 2. В любом полном множестве существует полное подмножество, состоящее не более чем из четырех функций.

Для доказательства функциональной полноты системы булевых функций по критерию Поста необходимо построить таблицу Поста, строки которой именуются функциями исследуемой системы, а столбцам присваиваются имена предполных классов. На пересечении i-й строки и j-го столбца таблицы ставится 1, если i-я функция принадлежит j-му классу, и 0 – в противном случае. Система функций полна, если в каждом столбце таблицы имеется хотя бы один 0. В противном случае система не является функционально полной в Р₂, так как входит целиком в один из предполных классов.

Пусть имеется система функций D={(x₁ x₂x₃ ), (x₁x₂), (x₁&x₂), 1}. Таблица Поста для нее будет иметь вид:

	T0	T1	S	M	L
f1={(x1 x2x3 )	1	1	1	0	1
f2=(x1x2)	0	1	0	0	0
f3=(x1&x2)	1	0	0	0	0
f4=1	0	1	0	1	1

Согласно критерию Поста система функций D функционально полна, так как в каждом столбце имеется хотя бы один 0. Критерии вхождения функции в предполные классы описаны выше.

Другой вопрос, связанный с использованием теоремы Поста, состоит в определении минимально необходимого набора функций из множества D, образующих функционально полную систему. Система функций D Р₂ называется базисом в Р₂, если она функционально полна в Р₂, но при исключении из нее любой функции, она перестает быть функционально полной, т.е. [D]=P₂, и f:((fD)([D\{f}]P₂)). Для определения базиса, соответствующего данной системе D, используют метод Петрика, состоящий в следующем. Рассматривая функции системы D как переменные, строим из них конъюнктивную нормальную форму, содержащую пять (по числу предполных классов) элементарных дизъюнкций, включая в каждую элементарную дизъюнкцию только те функции системы, которые принадлежат данному предполному классу, соединяя полученные дизъюнкции связкой &. Затем преобразуем полученное выражение к ДНФ, использую аксиомы и тождества логики высказываний. Каждая из конъюнкций в полученной ДНФ содержит все функции, образующие базис. Длина ДНФ соответствует числу базисов, соответствующих данной системе. Для рассмотренного примера применение метода Петрика состоит в следующем:

(f₂f₄)&f₃&(f₂f₃f₄)&(f₁f₂f₃)&(f₂f₃)=(f₂f₄)&f₃=f₂f₃  f₃f₄.

Таким образом, данная система содержит два базиса: D1= {f₂,f₃ }, D2={f₃, f₄}.