Logik, gates og kredsløb

George Boole indså i slutningen af det 19. århundrede, at visse dele af logikken kan udstrykkes som algebra ved anvendelse af funltioner eller operatorer, som virker på de to værdier: sand (T) og falsk (F). De tre grundlæggende operatorer er ¬ (NOT), ∧ (AND) og ∨ (OR). De boolske operatorer defineres ved sandhedstabeller:

P:(T,F) ⇒ ¬P:(F,T)
P:(T,T,F,F),Q(T,F,T,F) ⇒ P∧Q:(T,F,F,F,F)
P:(T,T,F,F),Q(T,F,T,F) ⇒ P∨Q:(T,T,T,F)
P:(T,T,F,F),Q(T,F,T,F) ⇒ P⊕Q:(F,T,T,F), ⊕ er exclusive or.
P:(T,T,F,F),Q(T,F,T,F) ⇒ ¬P:(F,F,T,T),¬Q:(F,T,F,T) ⇒ ¬P∧¬Q:(F,F,F,T)
Sandhedstabellen for negationen af (¬P∧¬Q) er:
P:(T,T,F,F),Q(T,F,T,F) ⇒ ¬(¬P∧¬Q):(T,T,T,F)
P∨Q ≡ ¬(¬P∧¬Q), ≡ betyder logisk ækvivalent med.
På tilsvarende måde finder vi:
P⊕Q ≡ (P∧¬Q)∨(¬P∧Q)
Ved anvendelse af udtrykket for OR findes:
P⊕Q ≡ ¬(¬(P∧¬Q)∧(¬(¬P∧Q)))
Både ∨ og ⊕ kan erstattes med ¬ og ∧. Denne metode virker helt generelt for andre udtryk.

Boolske funktioner

De logiske operatorer kan opfattes som boolske funktioner. En funktion af 3 variable P, Q og R, f(P,Q,R) defineres ved en sandhedstabel med 2³ = 8 værdier:
P:(T,T,T,T,F,F,F,F),Q:(T,T,F,F,T,T,F,F),R:(T,F,T,F,T,F,T,F) ⇒ f(P,Q,R):(…)
For enhver funktion f(P,Q,R) findes et ækvivalent udtryk, som kun indeholder funktionerne ¬ og ∧. Man anvender nøjagtigt den samme metode, som jeg brugte til at finde et udtryk for P∨Q. Metoden virker helt generelt. f er logisk ækvivalent med et udtryk, som kun involverer funktionerne ¬ og ∧, hvis f er en funktion defineret ved en sandhedstabel. Man siger derfor, at {¬,∧} er et funktionelt komplet sæt af boolske operatorer. Det forekommer overraskende, at vi kan frembringe enhver funktion defineret ved en sandhedstabel ved kun at anvende ¬ og ∧, men vi kan gøre det endnu bedre. En vilkårlig boolsk funktion er logisk ækvivalent med et udtryk, som kun anvender NAND operatoren.

NAND

NAND er en kombination af not og and. Den angives med tegnet ↑ og defineres som:
P↑Q ≡ ¬(P∧Q)
Sandhedstabellen for det specielle tilfælde ¬(P∧P):
P:(T,F) ⇒ P∧P:(T,F) ⇒ ¬(P∧P):(F,T). Dette er sandhedstabellen for ¬P:
¬(P∧P) ≡ ¬P ≡ P↑P
Jeg benytter mig af, at NOT er reversibel: ¬¬P ≡ P:
P∧Q ≡ ¬(¬(P∧Q)) ≡ ¬(P↑Q) ≡ (P↑Q)↑(P↑Q)

Jeg har nu vist, at både ∧ og ¬ har ækvivalente udtryk, som kun indeholder den boolske operator ↑. Jeg har vist, at NAND er funktionelt komplet: En vilkårlig boolsk operator kan omskrives til en ækvivalent funktion, som kun anvender NAND.

Boolske variable antager én af to værdier. Man anvender traditionelt værdierne T og F, men man kan også anvende 0 og 1. Boolske udtryk kan herved opfattes som funktioner af bitværdier.

Der er to mulige valg for udskiftning af T og F. Man vælger konventionelt at udskifte F med 0 og T med 1. Man lister konventionelt T før F, hvorimod 0 listes før 1. Dette betyder, at sandhedstabeller udtrykt ved 0 og 1 har en omvendt rækkefølge sammenlignet med den samme tabel for T og F:
P:(T,T,F,F),Q:(T,F,T,F) ⇒ P∧Q:(T,T,T,F)
P:(0,0,1,1),Q:(0,1,0,1) ⇒ P∧Q:(0,1,1,1)

Gates

Claude Shannon viste (som student på MIT), at al boolsk algebra kan udføres ved anvendelse af elektriske kontakter. Dette er en af de fundamentale idéer bag kredsløbsdesign i alle moderne computere.

En elektrisk impuls sendes (T eller 1) eller ej (F eller 0) med diskrete tidsintervaller. Kombinationen af kontakter, som svarer til de omtalte binære operatorer, kaldes gates. De mest almindelige gates er blevet teldelt nogle specielle diagrammer. NOT Gate har 1 input-ledning og 1 output-ledning. AND Gate har 2 input-ledninger og 1 output-ledning. OR Gate har ligeledes 2 input-ledninger og 1 output-ledning. Det samme gælder for NAND Gate.

Kredsløb

Vi kan frembringe kredsløb ved at forbinde de omtalte gates. De er lineære og læses fra venstre til højre. Vi skriver input-bit til ledningerne på venstre side og læser output-bit fra ledningerne på højre side. Et interessant eksempel er P↑P. Vi ønsker at skrive den samme bitværdi, P, til begge input-ledninger for et NAND gate. Dette opnås ved at splitte signalet til to ledninger. Processen med at splitte et signal til flere kopier kaldes fan-out.

NAND er et universelt gate

Vi kan konstruere et kredsløb, som beregner en vilkårlig boolsk funktion ved blot at anvende NOT og AND gates. Man anvender traditionelt betegnelsen universelt om et gate. NAND er et universelt gate. Vi må imidlertid anvende fan-out for at slippe af med NOT og AND til fordel for det universelle NAND. Det kunne forekomme indlysende, at man blot kan kopiere et signal ved at føre det til flere ledninger; men det viser sig, at vi ikke kan anvende dette trick på en qubit.

Gates og beregninger

The exclusive or med den binære operator ⊕ er defineret ved:
0⊕0 = 0, 0⊕1 = 1, 1⊕0 = 1, 1⊕1 = 0.
Dette kan sammenlignes med addition af lige og ulige hele tal. Denne addition kaldes addition modulo 2. XOR gate svarer til operatoren⊕. XOR kan anvendes til at konstruere et half-adder kredsløb, som adderer to binære cifre. Det konstrueres ved anvendelse af et XOR gate og et AND gate. XOR beregner cifferdelen og AND beregner menten. Dette kredsløb anvender fan-out.

Reversible beregninger

Studiet af reversible gates og reversible beregninger startede med beregningers termodynamik. Shannon definerede information som negativ entropi. Shannon fik idéen fra den termodynamiske entropi. Hvor tæt er disse to entropier beslægtede? Kan teorien bag beregninger udtrykkes ved anvendelse af begreber fra termodynamik? Kan man finde et minimum for den energi, som kræves for at udføre en beregning? John von Neumann gættede sig til, at der udvikles varme ved tab af information. Rolf Landauer udledte den minimale energi, som kræves for at slette en bit af information. Denne energi kaldes Landauers grænse.

Der tabes ingen information, hvis beregningen er reversibel, og den kan udføres uden varmeudvikling.  Jeg vil i det følgende gennemgå 3 reversible gates: CNOT, Toffoli og Fredkin.

Controlled Not Gate

CNOT har 2 input og leverer 2 output. Det første input er en kontrol-bit. Det andet input-bit forlader CNOT uændret, hvis det første input-bit er 0. CNOT virker som NOT på det andet input-bit, hvis det første input-bit er 1:
CNOT(x,y) = (x,x⊕y)
Denne operation er reversibel. Vi kan konstruere et kredsløb, som udfører denne operation ved anvendelse af fan-out og et XOR gate. CNOT har den nyttige egenskab, at den er sin egen inverse funktion:
CNOT(x,x⊕y) = (x,x⊕x⊕y) = (x,y), hvor jeg anvender x⊕x = 0 og 0⊕y = y.
Man kan vise, at CNOT er et universelt gate: Alle boolske funktioner kan udføres med CNOT.

The Toffoli Gate

The Toffoli gate, opfundet af Tommaso Toffoli, har 3 input og 3 output. De første 2 input er kontrol-bit. Dette gate virker som NOT på det tredje input, hvis de 2 første input begge er 1. Dette gate er givet ved funktionen:
T(x,y,z) = (x,y,(x∧y)⊕z)
Dette gate er også sin egen inverse funktion:
T(x,y,(x∧y)⊕z) = T(x,y,(x∧y)⊕(x∧y)⊕z) = (x,y,z),
da (x∧y)⊕(x∧y) = 0 og 0⊕z = z.
Man kan vise, at Toffoli er et universelt gate.

The Fredkin Gate

Fredkin har som Toffoli 3 input-ledninger og 3 output-ledninger. Den første er en kontrol-ledning. Hvis den modtager et 0, føres de næste 2 ledninger direkte igennem til output. Hvis den derimod modtager et 1, vil de næste 2 ledninger bytte plads mellem input og output. Kontrol-ledningen føres lige igennem til output. Fredkin opfører sig som et sporskifte på en jernbane. Hvis man sender output fra dette gate direkte ind i det samme gate vil output blive det samme som input til det første gate. Fredkin er altså sin egen inverse funktion defineret ved:
F(0,y,z) = (0,y,z), F(1,y,z) = (1,z,y)
Denne definition er usædvanlig ved ikke at anvende de sædvanlige boolske operatorer.

Output fra dette gate er 3 binære tal. Det første er altid lig det binære input x. Det andet tal bliver 1, hvis enten x = 0 og y = 1 eller  x = 1 og z = 1, hvilket udtrykkes som (¬x∧y)∨(x∧z). Det tredje tal bliver 1, hvis enten x = 0 og z = 1 eller x = 1 og y = 1, hvilket udtrykkes som (¬x∧z)∨(x∧y). Fredkin kan derfor defineres ved den boolske funktion:
F(x,y,z) = (x,(¬x∧y)∨(x∧z),(¬x∧z)∨(x∧y)).

Man kan endvidere vise, at Fredkin er et universelt gate, så alle boolske operationer kan udføres ved anvendelse af dette reversible gate.

Man kan altså konstruere et reversibelt gate ved anvendelse a de boolske operatorer ¬, ∧ og ∨. Det kom som en overraskelse for mig, at alle klassiske beregninger kan udføres reversibelt, hvis man anvender CNOT eller Fredkin gates.