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

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

Ф-ция f(x₁,…x_n) наз. линейной, если ее представление в виде полинома Жегалкина имеет вид:

f(x₁,…x_n)=a₀a₁x₁a₂x₂…a_nx_n.

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

линейные: 0, 1, x, x=x1, .

нелинейные: &, , , , .

Каждая линейная ф-ция однозначно определяется своими коэфициэнтами, поэтому |L|=2ⁿ⁺¹.

т.к. суперпозиция линейных ф-ций – линейная ф-ция, то класс линейных ф-ций замкнут: |L|=L.

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

Док-во: Пусть fL. Тогда в ее представлении в виде полинома Жегалкина имеется наименьшее слагаемое. Будем предполагать, что в это слогаемое входят переменные x₁ и x₂. Тогда (₃, ₄,…,_n):

f(x₁, x₂, ₃, ₄,…,_n)=x₁x₂x₁x₂.

(в противном случае, переменные x₁, x₂ были бы фиктивными).

(x₁, x₂)= x₁x₂x₁x₂.

По ф-ции построем ф-цию S:

S(x₁, x₂)=(x₁, x₂).

Можно показать, что S(x₁, x₂)=x₁&x₂.

	T0	T1	S	M	L
1	-	+	+	+	+
x	+	+	+	+	+
x	-	-	-	-	+

Из таблицы видно, что основные замкнутые классы попарно не совпадают.

43. Алгебра Жегалкина. Полином Жегалкина.

Определение:

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

В алгебре Жегалкина выполняются следующие соотношения:

х+у=у+х

х(y+z)=xy+xz

x+0=x

x+1=не х

Если в обычном алгебраическом полиноме все сложения заменить сложениями по модулю 2, а все умножения заменить коньюнкциями, числовые коэффициенты заменить булевыми константами 0,1, то получится полином Жегалкина.

От булевой функции всегда можно перейти к формуле алгебры Жегалкина, а следовательно построить полином Жегалкина, использую равенство:

не х=х+1.

х дизъюнкция у=ху+х+1

44. Полином Жегалкина. Теорема.

Полиномом (многочленом) Жегалкина от п переменных называется функция

f(x1, x2, …, xn)=С₀+С₁х₁+C₂x₂+…+C_nx_n+C₁₂x₁₂+…+C_12…nx₁x₂..x_n

Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.

Доказательство. Любая функция f(x1, x2, …, xn) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2п), отсюда следует утверждение теоремы.

Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.

Имеется 2-й способ нахождения полинома Жегалкина для функций, заданных в виде ДНФ. Этот способ основан на том, что х+1 = . Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило де Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как х+ х = 0), а нечетное число одинаковых слагаемых равно одному такому слагаемому.