2.2 Kretsanalyse og boolsk algebra

To boolske uttrykk er ekvivalente når de gir samme utgang i hver eneste rad i sannhetstabellen — ikke bare i noen av dem.

Ekvivalens er en påstand om hele tabellen, og den avgjøres på to lovlige måter: enten ved å føre det ene uttrykket over i det andre med identitetene, eller ved å sette opp begge kolonnene og sammenligne rad for rad.

Det finnes uendelig mange uttrykk som er ekvivalente med et gitt uttrykk. A + C, C + A, A + A·B + C og (A + C)·(A + C) er alle det samme.

Den faste feilslutningen: å tro at det korteste uttrykket er det «riktige» og de andre gale. På eksamen er alle ekvivalente former riktige, og de skal alle krysses av.

De tre temaene i kretslæren som er ikke pensum i emnet, og som du derfor ikke skal drille: systematisk forenkling med rutediagram (Karnaugh-diagram, K-map), og byggeblokkene multiplekser og dekoder.

De finnes i eldre oppgavesett, og emnet har eksplisitt plassert dem utenfor pensum. Møter du dem når du øver, hopp over oppgaven.

Det du skal kunne i sjangeren, er tre ting: identifisere portene, propagere en portliste fram til F, og forenkle med identitetslista.

Den faste feilslutningen: å tro at «det står i et gammelt sett, altså kan det komme». Emnet har endret pensum, og de nyeste settene følger det nye.

Å regne seg gjennom en krets fra inngangene og framover, port for port, og skrive uttrykket for hvert mellomsignal underveis.

En port kan regnes ut så snart alle inngangene dens er kjent. Rekkefølgen i en portliste er alltid satt opp slik at dette går opp.

Den faste feilen er å starte ved utgangen og resonnere bakover. Det går an i enkle kretser, men i en krets med fire porter og to forgreninger mister nesten alle oversikten.

Det boolske uttrykket som beskriver kretsens sluttutgang som funksjon av inngangene.

F er svaret på «hva gjør kretsen?» — og det er dette uttrykket alle alternativene i en eksamensoppgave skal måles mot.

Merk at F ikke er entydig som skrivemåte: samme funksjon kan skrives på uendelig mange ekvivalente måter. Det er funksjonen, altså kolonnen i sannhetstabellen, som er entydig.

Regneregelverket for uttrykk der alle variabler er 0 eller 1, og der operatorene er NOT, AND og OR.

De fleste reglene ligner vanlig algebra: kommutativitet, assosiativitet og «gang inn i parentesen».

Tre regler har ingen motstykke i tallregning, og det er de tre eksamen liker: idempotens (A + A = A), komplement (A + A′ = 1) og distributivitet OR over AND (A + B·C = (A + B)·(A + C)).

Den kjente «gang inn i parentesen». Den brukes til å gjøre om et uttrykk fra produkt-av-summer til sum-av-produkter.

Dette er den formen eksamen oftest lister som et ekvivalent alternativ ved siden av kretsens eget uttrykk — begge er riktige og begge skal krysses av.

Denne finnes ikke i vanlig tallregning: 2 + 3·4 er ikke (2+3)·(2+4).

I boolsk algebra stemmer den, og du kan kontrollere den i alle åtte radene. Begrunnelsen i ord: er A lik 1, er begge sider 1. Er A lik 0, blir venstre side B·C og høyre side B·C.

Fordi loven ser «umulig» ut, er den en av de mest oversette riktige alternativene i sjanger D.

Det lengre leddet forsvinner helt, og A blir stående alene.

Begrunnelsen for den første: er A lik 1, er summen 1 uansett B. Er A lik 0, er også A·B lik 0, og summen er 0. Utgangen følger A nøyaktig.

Den faste feilen er å ende på A·B i stedet for A. Begge formene ender på A alene — ingen B blir igjen.

Inverteringen forsvinner, og B blir stående uten den.

Begrunnelsen: er A lik 1, er begge sider 1. Er A lik 0, er A′ lik 1, og begge sider blir B.

Dette er den identiteten som gjør flest krets-eksempler korte, og den brukes ofte baklengs på eksamen: et alternativ som ser unødvendig langt ut (A + A′·B·C) er ekvivalent med det korte (A + B·C) og skal krysses av.

Grupperingen betyr ingenting så lenge operatoren er den samme hele veien.

Praktisk følge: en OR-port med tre innganger gjør det samme som to OR-porter i serie, og en AND med tre innganger det samme som to AND-er i serie.

Merk at assosiativiteten ikke gjelder på tvers av operatorer: (A + B)·C er ikke A + (B·C).

Formen der uttrykket er en OR av AND-ledd: A·B + A′·C + B·C′.

Dette er standardformen for en funksjon lest rett ut av sannhetstabellen: ett AND-ledd per rad som gir 1, OR-et sammen til slutt.

Eksempel: gir kolonnen 1 i radene 001 og 110 (for A, B, C), er uttrykket A′·B′·C + A·B·C′.

SOP er den vanligste formen i eksamensalternativer, fordi den er lett å sammenligne rad for rad.

Formen der uttrykket er en AND av OR-ledd: (A + B)·(A′ + C).

POS og SOP beskriver de samme funksjonene — de er to måter å skrive det samme på, og du kommer fra den ene til den andre med de distributive lovene.

På eksamen står de ofte som to alternativer ved siden av hverandre, og da er begge riktige.

Metoden for å gå fra en ferdig utfylt tabell til et uttrykk:

1. Se på hver rad der utgangen er 1.
2. Skriv ett AND-ledd per slik rad: variabelen selv der den er 1, invertert der den er 0.
3. OR sammen alle leddene.

Gir kolonnen 1 bare i raden A = 1, B = 0, er uttrykket A·B′.

Metoden gir alltid et riktig uttrykk, men ikke nødvendigvis det korteste — det finner du ved å forenkle etterpå med identitetslista.

Den sikre måten å avgjøre om to uttrykk er like: sett opp én kolonne for hvert og sammenlign rad for rad.

Er det minst én rad der de er ulike, er uttrykkene ikke ekvivalente — og den ene raden er hele begrunnelsen du trenger i et løsningsforslag.

Med tre innganger tar kontrollen åtte rader, altså under to minutter. Under negativ poenggiving er det godt betalt tid: du bytter to minutter mot sikkerhet i alle fire alternativene.

Den ene raden i sannhetstabellen der to uttrykk gir ulikt svar — beviset på at de ikke er ekvivalente.

For å avvise et alternativ trenger du bare én motrad. For å godta et alternativ trenger du derimot alle radene, eller en gyldig identitet.

Denne asymmetrien er verdt å utnytte under tidspress: let etter en motrad først, og gå bare gjennom hele tabellen hvis du ikke finner noen.

De Morgan lest som en regel om portsymboler: en AND med boble på utgangen (NAND) er det samme som en OR med bobler på inngangene.

(A·B)′  =  A′ + B′
(A+B)′  =  A′ · B′

I ord: du kan flytte boblen fra utgangen til inngangene hvis du samtidig bytter porttype.

Dette er grunnen til at samme krets kan tegnes på to måter som ser helt ulike ut — og til at begge skrivemåtene kan stå som riktige alternativer i samme oppgave.

To inverteringer etter hverandre opphever hverandre: (A′)′ = A.

I en portliste ser dette ut som en NAND fulgt av en NOT, eller en NOR fulgt av en NOT. Resultatet er ganske enkelt AND og OR:

Port 1: NAND med inngangene A og B   -> P
Port 2: NOT  med inngangen P         -> F = A·B

Kjenner du igjen mønsteret, sparer du et helt utregningssteg — og det er ofte nettopp slik en eksamenskrets er bygd, for å se mer komplisert ut enn den er.

En krets der F er den samme uansett inngangene. Det skjer når uttrykket forenkler seg til 1 eller til 0.

Typiske mønstre: A + A′ gir alltid 1, og A·A′ gir alltid 0. Det samme gjør A + 1 og A·0.

En krets med konstant utgang er en krets som ikke gjør noe nyttig — og på eksamen er «utgangen er alltid 1» av og til et av alternativene. Sjekk det med komplementlovene før du avviser det.

Hensikten med å forenkle er å bruke færre porter for samme funksjon.

Færre porter gir færre transistorer, mindre plass på brikken, lavere strømforbruk og kortere forsinkelse gjennom kretsen.

På eksamen har forenklingen en annen nytte: det forenklede uttrykket står nesten alltid blant alternativene sammen med det uforenklede, og begge er riktige. Ser du ikke forenklingen, ser du ikke at de er samme funksjon.

Antall porter et signal må passere fra inngang til utgang, langs den lengste veien.

I kretsen P = A·B, Q = C′, F = P + Q er dybden 2: hvert signal passerer høyst to porter.

Dybden er interessant fordi hver port bruker litt tid. En krets med dybde 2 rekker å gi svar raskere enn en med dybde 5, selv om de regner ut nøyaktig det samme.

Merk at dybde ikke er det samme som antall porter: en krets kan ha mange porter i bredden og likevel være grunn.

At det samme signalet står oppført som inngang på flere linjer i portlisten.

Port 1: NOT med inngangen A         -> P
Port 2: AND med inngangene P og B   -> Q
Port 3: OR  med inngangene P og C   -> R

Her mater P både port 2 og port 3. Det er helt vanlig og betyr bare at ledningen er delt.

Den faste feilen er å tro at P «brukes opp» av den første porten som tar den inn. Et signal kan leses av så mange porter du vil.

Linjene i en portliste står alltid i en rekkefølge der hvert mellomsignal er beregnet før det brukes.

Det betyr at du kan lese listen ovenfra og ned og fylle ut sannhetstabellen kolonne for kolonne, uten å hoppe.

Det betyr også at listen aldri er sirkulær: et signal kan ikke avhenge av seg selv. Kretser der utgangen mates tilbake til inngangen, hører til lagringskretsene, og de detaljene er nedtonet i emnet.

Fordi én funksjon har mange riktige skrivemåter. Kretsens uttrykk, den distribuerte formen, den De Morgan-omskrevne formen og den unødvendig lange formen er alle ekvivalente — og alle riktige.

Svarform F1 er «velg ett eller flere alternativer», og oppgaven ber deg vurdere hvert alternativ som en selvstendig påstand.

Den faste feilen er å stoppe ved det første riktige. Da mister du poeng uten å ha krysset av noe galt — og under negativ poenggiving er det den billigste måten å tape poeng på.