Minimalizacija kola

U Bulovoj algebri, minimalizacija kola (sreće se i izraz „minimizacija“) je problem dobijanja najmanjeg logičkog kola (Bulova konfiguracija) koje predstavlja datu bulovu funkciju ili tablicu istinitosti. Opšti problem minimalizacije kola je računski težak, ali postoje efikasne heuristike kao što su Karnoove karte i Kvajn–Maklaskijev algoritam koje olakšavaju proces.

Svrha

Problem sa komplikovanim kolom (tj. kolom sa mnogo elemenata , kao sto su logička vrata koja predstavljaju elektronski sklop koji sliži za ostvarenje logičke operacije) sastoji se u tome da zauzima fizički prostor za njegovo sprovođenje i što se potroši vreme i novac za njegovu proizvodnju. Mimimizacija kola može biti jedan oblik logičke optimizacije, koji se koristi da bi se smanjilo područje kompleksne logike u integrisanim kolima.

Primer

Iako postoji mnogo načina da se minimalizuje (smanji) kolo, ovo je primer koji minimalizuje (ili pojednostavljuje) bulovu funkciju. Treba imati na umu da je Bulova funkcija, izvedna pomoću kola, u direktnoj vezi sa algebarskim izrazom iz kojeg se realizuje funkcija. Razmotrimo kolo koje se koristi da predstavi $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)$. Evidentno je da su u ovom kolu upotrebljene dve negacije , dve konjunkcije i disjunkcija. To znači da su za izgradnju kola potrebno dva invertora , dvoje I vrata i ILI vrata.

Kolo se može pojednostaviti primenom logičkih identiteta ili pomoću intuicije. Pošto se u primeru navodi da je A tačno kada je B netačno ili obrnuto, može se zaključiti da ovo jednostavno znači $A\neq B$. U izrazima logičkih vrata, nejednakost jednostavno znači EKSILI vrata (ekskluzivno ILI). Prema Tome, $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B$. Tada su dva kola, prikazana ispod, ekvivalentna:

Ispravnost rezultata može se dodatno proveriti pomoću tablice istinitosti.

Literatura

• De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994, Part III, Logic-Level Syntesis and Optimization
• Zvi Kohavi, Niraj K. Jha (2009). Switching and Finite Automata Theory (3rd izd.). Cambridge University Press. ISBN 978-0-521-85748-2. 
• Knuth, Donald E. (2010). „chapter 7.1.2: Boolean Evaluation”. The Art of Computer Programming. 4A. Addison-Wesley. str. 96—133. ISBN 978-0-201-03804-0.