Класс l

L – класс линейных ф-ций.

Ф-ция f(x1,…xn) наз. линейной, тогда и только тогда, когда ее представление в виде полинома Жегалкина имеет вид: fЄLf(x1,…xn)=a0a1x1a2x2…anxn, то есть, содержит только линейные слагаемые

Слогаемые aixi наз. линейными, а все остальные – нелинейными.

Каждая линейная ф-ция однозначно определяется своими коэфициэнтами. Для ф-ции от nпеременных всего n+1 коэфициент, поэтому всего линейных ф-ций 2^(n+1). Непосредственно из определения линейной ф-ции следует, что класс линейных ф-ций замкнут.

Лема о нелинейных ф-циях: Если ф-ция нелинейна, то из нее путем подстановки вместо переменных констант, тождественной ф-ции и отрицания самой ф-ции можно получить коньюнкцию.

Док-во: Пусть fL. Тогда в ее представлении в виде полинома Жегалкина имеется наименьшее слагаемое. Будем предполагать, что в это слогаемое входят переменные x1 и x2, если это не так, то переменные можно перенумеровать. Тогда ф-цию f можно представить в виде:f(x1,x2,…,xn)=x1x2f1(x3,x4,…,xn)⨁x1f2(x3,x4,…,xn)⨁x2f3(x3,x4,…,xn)⨁f4(x3,x4,…,xn)(f1≢0)

Поэтому (3, 4,…,n), значение переменных x3,x4,…xn, на котором ф-ция f(1) принимает значение 1(f1(α3,α4,…,αn))=1. Предположим, что f2 принимает значение α, f3-β, f4-Построим ф-цию φ от двух переменных: (x1, x2)= x1x2x1x2

Эта ф-ция получена из ф-ции f путём подстановки в неё константы.

По ф-ции φ построим ф-цию S:S(x1, x2)=(x1, x2)=(x1⨁β)(x2⨁α)⨁x(x1⨁β)⨁β(x2⨁α)⨁⨁xβ⨁ xx⨁αx1⨁βx2⨁αβ⨁αx1⨁αβ⨁βx2⨁αβ⨁αβ=x1x2.

Теорема(о функциональной полноте). Система функций D является полной тогда и только тогда, когда она целиком не входит ни в один из основных замкнутых класов T0,T1,S,M,L

Доказательство.Пусть система D полностью не входит ни в один из основных замкнутых классов. Тогда в D найдутся ф-и f0T0,f1T1,fsS,flL, fmM.Покажем, что конъюнкцию и отрицание можно представить в виде суперпозиции этих пяти функций. Из этого будет следовать, что это множество этих ф-ций образуют полную систему. Возьмём функцию f0(f0≠T0), которая не сохраняет 0. Это означает f(0,0,...,0)=1

1.f0(1,1,...,1)=0

2.f0(1,1,...,1)=1

Рассмотрим первый случай. f0(x,x,...,x)=x. Возьмём несамодвойственную ф-цию fsS. Из несамодвойственной ф-и fs путём подстановки вместо переменных тождественной функции, отрицания можно получить константу. Вторую константу можно получить путём навешивания отрицания над первой.

Из flL при помощи тождественной функции, отрицания и констант строится конъюнкция.

В I случае в построении участвовали f0,fs,fl

Рассмотрим случай2. f0(x,x,...,x)=1

Рассмотрим f1T1.Она на единичном наборе принимает нулевые значения. Тогда результат подстановки вместо переменных в функцию f1 функции f0(x,x,...x) даёт значение ноль. Из немонотонной ф-и fM, используя константы 0,1 и тождественную функцию, можно построить отрицание. Из нелинейной функции путем подстановки констант, отрицаний, тождественной функции можно получить конъюнкцию.

Следствие1. Любой замкнутый класс, отличный от P2 является подмножеством одного из основных замкнутых классов.

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