Diagramele Karnaugh

 Folosirea unei diagrame pentru simplificarea funcţiilor booleene a fost sugerată pentru prima dată de E. Veitch. Ulterior, M. Karnaugh propune de asemenea o formă de diagramă în acelaşi scop, rezultând diagrama Karnaugh. Această diagramă se utilizează în mod curent pentru reprezentarea funcţiilor booleene cu un număr relativ mic de variabile.

 O diagramă Karnaugh constituie o variantă modificată a unui tabel de adevăr. În general, o diagramă Karnaugh pentru o funcţie booleană de n variabile se reprezintă sub forma unui pătrat sau dreptunghi împărţit în 2ⁿ pătrate (compartimente), fiecare pătrat fiind rezervat unui termen canonic al funcţiei.    

    Pentru o funcţie de două variabile - f(x,y):

        Pentru o funcţie de trei variabile f(x,y,z):

      Se utilizează mintermenii mi - pentru FCD şi maxtermenii Mi - pentru FCC.

      Pentru o funcţie de patru variabile - f(x,y,z,t):

        Algoritmul de minimizare, ultilizând diagramele Karnaugh, este următorul:

       1. Scrierea valorilor funcţiei în diagramă, scrierea după 1 (sau după 0) dacă se foloseşte FCD (sau FCC) a funcţiei.

        2. Gruparea a 2^k (k = 0,1,2,..) suprafeţe elementare adiacente, care au valoarea logică 1 (sau 0 dacă s-a folosit FCC), astfel încât să formeze o suprafaţă dreptunghiulară. În suprafeţele extinse se încearcă includerea tuturor suprafeţelor elementare care au valoarea logică 1 (sau 0 în FCC).

      3. Corespunzător unei suprafeţe extinse se obţine un produs elementar al variabilelor ce nu-şi schimbă valoarea pe această suprafaţă, dacă s-a folosit FCD, sau o sumă elementară a variabilelor ce nu-şi schimbă valoarea în FCC. Dacă nu este posibil ca o suprafaţă elementară să se alipească altei suprafeţe elementare, pentru aceasta se va scrie expresia ce corespunde mintermenului/ maxtermenului.

     În unele cazuri, în practică, anumite combinaţii ale valorilor variabilelor de intrare nu apar niciodată în timp, funcţia numindu-se incomplet definită. Se poate considera că aceste combinaţii sunt nesemnificative pentru determinarea funcţiei logice de la ieşire. Se pot folosi aceste situaţii atribuind suprafeţelor elementare respective valoarea logică 1 sau 0 (R), în funcţie de modul în care se poate obţine o formă mai simplă pentru funcţia logică.

         
        Exemplu:

        Să se simplifice funcţia logică f(x,y,z), dată prin tabelul de adevăr prezentat mai jos.

   

      FCD a funcţiei este: f(x,y,z) = m₂ + m₃ + m₆ + m₇ =  ̅x y ̅z + ̅x y z + x y ̅z + x y z 

       Diagrama Karnaugh este:

     Forma simplificată a FCD este : f(x,y,z) = y

     Pentru mai multe detalii și exemple puteți accesa site-ul următor: Karnaugh