Karnaughdiagram
Wikipedia
Ett Karnaughdiagram är ett verktyg för analys och minimering av booleska uttryck. Det uppfanns av Maurice Karnaugh 1958.
Innehåll |
[redigera] Diagrammets utseende
Det enklaste sättet att göra ett Karnaughdiagram är att först skriva en sanningstabell. Karnaughdiagrammet för denna tabell innehåller en ruta (se exemplet under nästa rubrik) för varje rad i denna sanningstabell.
Mycket viktigt när man gör upp ett Karnaughdiagram är att man minns att intilliggande värden i diagrammet inte får avvika med mer än en bit ,till skillnad från standard binärsekvens. Exempelvis är vanlig binärordning med tre bitar 000, 001, 010, 011, 100, 101, 110 och 111. Med detta i en Karnaughtabell måste man sätta till exempel 000, 001, 011, 010, 110, 111, 101 och 100, så att bara en bit ändras varje gång. Detta gäller både för den vågräta raden och den lodräta raden.
Notera att den översta och den nedersta raden sinsemellan och kolumnerna längst till vänster resp. höger också enbart skiljer sig med en bit. Detta betyder att den gruppering vi ser längre ner i texten även gäller över "kanterna". Man kan tänka sig att man rullar ihop kartan till en cylinder, antingen horisontalt eller vertikalt.
[redigera] Exempel 1
Låt oss ta funktionen logisk konjunktion (AND) som exempel. Denna funktion har följande sanningstabell:
| A | B | A ∧ B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
I tabellen representerar en nolla värdet falskt och en etta motsv. värdet sant. Eftersom det finns fyra rader i denna tabell så kommer det att finnas fyra rutor i vårt Karnaughdiagram. Vi väljer denna gång att sätta båda variablerna A och B på samma rad.
| \AB | 00 | 01 | 11 | 10 |
| 1 |
I den övre raden har vi placerat variablerna A och B i ordningen AB, så de binärtal som synst till höger är skrivna i den ordningen. Snedstrecket före AB har ingen annan betydelse än att vara avskiljare till de variabler som kan finnas i den lodräta kolumnen längst till vänster. Notera att endast en bit ändrar för varje steg vi går åt höger.
I rutan nedanför talet där A = 1 och B = 1, har vi fyllt i en etta, precis som framgår ur sanningstabellen för vår funktion. Så här gör man för hela sanningstabellen och när man är färdig har man fyllt i Karnaughdiagrammet. För klarhets skull skriver man inte ut nollor utan endast ettor.
[redigera] Exempel 2
Låt oss nu ta ett lite mer omfattande exempel. Låt oss skapa en funktion som har tre variabler, ABC. Funktionen får vara (A ∧ B ) ∨ C. Sanningstabellen blir då följande:
| A | B | C | (A ∧ B ) ∨ C |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Då vi gör ett Karnaughdiagram av detta placerar vi till exempel variablerna A och B som i föregående exempel på övre raden, men vi placerar C i den lodräta kolumnen till vänster. Sedan placerar vi in resultatet och vi får följande diagram.
| C\AB | 00 | 01 | 11 | 10 |
| 0 | 1 | |||
| 1 | 1 | 1 | 1 | 1 |
[redigera] Exempel på minimering
Med hjälp av Karnaughdiagram kan man även ibland minimera (dvs. förenkla) invecklade booleska uttryck. Detta tas upp i detta exempel.
Minimeringen baserar sig på det faktum att när diagrammet ställts upp korrekt, så skiljer sig närliggande binärtal med endast en bit. Om man hittar två vågrätt eller lodrätt intilliggande rutor i diagrammet, så skiljer sig en variabel i dessa två rutor. Denna blir då irrelevant i sammanhanget och kan förkastas.
I detta exempel tar vi funktionen Y = (¬A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ ¬B ∧ C). Dess sanningstabell har detta utseende:
| A | B | C | Y |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
Vi gör ett Karnaughdiagram av tabellen och får då följande:
| C\AB | 00 | 01 | 11 | 10 |
| 0 | 1 | |||
| 1 | 1 | 1 | 1 |
Vi hittar i diagrammet två fall där två intilliggande rutor (vågrätt eller lodrätt) innehåller ettor. Vi börjar med att granska det vågräta fallet. Variabeln A har värdet 0 för båda rutorna, variabeln C har värdet 1 för båda rutorna, och variabel B har värdet 0 i ena och 1 i andra rutan. Därmed, för denna grupp, så har värdet B ingen inverkan på "resultatet". Därmed är variabeln B överflödig i denna grupp och kan förkastas.
I det lodräta fallet är variabel A konstant 1, B konstant 0 och C varierar. Därmed kan C förkastas ur den lodräta gruppen.
Då vi reducerar uttrycket för funktionen ovan tar vi alltså bort B ur de två fall som berörde den vågräta gruppen och C ur de som rörde den lodräta gruppen. Vi har då kvar den minimerade funktionen Z = (¬A ∧ C) ∨ (¬A ∧ C) ∨ (A ∧ ¬B) ∨ (A ∧ ¬B). Då vi ytterligare raderar dubbletterna får vi det enkla uttrycket Z = (¬A ∧ C) ∨ (A ∧ ¬B). Denna funktion har samma sanningstabell som den mer komplicerade funktionen som vi utgick ifrån.
[redigera] Exempel på Karnaughdiagram med fyra variabler
Ett Karnaughdiagram med fyra variabler har två i den vågräta raden och två i den lodräta kolumnen. Båda måste arrangeras enligt principen ovan, dvs. endast en bits skillnad.
| CD\AB | 00 | 01 | 11 | 10 |
| 00 | ||||
| 01 | ||||
| 11 | ||||
| 10 |
