 |
Замечательные классы булевых функций
|
|
|
|
Определение. Булева функция называется сохраняющей ноль, если на нулевом наборе аргументов она принимает значение равное нулю, то есть f (0, 0, 0,..., 0) = 0. В противном случае функция относится к классу не сохраняющих ноль.
К функциям, сохраняющим ноль, относятся
f(x1,x2)= x1 Ú x2, f(x1,x2)= x1 × x2.
К функциям, не сохраняющим ноль, относятся
f(x)= 
, f(x1,x2)=x1~ x2.
Определение. Булева функция называется сохраняющей единицу, если на единичном наборе аргументов она принимает значение равное единице, то есть f (1, 1, 1,..., 1) = 1.
В противном случае функция относится к классу не сохраняющих единицу.
К функциям, сохраняющим единицу, относятся:
f(x1,x2)= x1 Ú x2, f(x1,x2)= x1 × x2.
К функциям, не сохраняющим единицу, относятся:
f(x)= и f(x1,x2)=x1 Å x2.
Определение. Булева функция называется линейной, если она представима полиномом Жегалкина первой степени.
В булевой алгебре доказывается теорема о возможности представления любой булевой функции от n переменных с помощью полинома Жегалкина n -ой степени.
В общем случае полином имеет вид:
f n(Х) = K0 Å K1x1 Å...Å Kn xn Å ...
... Å Kn+1x1x2 Å Kn+2x1x3 Å...Å Kn+lxn-1xn Å ...
... Å Kn+mx1x2...xn.
K0, K1,…, Kn+m - являются коэффициентами полинома и представляют собой логические константы Ki= 0или Ki =1.
В алгебре Жегалкина одноименный полином (полином Жегалкина) можно считать аналогом канонической нормальной формы функции для булевой алгебры.
Определение. Полином Жегалкина является линейным (1-ой степени), если все коэффициенты общего полинома, начиная с Kn+1, равны нулю.
В отношении функции от 2-х переменных линейный полином Жегалкина имеет вид: f 2(Х)=K0Å K1x1Å K2x2.
Примерами линейных функций являются:
y= x1 Å x2 (K0=0, K1=K2=1), 
|
|
|
y= =1 Å x (K0=K1=1, K2=0).
Примеры нелинейных функций:
y= x1× x2,
Определение. Булева функция называется монотонной, если при возрастании наборов аргументов она принимает неубывающие значения.
A =(a1,a2,...,an)> B =(b1,b2,...,bn) Þ f(A)³ f(B).
Между наборами аргументов А и В имеет место отношение возрастания в том и только том случае, если имеет место отношение неубывания для всех компонент этого набора:
ai ³ bi (i=1, 2,..., n)
и, по крайней мере, для одной компоненты имеет место отношение возрастания.
Примеры наборов, для которых имеет место отношение возрастания:
(1011) > (0011)
(1011) > (0001)
(0001) > (0000).
Пример несопоставимых наборов (1011) и (0111).
В отношении функции от 2-х переменных несопоставимыми являются наборы (01) и (10)
Пример немонотонных функций:
y = , y = x1 Å x2.
Определение. Две булевы функции f n(Х) и gn(Х) называются двойственными, если для любых наборов аргументов выполняется равенство
то есть функции f и g на противоположных наборах аргументов Х и 
принимает противоположные значения.
Определение. Два набора аргументов называются противоположными, если любая из их компонент принимает противоположные значения, например,
x = (0101) и = (1010).
Определение. Булева функция называется самодвойственной, если она является двойственной по отношению к самой себе, то есть принимает противоположные значения на противоположных наборах аргументов.
Примером самодвойственной функции является: у = .
Примеры не самодвойственных функций:
у=х1× х2, у=х1Ú х2, у=х1 Å х2.
Принадлежность базовых булевых функций и логических констант к замечательным классам представлена табл. 10. Знаком “+” отмечена принадлежность функции соответствующему классу, а знаком “-” не принадлежность.
Принадлежность булевых функций к замечательным классам
Таблица 10.
| Функция | К0 | К1 | КL | КM | КS |
| + | - | + | + | - | |
| - | + | + | + | - | |
|
| - | - | + | - | + |
| х1× х2 | + | + | - | + | - |
| х1Ú х2 | + | + | - | + | - |
| х1 Å х2 | + | - | + | - | - |
| х1~ х2 | - | + | + | - | - |
| х1 D х2 | + | - | - | - | - |
| х1® х2 | - | + | - | - | - |
| х1 | х2 | - | - | - | - | - |
| х1 ¯ х2 | - | - | - | - | - |
|
|
|
Конструктивный подход к доказательству функциональной
|
|
|
