Линейные функции.

Рассмотрим класс функций, порождённый множеством
F={xx×yy, xxÅyy, 1}.

Из того, что xxÅ1=`х, следует, что в данном базисе реализуется инверсия, которая вместе с конъюнкцией даёт возможность построить любую функцию. Значит, данный базис порождает класс всех функций – класс С.

Сравним таблицы функции сложения по модулю два и дизъюнкции (табл.5.12).

Таблица. 5.12

Из таблицы видно, что аÚbb=(а Å bb) Úа×bb.

Если а и b такие, что имеет место равенство a×b=0, то такие переменные называются ортогональными. Для ортогональных переменных aÚb=(aÅb).

Если рассматривать СДНФ любой функции, то можно показать, что в ней любая пара конъюнкций ортогональна. Это приводит к следующему алгоритму построения записи функции в рассматриваемом базисе.

· записать функцию в СДНФ;

· заменить в СДНФ символы дизъюнкции на символы сложения по модулю два;

· заменить все инверсии по формуле `х =(хÅ1);

· раскрыть скобки, пользуясь свойством дистрибуции х×(yyÅz)=xx×yyÅxx×z;

· сделать сокращения, используя свойство хÅх=0, хÅ0=x.

В результате получается запись функции в форме, которую представим в общем виде

f=CC₀ ÅCC₁×xx₁Å CC₂×xx₂ Å… ÅCC_n×xx_nÅ CC(n+1)×xx₁×xx₂Å…ÅCC_m×xx₁×xx₂×…×xx_n , где С₀,С₁,С₂,…, принимают значения 0 или 1.

Это представление называется полиномом Жегалкина, а алгебра с сигнатурой {F={xx×yy, xxÅyy, 1}} – алгеброй Жегалкина.

ПримерПример. Построим полином Жегалкина для функции импликации. По её таблице истинности запишем СДНФ этой функции

a®b =`a`b Ú`abÚ ab,

после замены дизъюнкций на сложение по модулю два имеем a®b =
=`a`b Å`abÅ ab = (aÅ1)(bÅ1)Å(aÅ1)×bÅa×b = a×bÅaÅbÅ1Åa×bÅbÅa×b =
= a×bÅaÅ1.

Определение. Функция называется линейной, если её полином Жегалкина не содержит конъюнкций. Общий вид линейной функции
f = CC₀ ÅCC₁×xx₁Å CC₂×xx₂ Å… ÅCC_n×xx_n.

Число различных линейных функций от не более чем n переменных определяется формулой N = 2ⁿ⁺¹.

Суперпозиция линейных функций есть функция линейная, следовательно, множество линейных функций образуют класс линейных функций, обозначаемый как L. Базисом класса L служит множество {xxÅyy, 1}.