У Буловој алгебри, свака Булова функција се може ставити у канонску дисјунктивну нормалну форму или ДНФ и његов дуал канонску конјунктивну нормалну форму или КНФ. Друге канонске форме укључују комплетну суму простих импликаната или Блејкова канонска форма, и његов дуал алгебарска нормална форма, другачије позната и као Zhegalkin или Reed–Muller.
ДНФ се зову производи јер представљају логичко И групе променљивих, и КНФ се зову сумама јер су заправо логичко ИЛИ групе променљивих. Ови концепти су дуални због њиховог комплементарно-симетричног односа који је исказан преко Де Морганових закона.
Две канонске форме било које Булове функције су "сума ДНФа" или "производ КНФа“. Израз сума производа се често користи када се мисли на дисјункцију ДНФа. Његов Де Морганов дуал је производ сума за канонски облик који је конјункција КНФа. Ови облици дозвољавају већу анализу за упрошћавање ових функција, што може бити од великог значаја за минимизацију Булових формула опште и дигиталних кола конкретно.
Садржај Једна примена Булове алгебра је у дизајнирању дигиталних кола. Циљ нам може бити да смањимо број потребних кола, да смањимо потребно време, итд.
Постоји 16 могућих комбинација функција две променљиве, али у логици дигиталног хардвера најпростија кола имплементирају само 4: конјункцију (И), дисјункцију (ИЛИ) и њихове комплементе (НИ и НИЛИ).
Већина кола прима више од две променљиве, на пример, компјутер за навођење свемирског Апола, који је био пионир интегрисаних кола шестдесетих година прошлог века, је био направљен од само једне врсте кола, троулазног НИЛИ, чији је излаз био истинит само када су сва три улаза били лажни.Eldon C. Hall, Journey to the Moon: The History of the Apollo Guidance Computer, AIAA .
КНФ За Булову функцију од променљивих производ у коме се свако појављује само једном (било у комплементарној или нормалној форми) се зове ДНФ. Тако је ДНФ логички израз од * променљивих који користи само оператор негације и оператор конјункције.
На пример , и су 3 примера од 8 ДНФ за Булову функцију од 3 променљиве , и . Читање последњег израза је а И б И НЕ ц.
Постоји 2n ДНФ од n променљивих, пошто променљива у изразу може бити или у нормалној форми или у комплементарној форми, и тако за n променљивих имамо по два избора.
Индексирање КНФ
ДНФ се често означавају бинарно у комплементарном обрасцу променљивих, где су променљиве написане у стандардном поретку, углавном алфабетном. Ова конвенција додељује вредност 1 нормалној форми () и вредност 0 комплементарној форми (); ДНФ је онда сума од вредности. На пример, ДНФ је написан као 1102 = 610 и означен као .
Функционална једнакост Дати ДНФ n даје истинитосну вредност (нпр. 1) само за једно комбинацију улазних променљивих. На пример, ДНФ 5, a b' c, је само истинит у случају када су и a и c истинити, а b' неистинит—када су постављени као a = 1, b = 0, c = 1 добијамо резултат 1.
За дату таблицу истинитости могуће је написати функцију као суму производа. Ово је специјалан облик дисјунктивне нормлане форме. На пример, ако имам таблицу истинитости за аритметичко сабирање бита u од једнобитног сабирача, као функцију од x и y као сабирке и прекорачење као ci:
cixyu(ci,x,y)00000011010101101001101011001111
Приметимо да редови који имају излаз 1 су други, трећи, пети и осми, и онда напишемо u као суму ДНФ и . Ако желимо да проверимо ово: једноставно проверимо свих 8 комбинација за три променљиве.
ДНФ За Булову функцију од променљивих је израз суме у коме се свака од променљивих појављује само једном (било у нормалној или комплементарној форми) се зове КНФ. Што значи да је КНФ логички изаз * променљивих који користи само оператор негације и оператор дисјункције. КНФ је дуална у односу на ДНФ и уместо И и негације користимо ИЛИ и негацију.
На пример, следе две од 8 могући КНФ за три израза: a + b' + c a' + b + cОпет постоји 2n комбинација од n променљивих јер се на исти начин као и код ДНФ изрази могу написати са нормалном формом или комплементарном формом променљивих, што нам даје по две опције за n променљивих.
Индексирање ДНФ Свакој КНФ је додељен индекс на основу супротне бинарне конвенције записа коришћене за ДНФ. КНФ конвенција додељује вредност 0 нормалној форми променљиве и вредност 1 комплементарној форми променљиве . На пример, доделимо индекс 6 КНФ (110) и означимо КНФ као M6. Слично, M0 од ове три променљиве је (000) и M7 је (111).
Функционална једнакост Очигледно је да КНФ n нам даје неистиниту вредност (нпр. 0) за једну комбинацију улазних променљивих. На пример, израз 5, a' + b + c', је неистинит само када су и a и c истинити а b неистинит—за улаз где је a = 1, b = 0, c = 1 резултат је 0.
Ако имамо таблицу истинитости логичке функције, могуће је написати функцију као производ сума. Ова специјална врста конјунктивне нормалне форме. На пример, ако имамо таблицу истинитости за бит преноса * једног сабирача, као функцију за x и y за сабирач и пренос ci:
cixyco(ci,x,y)00000010010001111000101111011111
Примећујући да су редови који имају резултат 0, први, други, трећи и пети, можемо да напишемо co као производ КНФ и . Ако желимо да проверимо ово:co(ci, x, y) = = (ci + x + y) (ci + x + y') (ci + x' + y) (ci' + x + y) једноставно проверимо да ли се за свих 8 комбинација вредности поклапају са таблицом истинитости.
Дуализација Комплемент ДНФ је одговарајући КНФ. Ово се лако може проверити Де Моргановим законом. На пример:
Неканонски облици суме производа и производа суме Често је случај да се канонска ДНФ може упростити у одговарајућу суму производа. Ово упрошћена форма се састоји од суме ДНФа. Али, у упрошћеном облику је могуће да буде мање производа израза и/или производа израза који садрже мање променљивих. На пример, следећа функција три променљиве:
abcf(a,b,c)00000010010001111000101011001111
има канонску ДНФ: , али има еквивалентну упрошћену форму: . У овом тривијалном пример је очигледно да , али пошто упрошћени израз има мање и производа израза и мање променљивих. Најпростији производе суме функције се назива минималним производом суме.
У сличном стилу, канонски КНФ може да има упрошћени израз производа сума.
Док је овај пример лако упрошћен користећи нормалне алгебарске методе [], у мање очигледним случајевима згодан начин за налажење минималне суме производа и производа суме је коришћење Карноових мапа.
Минимални производ суме и сума производа су веома битни за налажење оптималне имплементације Булових функција и за минимизацију логичких кола.
Пример примене Пример таблице истинитости ДНФ и КНФ изнад су довољни за стварање канонске форме за једнобитне позиције у сабирању бинарних бројева, али нису довољне за дизајнирање дигиталних кола уколико у инвентару немам кола И и ИЛИ. Где су перформансе битне (Као у Аполовом компјутеру), углавном се користе НИ и НИЛИ кола јер је акција негације наслеђена из логике транзистора. Вредности су дефинисане као стања напона, једно близу уземљењу и једно близу улазног напона Vcc, на пример +5 VDC. Ако је већи напон дефинисан као 1 или истинита вредност, НИЛИ коло је најпростији логички елемент.
Прецизније, троулазно НИЛИ коло се може састојати од 3 биполарна споја транзистора са уземљеним одашиљачима, везаним колектором и спојеним на Vcc кроз импедансу. Свака база је повезана са улазним сигналом и заједнички колектор представља излазни сигнал. Сваки улаз који је 1 (висок напон) ка својој бази спаја одашиљач транзистора са његовим колектором, чинећи да струја пролази кроз импедансу, што поставља напон колектора веома близу уземљењу. Резултат је независан од свих осталих улаза. Само када су сва 3 сигнала 0 (низак напон) одашиљачи-колектори импеданси сва 3 транзистора остају са виском напоном. Она веома мало струје прође, и ефекат дељења напона се импедансом се примењује високи напон веома близу Vcc на колекторима.
Комплементарно својство ових кола можда изгледа као мана када покушавамо да имплементирамо функцију из канонског облика, али има предност: такво коло са само једним улазом имплементира комплементарну функцију, која је често неопходна у дигиталној логици.
Овај пример претпоставља да је Аполо има само троулазно НИЛИ коло, али је дискусија упрошћена претпоставком да су и четворо улазна НИЛИ кола била такође доступна (у Аполу су она била састављена од парова троулазних НИЛИ кола).
Канонске и неканонске последице примене НИЛИ кола Прва чињеница: група од 8 НИЛИ кола, ако су њихови улази све комбинације нормалних и комплементарних вредности три променљиве ci, x, и y, увек производе ДНФ, никад КНФ—то јест, од 8 кола потребних за обраду свих комбинација 3 улазне променљиве, само једно има излаз 1. То је зато што НИЛИ кола, упркос имену, се боље могу видети као И кола са комплиментираним улазним сигналима.
Друга чињеница: разлог зашто прва чињеница није проблем је дуални ДНФ и КНФ, односно сваки ДНФ је комплемент слично индексираног КНФ и обрнуто.
У ДНФ примеру изнад, написали смо али да претворимо ово у четворо улазно НИЛИ коло морамо да препишемо израз као производ сума, где су суме супротне КНФ. Односно,
= AND() = NOR(). Таблице истинитости:
cixyM0M3M5M6ANDu(ci,x,y)000011100001111111010111111011101100100111111101110100110111000111111111
cixym0m3m5m6NORu(ci,x,y)000100000001000011010000011011010000100000011101001000110000100111000011
У КНФ примеру изнад, написали смо , али да претворимо ово у четворо улазно НИЛИ коло морамо да приметимо једнакост са НИЛИ од његових истих ДНФ. Односно, = AND() = NOR() . Таблице истинитости:
cixyM0M1M2M4ANDco(ci,x,y)000011100001101100010110100011111111100111000101111111110111111111111111
cixym0m1m2m4NORco(ci,x,y)000100000001010000010001000011000011100000100101000011110000011111000011
Компромиси дизајнирања поред канонских форми Неко ће претпоставити да је посао дизајнирања сабирача готов, али нисмо обратили чињеницу да све три улазне променљиве морају да се појаве у нормалној и комплементарној форми. Нема потешкоћа око сабирака x и y у овом погледу, јер су статични приликом целог сабирања и налазе се у леч колима која имају и директан и комплементаран излаз. (Најпростије леч коло је направљено од НИЛИ кола као пар кола међусобно повезаних да направе флип-флоп; излаз сваког је повезан за улазом другог.) Такође, нема потребе да правимо комплемент израза суме u. Али, пренос једног бита се мора пребацити у следећу позицију бита и у директној и у комплементарној форми. Најпростије решење је да проследимо co кроз једно улазно НИЛИ коло и да му дамо ознаку co', али то би допринело кашњењу кола на најгорем могућем месту, успоравајући преносе здесна налево. Додатно четворо улазно НИЛИ коло које прави канонску форму од co' (од супротних ДНФ као co) решава овај проблем.
Таблице истинитости:
cixyM3M5M6M7ANDco'(ci,x,y)000111111001111111010111111011011100100111111101101100110110100111111000
cixym3m5m6m7NORco'(ci,x,y)000000011001000011010000011011100000100000011101010000110001000111000100
Компромис за постизање пуне брзине на овај начин укључује неочекивану цену (поред тога што мора да се користи веће коло). Ако бисмо користили једно улазно коло да комплиментирамо co, не би било користи за израз , и коло које је га је генерисало би могло да буде избачено. Али ово је ипак, добар компромис.
Сад бисмо могли да имплементирамо те функције тачно по њиховим сумама производа и производа сума, претварајући НИЛИ кола у потребне функције. Нили коло се састоји од ИЛИ кола са излазом у једно улазно НИЛИ коло; и направљено је као И коло са улазима од два једно улазна НИЛИ кола. Али ипак, овај приступ не само да повећава број укључених кола, него и дуплира кашњење у преради сигнала, смањујући брзину обраде на пола. Последично, када год су перформансе битне, излазак ван канонских форми и рад са Буловом алгебром је веома значајан.
Одозго надоле против одоздо нагоре дизајна