Karnaugh-diagram

Een Karnaugh-diagram of ook wel een Veitch-diagram is een hulpmiddel om expressies in booleaanse algebra te vereenvoudigen. Het diagram werd uitgevonden in 1950 door Maurice Karnaugh, een telecommunicatie-ingenieur bij Bell Labs.

Dikwijls zijn er uitgebreide berekeningen nodig om een booleaanse expressie of functie zo eenvoudig mogelijk te schrijven, maar met een Karnaugh-diagram kan dit vaak sneller. Doordat het menselijk brein gemakkelijk patronen kan herkennen, helpt het diagram om snel op te zoeken welke termen gecombineerd kunnen worden om een expressie te vereenvoudigen. Daarenboven kan men met Karnaugh-diagrammen snel herkennen waar eventueel een zogenaamde "race condition" zou kunnen voorkomen, en men kan ze dan ook verwijderen, wat met booleaanse expressies alleen niet kan.

Een Karnaugh-diagram is geschikt voor vereenvoudigen tot maximaal zes variabelen; meer variabelen maken het zelfs voor het brein moeilijk om nog patronen te herkennen. Voor expressies met meer dan 4 variabelen is het beter het Quine-McCluskey-algoritme te gebruiken. Heden ten dage wordt voor dit doel echter in de regel de veel efficiëntere Espresso heuristische logische minimalisator toegepast.

Karnaugh-diagrammen zijn ook nuttig bij het aanleren van booleaanse functies en minimalisatie.

VoorbeeldBewerken

De functie   heeft de volgende waarheidstabel (met 0 voor onwaar en 1 voor waar):

          Waarde van             Waarde van  
0 0 0 0 0 0 8 1 0 0 0 1
1 0 0 0 1 0 9 1 0 0 1 1
2 0 0 1 0 0 10 1 0 1 0 1
3 0 0 1 1 0 11 1 0 1 1 1
4 0 1 0 0 0 12 1 1 0 0 1
5 0 1 0 1 0 13 1 1 0 1 1
6 0 1 1 0 1 14 1 1 1 0 1
7 0 1 1 1 0 15 1 1 1 1 0

De waarheidstabel wordt anders weergegeven door de invoervariabelen   en   in paren   en   tegen elkaar uit te zetten. De waarden van deze paren zijn geordend in Gray-code, om ervoor te zorgen dat in twee opeenvolgende waarden er slechts één variabele verandert.

Het zo ontstane Karnaugh-diagram is een 4 bij 4 diagram, met in het veld   de functiewaarde  

Als eenmaal de getallen ingevuld zijn, is de volgende stap het vinden van minimale termen voor de uiteindelijke expressie. Deze termen kunnen gevonden worden door de enen in het diagram te omkaderen. Dit moet gebeuren op een dusdanige manier dat de "kaders" rechthoekig zijn en exact   velden omvatten, waarbij   een natuurlijk getal is groter dan 0. De omkaderingen moeten ook zo groot mogelijk zijn. De optimale kaders worden hierboven getoond in groen, rood en blauw.

Voor elk van deze kaders wordt nagegaan welke variabele in alle velden van het kader dezelfde waarde heeft. Voor het eerste (rode) kader blijkt:

  • De variabele   heeft dezelfde waarde (1) in het hele kader, dus behoort   tot de term die hoort bij het rode kader.
  • De variabele   heeft niet dezelfde waarde (ze verandert van 1 naar 0), dus wordt ze uitgesloten.
  • Op dezelfde manier verandert   wel, maar   niet.   is hier altijd gelijk aan 0.

Omdat   wordt de negatie aan de term toegevoegd. De eerste term wordt daarom  

In het groene kader is in elk veld   en   maar veranderen   en   De tweede term wordt daarom  

In het blauwe kader ten slotte is   en verandert   van waarde, zodat de derde term   is.

De volledige expressie wordt dus gegeven door

 

Men verifieert eenvoudig dat bijvoorbeeld

 

De inverse functie kan gevonden worden door de nullen te omcirkelen in plaats van de enen.

Zie ookBewerken

Externe linksBewerken

  Zie de categorie Karnaugh maps van Wikimedia Commons voor mediabestanden over dit onderwerp.