|
|
Algebarsko-logičke metode Kvajna za minimizaciju Bulovih funkcija
Kvejn je izgradio dve nezavisne algebarsko-logičke metode.Prva od njih uprošćuje Bulov izraz funkcije,ali ne garantuje minimum,dok druga metoda sistematski dovodi do minimalnog normalnog ekvivalenta.
Ekvivalentnost formula Kvajn uvodi na sledeći način: -formula φ implicira formulu ψ,ako ne postoje takve kombinacije vrednosti promenjljivih za koje φ ima vrednost 1, ψ ima vrednos 0. Promenljive ili njihove negacije zovu se literali.Konjunkcije literala u kojima se ni jedna promenljiva ne pojavljuje više od jedanput zovu se termi. Disjunkcija terma zove se normalna forma. Neki term φ može biti suvišan u normalnoj formi tj. φ V ψ ekvivalentno sa ψ. Neki literal ξ može biti suvišan u normalnoj formi,tj. φξ V ψ ekvivalentno sa φ V ψ. Normaln forma je skraćena ako ne sadrži suvišne terme i literale. Algoritam svodjenja normalne forme na skraćeni ekvivalent svodi se na sledeće: -Ispituje se svaki od terma na implikaciju ostatka formule, i isključuje se ako takva implikacija postoji; -Za svaki term bez po jednog literala ispituje se da li važi implikacija ostatka formule.Ako implikacija postoji,taj se literal isključuje.
Metoda sistematskog svodjenja: Polazi se od KDNF.Term φ sadrži ψ akko se svi literali ψ nalaze u φ. Term φ je prosta implikacija za formulu ψ akko φ implicira ψ i ne sadrži podterm koji bi takodje implicirao ψ.
Algoritam minimizacije po Kvajnu može se ovako opisati: Za datu KDNF C1VC2V...VCk(Ci su termi),sve proste implikacije odredjuje se na sledeći način: 1)Ako se javljaju dva terma oblika xξ ili 
, onda se zajednički deo x uključuje u spisak nove vrste;2)Svi termi se zadržavaju u spisku i mogu se iskoristiti višekratno za druge kombinacije sparivanja, a termi koji učestvuju u sparivanju se markiraju; 3)Kada novih mogućnosti sparivanja nema,nemarkirani termi u spisku su proste implikacije. Proste implikacije se grupišu tako da svaki term Ci(i=1,...,k) sadrži neku prostu implikantu. Svaka najprostija grupa prostih implikacija koja pokriva sve terme Ci(i=1,...,k), predstavlja se u formi disjunkcije i predstavlja minimalni normalni ekvivalent date funkcije.