2.3 Boolsk algebra

Matematikken med bare to tall

Tenk deg en matematikk der det bare finnes to tall: 0 og 1. Ingen brøker, ingen desimaler, ingenting imellom – bare av eller på, usant eller sant, lav eller høy. Det høres fattig ut, men nettopp dette systemet ligger til grunn for absolutt alt digitalt utstyr du eier. Vi kaller det boolsk algebra, etter den engelske matematikeren George Boole, som på 1800-tallet gjorde logisk tenkning om til regnestykker.

Hvorfor er dette så viktig i elektronikk? Fordi en transistor er en bryter – den er enten på eller av – og en hel datamaskin er ikke noe annet enn milliarder slike brytere som samarbeider. For å designe digitale kretser bruker vi boolsk algebra til tre ting: å beskrive hva kretsen skal gjøre, å forenkle den så vi trenger færrest mulig komponenter, og å sjekke at den faktisk virker som tenkt.

I dette kapittelet skal vi bli kjent med de tre grunnoperatorene AND, OR og NOT, lære å sette opp sannhetstabeller, oppdage reglene som lar oss forenkle uttrykk, og til slutt mestre De Morgans lover – et par knep som er uvurderlige når du jobber med logiske porter.

De tre grunnoperatorene

All boolsk logikk bygger på tre operatorer. La oss møte dem én etter én.

AND (OG), som skrives med en prikk, $A \cdot B$, gir bare 1 når alle inngangene er 1. Tenk på det som en streng betingelse: både A og B må være oppfylt. Er det minste én null, blir resultatet null. OR (ELLER), som skrives med pluss, $A + B$, er mer sjenerøs: den gir 1 så lenge minst én inngang er 1. Bare når begge er null, blir resultatet null. Til slutt har vi NOT (IKKE), skrevet med en strek over, $\bar{A}$, som rett og slett snur verdien: 0 blir til 1, og 1 blir til 0.

Legg merke til at symbolene er valgt med omhu. Pluss og prikk oppfører seg nemlig litt som i vanlig matematikk, og det gjelder også prioriteringen: AND regnes før OR, akkurat som ganging går før addisjon. Et uttrykk som $1 \cdot 0 + 1$ regnes derfor slik: først AND, $1 \cdot 0 = 0$, deretter OR, $0 + 1 = 1$.

For å holde oversikten over hva en logisk funksjon gjør, bruker vi en sannhetstabell som lister opp utgangen for hver eneste kombinasjon av innganger. Ta uttrykket $Y = A \cdot B + \bar{A} \cdot C$. Med tre variabler er det åtte kombinasjoner å gå gjennom. Resultatet blir at $Y$ er 1 i fire av dem: alltid når $A = 1$ og $B = 1$, og alltid når $A = 0$ og $C = 1$. Slik kan en tabell avsløre nøyaktig oppførselen til et uttrykk vi kanskje synes ser komplisert ut.

Reglene som krymper uttrykk

Hvorfor bry seg med å forenkle et boolsk uttrykk? Fordi hvert ledd i uttrykket svarer til en fysisk port på kretskortet. Klarer vi å gjøre uttrykket kortere, sparer vi komponenter, plass, strøm og penger. Heldigvis har boolsk algebra et knippe regler nettopp for dette.

Noen er åpenbare når du tenker etter. Identitetsreglene sier at $A + 0 = A$ og $A \cdot 1 = A$ – å legge til 0 med OR eller gange med 1 endrer ingenting. Nullreglene sier at $A + 1 = 1$ og $A \cdot 0 = 0$, fordi en OR med 1 alltid blir 1, og en AND med 0 alltid blir 0. De viktigste til forenkling er komplementreglene: $A + \bar{A} = 1$ og $A \cdot \bar{A} = 0$. En variabel sammen med sin egen motsetning dekker enten alt eller ingenting.

La oss se hvor kraftig dette er. Tenk på uttrykket $Y = A \cdot B + A \cdot \bar{B}$. Først ser vi at $A$ er en felles faktor, så vi setter den utenfor (distributiv lov): $Y = A \cdot (B + \bar{B})$. Inni parentesen står $B + \bar{B}$, som komplementregelen sier er 1. Da har vi $Y = A \cdot 1$, og med identitetsregelen blir det rett og slett $Y = A$. Et uttrykk med to ledd og to porter ble til ingenting annet enn variabelen $A$ – $B$ spilte aldri noen rolle!

Samme trikk virker med flere variabler. $Y = A \cdot B \cdot C + A \cdot B \cdot \bar{C}$ har $A \cdot B$ som felles faktor: $Y = A \cdot B \cdot (C + \bar{C}) = A \cdot B \cdot 1 = A \cdot B$. Ved siden av disse finnes også absorpsjonsreglene ($A + A \cdot B = A$) og de distributive reglene, men prinsippet er alltid det samme: finn felles faktor, bruk komplementregelen, og rydd opp.

De Morgans lover – å bryte streken

De siste, og kanskje mest elegante, verktøyene er De Morgans lover. De forteller hva som skjer når du inverterer et helt sammensatt uttrykk. Den første loven sier:

$$\overline{A \cdot B} = \bar{A} + \bar{B}$$

Med ord: «IKKE (A OG B)» er det samme som «(IKKE A) ELLER (IKKE B)». Den andre loven er speilbildet:

$$\overline{A + B} = \bar{A} \cdot \bar{B}$$

Det finnes en lett huskeregel for begge: når du «bryter streken» over et uttrykk, bytter AND og OR plass – $\cdot$ blir til $+$ og omvendt – og hver enkelt variabel får sin egen strek. Dette gjelder også med flere variabler: $\overline{A \cdot B \cdot C} = \bar{A} + \bar{B} + \bar{C}$.

Disse lovene er gull verdt i praksis. De lar oss konvertere mellom NAND- og NOR-porter og vanlige AND-, OR- og NOT-porter, noe som ofte gjør kretser billigere å bygge. La oss se et eksempel der de virkelig skinner: $Y = \overline{\bar{A} \cdot \bar{B}}$. Vi bruker De Morgan på det ytre uttrykket: $Y = \overline{\bar{A}} + \overline{\bar{B}}$. Nå har vi doble streker, og en dobbel inversjon opphever seg selv – $\overline{\bar{A}} = A$. Dermed blir hele uttrykket bare $Y = A + B$.

Til slutt et praktisk eksempel. Et alarmsystem skal slå seg på ($Y = 1$) hvis vinduet er åpent ($A$) OG det er natt ($B$), ELLER hvis døren er åpen ($C$): $Y = A \cdot B + C$. Vil vi vite når alarmen IKKE er aktiv, inverterer vi: $\bar{Y} = \overline{A \cdot B + C}$. De Morgan gir $\bar{Y} = \overline{A \cdot B} \cdot \bar{C} = (\bar{A} + \bar{B}) \cdot \bar{C}$. Alarmen er altså av når døren er lukket OG enten vinduet er lukket eller det er dag.

Oppsummering

Vi har bygd opp fundamentet under all digital elektronikk. Boolsk algebra kjenner bare to verdier, 0 og 1, og tre grunnoperatorer: AND ($\cdot$), som gir 1 bare når alle innganger er 1; OR ($+$), som gir 1 når minst én er 1; og NOT ($\bar{A}$), som inverterer. En sannhetstabell viser utgangen for hver kombinasjon av innganger.

Med forenklingsreglene – identitet, null, og særlig komplementregelen $A + \bar{A} = 1$ – kan vi krympe uttrykk og dermed antall porter i kretsen. De Morgans lover, $\overline{A \cdot B} = \bar{A} + \bar{B}$ og $\overline{A + B} = \bar{A} \cdot \bar{B}$, lar oss «bryte streken», bytte AND og OR, og konvertere mellom portkombinasjoner. Til sammen er dette verktøykassen som lar oss designe digitale kretser som er både korrekte og så enkle som mulig.