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

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

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

f(x₁,x₂)= x₁ Ú x₂, f(x₁,x₂)= x₁ × x₂.

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

f(x)= , f(x₁,x₂)=x₁~ x_2.

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

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

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

f(x₁,x₂)= x₁ Ú x₂, f(x₁,x₂)= x₁ × x₂.

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

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

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

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

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

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

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

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

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

В алгебре Жегалкина одноименный полином (полином Жегалкина) можно считать аналогом канонической нормальной формы функции для булевой алгебры.

Определение.Полином Жегалкина является линейным (1-ой степени), если все коэффициенты общего полинома, начиная с K_n+1, равны нулю.

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

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

y= x₁Å x₂ (K₀=0, K₁=K₂=1),

y= =1Å x (K₀=K₁=1, K₂=0).

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

y= x₁× x_2,

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

A=(a₁,a₂,...,a_n)>B=(b₁,b₂,...,b_n) Þ f(A)³ f(B).

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

a_i ³ b_i (i=1, 2,..., n)

и, по крайней мере, для одной компоненты имеет место отношение возрастания.

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

(1011) > (0011)

(1011) > (0001)

(0001) > (0000).

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

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

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

y = , y = x₁Å x₂.

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

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

Определение. Два набора аргументов называются противоположными, если любая из их компонент принимает противоположные значения, например,

x = (0101) и = (1010).

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

Примером самодвойственной функции является: у = .

Примеры не самодвойственных функций:

у=х₁× х₂, у=х₁Ú х₂, у=х₁Å х₂.

Принадлежность базовых булевых функций и логических констант к замечательным классам представлена табл. 10. Знаком “+” отмечена принадлежность функции соответствующему классу, а знаком “-” не принадлежность.

Принадлежность булевых функций к замечательным классам

Таблица 10.

Функция	К0	К1	КL	КM	КS
	+	-	+	+	-
	-	+	+	+	-
	-	-	+	-	+
х1× х2	+	+	-	+	-
х1Ú х2	+	+	-	+	-
х1Å х2	+	-	+	-	-
х1~ х2	-	+	+	-	-
х1 D х2	+	-	-	-	-
х1® х2	-	+	-	-	-
х1 | х2	-	-	-	-	-
х1¯ х2	-	-	-	-	-