Senter for Marxistiske og Matematiske Studium, Enschede (SMMSE)

Du har sikkert høyrt eller lest at ei datamaskin berre skjønar eittal og nullar, eller enno verre at ei datamaskin er bygd opp av berre eittal og nullar. Den siste av desse påstandane er noko tvilsam, medan den fyrste kan seiast å vere både riktig og gal. Han er gal av di det ei datamaskin eigentleg opererer med er høg og låg spenning (dessutan har vi metodar for å omsetje til dømes tastetrykk til impulsar av høg og låg spenning, så det er ikkje feil å seie at ei datamaskin skjønar tastetrykk). Han er riktig av di det er ei veldig nyttig, og ikkje tilfeldig, måte å sjå det på; ein abstraksjon eller analogi kor vi assosierer 0 med låg spenning og 1 med høg spenning.

Eit viktig bidrag til datamaskina si utvikling (og såleis viktig i datamaskina si historie) var masteroppgåva Claude Elwood Shannon leverte i 1940 (og ein artikkel han skreiv med same namn og tema som sto på trykk i 1938). I masteroppgåva si etablerte han denne analogien vi er vorte så kjende og vane med at mest ikkje tenkjer over han – mellom elektriske/elektroniske krinsar og eittal og nullar – og viste korleis det er ein perfekt analogi til boolsk algebra.

I denne teksten skal eg sjå på nokre av dei tinga som gjer 0 og 1 til fine tal, og så på analogien til Shannon (og ein variant) og nokre enkle ting vi kan gjere med han. I del II vil eg sjå på bidraget til Shannon i tilhøve til skjemaet eg nytta på Jevons.

Lat oss gå rett på saka og seie at vi (berre) har tala 0 og 1 og dei aritmetiske operatoraren + og ·. Operatorane + og · er som vanleg berre at vi lèt 1 + 1 = 1 sidan vi ikkje har fleire tal. (Det einaste alternativet er 1 + 1 = 0. Det er ikkje noko dårleg alternativ, og ofte ganske nyttig, så vi introduserer ein ny pluss ⊕ som er akkurat som + berre at 1 ⊕ 1 = 0.) I tillegg lat oss seie at x' = 1 - x. (Det er no mogleg å sjå at x ⊕ y = x · y' + x' · y.)

Legg fyrst merke til at 0, 1, ⊕ og · gjev oss totalssystemet med pluss og gange. I eit talsystem med fleire plassar vil vi til dømes ha at 1 pluss 1 = 10 (eg skriv det sånn for å ikkje blande det med 1 + 1 = 1). Det kan vi få til ved å la x pluss y = zw sånn at w = x ⊕ y og z = x · y. Totalsystemet fungerar akkurat som titalssystemet, berre at det er to tal i staden for ti. I tillegg kan vi lett omsetje tal frå titalssystemet til totalssystemet og tilbake, så alt vi vil gjere i titalssystemet kan vi gjere med totalssystemet om vi vil.

Lat oss no definere +, · og ' ved hjelp av tabellar. I tillegg skal vi setje opp sanningstabellar for dei logiske konnektiva ∨, ∧ og ¬ ved sidan av og sjå noko interessant.

x y x + y 0 0 0 0 1 1 1 0 1 1 1 1

A B A∨B U U U U S S S U S S S S

x y x · y 0 0 0 0 1 0 1 0 0 1 1 1

A B A∧B U U U U S U S U U S S S

x x' 0 1 1 0

A ¬A U S S U

Det vi ser er at definisjonane av +, · og ' er heilt like definisjonane av ∨, ∧ og ¬, berre vi bytar 0 med U og 1 med S. Det vil seie at dei essensielt er det same systemet, og at alt vi kan gjere i utsegnslogikk kan vi òg gjere med 0, 1, +, · og '. Med 0 og 1 kan vi gjere både aritmetikk og utsegnslogikk, så vi skjønar at dei er både fine og nyttige tal! No skal vi sjå kva Shannon gjorde med dei.

Tenk deg ein brytar x på ein leidning mellom to punkt a og b. Vi skal teikne brytaren som

      x
a----o o----b

og kalle dette for ein krins. Analogien Shannon laga var å seie at om brytaren er lukka (så det er ei forbinding mellom a og b og straumen kjem gjennom) så har variabelen x verdien 0, og om brytaren er open (så det ikkje er ei forbinding mellom a og b og straumen ikkje kjem gjennom) så er x lik 1. Han observerte at om to brytarar er kopla saman i serie

      x     y
a----o o---o o----b

må båe vere lukka for at det skal gå straum mellom a og b. Krinsen av x og y i serie kan difor få verdien x + y, sidan x + y er 0 berre om både x og y er 0. Om x og y er kopla i parallell

          x
     +---o o---+
a----+    y    +----b
     +---o o---+

må båe vere opne for at det ikkje skal gå straum mellom a og b, og krinsen kan få verdi x · y av di x · y har verdien 1 berre når både x og y er 1.

Det er vanleg å byte om på det, og vi får då den alternative tolkinga i tabellen nedanfor.

Krins	Tyding	Shannon	Alternativ
x a----o-o----b	x er lukka	x = 0	x = 1
x a----o|o----b	x er open	x = 1	x = 0
x y a----o o---o o----b	x og y i serie	x + y	x · y
x +---o o---+ a----+ y +----b +---o o---+	x og y i parallell	x · y	x + y

Resultatet vert akkurat det same. Den alternative tolkinga er kanskje meir intuitiv, så frå no av skal vi halde oss til ho.

No kan vi lage uttrykk for større samansette krinsar. Ta til dømes krinsen

              x
         +---o o---+      
     +---+    y    +---+
     |   +---o o---+   |
a----+    x'      z    +----b
     +---o o-----o o---+

Vi kan tenkje oss at x og x' er forbundi på ein sånn måte at x er open berre når x' er lukka og omvendt. Eit uttrykk for krinsen er (x + y) + (x' · z). Ved å gje verdiar til x, y og z, til dømes, x = 0, y = 0 og z = 1, kan vi finne ut om det går straum mellom a og b når x og y er lukka, og x' og z er opne. Av di 0 + 0 + (0' · 1) = 1 · 1 = 1, ser vi at, ja, det er straum mellom a og b. Vi kan òg omsetje uttrykket til ei logisk utsegn basert på den samanhengen vi såg tidlegare. Om vi lèt X, Y og Z vere grunnutsegner som representere x, y og z (X er sann når x er lukka osb.) får vi at utsegna (X ∨ Y) ∨ (¬X ∧ Z) er sann akkurat når det går straum gjennom krinsen.

Analogien vi no har etablert kan vi nytte på ulike måtar. Til dømes kan vi analysere krinsar. Lat oss seie vi har krinsen under.

                         x
              z     +---o o---+
     +-------o o----+    y'   +---+
     |              +---o o---+   |
     |        z'         x        |
a----+-------o o--------o o-------+----b
     |        z                   |
     |   +---o o---+     z'       |
     +---+    y'   +----o o-------+
         +---o o---+

Eit logisk uttrykk for denne krinsen er P = (Z ∧ (X ∨ ¬Y)) ∨ (¬Z ∧ X) ∨ ((Z ∨ ¬Y) ∧ ¬Z). Men vi kan finne at utsegna Q = X ∨ ¬Y er logisk ekvivalent med P (P og Q har same sanningsverdi for alle tilordningar av sanningsverdiar til X, Y og Z). Basert på Q vi kan lage ein mykje enklare krins, men som gjer akkurat same jobben:

          x
     +---o o---+
a----+    y'   +----b
     +---o o---+

Noko anna vi kan gjere er å realisere formlar som krinsar. Som eit eksempel kan vi tenkje oss at vi ønskjer å leggje saman to tal med to plassar i totalssystemet. Svaret må ha tre plassar sånn at, til dømes, 11 pluss 10 = 101 og 10 pluss 01 = 011. Generelt kan vi skrive det som xy pluss zw = ijk. Om vi tek den vanlege måten å leggje saman på, kan k ganske enkelt uttrykkjast som

k = y ⊕ w = y · w' + y' · w

For j må vi take omsyn til om vi får mente frå summen av y og w. Det kan uttrykkjast som y · w, så vi får

j = x ⊕ z ⊕ (y · w) = (x · z' + x' · z) · (y' + w') + y · w · (x' + z) · (x + z')

i avheng berre av om vi får mente frå x og z, så med andre ord:

i = x · z + x · y · w + z · y · w = x · z + (x + z) · y · w

Vi lagar ein krins med punkta g, i, j og k, og seier at i er 1 om det straum mellom g og i og 0 om det ikkje er straum mellom g og i, og tilsvarande for j og k.

              x
         +---o o---+    y       w
     +---+    z    +---o o-----o o---+
     |   +---o o---+                 |
     |                      z        +-----------------i
     |           +---------o o-------+
     |        x  |  z'             y'
     |   +---o o-+-o o---+    +---o o---+
g----+---+    x'    z    +----+    w'   +---------+
     |   +---o o---o o---+    +---o o---+         |
     |                      x'            x       +----j
     |              w  +---o o---+   +---o o---+  | 
     |           +-o o-+    z    +---+    z'   +--+
     |           |     +---o o---+   +---o o---+
     |        y  |  w'
     |   +---o o-+-o o---+ 
     +---+    y'    w    +-----------------------------k
         +---o o---o o---+

Sidan krinsen er laga ut frå formlane for i, j og k over, vil dei leggje saman tala xy og zw for oss. Vi berre set brytarane sånn at dei tilsvarar tala vi vil leggje saman, og om vi har kopla nokre lampar til i, j, og k kan vi lese av svaret.

Med analogien mellom straum og 0 og 1, eller utsegnslogikk, kan vi både analysere og designe elektriske krinsar. Metodane og teknikkane har sjølvsagt vorte vidareutvikla sidan Shannon fyrst gjorde analogien (når rett skal vere rett hadde både russarane Paul Ehrenfest og V. I. S. Sestakov og japanarane Akira Nakasima og Masao Hanzawa funne analogien før Shannon, men det var arbeidet til Shannon som vart lagt merke til), men når vi nokre gonger seier at datamaskiner berre skjønar eittal og nullar er det av di den grunnleggjande ideen framleis er den same.

Kjelder

William Aspray. Logic machines. I, William Asprey (red.), Computing before computers, side 99-121, Iowa State University Press/Ames, 1990.

Elliott Mendelson. Introduction to mathematical logic. Fjerde utgåve. Chapman & Hall, 1997.

J. Donald Monk. The Mathematics of Boolean Algebra. I, Edward N. Zalta (red.), The Stanford Encyclopedia of Philosophy, 2002.

David A. Patterson and John L. Hennessy. Computer organization & design. The hardware/software interface. Andre utgåve. Morgan Kaufmann Publishers, 1998.

Claude Elwood Shannon. A symbolic analysis of relay and switching circuits. Master's thesis, Massachusetts Institute of Technology, 1940.