Замечательные классы булевых функций

1. Булева функция называется сохраняющей константу нуль, если на нулевом наборе аргументов она принимает значение равное нулю, то есть f(0,0,0,...,0) = 0.

В противном случае функция относится к классу не cохраняющих константу нуль.

К функциям, сохраняющим константу нуль, относятся

_. (3.4.)

К функциям не cохраняющим константу нуль относятся

f(x)= и f(x₁,x₂)=x₁~x. (3.5.)

2. Булева функция называется сохраняющей константу единица, если на единичном наборе аргументов она принимает значение равное единице, то есть f(1,1,1,...,1)= 1;

В противном случае функция относится к классу не cохраняющих константу единица.

К функциям, сохраняющим константу единица, относятся

и _. (3.6.)

К функциям, не cохраняющим константу единица, относятся

f(x)= и f(x₁,x₂)=x₁Åx_2. (3.7.)

3. Булева функция называется линейной если она представима полиномом Жегалкина первой степени.

В булевой алгебре доказывается теорема о возможности представления любой булевой функции от n переменных с помощью полинома Жегалкина n-ой степени.

В общем случае полином имеет вид :

fⁿ (x) = K₀ ÅK₁x₁ Å...ÅK_n x_n Å...

...ÅK_n+1x₁x₂ ÅK_n+2x₁x₃ Å...ÅK_n+lx_n-1x_n Å... (3.8.)

...

...ÅK_n+mx₁x₂...x_n

K₀ ,K₁ ,K_n+m - являются коэффициентами и представляют собой логические константы нуля или единицы.

В алгебре Жегалкина одноименной полином можно считать канонической нормальной формой для булевой алгебры [12-14].

Полином Жегалкина является линейным (первой степени) если все коэффициенты общего полинома, начиная с K_n+1=K_n+2 =...=K_n+m = 0.

В отношении функции от двух переменных полином Жегалкина имеет вид (линейный): f²(x)=K₀ÅK₁x₁ÅK₂x₂ .

Примерами линейных функций являются:

Примеры нелинейных функций:

1. Булева функция называется монотонной, если при возрастании наборов аргументов она принимает неубывающие значения.

(3.9.)

.

Между наборами аргументов А и В имеет место отношение возрастания в том и только том случае, если имеет место отношение не убывания для всех компонент этого набора: ) и, по крайней мере, для одной компоненты имеет место отношение возрастания.

Примеры наборов, для которых имеет место отношение возрастания:

(1011)>(0011)

(1011)>(0001)

(0001)>(0000)

Пример несопоставимых наборов (1011) и (0111)

В отношении функции от двух переменных несопоставимыми являются наборы (01) и (10)

Пример немонотонных функций: y= ; y= x₁Åx₂ .

Две булевы функции fⁿ(x) и gⁿ(x) называются двойственными если для любых наборов аргументов выполняется равенство

, (3.10.)

то есть функции f и g на противоположных наборах аргументов х и принимает противоположные значения.