Karnaugh-kaarten, waarheidstabellen en Booleaanse uitdrukkingen

Wie heeft de Karnaugh-kaart ontwikkeld?

Maurice Karnaugh, een telecommunicatie-ingenieur, ontwikkelde de Karnaugh-kaart in Bell Labs in 1953 terwijl hij op digitale logica gebaseerde telefoonschakelcircuits ontwierp.

Het gebruik van Karnaugh-kaart

Nu we de Karnaugh-kaart hebben ontwikkeld met behulp van Venn-diagrammen, gaan we hem gebruiken. Karnaugh-kaarten verminderen logica werkt sneller en gemakkelijker in vergelijking met Booleaanse algebra. Met verminderen bedoelen we vereenvoudigen, het verminderen van het aantal poorten en ingangen.

We willen logica vereenvoudigen tot een laagste prijs vorm om kosten te besparen door componenten te elimineren. We definiëren de laagste kosten als het laagste aantal poorten met het laagste aantal ingangen per poort.

Als ze de keuze hebben, doen de meeste studenten logische vereenvoudiging met Karnaugh-kaarten in plaats van Booleaanse algebra zodra ze deze tool leren.

We laten hierboven vijf afzonderlijke items zien, die gewoon verschillende manieren zijn om hetzelfde voor te stellen:een willekeurige digitale logische functie met 2 ingangen. De eerste is relaisladderlogica, dan logische poorten, een waarheidstabel, een Karnaugh-kaart en een Booleaanse vergelijking.

Het punt is dat elk van deze gelijkwaardig is. Twee ingangen A en B kan waarden aannemen van 0 of 1 , hoog of laag, open of gesloten, waar of niet waar, naargelang het geval. Er zijn 2 ² =4 combinaties van inputs die een output produceren. Dit is van toepassing op alle vijf voorbeelden.

Deze vier uitgangen kunnen worden waargenomen op een lamp in de relaisladderlogica, op een logische sonde op het poortdiagram. Deze resultaten kunnen worden vastgelegd in de waarheidstabel of in de Karnaugh-kaart. Bekijk de Karnaugh-kaart als een herschikte waarheidstabel.

De uitvoer van de Booleaanse vergelijking kan worden berekend met de wetten van de Booleaanse algebra en worden overgebracht naar de waarheidstabel of Karnaugh-kaart.

Welke van de vijf equivalente logische beschrijvingen moeten we gebruiken? Degene die het nuttigst is voor de te volbrengen taak.

De uitvoer van een waarheidstabel komt één-op-één overeen met Karnaugh-kaartinvoeren. Beginnend bij de top van de waarheidstabel, produceren de A=0, B=0 inputs een output α.

Merk op dat dezelfde uitvoer α wordt gevonden in de Karnaugh-kaart op het celadres A=0, B=0, linkerbovenhoek van K-map waar de A=0 rij en B=0 kolom elkaar kruisen. De andere waarheidstabel-uitgangen β, χ, δ van de ingangen AB=01, 10, 11 zijn te vinden op de corresponderende K-map-locaties.

Hieronder tonen we de aangrenzende 2-celregio's in de 2-variabele K-map met behulp van eerdere rechthoekige Venn-diagrammen zoals Booleaanse regio's.

Cellen α en χ zijn naast elkaar in de K-map als ellipsen in de meest linkse K-map hieronder. Verwijzend naar de vorige waarheidstabel is dit niet het geval. Er is nog een waarheidstabel (β) tussen hen in. Dat brengt ons bij het hele punt van het organiseren van de K-map in een vierkante array, cellen met alle Booleaanse variabelen die gemeenschappelijk zijn, moeten dicht bij elkaar zijn om een ​​patroon te presenteren dat ons opvalt.

Voor cellen α en χ hebben ze de Booleaanse variabele B’ met elkaar gemeen. We weten dit omdat B=0 (zelfde als B' ) voor de kolom boven de cellen α en χ. Vergelijk dit met het vierkante Venn-diagram boven de K-map.

Een soortgelijke redenering laat zien dat β en δ Booleaanse B . hebben (B=1) gemeen. Dan hebben α en β Booleaanse A' (A=0) gemeen. Ten slotte hebben χ en δ Booleaanse A (A=1) gemeen. Vergelijk de laatste twee kaarten met het middelste vierkante Venn-diagram.

Samenvattend zoeken we naar gemeenschappelijkheid van Booleaanse variabelen tussen cellen. De Karnaugh-kaart is zo georganiseerd dat we die gemeenschappelijkheid kunnen zien. Laten we wat voorbeelden proberen.

Voorbeelden

Voorbeeld:

Breng de inhoud van de waarheidstabel over naar de Karnaugh-kaart hierboven.

Oplossing:

De waarheidstabel bevat twee 1 s. de K-map moet ze allebei hebben. zoek de eerste 1 in de 2e rij van de waarheidstabel hierboven.

• noteer het AB-adres van de waarheidstabel
• zoek de cel in de K-map met hetzelfde adres
• plaats een 1 in die cel

Herhaal het proces voor de 1 in de laatste regel van de waarheidstabel.

Voorbeeld:

Schrijf voor de Karnaugh-kaart in het bovenstaande probleem de Booleaanse uitdrukking. Oplossing staat hieronder.

Oplossing:

Zoek naar aangrenzende cellen, dat wil zeggen boven of naast een cel. Diagonale cellen zijn niet aangrenzend. Aangrenzende cellen hebben een of meer Booleaanse variabelen gemeen.

• Groep (omcirkel) de twee 1 s in de kolom
• Zoek de variabele(n) boven en/of zijkant die hetzelfde zijn voor de groep, Schrijf dit op als het Booleaanse resultaat. Het is B in ons geval.
• Negeer variabele(n) die niet hetzelfde zijn voor een celgroep. In ons geval varieert A, is zowel 1 als 0, negeer Booleaanse A.
• Negeer alle variabelen die niet zijn gekoppeld aan cellen die enen bevatten. B' heeft niemand eronder. Negeer B'
• Resultaat Uit =B

Dit is misschien gemakkelijker te zien door te vergelijken met de Venn-diagrammen aan de rechterkant, met name de B kolom.

Voorbeeld:

Schrijf de Booleaanse uitdrukking voor de Karnaugh-kaart hieronder.

Oplossing: (hierboven)

• Groep (omcirkel) de twee 1's in de rij
• Zoek de variabele(n) die hetzelfde zijn voor de groep, Out =A'

Voorbeeld:

Breng voor de onderstaande Waarheidstabel de uitvoer over naar de Karnaugh en schrijf vervolgens de Booleaanse uitdrukking voor het resultaat.

Oplossing:

Zet de 1 . over s van de locaties in de waarheidstabel naar de corresponderende locaties in de K-map.

• Groep (omcirkel) de twee enen in de kolom onder B=1
• Groep (omcirkel) de twee enen in de rij rechts van A=1
• Schrijf productterm voor eerste groep =B
• Schrijf productterm voor tweede groep =A
• Schrijf som-van-producten van bovenstaande twee termen Output =A+B

De oplossing van de K-map in het midden is de eenvoudigste of goedkoopste oplossing. Een minder wenselijke oplossing is uiterst rechts. Na het groeperen van de twee 1 s, maken we de fout om een ​​groep van 1-cel te vormen. De reden dat dit niet wenselijk is, is dat:

• De enkele cel heeft een productterm van AB'
• De corresponderende oplossing is Output =AB’ + B
• Dit is niet de eenvoudigste oplossing

De manier om deze single op te pikken 1 is om een ​​groep van twee te vormen met de 1 rechts ervan, zoals weergegeven in de onderste regel van de middelste K-map, ook al is deze 1 is al opgenomen in de kolomgroep (B ). We mogen cellen hergebruiken om grotere groepen te vormen. In feite is het wenselijk omdat het tot een eenvoudiger resultaat leidt.

We moeten erop wijzen dat een van de bovenstaande oplossingen, Output of Wrong Output, logisch correct is. Beide circuits leveren dezelfde output. Het gaat erom dat het eerste circuit de goedkoopste oplossing is.

Voorbeeld:

Vul de Karnaugh-kaart in voor de Booleaanse uitdrukking hieronder en schrijf vervolgens de Booleaanse uitdrukking voor het resultaat.

Oplossing: (hierboven)

De Booleaanse uitdrukking heeft drie producttermen. Er komt een 1 ingevoerd voor elke productterm. Hoewel, in het algemeen, het aantal 1 s per productterm varieert met het aantal variabelen in de productterm in vergelijking met de grootte van de K-map.

De productterm is het adres van de cel waar de 1 wordt ingevoerd. De eerste productterm, A'B , komt overeen met de 01 cel op de kaart. Een 1 wordt in deze cel ingevoerd. De andere twee P-termen worden ingevoerd voor in totaal drie 1s

Ga vervolgens verder met het groeperen en extraheren van het vereenvoudigde resultaat zoals in het vorige probleem met de waarheidstabel.

Voorbeeld:

Vereenvoudig het onderstaande logicaschema.

Oplossing: (Figuur hieronder)

• Schrijf de Booleaanse uitdrukking voor het originele logische diagram zoals hieronder weergegeven
• Verplaats de productvoorwaarden naar de Karnaugh-kaart
• Vorm groepen cellen zoals in eerdere voorbeelden
• Schrijf Booleaanse uitdrukkingen voor groepen zoals in eerdere voorbeelden
• Teken vereenvoudigd logisch diagram

Voorbeeld: Vereenvoudig het onderstaande logicaschema.

Oplossing:

• Schrijf de Booleaanse uitdrukking voor het originele logische diagram hierboven weergegeven
• Verplaats de productvoorwaarden naar de Karnaugh-kaart.
• Het is niet mogelijk om groepen te vormen.
• Er is geen vereenvoudiging mogelijk; laat het zoals het is.

Voor het bovenstaande diagram is geen logische vereenvoudiging mogelijk. Dit gebeurt soms. Noch de methoden van Karnaugh-kaarten noch Booleaanse algebra kunnen deze logica verder vereenvoudigen.

We tonen hierboven een Exclusief-OF schematisch symbool; dit is echter geen logische vereenvoudiging. Het maakt een schematisch diagram er alleen maar mooier uit.

Aangezien het niet mogelijk is om de Exclusive-OR-logica te vereenvoudigen en deze veel wordt gebruikt, wordt deze door fabrikanten geleverd als een basis-geïntegreerd circuit (7486).

GERELATEERDE WERKBLAD:

• Werkblad Karnaugh-toewijzing
• Booleaanse algebra-werkblad
• Basis Logic Gates-werkblad