Prekidačka algebra – Boole-ova algebra – Algebra logike
5. Minimizacija prekidačkih funkcija

5.2 Karnoova (Karnaugh) metoda minimizacije

Karnoova metoda minimizacije koristi matričnu mrežu polja, čiji je broj jednak vrijednosti , gdje je n broj nezavisno promjenljivih veličina. Dakle, broj polja može biti 2, 4, 8, 16, itd. Na sljedećoj slici ucrtane su Karnoove tablice (K-tablice) za prikazivanje funkcija sa 2, 3 i 4 promjenljive. Svako polje u tim tablicama odgovara jednom potpunom proizvodu promjenljivih veličina date funkcije.

Raspored logičkih proizvoda po poljima tablice izvodi se tako, da se članovi potpunih proizvoda u susjednim poljima ili površinama razlikuju samo po vrijednosti jedne promjenljive. Pri tome je očigledno da su susjedna polja ona koja imaju zajedničku stranicu, ali isto tako i ona kod kojih bi se ostvarila zajednička stranica kada bi se sastavile naspramne strane tablice.
Način korištenja Karnoovih tablica pokazaćemo na nekoliko primjera. Neka je data funkcija u SOP obliku

Očigledno je da ova funkcija sa 4 promjenljive ima nepotpune logičke proizvode, pa se stoga oni ne mogu direktno unijeti u Karnoovu tablicu. Funkcija se mora proširiti tako da se dobiju potpuni proizvodi

Ovako dobijeni potpuni proizvodi unijeti su u K-tablicu tako što su odgovarajuća polja obilježena sa 1, kao na sljedećoj slici (preostala polja ostaju prazna, nule se ne upisuju):

Definišimo i red zajedničkih površina u tablici: dva susjedna polja čine površinu prvog reda , dve susjedne površine prvog reda čine površinu drugog reda  koja ima 4 polja, dve susjedne površine drugog reda čine površinu trećeg reda  koja ima 8 polja, itd. Važi pravilo da će broj promjenljivih u funkciji, koja odgovara zajedničkoj površini, biti smanjen za vrijednost reda površine. Što je veći broj susjednih polja i površina to je i moguća minimizacija funkcije veća.
U ovom primjeru je očigledno da susjedna polja  i  čine površinu prvog reda, dok polja  čine površinu drugog reda. Konačna vrijednost minimizirane funkcije se nalazi tako što se za svaku zajedničku površinu ispisuju samo promjenljive koje su identičnih vrijednosti u svim poljima u okviru te površine. Stoga se redovno zajedničke površine uokviruju, da bi se lakše izvršilo očitavanje odgovarajućih članova funkcije iz tablica.
Dakle, za površinu prvog reda koju čine polja  i  imaćemo (0 negacija, 1 bez negacije):

Za površinu drugog reda koju čine polja  imaćemo :

Prema tome, konačni oblik minimizirane funkcije je

Algebarska metoda minimizacije    <    Index    >    Karnoova (Karnaugh) metoda minimizacije - Drugi primjer