MINIMIZACIJA LOGIČKIH FUNKCIJA

1. UVOD

Savremeni tehnološki problemi su veoma složeni i njihovo rješavanje zahtijeva učešće inženjera i istraživača iz raznih oblasti nauke i tehnike, koji se organizuju u razvojne ili istraživačke timove. U takvim uslovima inženjer, koji je specijalizovan za određenu oblast, često treba da radi sa stručnjacima drugih specijalnosti.

Da bi se olakšala saradnja inženjera različitih specijalnosti potrebno je da svaki od njih bar djelimično poznaje srodne oblasti tehnike, kako bi razumio probleme i ograničenja u rješavanju problema u cjelini. Zbog toga se u svijetu, prilikom obrazovanja inženjera uvek proučavaju i oblasti koje nisu direktno u vezi sa odabranom specijalizacijom.

U savremenom svijetu svedoci smo da električni ili elektronski uređaji prodiru u sve oblasti života. Automobili imaju elektronske uređaje za nadzor i upravljanje, uređaji bijele tehnike u domaćinstvu imaju sve više elektronskih funkcija, mobilni telefoni su napravili revoluciju u telekomunikacijama, uvođenje računara i Interneta u kuće, porodice je promijenilo način života, itd.

Složenu strukturu koja obezbjeđuje potrebnu funkcionalnost računarskom sistemu moze se opisati putem logičkih funkcija.

2. LOGIČKE FUNKCIJE

Već je rečeno da se rad računarskih sistema u suštini zasniva na primjeni logičkih operacija nad binarnim vrijednostima. Kombinovanjem različitih logičkih kola mogu se dobiti vrlo složene logičke strukture koje obezbjeđuju potrebnu funkcionalnost u računarskom sistemu. Te strukture se opisuju logičkim funkcijama. S obzirom da se binarna logika (0 ili 1, ima ili nema signala) jednostavno može predstaviti prekidačkim elementom, logičke funkcije se često nazivaju i prekidačkim funkcijama.

Između aritmetičkih i logičkih funkcija postoje sličnosti, ali i značajne razlike. Logičke funkcije su jednostavnije od aritmetičkih jer operišu nad binarnim skupom vrijednosti. Međutim, način razmišljanja karakterističan za logičke funkcije se često teško usvaja zbog navike stečene u radu sa aritmetičkim funkcijama u ranijem periodu.

Logička funkcija Y se, slično aritmetičkoj, može definisati nad proizvoljnim brojem promjenljivih A, B, C, … na sljedeći način:

Y = f(A, B, C, …)

Osnovna razlika u odnosu na aritmetičku funkciju je u tome što vrijednost logičke funkcije Y mora pripadati skupu {0,1}. Takođe, i vrijednosti promenljivih u logičkim funkcijama moraju pripadati istom skupu, tj. mogu biti samo 0 ili 1. Pošto se vrijednosti 0 i 1 nazivaju logičkim, to se i promjenljive u logičkim funkcijama nazivaju logičkim promjenljivama.

Logičke promjenljive u logičkoj funkciji su međusobno povezane logičkim operacijama (I, ILI, NE,…). Vrijednost logičke funkcije za zadate vrijednosti logičkih promjenljivih dobija se kao rezultat izvršavanja logičkih operacija korišćenih u logičkoj funkciji.

Predstavljanje logičkih funkcija

 

Logičke funkcije se mogu predstavljati na različite načine. U nastavku će biti opisana tri često primjenjivana načina: pomoću kombinacione tablice, u vidu algebarskog izraza i pomoću Karnoovih karti. Zatim će biti pokazano kako se neka logička funkcija predstavljena na jedan od opisanih načina može prikazati na neki drugi način.

• Kombinacione tablice

Pošto logičke funkcije zavise od konačnog broja logičkih promjenljivih (n), pri čemu svaka promjenljiva može imati samo dvije vijrednosti, 0 ili 1, to je broj mogućih različitih kombinacija promjenljivih 2n. Iz ovoga slijedi da logičke funkcije imaju konačnu oblast definisanosti. Zahvaljujući tome, one se mogu predstaviti pomoću tablica koje se nazivaju kombinacionim tablicama ili tablicama istinitosti.

Kombinaciona tablica predstavlja tabelu u kojoj su date vrijednosti logičke funkcije za sve moguće kombinacije vrijednosti logičkih promenljivih koje se u njoj pojavljuju.

• Algebarski oblik funkcije

Kao što je ranije rečeno, iako se svaka prekidačka funkcija može predstaviti kom- binacionom tablicom, za funkcije većeg broja promjenjivih to nije pogodna forma predstavljanja. U tom slučaju je bolje koristiti druge načine predstavljanja, kao na primjer algebarski prikaz logičke funkcije.

U algebarskom prikazu, logička funkcija se predstavlja algebarskim izrazom koga čine logičke promjenljive međusobno povezane logičkim operacijama (I, ILI, NE, …). Postoje različiti načini algebarskog predstavljanja logičke funkcije. Jedan od često korišćenih načina je primjena tzv. savršenih normalnih formi. Savršene normalne forme se pojavljaju u dva oblika, kao: savršena disjunktivna normalna forma (SDNF)

• savršena konjuktivna normalna forma (SKNF)

Neka je data logička funkcija Y koja zavisi od n logičkih promenljivih A1, A2, …, An. Bilo koja logička promjenljiva, osim svoje originalne vijrednosti (na primjer A) ima i svoju negiranu vrijednost (Ā). Označimo sa à promenljivu A ili njenu negiranu vrijednost Ā, tj. Ã=A ili Ã=Ā. Uvedimo sada dva nova pojma: potpuni proizvod i potpunu sumu.

Potpuni proizvod predstavlja logički proizvod Ã1Ã2 … Ãn. Dakle, to je proizvod u kome se pojavljuju sve promjenljive od kojih zavisi logička funkcija (zbog toga se proizvod i zove potpunim), s tim što neke od promjenjivih imaju svoju originalnu, a neke negiranu vrijednost. Potpuni proizvod ima vrijednost 1 samo za jednu kombinaciju vrijednosti promenljivih, dok za sve ostale kombinacije ima vrijednost 0.

Na sličan način, potpuna suma se definiše kao logički zbir Ã1+Ã2+ … +Ãn. U potpunoj sumi se, takođe, pojavljuju sve promjenljive funkcije (što opravdava naziv potpuna) bilo u svojoj originalnoj ili negiranoj vrijednosti.

Potpuna suma ima vrijednost 0 samo za jednu kombinaciju vrijednosti promjenljivih, dok za sve ostale kombinacije ima vrijednost 1.

Primjenom uvedenih pojmova mogu se definisati SDNF i SKNF. SDNF predstavlja logički zbir potpunih proizvoda, a SKNF logički proizvod potpunih suma.

Postupak predstavljanja logičke funkcije u algebarskom obliku korišćenjem SDNF opisan je teoremom čije će tvrđenje biti dato bez dokaza:

Teorema 1: Svaka logička funkcija Y=f(A1, A2, …, An), izuzev konstante nula, može se na jedinstven način napisati u obliku

Y = P1  + P2 +…+ Pm       (m ≤ 2n)

gdje su P1, P2, …, Pm potpuni proizvodi koji odgovaraju kombinacijama vrijednosti promjenljivih za koje funkcija Y ima vrijednost 1, tj. kao SNDF.

Na sličan način, logička funkcija se u algebarskom obliku može predstaviti i korišćenjem SKNF u skladu sa sledećom teoremom:

Teorema 2: Svaka logička funkcija Y=f(A1, A2, …, An), izuzev konstante jedinica, može se na jedinstven način napisati u obliku

Y = S1  S2 … Sm        (m ≤ 2n)

gde su S1, S2, …, Sm potpune sume koje odgovaraju kombinacijama vrednosti promenljivih za koje funkcija Y ima vrednost 0, tj. kao SKNF.

Tvrđenja ovih teorema biće ilustrovana na jednom primeru. Neka je data logička funkcija Y koja zavisi od tri logičke promenljive, tj. Y=f(A1, A2, A3). Neka funkcija ima vrednost 1 za sledeće kombinacije vrednosti promenljivih A1, A2 i A3: 010, 100, 101 i 111. Za sve ostale kombinacije vrednosti promenljivih, funkcija ima vrednost 0.

Prema prvoj teoremi, za kombinacije na kojima funkcija ima vrednost 1 mogu se formirati sledeći potpuni proizvodi:

P1 = Ā1 A2 Ā3, P2 = A1 Ā2 Ā3, P3 = A1 Ā2 A3 i P4 = A1 A2 A3.

Potpuni proizvodi su formirani tako što, ukoliko je vrednost promenljive u kom- binaciji 1, promjenljiva ulazi u proizvod sa svojom originalnom vrijednošću, a ako je vrednost 0, u proizvod se uključuje negirana vijrednost promjenljive. Sada se, po tvrđenju teoreme, logička funkcija Y može predstaviti u algebarskom obliku u vidu SDNF, ili tzv. sume proizvoda kao:

Y = Ā1 A2 Ā3 + A1 Ā2 Ā3 + A1 Ā2 A3 + A1 A2 A3

Dakle, logička funkcija se predstavlja u vidu sume proizvoda tako što se operacijom logičkog sabiranja ILI povežu svi potpuni proizvodi koji odgovaraju kombinacijama vrednosti promenljivih za koje funkcija ima vrijednost 1. Iz datog  algebarskog izraza slijedi da ukoliko logičke promenljive dobiju vrijednosti koje odgovaraju jednoj od gore navedenih kombinacija, taj proizvod u zbiru postaje 1 (ostali proizvodi su 0), pa vrijednost funkcije postaje 1 (rezultat logičkog sabiranja je 1 ako je bar jedan sabirak jednak 1).

Ista logička funkcija može se predstaviti i u vidu SKNF, ili tzv. proizvoda suma. Prema drugoj teoremi, za kombinacije na kojima funkcija ima vrijednost 0, a to su kombinacije 000, 001, 011 i 110, mogu se formirati sljedeće potpune sume:

S1 = A1+A2+A3, S2 = A1+A2+Ā3, S3 = A1+Ā2+Ā3 i S4 = Ā1+Ā2+A3

• Karnoova karta

Osim kombinacionih tablica, za predstavljanje logičkih funkcija često se koristi još jedan tabelarni prikaz, a to je Karnoova (Karnaugh) karta. Ova karta, kao i kom- binaciona tablica, predstavlja tabelu u kojoj su date vrijednosti logičke funkcije za sve moguće kombinacije vrijednosti logičkih promenljivih koje se u njoj pojavljuju. Razlika između ovih tabela je u njihovoj organizaciji.

Karnoova karta koja prikazuje logičku funkciju Y sa n logičkih promjenljivih ima ukupno 2n polja (koliko ima i mogućih kombinacija vrijednosti promjenljivih). Ukoliko je n paran broj, tabela ima 2n/2 vrsta i 2n/2 kolona, a ako je n neparan broj, 2(n-1)/2 vrsta i 2(n+1)/2 kolona (ili obrnuto, 2(n-1)/2 kolona i 2(n+1)/2 vrsta). Ovakvim rasporedom vrsta  i kolona postiže se da Karnoova karta ima izgled što sličniji kvadratu, što doprinosi njenoj preglednosti.

Svakom polju u Karnoovoj karti odgovara jedna kombinacija vrijednosti logičkih promjenljivih funkcije. O kojoj kombinaciji je reč, određeno je binarnim oznakama vrsta i kolona. Naime, svakoj vrsti i koloni pridružena je binarna oznaka koja ukazuje na vrijednosti koje neka logička promjenljiva ima u toj vrsti ili koloni. Da bi se pokazao način formiranja oznaka vrsta i kolona, najprije će biti uvedene neke pretpostavke.

Pretpostavimo da je skup svih promjenljivih funkcije podjeljen u dva podskupa. Broj elemenata u podskupovima je uslovljen brojem vrsta, odnosno kolona u Karnoovoj karti. Tako, ukoliko je n paran broj, podskupovi imaju po n/2 elemenata, a ako je n neparan broj, jedan podskup ima (n-1)/2 elemenata, a drugi (n+1)/2 elemenata.

Pretpostavimo sada da je jedan podskup pridružen vrstama, a drugi kolonama (u slučaju parnog n, potpuno je svejedno koji podskup se pridružuje vrstama, a koji kolonama, dok u slučaju neparnog n, broj vrsta i kolona mora biti usklađen sa brojem elemenata u podskupu). Izbor konkretnih logičkih promjenljivih koje će se naći u podskupovima može biti napravljen na različite načine i za svaki učinjeni izbor, Karnoova karta  je ispravno definisana.

Na osnovu uvedenih pretpostavki, oznake vrsta i kolona se formiraju kao sve moguće kombinacije vrijednosti promjenljivih koje se pojavljuju u podskupovima pridruženim vrstama, odnosno kolonama.

Pri raspoređivanju kombinacija po poljima Karnoove karte mora se poštovati pravilo da se kombinacije koje odgovaraju susjednim poljima u Karnoovoj karti razlikuju samo u jednoj vrijednosti (cifri). To se postiže tako što se poštuje pravilo da se i susjedne oznake vrsta, odnosno kolona, takođe mogu razlikovati samo u jednoj vrednosti (cifri). Karnoova karta se popunjava tako što se u svako polje unosi vrijednost koju funkcija ima za kombinaciju promjenljivih koja odgovara tom polju.

Realizacija logičkih funkcija

Način funkcionisanja računarskog sistema u velikoj mjeri se može opisati logičkim funkcijama. S obzirom da one, kao i sve druge funkcije, predstavljaju apstraktan pojam, da bi se prešlo sa opisa sistema na sistem koji zaista radi, neophodno je fizički realizovati logičke funkcije koje opisuju sistem. Logičke funkcije se realizuju pomoću prekidačkih mreža koje predstavljaju najvažnije komponente računara i drugih digitalnih sistema.

Prekidačke mreže se sastoje od skupa elemenata povezanih tako da realizuju zadatu logičku funkciju. To znači da kada se na ulaze mreže dovedu određeni binarni signali, na njenim izlazima se dobijaju, u skladu sa logičkom funkcijom koju realizuju, očekivane binarne vrijednosti.

Prema funkcijama koje realizuju, prekidačke mreže se dijele na kombinacione i sekvencijalne. Glavna osobina kombinacione mreže je da vrijednost na njenom izlazu (vrijednost logičke funkcije) zavisi samo od trenutnog stanja na njenom ulazu (vrijednosti logičkih promenljivih funkcije).

Kombinacione mreže se realizuju kao kompozicija logičkih elemenata. Logički elementi, po pravilu, realizuju samo jednu jednostavnu prekidačku funkciju (imaju samo jedan izlaz). Opisuju se funkcijom koju realizuju, grafičkim simbolom i nazivom elementa. U logičke elemente, između ostalih, spadaju logička kola I, ILI, NE, ekskluzivno ILI, itd. Za razliku od kombinacione, kod sekvencijalne mreže vrijednost na izlazu (vrijednost logičke funkcije) zavisi, ne samo od trenutnog stanja na ulazu (vrijednosti logičkih promenljivih), već i od stanja u kome se mreža nalazi u datom trenutku (vrijednosti na unutrašnjim linijama mreže).

Sekvencijalne mreže se realizuju kao kompozicija logičkih i memorijskih elemenata, ili samo logičkih elemenata.

Da li će kompozicija logičkih elemenata predstavljati kombinacionu ili sekvencijalnu mrežu, zavisi od načina povezivanja.

Memorijski elementi se obično realizuju kao kompozicija logičkih elemenata. Glavna osobina memorijskih elemenata je da imaju samo dva stanja na koja utiču povratne veze koje postoje u strukturi ovih elemenata. Primjer memorijskih elemenata su flipflopovi.

Rad sa prekidačkim mrežama podrazumjeva rješavanje dve vrste problema. U nekim slučajevima potrebno je za postojeću prekidačku mrežu odrediti funkciju koju ona obavlja. Rješavanje ovog problema je predmet analize prekidačke mreže.

Međutim, moguća je i obrnuta situacija u kojoj je potrebno zadatu logičku funkciju realizovati pomoću prekidačke mreže. Ovaj postupak se naziva sintezom prekidačke mreže.

U ovom poglavlju će biti opisan jedan postupak sinteze prekidačke mreže koja realizuje logičku funkciju zadatu u aglebarskom obliku (ukoliko je funkcija predstavljena na neki drugi način, ranije opisanim postupcima može se prevesti u algebarski oblik).

Neka je data logička funkcija Y koja zavisi od nepromenljivih međusobno povezanih logičkim operacijama. Ona se može realizovati prekidačkom mrežom koja:

• ima n ulaza koji odgovaraju logičkim promjenljivama i jedan izlaz koji predstavlja vrijednost funkcije Y
• ima onoliko različitih vrsta logičkih kola (NE, I, ILI, …) koliko ima različitih logičkih operacija u funkciji
• ima onoliko logičkih kola jedne vrste koliko ih je potrebno za obavljanje svih logičkih operacija te vrste u funkciji.

Ovo će biti ilustrovano na primjeru funkcije Y  ABC  ABC  ABC  ABC .

Prekidačka mreža koja realizuje ovu funkciju ima tri ulaza koja odgovaraju promjen- ljivama A, B i C i jedan izlaz Y. U strukturi prekidačke mreže postoje tri vrste logičkih kola: NE, I i ILI. Pošto se svaka promjenljiva u funkciji pojavljuje i kao negirana vrijed- nost, prekidačka mreža mora da sadrži 3 invertora (NE kola). Osim toga, za realizaciju svakog člana u zbiru potrebno je po jedno I kolo, što ukupno zahtjeva 4 logička I kola (ovde se dopušta da logičko I kolo ima više ulaza i jedan izlaz). Takođe, potrebno je i jedno ILI kolo sa više ulaza za realizaciju logičkog zbira.

U praktičnoj realizaciji, pogodno je poći od izlaza prekidačke mreže. Kao što se iz funkcije vidi, vrijednost Y se dobija kao logički zbir četiri binarna signala. Stoga izlaz prekidačke mreže treba istovremeno da bude i izlaz logičkog ILI kola. Na ulaze ILI kola treba dovesti 4 binarna signala koji odgovaraju članovima zbira.

To se može postići tako što se na svaki ulaz ILI kola dovede izlaz I kola koje realizuje odgovarajući član zbira. Da bi I kolo realizovalo član zbira, na njegove ulaze treba dovesti odgovarajuću kombinaciju logičkih promjenljivih koje se u njemu pojavljuju. Ako se promjenljiva u članu javlja kao originalna vrednost, na ulaz I kola se dovodi direktno sa ulaza prekidačke mreže, a ako se javlja kao negirana vrijednost, mora se dovesti sa izlaza logičkog NE kola na čiji je ulaz dovedena originalna vrijednost te promjenljive sa ulaza prekidačke mreže.

3. MINIMIZACIJA LOGIČKIH FUNKCIJA

Struktura prekidačke mreže (broj logičkih kola i način njihovog povezivanja) zavisi od algebarskog izraza kojim je predstavljena logička funkcija. U većini algebarskih načina predstavljanja, ista logička funkcija se može napisati u vidu različitih algebarskih izraza koji ne moraju biti jednako pogodni za praktičnu realizaciju. Sa stanovišta ekonomičnosti i efikasnosti, cilj je da se za realizaciju funkcije upotrebi što manji broj logičkih kola uz što manje veza između njih.

Minimizacijom se naziva postupak određivanja najprostijeg između više algebarskih izraza kojima se logička funkcija može predstaviti. Naziv postupka potiče od toga što se za poređenje izraza koristi neka veličina koja u najprostijem izrazu ima minimalnu vrijednost (na primer broj operacija, broj simbola i sl.).

Postoje različite metode minimizacije logičkih funkcija. Za ranije opisane algebarske načine predstavljanja funkcija, najopštija podjela metoda minimizacije je na grafičke i algoritamske. Grafičke metode se zasnivaju na vizuelnoj analizi grafički predstavljene logičke funkcije. Ove metode su teorijski vrlo jednostavne, a pogodne su za funkcije sa manje promjenljivih (do 6).

Algoritamske metode koriste razne algoritme za transformisanje analitički ili tabelarno predstavljene funkcije. Složenije su od grafičkih metoda, ali su zato efikasne i u slučaju funkcija sa znatno većim brojem promjenljivih.

Može se prikazati najčešće korišćenja grafička metoda minimizacije koja se zasniva na primjeni Karnoove karte. Metoda će biti samo opisana, tj. tvrdnje i pravila na kojima ona zasniva neće biti dokazivani.

Postupak minimizacije logičke funkcije pomoću Karnoove karte sprovodi se u tri koraka:

1. zadatu logičku funkciju predstaviti popunjenom Karnoovom kartom na ranije opisan način
2. od polja Karnoove karte u kojima logička funkcija ima vrijednost 1 formirati pravougaone površine poštujući unapred definisana pravila
3. na osnovu pravougaonih površina, po određenim pravilima, ispisati minimalni zapis logičke funkcije u vidu sume proizvoda

Pri formiranju pravougaonih površina, moraju biti poštovana sljedeća pravila:

• pravougaone površine sadrže samo ona polja Karnoove karte u kojima logička funkcija ima vrednost 1 (nijedno polje sa vrijednošću 0 ne može pripadati pra- vougaonoj površini)
• broj polja u pravougaonoj površini može biti samo 2k, k = 0,1,2,… (površina može imati samo 1,2,4,8, … polja)
• jednu pravougaonu površinu mogu da čine samo susedna polja u kojima je vrijednost logičke funkcije 1
• pravougaone površine treba da budu što je moguće veće (da sadrže što više polja), a njihov broj što manji
• prema potrebi, isto polje može se naći u više pravougaonih površina

Nakon formiranja pravougaonih površina, može se pristupiti ispisivanju minimalnog zapisa logičke funkcije. Minimalni zapis ima oblik sume proizvoda sa onoliko članova (proizvoda) koliko ima pravougaonih površina, jer se za svaku pravougaonu površinu generiše po jedan član (proizvod) sume. Proizvod koji odgovara jednoj pravougaonoj površini dobija se analizom oznaka vrsta i kolona za sva polja koja pripadaju toj površini. On se formira tako što se za svaku logičku promjenljivu pojedinačno analizira da li ona ulazi u proizvod i, ako ulazi, na koji način. Ova analiza se obavlja po sledećim pravilima:

• ako u oznakama vrsta koje odgovaraju pravougaonoj površini promjenljiva ima vrijednost i 0 i 1 (u oznaci jedne vrste ima vrijednost 1, a u oznaci neke druge vrste vrednost 0), ta promjenljiva ne ulazi u proizvod
• ako u svim oznakama vrsta koje odgovaraju pravougaonoj površini promen- ljiva ima vrednost 1, ta promenljiva ulazi u proizvod sa svojom originalnom vrednošću
• ako u svim oznakama vrsta koje odgovaraju pravougaonoj površini promjenljiva ima vrijednost 0, ta promjenljiva ulazi u proizvod sa svojom negiranom vrijednošću
• ako u oznakama kolona koje odgovaraju pravougaonoj površini promjenljiva ima vrijednost i 0 i 1 (u oznaci jedne kolone ima vrednost 1, a u oznaci neke druge kolone vrednost 0), ta promenljiva ne ulazi u proizvod
• ako u svim oznakama kolona koje odgovaraju pravougaonoj površini promen- ljiva ima vijrednost 1, ta promjenljiva ulazi u proizvod sa svojom originalnom vrijednošću
• ako u svim oznakama kolona koje odgovaraju pravougaonoj površini promen- ljiva ima vrijednost 0, ta promjenljiva ulazi u proizvod sa svojom negiranom vrijednošću

Iako opisani postupak minimizacije pomoću Karnoove karte izgleda prilično složeno, već nakon nekoliko praktično urađenih primjera, on prelazi u rutinu. U nastavku će biti prikazano nekoliko karakterističnih primjera minimizacije logičke funkcije Y koja zavisi od četiri logičke promenljive A, B, C i D

Primjer : Minimizirati logičku funkciju zadatu Karnoovom kartom na slici.

Y(1) ={2, 3, 6, 8, 9, 10, 11, 12}.

Rešenje: Pri formiranju pravougaonih površina, pogodno je poći od onih polja sa vrijednošću 1 koja nemaju susednih polja, ili, ako takvih nema, od polja sa najmanjim brojem susednih polja. Ovaj princip se dalje može koristiti do kraja postupka formiranja pravougaonih površina.

U ovom primjeru postoji samo jedno polje koje nema susednih, a to je polje kome odgovara kombinacija 0001. Stoga se od njega formira prva pravougaona površina koja ima samo jedno polje. Sljedeće polje sa najmanje susjeda odgovara kombinaciji 1101. Ono ima samo jednog susjeda (polje 1100) i stoga mora sa njim formirati pravougaonu površinu. Polje 1100 ima i drugog susjeda, polje 1110, ali za njih nema potrebe formirati pravougaonu površinu, jer je polje 1110 bolje uključiti u veću pravougaonu površinu sa ostalim poljima posljednje kolone.

Pošto su formirane pravougaone površine, može se ispisati minimalna forma logičke funkcije. Ona predstavlja sumu proizvoda od tri člana. Neka prvi član odgo- vara pravougaonoj površini od jednog polja, drugi od dva polja, a treći površini od četiri polja.

Prvi član se generiše sljedećom analizom:

• pošto u oznaci prve vrste promjenljivama A i B odgovaraju vrijednosti 0, obje promjenljive ulaze u proizvod kao negirane vrijednosti
• pošto u oznaci druge kolone promjenljivoj C odgovara vrednost 0, a promenljivoj D vrednost 1, onda promenljiva C ulazi u proizvod kao negirana, a promenljiva D kao originalna vrednost

Drugi član se generiše sledećom analizom:

• pošto u oznaci treće vrste promenljivama A i B odgovaraju vrijednosti 1, obe promjenljive ulaze u proizvod kao originalne vrijednosti
• pošto u oznakama prve i druge kolone promjenljivoj C odgovara vrednost 0, ona u proizvod ulazi kao negirana vrijednost
• pošto u oznakama prve i druge kolone promenljivoj D odgovaraju vrijednost 0 u prvoj koloni, a vijrednost 1 u drugoj, to vrijednost ove promjenljive ne utiče na vrijednost funkcije u ovoj površini, pa promjenljiva D ne ulazi u proizvod

Treći član se generiše sljedećom analizom:

• pošto u oznakama vrsta (od prve do četvrte) promjenljivama A i B odgovaraju vrijednosti bilo 0 bilo 1, ove promenljive ne ulaze u proizvod
• pošto u oznaci četvrte kolone promjenljivoj C odgovara vrijednost 1, a promjenljivoj D vrijednost 0, onda promjenljiva C ulazi u proizvod kao originalna, a promjenljiva D kao negirana vrijednost

Na osnovu sprovedene analize, dobija se sljedeća minimalna forma funkcije:

Y = ABCD + ABC + CD

Iz dobijenog izraza se vidi da je proizvod u sumi jednostavniji ukoliko mu odgovara pravougaona površina sa više polja.

Primjer :Naći minimalnu formu logičke funkcije zadate skupom indeksa

Y(1) ={2, 3, 6, 8, 9, 10, 11, 12}.

Rješenje: U ovom primjeru postoje dva polja (0011 i 0110) koja imaju samo po jedno susedno polje. Stoga se za svako od ovih polja mora napraviti pravougaona površina koja obuhvata to polje i njemu susjedno. Pošto je susjedno polje u oba slučaja isto (polje 0010), to će ono biti uključeno u dvije pravougaone površine, što je dozvoljeno. Poslednja pravougaona površina obuhvata četiri preostale sujsedne jedinice.

Minimalna forma logičke funkcije ima tri člana. Neka prvi član odgovara površini koju čine polja 0011 i 0010, drugi površini koju čine polja 0010 i 0110, a treći površini od četiri polja.

Prvi član se generiše sljedećom analizom:

• pošto u oznaci prve vrste promjenljivama A i B odgovaraju vrijednosti 0, obje promenljive ulaze u proizvod kao negirane vrednosti,
• pošto u oznakama treće i četvrte kolone promjenljivoj C odgovara vrijednost 1, a promjenljivoj D i 0 i 1, to u proizvod ulazi samo promjenljiva C i to kao origi- nalna vrijednost.

Drugi član se generiše sljedećom analizom:

• pošto u oznaci poslednje kolone promenljivoj C odgovara vrednost 1, a promjen- ljivoj D vrijednost 0, to promjenljiva C ulazi u proizvod kao originalna vrijjednost, a promenljiva D kao negirana,
• pošto u oznakama prve i druge vrste promjenljivoj A odgovara vrijednost 0, a promjenljivoj B i 0 i 1, to u proizvod ulazi samo promjenljiva A i to kao negirana vrijednost.

Treći član se generiše sljedećom analizom:

• pošto u oznakama treće i četvrte vrste promjenljivoj A odgovara vrijednost 1, a promjenljivoj B i 0 i 1, to u proizvod ulazi samo promjenljiva A i to kao originalna vrijednost,
• pošto u oznakama prve i druge kolone promjenljivoj C odgovara vrijednost 0, a promenljivoj D i 0 i 1, to u proizvod ulazi samo promenljiva C i to kao negi- rana.

Na osnovu sprovedene analize, dobijena je sljedeća minimalna forma funkcije:

Y = ABC + AC D + AC

Iz navedenog izraza može se zaključiti da pravouganim površinama sa istim brojem polja odgovaraju proizvodi sa istim brojem promjenljvih (za površine od dva polja, proizvodi sadrže tri promjenljive, a za površinu od četiri polja, samo dve). Ova činjenica može da posluži za brzu provjeru ispravnosti formiranih proizvoda.