КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Замечательные классы булевых функций1. Булева функция называется сохраняющей константу нуль, если на нулевом наборе аргументов она принимает значение равное нулю, то есть f(0,0,0,...,0) = 0. В противном случае функция относится к классу не cохраняющих константу нуль. К функциям, сохраняющим константу нуль, относятся
. (3.4.)
К функциям не cохраняющим константу нуль относятся f(x)= и f(x1,x2)=x1~x. (3.5.) 2. Булева функция называется сохраняющей константу единица, если на единичном наборе аргументов она принимает значение равное единице, то есть f(1,1,1,...,1)= 1; В противном случае функция относится к классу не cохраняющих константу единица. К функциям, сохраняющим константу единица, относятся
и . (3.6.)
К функциям, не cохраняющим константу единица, относятся f(x)= и f(x1,x2)=x1Åx2. (3.7.)
3. Булева функция называется линейной если она представима полиномом Жегалкина первой степени. В булевой алгебре доказывается теорема о возможности представления любой булевой функции от n переменных с помощью полинома Жегалкина n-ой степени. В общем случае полином имеет вид :
fn (x) = K0 ÅK1x1 Å...ÅKn xn Å... ...ÅKn+1x1x2 ÅKn+2x1x3 Å...ÅKn+lxn-1xn Å... (3.8.) ... ...ÅKn+mx1x2...xn K0 ,K1 ,Kn+m - являются коэффициентами и представляют собой логические константы нуля или единицы. В алгебре Жегалкина одноименной полином можно считать канонической нормальной формой для булевой алгебры [12-14]. Полином Жегалкина является линейным (первой степени) если все коэффициенты общего полинома, начиная с Kn+1=Kn+2 =...=Kn+m = 0. В отношении функции от двух переменных полином Жегалкина имеет вид (линейный): f2(x)=K0ÅK1x1ÅK2x2 . Примерами линейных функций являются: Примеры нелинейных функций: 1. Булева функция называется монотонной, если при возрастании наборов аргументов она принимает неубывающие значения.
(3.9.) .
Между наборами аргументов А и В имеет место отношение возрастания в том и только том случае, если имеет место отношение не убывания для всех компонент этого набора: ) и, по крайней мере, для одной компоненты имеет место отношение возрастания. Примеры наборов, для которых имеет место отношение возрастания: (1011)>(0011) (1011)>(0001) (0001)>(0000) Пример несопоставимых наборов (1011) и (0111) В отношении функции от двух переменных несопоставимыми являются наборы (01) и (10) Пример немонотонных функций: y= ; y= x1Åx2 . Две булевы функции fn(x) и gn(x) называются двойственными если для любых наборов аргументов выполняется равенство , (3.10.)
то есть функции f и g на противоположных наборах аргументов х и принимает противоположные значения.
|