Karnaugh-diagram Solver (K-Map Calculator)

Booleaanse functies vereenvoudigen met een Karnaughdiagram

Een Karnaughdiagram, vaak K-Map genoemd, zet een Booleaanse functie in een rooster waarin logisch verwante combinaties naast elkaar liggen. Daardoor kun je sneller zien welke variabelen uit een uitdrukking kunnen verdwijnen.

Deze K-Map ondersteunt functies met 2, 3, 4 en 5 variabelen. Je hoeft niet altijd met het diagram zelf te beginnen. Dezelfde functie kan worden ingevoerd via de waarheidstabel, een Booleaanse expressie, mintermen of maxtermen.

De invoermethoden zijn met elkaar verbonden. Wanneer je een waarde verandert, werken de andere weergaven dezelfde functie automatisch bij.

Wat betekenen 0, 1 en X?

Een cel kan drie toestanden hebben:

• 1 betekent dat de functie voor die combinatie waar is.
• 0 betekent dat de functie onwaar is.
• X geeft een don't-carewaarde aan.

Een don't-care mag worden gebruikt wanneer die een grotere en eenvoudigere groep mogelijk maakt. Als de X geen voordeel oplevert, hoeft hij niet in een groep te worden opgenomen.

Van waarheidstabel naar K-Map

Een waarheidstabel toont alle mogelijke combinaties van de invoervariabelen en de bijbehorende uitvoer.

Een Karnaughdiagram bevat precies dezelfde informatie, maar zet de combinaties in Gray-codevolgorde. Hierdoor verschilt een cel van een direct aangrenzende cel in slechts één variabele.

Neem bijvoorbeeld:

A'B'

A'B

Alleen B verandert. A' blijft gelijk.

De twee termen kunnen daarom worden samengevoegd tot:

A'

Dat is het basisidee achter K-Map-groepen: variabelen die binnen een groep veranderen, hoeven niet in de vereenvoudigde term te blijven staan.

Mintermen, maxtermen en Booleaanse expressies

Als een opgave al mintermen of maxtermen geeft, hoef je het hele diagram niet handmatig in te vullen.

Bijvoorbeeld:

Σm(1,3,5,7)

beschrijft de mintermen waarvoor de functie 1 is.

Een invoer als:

ΠM(0,2,4,6)

geeft de maxtermen aan waarvoor de uitvoer 0 is.

Je kunt ook rechtstreeks met een Booleaanse expressie beginnen. De solver evalueert die expressie en bouwt daaruit de bijbehorende waarheidstabel, K-Map, mintermen en maxtermen.

Zo kun je verschillende notaties van dezelfde functie naast elkaar controleren zonder iedere vorm apart uit te werken.

Hoe groepen in een Karnaughdiagram werken

Een geldige groep bevat een macht van twee cellen:

1, 2, 4, 8, 16

Een grotere geldige groep levert meestal een term met minder literalen op.

De randen van een Karnaughdiagram sluiten logisch op elkaar aan. De meest linkse en meest rechtse kolom zijn dus buren. Hetzelfde geldt voor de bovenste en onderste rij.

Daardoor kunnen ook de vier hoekcellen samen een groep vormen.

Groepen mogen bovendien overlappen. Dat is soms nodig wanneer dezelfde cel helpt om meerdere eenvoudige termen te vormen.

De gemarkeerde groepen in de solver laten zien hoe de uiteindelijke expressie uit de K-Map ontstaat.

SOP en POS vergelijken

Bij SOP (Sum of Products) worden vooral de cellen met uitvoer 1 gebruikt.

Een vereenvoudigde SOP kan bijvoorbeeld zijn:

A'B + BC

Bij POS (Product of Sums) wordt juist gekeken naar de cellen met uitvoer 0.

Een resultaat kan er zo uitzien:

(A + B')(B + C)

SOP is niet automatisch beter dan POS. Bij de ene functie is de SOP-vorm kleiner, terwijl een andere functie met POS minder termen of literalen nodig heeft.

Als een opdracht geen vaste vorm voorschrijft, kan het daarom nuttig zijn beide resultaten te bekijken.

Quine-McCluskey en Petrick's Method

Op een kleine K-Map zijn goede groepen vaak snel met het oog te vinden. Bij 4 of 5 variabelen kunnen er echter meerdere geldige combinaties zijn.

De solver gebruikt Quine-McCluskey om mogelijke implicanten systematisch te combineren.

Wanneer een implicant niet verder kan worden uitgebreid, is het een prime implicant. Sommige daarvan zijn essentieel omdat ze een vereiste combinatie afdekken die niet door een andere prime implicant wordt gedekt.

Als na deze stap meerdere mogelijke dekkingen overblijven, kan Petrick's Method de resterende combinaties analyseren.

Dat is vooral nuttig bij functies waarbij verschillende K-Map-groepen op het eerste gezicht even goed lijken.

K-Maps met 2 tot 5 variabelen

Een K-Map met 2 variabelen bevat 4 cellen en maakt het basisidee van groeperen duidelijk.

Met 3 variabelen zijn er 8 cellen. Hier wordt ook zichtbaar waarom groepen over de rand van het diagram mogen lopen.

Een 4-variabelen-Karnaughdiagram bevat 16 cellen en komt veel voor bij digitale logica.

Bij 5 variabelen zijn er 32 mogelijke invoercombinaties. Handmatig controleren wordt dan lastiger, vooral wanneer er don't-carewaarden of meerdere prime implicants zijn.

De solver houdt voor elke ondersteunde grootte de K-Map, waarheidstabel, expressie, mintermen en maxtermen gekoppeld.

Logische schakeling en PDF-export

Na de vereenvoudiging kun je de uitdrukking ook bekijken als een logische schakeling.

Hierdoor is te zien hoe een SOP- of POS-uitdrukking kan worden opgebouwd met AND-, OR- en NOT-poorten.

De resultaten tonen daarnaast informatie over termen, literalen en het aantal logische poorten.

Wil je de uitwerking bewaren, dan kan de oplossing als PDF worden geëxporteerd met de K-Map, groepen, tussenstappen en schakeling.