Канонска нормална форма

У Буловој алгебри, свака Булова функција се може ставити у канонску дисјунктивну нормалну форму или ДНФ и његов дуал канонску конјунктивну нормалну форму или КНФ. Друге канонске форме укључују комплетну суму простих импликаната или Блејкова канонска форма, и његов дуал алгебарска нормална форма, другачије позната и као Zhegalkin или Reed–Muller.

ДНФ се зову производи јер представљају логичко И групе променљивих, и КНФ се зову сумама јер су заправо логичко ИЛИ групе променљивих. Ови концепти су дуални због њиховог комплементарно-симетричног односа који је исказан преко Де Морганових закона.

Две канонске форме било које Булове функције су "сума ДНФа" или "производ КНФа“. Израз сума производа се често користи када се мисли на дисјункцију ДНФа. Његов Де Морганов дуал је производ сума за канонски облик који је конјункција КНФа. Ови облици дозвољавају већу анализу за упрошћавање ових функција, што може бити од великог значаја за минимизацију Булових формула опште и дигиталних кола конкретно.

Садржај

Једна примена Булове алгебра је у дизајнирању дигиталних кола. Циљ нам може бити да смањимо број потребних кола, да смањимо потребно време, итд.

Постоји 16 могућих комбинација функција две променљиве, али у логици дигиталног хардвера најпростија кола имплементирају само 4: конјункцију (И), дисјункцију (ИЛИ) и њихове комплементе (НИ и НИЛИ).

Већина кола прима више од две променљиве, на пример, компјутер за навођење свемирског Апола, који је био пионир интегрисаних кола шестдесетих година прошлог века, је био направљен од само једне врсте кола, троулазног НИЛИ, чији је излаз био истинит само када су сва три улаза били лажни.^[1]

КНФ

За Булову функцију од ${\displaystyle n}$ променљивих ${\displaystyle {x_{1},\dots ,x_{n}}}$ производ у коме се свако ${\displaystyle n}$ појављује само једном (било у комплементарној или нормалној форми) се зове ДНФ. Тако је ДНФ логички израз од * променљивих који користи само оператор негације и оператор конјункције.

На пример ${\displaystyle abc}$, ${\displaystyle ab'c}$ и ${\displaystyle abc'}$ су 3 примера од 8 ДНФ за Булову функцију од 3 променљиве ${\displaystyle a}$, ${\displaystyle b}$ и ${\displaystyle c}$. Читање последњег израза је а И б И НЕ ц.

Постоји 2ⁿ ДНФ од n променљивих, пошто променљива у изразу може бити или у нормалној форми или у комплементарној форми, и тако за n променљивих имамо по два избора.

Индексирање КНФ

ДНФ се често означавају бинарно у комплементарном обрасцу променљивих, где су променљиве написане у стандардном поретку, углавном алфабетном. Ова конвенција додељује вредност 1 нормалној форми (${\displaystyle x_{i}}$) и вредност 0 комплементарној форми (${\displaystyle x'_{i}}$); ДНФ је онда сума од ${\displaystyle 2^{i}}$ вредности${\displaystyle (x_{i})}$. На пример, ДНФ ${\displaystyle abc'}$ је написан као 110₂ = 6₁₀ и означен као ${\displaystyle m_{6}}$.

Функционална једнакост

Дати ДНФ n даје истинитосну вредност (нпр. 1) само за једно комбинацију улазних променљивих. На пример, ДНФ 5, a b' c, је само истинит у случају када су и a и c истинити, а b' неистинит—када су постављени као a = 1, b = 0, c = 1 добијамо резултат 1.

За дату таблицу истинитости могуће је написати функцију као суму производа. Ово је специјалан облик дисјунктивне нормлане форме. На пример, ако имам таблицу истинитости за аритметичко сабирање бита u од једнобитног сабирача, као функцију од x и y као сабирке и прекорачење као ci:

ci	x	y	u(ci,x,y)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Приметимо да редови који имају излаз 1 су други, трећи, пети и осми, и онда напишемо u као суму ДНФ ${\displaystyle m_{1},m_{2},m_{4},}$ и ${\displaystyle m_{7}}$. Ако желимо да проверимо ово: ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)}$ једноставно проверимо свих 8 комбинација за три променљиве.

ДНФ

За Булову функцију од ${\displaystyle n}$ променљивих ${\displaystyle {x_{1},\dots ,x_{n}}}$ је израз суме у коме се свака од ${\displaystyle n}$ променљивих појављује само једном (било у нормалној или комплементарној форми) се зове КНФ. Што значи да је КНФ логички изаз * променљивих који користи само оператор негације и оператор дисјункције. КНФ је дуална у односу на ДНФ и уместо И и негације користимо ИЛИ и негацију.

На пример, следе две од 8 могући КНФ за три израза:

a + b' + c

a' + b + c

Опет постоји 2ⁿ комбинација од n променљивих јер се на исти начин као и код ДНФ изрази могу написати са нормалном формом или комплементарном формом променљивих, што нам даје по две опције за n променљивих.

Индексирање ДНФ

Свакој КНФ је додељен индекс на основу супротне бинарне конвенције записа коришћене за ДНФ. КНФ конвенција додељује вредност 0 нормалној форми променљиве ${\displaystyle (x_{i})}$ и вредност 1 комплементарној форми променљиве ${\displaystyle (x'_{i})}$. На пример, доделимо индекс 6 КНФ ${\displaystyle a'+b'+c}$ (110) и означимо КНФ као M₆. Слично, M₀ од ове три променљиве је ${\displaystyle a+b+c}$ (000) и M₇ је ${\displaystyle a'+b'+c'}$ (111).

Функционална једнакост

Очигледно је да КНФ n нам даје неистиниту вредност (нпр. 0) за једну комбинацију улазних променљивих. На пример, израз 5, a' + b + c', је неистинит само када су и a и c истинити а b неистинит—за улаз где је a = 1, b = 0, c = 1 резултат је 0.

Ако имамо таблицу истинитости логичке функције, могуће је написати функцију као производ сума. Ова специјална врста конјунктивне нормалне форме. На пример, ако имамо таблицу истинитости за бит преноса * једног сабирача, као функцију за x и y за сабирач и пренос ci:

ci	x	y	co(ci,x,y)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Примећујући да су редови који имају резултат 0, први, други, трећи и пети, можемо да напишемо co као производ КНФ ${\displaystyle M_{0},M_{1},M_{2},}$ и ${\displaystyle M_{4}}$. Ако желимо да проверимо ово: co(ci, x, y) = ${\displaystyle M_{0}M_{1}M_{2}M_{4}}$ = (ci + x + y) (ci + x + y') (ci + x' + y) (ci' + x + y) једноставно проверимо да ли се за свих 8 комбинација вредности поклапају са таблицом истинитости.

Дуализација

Комплемент ДНФ је одговарајући КНФ. Ово се лако може проверити Де Моргановим законом. На пример: ${\displaystyle M_{5}=a'+b+c'=(ab'c)'=m_{5}'}$

Неканонски облици суме производа и производа суме

Често је случај да се канонска ДНФ може упростити у одговарајућу суму производа. Ово упрошћена форма се састоји од суме ДНФа. Али, у упрошћеном облику је могуће да буде мање производа израза и/или производа израза који садрже мање променљивих. На пример, следећа функција три променљиве:

a	b	c	f(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

има канонску ДНФ: ${\displaystyle f=a'bc+abc}$, али има еквивалентну упрошћену форму: ${\displaystyle f=bc}$. У овом тривијалном пример је очигледно да ${\displaystyle bc=a'bc+abc}$, али пошто упрошћени израз има мање и производа израза и мање променљивих. Најпростији производе суме функције се назива минималним производом суме.

У сличном стилу, канонски КНФ може да има упрошћени израз производа сума.

Док је овај пример лако упрошћен користећи нормалне алгебарске методе [${\displaystyle f=(a'+a)bc}$], у мање очигледним случајевима згодан начин за налажење минималне суме производа и производа суме је коришћење Карноових мапа.

Минимални производ суме и сума производа су веома битни за налажење оптималне имплементације Булових функција и за минимизацију логичких кола.

Пример примене

Пример таблице истинитости ДНФ и КНФ изнад су довољни за стварање канонске форме за једнобитне позиције у сабирању бинарних бројева, али нису довољне за дизајнирање дигиталних кола уколико у инвентару немам кола И и ИЛИ. Где су перформансе битне (Као у Аполовом компјутеру), углавном се користе НИ и НИЛИ кола јер је акција негације наслеђена из логике транзистора. Вредности су дефинисане као стања напона, једно близу уземљењу и једно близу улазног напона V_cc, на пример +5 VDC. Ако је већи напон дефинисан као 1 или истинита вредност, НИЛИ коло је најпростији логички елемент.

Прецизније, троулазно НИЛИ коло се може састојати од 3 биполарна споја транзистора са уземљеним одашиљачима, везаним колектором и спојеним на V_cc кроз импедансу. Свака база је повезана са улазним сигналом и заједнички колектор представља излазни сигнал. Сваки улаз који је 1 (висок напон) ка својој бази спаја одашиљач транзистора са његовим колектором, чинећи да струја пролази кроз импедансу, што поставља напон колектора веома близу уземљењу. Резултат је независан од свих осталих улаза. Само када су сва 3 сигнала 0 (низак напон) одашиљачи-колектори импеданси сва 3 транзистора остају са виском напоном. Она веома мало струје прође, и ефекат дељења напона се импедансом се примењује високи напон веома близу V_cc на колекторима.

Комплементарно својство ових кола можда изгледа као мана када покушавамо да имплементирамо функцију из канонског облика, али има предност: такво коло са само једним улазом имплементира комплементарну функцију, која је често неопходна у дигиталној логици.

Овај пример претпоставља да је Аполо има само троулазно НИЛИ коло, али је дискусија упрошћена претпоставком да су и четворо улазна НИЛИ кола била такође доступна (у Аполу су она била састављена од парова троулазних НИЛИ кола).

Канонске и неканонске последице примене НИЛИ кола

Прва чињеница: група од 8 НИЛИ кола, ако су њихови улази све комбинације нормалних и комплементарних вредности три променљиве ci, x, и y, увек производе ДНФ, никад КНФ—то јест, од 8 кола потребних за обраду свих комбинација 3 улазне променљиве, само једно има излаз 1. То је зато што НИЛИ кола, упркос имену, се боље могу видети као И кола са комплиментираним улазним сигналима.

Друга чињеница: разлог зашто прва чињеница није проблем је дуални ДНФ и КНФ, односно сваки ДНФ је комплемент слично индексираног КНФ и обрнуто.

У ДНФ примеру изнад, написали смо ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}}$ али да претворимо ово у четворо улазно НИЛИ коло морамо да препишемо израз као производ сума, где су суме супротне КНФ. Односно,

${\displaystyle u(ci,x,y)}$ = AND(${\displaystyle M_{0},M_{3},M_{5},M_{6}}$) = NOR(${\displaystyle m_{0},m_{3},m_{5},m_{6}}$). Таблице истинитости:

ci	x	y	M0	M3	M5	M6	AND	u(ci,x,y)
0	0	0	0	1	1	1	0	0
0	0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1	1
0	1	1	1	0	1	1	0	0
1	0	0	1	1	1	1	1	1
1	0	1	1	1	0	1	0	0
1	1	0	1	1	1	0	0	0
1	1	1	1	1	1	1	1	1

 

ci	x	y	m0	m3	m5	m6	NOR	u(ci,x,y)
0	0	0	1	0	0	0	0	0
0	0	1	0	0	0	0	1	1
0	1	0	0	0	0	0	1	1
0	1	1	0	1	0	0	0	0
1	0	0	0	0	0	0	1	1
1	0	1	0	0	1	0	0	0
1	1	0	0	0	0	1	0	0
1	1	1	0	0	0	0	1	1

У КНФ примеру изнад, написали смо ${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$, али да претворимо ово у четворо улазно НИЛИ коло морамо да приметимо једнакост са НИЛИ од његових истих ДНФ. Односно, ${\displaystyle co(ci,x,y)}$ = AND(${\displaystyle M_{0},M_{1},M_{2},M_{4}}$) = NOR(${\displaystyle m_{0},m_{1},m_{2},m_{4}}$) . Таблице истинитости:

ci	x	y	M0	M1	M2	M4	AND	co(ci,x,y)
0	0	0	0	1	1	1	0	0
0	0	1	1	0	1	1	0	0
0	1	0	1	1	0	1	0	0
0	1	1	1	1	1	1	1	1
1	0	0	1	1	1	0	0	0
1	0	1	1	1	1	1	1	1
1	1	0	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1

 

ci	x	y	m0	m1	m2	m4	NOR	co(ci,x,y)
0	0	0	1	0	0	0	0	0
0	0	1	0	1	0	0	0	0
0	1	0	0	0	1	0	0	0
0	1	1	0	0	0	0	1	1
1	0	0	0	0	0	1	0	0
1	0	1	0	0	0	0	1	1
1	1	0	0	0	0	0	1	1
1	1	1	0	0	0	0	1	1

Компромиси дизајнирања поред канонских форми

Неко ће претпоставити да је посао дизајнирања сабирача готов, али нисмо обратили чињеницу да све три улазне променљиве морају да се појаве у нормалној и комплементарној форми. Нема потешкоћа око сабирака x и y у овом погледу, јер су статични приликом целог сабирања и налазе се у леч колима која имају и директан и комплементаран излаз. (Најпростије леч коло је направљено од НИЛИ кола као пар кола међусобно повезаних да направе флип-флоп; излаз сваког је повезан за улазом другог.) Такође, нема потребе да правимо комплемент израза суме u. Али, пренос једног бита се мора пребацити у следећу позицију бита и у директној и у комплементарној форми. Најпростије решење је да проследимо co кроз једно улазно НИЛИ коло и да му дамо ознаку co', али то би допринело кашњењу кола на најгорем могућем месту, успоравајући преносе здесна налево. Додатно четворо улазно НИЛИ коло које прави канонску форму од co' (од супротних ДНФ као co) решава овај проблем.

${\displaystyle co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).}$

Таблице истинитости:

ci	x	y	M3	M5	M6	M7	AND	co'(ci,x,y)
0	0	0	1	1	1	1	1	1
0	0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1	1
0	1	1	0	1	1	1	0	0
1	0	0	1	1	1	1	1	1
1	0	1	1	0	1	1	0	0
1	1	0	1	1	0	1	0	0
1	1	1	1	1	1	0	0	0

 

ci	x	y	m3	m5	m6	m7	NOR	co'(ci,x,y)
0	0	0	0	0	0	0	1	1
0	0	1	0	0	0	0	1	1
0	1	0	0	0	0	0	1	1
0	1	1	1	0	0	0	0	0
1	0	0	0	0	0	0	1	1
1	0	1	0	1	0	0	0	0
1	1	0	0	0	1	0	0	0
1	1	1	0	0	0	1	0	0

Компромис за постизање пуне брзине на овај начин укључује неочекивану цену (поред тога што мора да се користи веће коло). Ако бисмо користили једно улазно коло да комплиментирамо co, не би било користи за израз ${\displaystyle m_{7}}$, и коло које је га је генерисало би могло да буде избачено. Али ово је ипак, добар компромис.

Сад бисмо могли да имплементирамо те функције тачно по њиховим сумама производа и производа сума, претварајући НИЛИ кола у потребне функције. Нили коло се састоји од ИЛИ кола са излазом у једно улазно НИЛИ коло; и направљено је као И коло са улазима од два једно улазна НИЛИ кола. Али ипак, овај приступ не само да повећава број укључених кола, него и дуплира кашњење у преради сигнала, смањујући брзину обраде на пола. Последично, када год су перформансе битне, излазак ван канонских форми и рад са Буловом алгебром је веома значајан.

Одозго надоле против одоздо нагоре дизајна

Сада смо видели како ДНФ/КНФ алати могу да се користе за дизајнирање сабирача у канонским формама са додатком мало Булове алгебре, коштајући нас само 2 кашњења кола за сваки од излаза. Ово је одозго надоле начин за дизајнирање дигиталног кола за ову функцију, али да ли је то најбољи начин? Дискусија је фокусирана на идентификацију најбржег и најбољег, и повећана канонска форма испуњава тај услов савршено, али некада други фактори преовлада. Дизајнер је можда ставио као главни циљ да минимизује број кола, или нешто друго. У таквом случају, дизајнер ће можда развити канонску форму од почетка, и пробати одоздо нагоре развој, и на крају упоредити резултат.

Развој одоздо нагоре укључује да приметимо да u = ci XOR (x XOR y), где XOR значи ексклузивно ИЛИ [истинито само када је један улаз истинит, али не када су оба], и да co = ci x + x y + y ci. Један такав развој узима 12 НИЛИ кола укупно: шест двоулазних, и две једноулазне да направе у 5 кола закашњења, плус три двоулазна кола и једно троулазно коло да направе co' у два кашњења улаза. Канонска основа узима 8 троулазних НИЛИ кола плус три четворо улазна НИЛИ кола да направи u, co и co' у два кашњења кола. Ако у инвентару имамо четворо улазна кола, одозго надоле канонски дизајн је очигледни победник у броју кола и брзини. Али ако су кола заправо троулазна НИЛИ кола, од који су нам два потребна за једно четворо улазно НИЛИ кола, онда је за канонски дизајн потребно 14 кола у поређењу са 12 која су потребна за одоздо нагоре приступ, али производи суму цифре u значајно брже. Поређење у табели је:

Variables	Top-down	Bottom-up
x	4	1
x'	4	3
y	4	1
y'	4	3
ci	4	1
ci'	4	3
M or m	4@1,4@2	N/A
x XOR y	N/A	2
Misc	N/A	5@1
Max	4	3

Која је најбоља одлука? Проницљиви читаоци ће приметити да у опису одозго нагоре развоја се помиње co' као излаз али не и co. Да ли тај дизајн нема потребу за директним обликом прекорачења? Па, да и не. У свакој фази, калкулација co' зависи само од 'ci', x' и y', што значи да се ток прекорачења таласа у позицији бита истом брзином као и канонски дизајн без стварања co. Калкулација u, коме је потребан ci се ради уз помоћ ci' са једно улазним НИЛИ колом, је спорија али за било коју дужину речи, овај дизајн плаћа ту казну само једном (када се најдаље лева цифра ствара). То је зато што се калкулације преклапају. И да будемо сигурни, излаз co' на најдаље левој позицији ће вероватно морати да се комплементира као део логике која одлучује да ли сабирање има прекорачења. Користећи троулазно НИЛИ коло, одоздо нагоре дизајн је веома близу по брзини као и паралелно сабирање нетривијалних дужина речи, али смањује број кола, смањује број улаза, итд. Што значи да побеђује у оним случајевима где нам је то значајно.

Референце

1. Eldon C. Hall, Journey to the Moon: The History of the Apollo Guidance Computer, AIAA . 1996.  978-1-56347-185-8.

Литература

-{

• Edward A. Bender, S. Gill Williamson, 2005, A Short Course in Discrete Mathematics, Dover Publications, Inc., Mineola, NY, 978-0-486-43946-4. The authors demonstrate a proof that any Boolean (logic) function can be expressed in either disjunctive or conjunctive normal form (cf pages 5–6); the proof simply proceeds by creating all 2^N rows of N Boolean variables and demonstrates that each row ("minterm" or "maxterm") has a unique Boolean expression. Any Boolean function of the N variables can be derived from a composite of the rows whose minterm or maxterm are logical 1s ("trues").
• E. J. McCluskey, 1965, Introduction to the Theory of Switching Circuits, McGraw–Hill Book Company, NY, Library of Congress Catalog Card Number 65-17394. Canonical expressions are defined and described on pages 78ff.
• Fredrick J. Hill, and Gerald R. Peterson, 1974, Introduction to Switching Theory and Logical Design, Second Edition, John Wiley & Sons, NY, 978-0-471-39882-0. Minterm and maxterm designation of functions appears on page 101ff.

}-

Спољашње везе