Карноова карта

Карно (Karnaugh) мапу (скраћено К-мапа) је измислио 1950, Морис Карно, тада телекомуникацијски инжењер у Бел лабораторији. Она је веома корисна алатка за рад са буловим изразима. Нормално је потребно мноштво калкулација да би се добио минимални израз булове функције, и у ову сврху можемо користити К-мапу. Карно користи чињеницу да људски мозак има одличну способност препознавања мустри да би се донела одлука који се елементи булове функције требају комбиновати да би се добио најједноставнији израз.

Као додатак, К-мапе дозвољавају брзу идентификацију и елиминацију потенцијалних race(?) хазарда, што булове једначине саме не могу да ураде.

Карноова мапа је одлична алатка за поједностављивања до шест варијабли, док је код више варијабли чак и нашем мозгу тешко да нађе оптималне мустре. За изразе који имају више од четири варијабле треба користити Кјуин-Меккласки алгоритам, који се такође зове и метод prime implicants. Овај алгоритам користи детерминистички приступ поједностављењу булских израза. Стога праћење корака алгоритма омогућава да се може наћи најједноставнији израз. Ово је посебно корисно за креацију софтверских програма који поједностављују било који задат булски израз. Карно мапе такође уче у вези булских функција и минимилизацији.

Пример

Погледај сљедећу функцију:

f(A, B, C, D) = E(4, 8, 9, 10, 11, 12, 14, 15)

Ова функција има ову истинитосну таблицу:

A B C D   f 
0 0 0 0   0
0 0 0 1   0
0 0 1 0   0
0 0 1 1   0
0 1 0 0   1
0 1 0 1   0
0 1 1 0   0 
0 1 1 1   0
1 0 0 0   1
1 0 0 1   1
1 0 1 0   1
1 0 1 1   1 
1 1 0 0   1
1 1 0 1   0
1 1 1 0   1
1 1 1 1   1

Улазне варијабле A,B,C,D се могу комбиновати на 16 различизих позиција. Најједноставнији начин да ово урадимо је да направимо 4x4 поља.

Бинарне бројке у мапи представљају излазне вредности функције за било коју дату комбинацију улазних вредности. Написали смо вредност 0 у скроз лијевом горњем углу мапе због тога што је f = 0 када је A = 0, B = 0, C = 0, D = 0. Слично тако уписаћемо вредност десног угла на дну да буде 1 због тога што кад имамо вредности A = 1, B = 0, C = 1, D = 0 даје вредност функције f = 1.

Након што је Карно мапа конструисана наш сљедећи задатак је да нађемо минималне услове које ћемо користити у заврсном изразу. Ови услови се налазе тако што ћемо заокружити у групу јединице на мапи. Групе могу само да садрже 2ⁿ поља, гдје је n цијели број ≥ 0 (1, 2, 4, 8...). Оне требају да буду велике колико је то могуће. Оптимална заокружења на овој мапи су маркирана зеленом, црвеном и плавом линијом.

За сваку од ових група треба да нађемо варијабле које имају исто стање и сваком заокруженом пољу. За прво заокружење (црвене боје) нашли смо да:

Варијабла А задржава исто стање (1) кроз цијело окружено поље, и зато треба да буде унесена у израз за 'црвено заокружење'

Варијабла B не задржава исто стање (мијења од 1 на 0) у црвеном заокружењу, и не треба је узети у израз за 'црвено заокружење'.

Слично овоме D се мијења, док C остаје стабилан (задржава исто стање) Први израз постаје AC.

За зелено окружење видимо да А и B задржавају исто стање, а C и D мијењају стања. Варијабла B има вредност 0, и треба је негирати прије него је унесемо у израз.

Други израз постаје AB'.

На исти начин као у претходна два окружења дошли смо до израза BC'D' тако да је наш коначни израз за функцију овакав: AC + AB' + BC'D'.