Kanonska normalna forma

U Bulovoj algebri, svaka Bulova funkcija se može staviti u kanonsku disjunktivnu normalnu formu ili DNF i njegov dual kanonsku konjunktivnu normalnu formu ili KNF. Druge kanonske forme uključuju kompletnu sumu prostih implikanata ili Blejkova kanonska forma, i njegov dual algebarska normalna forma, drugačije poznata i kao Zhegalkin ili Reed–Muller.

DNF se zovu proizvodi jer predstavljaju logičko I grupe promenljivih, i KNF se zovu sumama jer su zapravo logičko ILI grupe promenljivih. Ovi koncepti su dualni zbog njihovog komplementarno-simetričnog odnosa koji je iskazan preko De Morganovih zakona.

Dve kanonske forme bilo koje Bulove funkcije su "suma DNFa" ili "proizvod KNFa“. Izraz suma proizvoda se često koristi kada se misli na disjunkciju DNFa. Njegov De Morganov dual je proizvod suma za kanonski oblik koji je konjunkcija KNFa. Ovi oblici dozvoljavaju veću analizu za uprošćavanje ovih funkcija, što može biti od velikog značaja za minimizaciju Bulovih formula opšte i digitalnih kola konkretno.

Sadržaj

Jedna primena Bulove algebra je u dizajniranju digitalnih kola. Cilj nam može biti da smanjimo broj potrebnih kola, da smanjimo potrebno vreme, itd.

Postoji 16 mogućih kombinacija funkcija dve promenljive, ali u logici digitalnog hardvera najprostija kola implementiraju samo 4: konjunkciju (I), disjunkciju (ILI) i njihove komplemente (NI i NILI).

Većina kola prima više od dve promenljive, na primer, kompjuter za navođenje svemirskog Apola, koji je bio pionir integrisanih kola šestdesetih godina prošlog veka, je bio napravljen od samo jedne vrste kola, troulaznog NILI, čiji je izlaz bio istinit samo kada su sva tri ulaza bili lažni.

KNF

Za Bulovu funkciju od $n$ promenljivih ${x_{1},\dots ,x_{n}}$ proizvod u kome se svako $n$ pojavljuje samo jednom (bilo u komplementarnoj ili normalnoj formi) se zove DNF. Tako je DNF logički izraz od * promenljivih koji koristi samo operator negacije i operator konjunkcije.

Na primer $abc$, $ab'c$ i $abc'$ su 3 primera od 8 DNF za Bulovu funkciju od 3 promenljive $a$, $b$ i $c$. Čitanje poslednjeg izraza je a I b I NE c.

Postoji 2ⁿ DNF od n promenljivih, pošto promenljiva u izrazu može biti ili u normalnoj formi ili u komplementarnoj formi, i tako za n promenljivih imamo po dva izbora.

Indeksiranje KNF

DNF se često označavaju binarno u komplementarnom obrascu promenljivih, gde su promenljive napisane u standardnom poretku, uglavnom alfabetnom. Ova konvencija dodeljuje vrednost 1 normalnoj formi ($x_{i}$) i vrednost 0 komplementarnoj formi ($x'_{i}$); DNF je onda suma od $2^{i}$ vrednosti$(x_{i})$. Na primer, DNF $abc'$ je napisan kao 110₂ = 6₁₀ i označen kao $m_{6}$.

Funkcionalna jednakost

Dati DNF n daje istinitosnu vrednost (npr. 1) samo za jedno kombinaciju ulaznih promenljivih. Na primer, DNF 5, a b' c, je samo istinit u slučaju kada su i a i c istiniti, a b' neistinit—kada su postavljeni kao a = 1, b = 0, c = 1 dobijamo rezultat 1.

Za datu tablicu istinitosti moguće je napisati funkciju kao sumu proizvoda. Ovo je specijalan oblik disjunktivne normlane forme. Na primer, ako imam tablicu istinitosti za aritmetičko sabiranje bita u od jednobitnog sabirača, kao funkciju od x i y kao sabirke i prekoračenje kao 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

Primetimo da redovi koji imaju izlaz 1 su drugi, treći, peti i osmi, i onda napišemo u kao sumu DNF $m_{1},m_{2},m_{4},$ i $m_{7}$. Ako želimo da proverimo ovo: $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)$ jednostavno proverimo svih 8 kombinacija za tri promenljive.

DNF

Za Bulovu funkciju od $n$ promenljivih ${x_{1},\dots ,x_{n}}$ je izraz sume u kome se svaka od $n$ promenljivih pojavljuje samo jednom (bilo u normalnoj ili komplementarnoj formi) se zove KNF. Što znači da je KNF logički izaz * promenljivih koji koristi samo operator negacije i operator disjunkcije. KNF je dualna u odnosu na DNF i umesto I i negacije koristimo ILI i negaciju.

Na primer, slede dve od 8 mogući KNF za tri izraza:

a + b' + c

a' + b + c

Opet postoji 2ⁿ kombinacija od n promenljivih jer se na isti način kao i kod DNF izrazi mogu napisati sa normalnom formom ili komplementarnom formom promenljivih, što nam daje po dve opcije za n promenljivih.

Indeksiranje DNF

Svakoj KNF je dodeljen indeks na osnovu suprotne binarne konvencije zapisa korišćene za DNF. KNF konvencija dodeljuje vrednost 0 normalnoj formi promenljive $(x_{i})$ i vrednost 1 komplementarnoj formi promenljive $(x'_{i})$. Na primer, dodelimo indeks 6 KNF $a'+b'+c$ (110) i označimo KNF kao M₆. Slično, M₀ od ove tri promenljive je $a+b+c$ (000) i M₇ je $a'+b'+c'$ (111).

Funkcionalna jednakost

Očigledno je da KNF n nam daje neistinitu vrednost (npr. 0) za jednu kombinaciju ulaznih promenljivih. Na primer, izraz 5, a' + b + c', je neistinit samo kada su i a i c istiniti a b neistinit—za ulaz gde je a = 1, b = 0, c = 1 rezultat je 0.

Ako imamo tablicu istinitosti logičke funkcije, moguće je napisati funkciju kao proizvod suma. Ova specijalna vrsta konjunktivne normalne forme. Na primer, ako imamo tablicu istinitosti za bit prenosa * jednog sabirača, kao funkciju za x i y za sabirač i prenos 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

Primećujući da su redovi koji imaju rezultat 0, prvi, drugi, treći i peti, možemo da napišemo co kao proizvod KNF $M_{0},M_{1},M_{2},$ i $M_{4}$. Ako želimo da proverimo ovo: co(ci, x, y) = $M_{0}M_{1}M_{2}M_{4}$ = (ci + x + y) (ci + x + y') (ci + x' + y) (ci' + x + y) jednostavno proverimo da li se za svih 8 kombinacija vrednosti poklapaju sa tablicom istinitosti.

Dualizacija

Komplement DNF je odgovarajući KNF. Ovo se lako može proveriti De Morganovim zakonom. Na primer: $M_{5}=a'+b+c'=(ab'c)'=m_{5}'$

Nekanonski oblici sume proizvoda i proizvoda sume

Često je slučaj da se kanonska DNF može uprostiti u odgovarajuću sumu proizvoda. Ovo uprošćena forma se sastoji od sume DNFa. Ali, u uprošćenom obliku je moguće da bude manje proizvoda izraza i/ili proizvoda izraza koji sadrže manje promenljivih. Na primer, sledeća funkcija tri promenljive:

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

ima kanonsku DNF: $f=a'bc+abc$, ali ima ekvivalentnu uprošćenu formu: $f=bc$. U ovom trivijalnom primer je očigledno da $bc=a'bc+abc$, ali pošto uprošćeni izraz ima manje i proizvoda izraza i manje promenljivih. Najprostiji proizvode sume funkcije se naziva minimalnim proizvodom sume.

U sličnom stilu, kanonski KNF može da ima uprošćeni izraz proizvoda suma.

Dok je ovaj primer lako uprošćen koristeći normalne algebarske metode [$f=(a'+a)bc$], u manje očiglednim slučajevima zgodan način za nalaženje minimalne sume proizvoda i proizvoda sume je korišćenje Karnoovih mapa.

Minimalni proizvod sume i suma proizvoda su veoma bitni za nalaženje optimalne implementacije Bulovih funkcija i za minimizaciju logičkih kola.

Primer primene

Primer tablice istinitosti DNF i KNF iznad su dovoljni za stvaranje kanonske forme za jednobitne pozicije u sabiranju binarnih brojeva, ali nisu dovoljne za dizajniranje digitalnih kola ukoliko u inventaru nemam kola I i ILI. Gde su performanse bitne (Kao u Apolovom kompjuteru), uglavnom se koriste NI i NILI kola jer je akcija negacije nasleđena iz logike tranzistora. Vrednosti su definisane kao stanja napona, jedno blizu uzemljenju i jedno blizu ulaznog napona V_cc, na primer +5 VDC. Ako je veći napon definisan kao 1 ili istinita vrednost, NILI kolo je najprostiji logički element.

Preciznije, troulazno NILI kolo se može sastojati od 3 bipolarna spoja tranzistora sa uzemljenim odašiljačima, vezanim kolektorom i spojenim na V_cc kroz impedansu. Svaka baza je povezana sa ulaznim signalom i zajednički kolektor predstavlja izlazni signal. Svaki ulaz koji je 1 (visok napon) ka svojoj bazi spaja odašiljač tranzistora sa njegovim kolektorom, čineći da struja prolazi kroz impedansu, što postavlja napon kolektora veoma blizu uzemljenju. Rezultat je nezavisan od svih ostalih ulaza. Samo kada su sva 3 signala 0 (nizak napon) odašiljači-kolektori impedansi sva 3 tranzistora ostaju sa viskom naponom. Ona veoma malo struje prođe, i efekat deljenja napona se impedansom se primenjuje visoki napon veoma blizu V_cc na kolektorima.

Komplementarno svojstvo ovih kola možda izgleda kao mana kada pokušavamo da implementiramo funkciju iz kanonskog oblika, ali ima prednost: takvo kolo sa samo jednim ulazom implementira komplementarnu funkciju, koja je često neophodna u digitalnoj logici.

Ovaj primer pretpostavlja da je Apolo ima samo troulazno NILI kolo, ali je diskusija uprošćena pretpostavkom da su i četvoro ulazna NILI kola bila takođe dostupna (u Apolu su ona bila sastavljena od parova troulaznih NILI kola).

Kanonske i nekanonske posledice primene NILI kola

Prva činjenica: grupa od 8 NILI kola, ako su njihovi ulazi sve kombinacije normalnih i komplementarnih vrednosti tri promenljive ci, x, i y, uvek proizvode DNF, nikad KNF—to jest, od 8 kola potrebnih za obradu svih kombinacija 3 ulazne promenljive, samo jedno ima izlaz 1. To je zato što NILI kola, uprkos imenu, se bolje mogu videti kao I kola sa komplimentiranim ulaznim signalima.

Druga činjenica: razlog zašto prva činjenica nije problem je dualni DNF i KNF, odnosno svaki DNF je komplement slično indeksiranog KNF i obrnuto.

U DNF primeru iznad, napisali smo $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}$ ali da pretvorimo ovo u četvoro ulazno NILI kolo moramo da prepišemo izraz kao proizvod suma, gde su sume suprotne KNF. Odnosno,

$u(ci,x,y)$ = AND($M_{0},M_{3},M_{5},M_{6}$) = NOR($m_{0},m_{3},m_{5},m_{6}$). Tablice istinitosti:

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

U KNF primeru iznad, napisali smo $co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}$, ali da pretvorimo ovo u četvoro ulazno NILI kolo moramo da primetimo jednakost sa NILI od njegovih istih DNF. Odnosno, $co(ci,x,y)$ = AND($M_{0},M_{1},M_{2},M_{4}$) = NOR($m_{0},m_{1},m_{2},m_{4}$) . Tablice istinitosti:

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

Kompromisi dizajniranja pored kanonskih formi

Neko će pretpostaviti da je posao dizajniranja sabirača gotov, ali nismo obratili činjenicu da sve tri ulazne promenljive moraju da se pojave u normalnoj i komplementarnoj formi. Nema poteškoća oko sabiraka x i y u ovom pogledu, jer su statični prilikom celog sabiranja i nalaze se u leč kolima koja imaju i direktan i komplementaran izlaz. (Najprostije leč kolo je napravljeno od NILI kola kao par kola međusobno povezanih da naprave flip-flop; izlaz svakog je povezan za ulazom drugog.) Takođe, nema potrebe da pravimo komplement izraza sume u. Ali, prenos jednog bita se mora prebaciti u sledeću poziciju bita i u direktnoj i u komplementarnoj formi. Najprostije rešenje je da prosledimo co kroz jedno ulazno NILI kolo i da mu damo oznaku co', ali to bi doprinelo kašnjenju kola na najgorem mogućem mestu, usporavajući prenose zdesna nalevo. Dodatno četvoro ulazno NILI kolo koje pravi kanonsku formu od co' (od suprotnih DNF kao co) rešava ovaj problem.

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

Tablice istinitosti:

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

Kompromis za postizanje pune brzine na ovaj način uključuje neočekivanu cenu (pored toga što mora da se koristi veće kolo). Ako bismo koristili jedno ulazno kolo da komplimentiramo co, ne bi bilo koristi za izraz $m_{7}$, i kolo koje je ga je generisalo bi moglo da bude izbačeno. Ali ovo je ipak, dobar kompromis.

Sad bismo mogli da implementiramo te funkcije tačno po njihovim sumama proizvoda i proizvoda suma, pretvarajući NILI kola u potrebne funkcije. Nili kolo se sastoji od ILI kola sa izlazom u jedno ulazno NILI kolo; i napravljeno je kao I kolo sa ulazima od dva jedno ulazna NILI kola. Ali ipak, ovaj pristup ne samo da povećava broj uključenih kola, nego i duplira kašnjenje u preradi signala, smanjujući brzinu obrade na pola. Posledično, kada god su performanse bitne, izlazak van kanonskih formi i rad sa Bulovom algebrom je veoma značajan.

Odozgo nadole protiv odozdo nagore dizajna

Sada smo videli kako DNF/KNF alati mogu da se koriste za dizajniranje sabirača u kanonskim formama sa dodatkom malo Bulove algebre, koštajući nas samo 2 kašnjenja kola za svaki od izlaza. Ovo je odozgo nadole način za dizajniranje digitalnog kola za ovu funkciju, ali da li je to najbolji način? Diskusija je fokusirana na identifikaciju najbržeg i najboljeg, i povećana kanonska forma ispunjava taj uslov savršeno, ali nekada drugi faktori preovlada. Dizajner je možda stavio kao glavni cilj da minimizuje broj kola, ili nešto drugo. U takvom slučaju, dizajner će možda razviti kanonsku formu od početka, i probati odozdo nagore razvoj, i na kraju uporediti rezultat.

Razvoj odozdo nagore uključuje da primetimo da u = ci XOR (x XOR y), gde XOR znači ekskluzivno ILI [istinito samo kada je jedan ulaz istinit, ali ne kada su oba], i da co = ci x + x y + y ci. Jedan takav razvoj uzima 12 NILI kola ukupno: šest dvoulaznih, i dve jednoulazne da naprave u 5 kola zakašnjenja, plus tri dvoulazna kola i jedno troulazno kolo da naprave co' u dva kašnjenja ulaza. Kanonska osnova uzima 8 troulaznih NILI kola plus tri četvoro ulazna NILI kola da napravi u, co i co' u dva kašnjenja kola. Ako u inventaru imamo četvoro ulazna kola, odozgo nadole kanonski dizajn je očigledni pobednik u broju kola i brzini. Ali ako su kola zapravo troulazna NILI kola, od koji su nam dva potrebna za jedno četvoro ulazno NILI kola, onda je za kanonski dizajn potrebno 14 kola u poređenju sa 12 koja su potrebna za odozdo nagore pristup, ali proizvodi sumu cifre u značajno brže. Poređenje u tabeli je:

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

Koja je najbolja odluka? Pronicljivi čitaoci će primetiti da u opisu odozgo nagore razvoja se pominje co' kao izlaz ali ne i co. Da li taj dizajn nema potrebu za direktnim oblikom prekoračenja? Pa, da i ne. U svakoj fazi, kalkulacija co' zavisi samo od 'ci', x' i y', što znači da se tok prekoračenja talasa u poziciji bita istom brzinom kao i kanonski dizajn bez stvaranja co. Kalkulacija u, kome je potreban ci se radi uz pomoć ci' sa jedno ulaznim NILI kolom, je sporija ali za bilo koju dužinu reči, ovaj dizajn plaća tu kaznu samo jednom (kada se najdalje leva cifra stvara). To je zato što se kalkulacije preklapaju. I da budemo sigurni, izlaz co' na najdalje levoj poziciji će verovatno morati da se komplementira kao deo logike koja odlučuje da li sabiranje ima prekoračenja. Koristeći troulazno NILI kolo, odozdo nagore dizajn je veoma blizu po brzini kao i paralelno sabiranje netrivijalnih dužina reči, ali smanjuje broj kola, smanjuje broj ulaza, itd. Što znači da pobeđuje u onim slučajevima gde nam je to značajno.

Literatura

• Edward A. Bender, S. Gill Williamson, 2005, A Short Course in Discrete Mathematics, Dover Publications, Inc., Mineola, NY, ISBN 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, ISBN 978-0-471-39882-0. Minterm and maxterm designation of functions appears on page 101ff.

Spoljašnje veze

• George Boole, 1848, "The Calculus of Logic," Cambridge and Dublin Mathematical Journal III: 183–98.