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.

I dei tidlegare tekstene om Jevons og logikkpianoet hans har eg hevda at dei har signifikans når ein freistar skjøne datamaskina si historie. Det er ikkje av di "[w]hile Jevons refers to his device as a logical machine, what he created was a simple, mechanical computer, perhaps the first successful one of its kind" slik som Buck og Hunka hevdar. Det er ingenting ved pianoet som liknar det vi i dag kallar datamaskiner. Det er og blir ei logikkmaskin, korkje meir eller mindre. Signifikansen ligg heller ikkje i ei historisk line frå Jenons til våre datamaskiner. Sjølv om vi veit at Jevons inspirerte nokre av sine samtidige, som Venn og Marquand, til å lage sine eigne logikkmaskiner er det lite eller ingenting som tydar på at dei som seinare lagde dei fyrste datamaskinene i noko utprega grad var inspirert av dette arbeidet. Signifikansen ligg i det tankesettet Jevons nytta då han bygde logikkmaskina si, som gjer at vi kan sjå på Jevons som ein tidleg oppdagar av eit av dei grunnleggande prinsippa som ligg til grunn for datamaskinar og datahandsaming. Det at dette prinsippet har blitt oppdaga og gjenoppdaga fleire gonger av andre personar gjer ikkje signifikansen til Jevons mindre, men gjer han heller til ein representant det er interessant å ta ein titt på.

Kva var det så Jevons oppdaga? Eg skal ta ein liten omveg og vitje George Boole på vegen. Boole var ein britisk matematikar og filosof som levde omtrent på same tid som Jevons, og reknest blant grunnleggjarane av den moderne logikken (i motsetnad til den aristoteliske logikken). Boole formulerte det som i dag vert kalla boolsk algebra. Kort fortalt er boolsk algebra ei matematisk formulering av logikk som gjev logiske uttrykk visse matematiske eigenskapar (boolsk algebra er mykje meir òg, men for oss er det dette som er viktig). Det gjer at vi kan ha matematiske reglar for logikken og at vi kan manipulere logiske uttrykk. I tekstane om utsegnslogikk og slutningar såg vi reglar for symbolsk manipulasjon av utsegner som bevarte sanninga i utsegnene. Desse reglane er eit eksempel på boolsk algebra. Ein måte å sjå det på kan kanskje vere at det vert etablert ein analogi mellom dei matematiske symbola og den intuitive forståinga vår av logikk, og at reglene for manipulering av symbola er intuisjonsbevarande.

Jevons var inspirert av Boole og tok analogien eit steg vidare. Han innsåg at han kunne lage ein fysisk representasjon av dei matematiske symbola; dei stavane med pinnar som representerer logiske utsegner i maskina hans. Eg har tidlegare sagt at denne måten å gjere det på ikkje er så interessant, men for Jevon var ikkje dette noko naudløysing. Det var sånn han meinte logikk skulle gjerast; det han var interessert i var nettopp å starte med alle moglegheiter og så stegvis eliminere dei som ikkje er konsistente med premissane, og han laga ein metode for å gjere akkurat det. Eg skal ikkje gå i detalj på metoden, men han inneber at etter kvart som ein analyserer premissane vert utsegnene ein jobbar på (dei på forma A ∧ B ∧ C ∧ D om de hugsar fyrste teksten om Jevons) klassifisert i fire ulike grupper og for kvart steg kan utsegene endre klassifisering. Når ein er ferdig vil kvar av utsegnene vere i gruppa "konsistent med premissane" eller i gruppa "ikkje konsistent med premissane".

Ein slik metode som stegvis fører oss fram til eit resultat kallest gjerne for ein algoritme, så vi kan seie at Jevons definerte ein algoritme. Ein sånn algoritme er på sett og vis ei abstrakt eining; han fortel korleis ein skal flytte rundt på symbol og andre abstrakte einingar og vert ikkje til noko konkret før vi utfører han, til dømes ved å nytte han til å løyse eit problem på eit stykke papir.

Kva gjorde Jevons så? Han bygde ei maskin som utførte algoritmen hans; han omsette den abstrakte algoritmen til ein fysisk prosess. Dette kunne han sjølvsagt ikkje ha gjort utan å fyrst ha funne analogien mellom dei abstrakte utsegnene og dei fysiske stavane og pinnane, av di ein fysisk prosess manipulerer fysiske ting. Mays og Henry har vist at det er eit perfekt samsvar ikkje berre mellom stavane i maskina og utsegnene, men òg mellom posisjonane til stavane og klassifiseringa av utsegner, og mellom flyttinga av stavane når ein trykkar på tangentane og stega i algoritmen.

For å oppsummere kan vi seie at dette er ein tretrinnsrakett:

1. Jevons definerte ein abstrakt algoritme.
2. Han etablerte ei rekkje enkle analogiar (utsegn/stav, klassifisering/posisjon, endring av klassifisering/flytting av stav).
3. Basert på desse analogiane omsette han algoritmen til ein fysisk prosess utført av ei maskin.

Når vi så nyttar logikkmaskina gjer vi ein abstraksjon; vi les av resultatet på maskina (dvs. posisjonen til stavane) og tolkar dette som abstrakte einingar (klassifisering av utsegner).

Kva er signifikansen av dette? Signifikansen er at dette er eit mønster vi ser igjen gong på gong når vi ser på datamaskina og datahandsaminga si historie, og er eit grunnleggjande tankesett som ligg til grunn for korleis datamaskiner verkar og korleis dei vert nytta.

I seinare tekstar vil eg vise fleire døme på at dette mønsteret dukkar opp, men som eit eksempel på den siste påstanden ("korleis dei vert nytta") skal eg nytte slutningskalkulatoren eg presenterte i ein tidlegare tekst.

Dette dataprogrammet er laga i eit programmeringsspråk som heiter Java og som er eit objektorientert programmeringsspråk. Det vil seie at "objekt" er ei grunnleggjande eining i språket. (Akkurat kva eit objekt er, er ikkje så nøye. Ein kan òg seie at objekt og andre ting i Java er abstrakte einingar, men det finst etablerte analogiar for korleis desse er representert fysisk i datamaskina, så vi skal ikkje vere så nøye på det heller, men berre tenkje oss at det å lage eit dataprogram liknar på det å byggje ei maskin).

Det eg starta ut med var ein algoritme for å undersøke gyldigheita av ei slutning (sanningstre/tremetoden). Denne algoritmen manipulerer abstrakte einingar som til dømes utsegner og tre. Eg laga ei rekkje enkle analogiar, som at ei utsegn vert representert av eit objekt og eit moteksempel vert representert av ei liste objekt som igjen representerer literalar, og nokre fleire liknande analogiar. Deretter omsette eg algoritmen til eit program ved beskrive korleis desse representasjonane skal manipulerast. Når eg nyttar programmet skjer manipulasjonane som fysisk prosessar inni datamaskina mi, og når programmet er ferdig les eg av resultatet frå skjermen og tolkar det som abstrakte einingar, til dømes som eit moteksempel til at ei slutning er gyldig.

Med andre ord følgde eg det same mønsteret som Jevons då eg laga slutningskalkulatoren. Og eg tenkte ikkje ein gong på det medan eg gjorde det, det var noko eg oppdaga etterpå. Heilt sant!

Kjelder

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

George H. Buck, Stephen M. Hunka. W. Stanley Jevons, Allen Marquand, and the origin of digital computing. IEEE Annals of the History of Computing, 21(4):21-27, 1999.

William Stanley Jevons. On the mechanical performance of logical inference. Philosophical Transactions of the Royal Society of London, 160:497-518, 1870.

W. Mays, D. P. Henry. Jevons and logic. Mind, 62(248):484-505, 1953.

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

J. J. O'Connor, E. F. Robertson. George Boole. The MacTutor History of Mathematics archive.(11. desember 2005)