Boolsk Algebra   
 

Opp

 

 

 

 

 

 

 

 

 

Boolsk Algebra

Boolsk algebra er et sett av matematiske regler for å håndtere sammensatte logiske funksjoner. Reglene for Boolsk algebra følger reglene for de elementære logiske funksjonene i tillegg til regler for forenkling av uttrykk:

A * 0 = 0

A * 1 = A

A * A = A

  A * A' = 0

 
A + 0 = A

A + 1 = 1

A + A = A

A + A' = 1

  (A')' = A

A + A*B = A*(1 + B) =
A * 1 = A

  A + A'*B = A + B

  (A + B) * (A + C) =
A*A + B*A + A*C + B*C = A + B*A + A*C + B*C =
(1 + B)*A + A*C + B*C =
A + A*C + B*C =
(1 + C)*A + B*C =
A + B*C

 

 


Boolsk algebra

Boolsk algebra, algebra på ein endelig mengde av 2 tal, er en spesiell men viktig del av programmering. Her forklarar me grunnleggjande boolsk algebra.

Introduksjon

Boolsk algebra er ein veldig spesiell måte å regne på, og det de fleste forbinder med namnet er datatypen boolean, som finns i de fleste programmeringsspråk. Det er derimot mange måtar å skrive ting på. Me byrjar med heilt grunnleggande logikk.

Først og fremst baserer boolsk algebra seg på boolsk verdiar, eller sanninngsverdiar. Notasjonen dei fleste er vant til er true og false, sant og usant, høg og lav eller 1 og 0. Ein boolsk variabel kan berre anta to verdiar, nemlig 1 og 0. Kva du ønskjer å kalle desse får vere opp til deg sjølv.

I programmering kan ein gjere visse operasjonar, som me nyttar oss av heile tida, t.d. i if-setningar, while- og for-loopar, og så vidare. Dette er det me kallar utsegn (frå engelsk statement). Ein utsegn er det som gjer oss ein sanningsverdi, og sanningsverdien avgjer ofte kva programmet skal gjere vidare. "1 + 1 = 2" er ei utsegn, som vil gje sanningsverdien 1 (sann). Me kan og kombinere utsegner, "1 + 1 = 2 eller 1 + 1 = 3", som og vil ha sanningsverdi 1.

Dette er det me kallar ei samansett utsegn, og me har her nytta operatoren "eller". Me har eit standard sett med slike operatorar, som er "og" (AND), "eller" (OR), "eksklusiv eller" (XOR) og "ikkje" (NOT). Det finns fleire, men desse er dei viktigaste. Nøyaktig korleis dei virkar, skal me straks definere.

Når me vil skrive utsegna fort, nyttar me ofte ein meir matematisk notasjon, og det er denne notasjonen me skal nytte utover i denne artikkelen. Difor kjem me ikkje til å bruke så konkrete døme som ovanfor, men litt meir abstrakte dømer. Me kjem til å kalle den første utsegna p, den andre q, og så vidare.

Me kjem heller ikkje til å bruke dei vanlege programmeringsoperatorane AND (&&) og OR (||), men dei relevante matematiske symbola. Det er eigentleg veldig enkelt, men det krev litt tilvenning. Me seier at AND vert skrive som multiplikasjon, som betyr at pq = p AND q = p*q berre er ulike skrivemåtar av det same uttrykket. I tillegg seier me at OR vert skrive som addisjon p + q = p OR q.

Og, eller, ekslusiv eller og ikkje

Når ein skal rekne med boolske verdiar, er det ikkje det same som å rekne med det binære talsystemet. T.d. er 1 + 1 = 10 i totalssystemet, men i boolsk algebra er 1 + 1 = 1. Dette er noko du må ha i bakhovudet heile vegen.

Ein logisk og, er akkurat det same som me nyttar i daglegtale. "Vegard er kul og Vegard er tøff" er sant berre dersom Vegard faktisk er kul OG tøff, men usant ellers. Me kan setje dette opp i ein sanningstabell, der me kallar "Vegard er kul" for Q og "Vegard er tøff" for P. Me byrjar med å sette opp alle moglege verdiar for Q og P, og fyller deretter ut med PQ. Merk at dette ikkje er noko du kan rekne deg fram til, men det er den faktiske definisjonen på boolsk multiplikasjon.

OR er litt annleis enn den daglegdagse betydninga. Om ein norsklærar seier at "Vegard er kul eller Vegard er tøff", så meiner han at eg er ein av delane, men ikkje begge. I logisk betydning er OR sann dersom P er sann, Q er sann eller begge to er sann.

XOR, som har operatoren , stemmer derimot meir med den daglegdagse betydninga av ordet "eller". Her er det nemlig slik at den er sann berre dersom P er sann eller Q er sann, men ikkje dersom begge er sann. Du les uttryket PQ som "P eller Q men ikkje begge" eller "P ekslusiv eller Q".

NOT (ikkje, ¬) er det ekvivalente med å setje minus foran eit tal; talet blir det "motsette". Sidan me berre har 2 "tal" å velgje mellom, betyr det at sann blir til usann og usann blir til sann. ¬P les du "ikkje P". Mange plassar nyttar ein og ordet komplement om NOT-operatoren, og ein skriv det då P' som er det same som ¬P. Ein les det "P komplement" eller "ikkje P", der ein i matematikken normalt ville lest "P merka" eller "P derivert". Me kjem til å bruke komplement i resten av denne artikkelen, sidan me har brukt matematisk notasjon ellers. Det kjem eit lite avsnitt om alternative skriveformar til slutt.

Følgjande tabell illustrerer bruken av desse operatorane.

P Q PQ P+Q PQ P'
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 0
1 1 1 1 0 0

Du ser at PQ berre er sann dersom både P og Q er sann, og er usann ellers. P+Q er derimot sann dersom ein av dei er sann, eller om begge er sann.

 

 

 

Reknereglar

Når du no har sett på dei vanlegaste operatorane innanfor boolsk algebra, er det på tide å vete kva reknereglar som gjeld for dei. Reknereglane er nemleg litt annleis enn for vanleg algebra. Først og fremst så finns ikkje subtraksjon og divisjon i boolsk algebra.

Først og fremst, så skal multiplikasjon gjerast før substitusjon, dvs. at uttrykket PQ + R er det same som (PQ) + R, men ikkje det same som P(Q + R). AND-funksjonar er nemlig distributive over OR-operasjonar, som gjer at P(Q + R) er det same som PQ + PR. Dette er det same som ein er vane til for vanleg algebra, og er lett å bevise ved hjelp av ein sanningstabell over uttrykka P(Q + R) og PQ + PR.

Noko som ein ikkje har i vanleg algebra, er at addisjon er distributiv over multiplikasjon, som vil seie at P + QR = (P + Q)(P + R). Denne er vanskelig å forklare, og me sett difor berre opp ein sanningstabell for å vise at uttrykka har same sanningsverdiar.

P
Q
R
QR
P + QR
P + Q
P + R
(P + Q)(P + R)
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1

Eit noko overraskande resultat? Dette er noko som krev litt tilvenning for å verte vant med.

Logiske implikasjonar

Det er no det byrjar å verte litt vanskelig, implikasjonar kan på ein måte samanliknast med ein if-setning, men har ikkje nøyaktig den same funksjonaliteten. "Dersom det regnar, er det overskya" er eit døme på ein implikasjon. Me sett her "det regnar" lik P og "det er overskya" lik Q. Me skriv då dette som PQ, og les det "P fører til Q", "P impliserer Q" eller "P medfører Q".

Måten dette virkar på, er at P er nødt til å vere sann, før me i det heile tatt ser på verdien av Q. Dersom P er usann, vil utsegna ikkje seie noko om det er overskya. Om det reknar og det er overskya, vil P→Q vere sann. Det eineste tilfellet der PQ er usann, er om P er sann og Q er usann.

Dette uttrykket kan me og skrive som ein kombinasjon av og, eller og ikkje. Me kan seie PQ = Q + P'. Dette kan me sjå ved hjelp av ein sanningstabell, som me nytta over for å vise korleis operatorane virka. I ein sanningstabell nyttar me definisjonen på ein implikasjon for å plotte den inn, og sett deretter saman uttrykka me treng for å komme fram til P→Q = PQ + P'.

P Q PQ P' P' + Q
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1

Om ein ser på sanningstabellen, kan ein sjå at kolonnene er heilt like for dei to uttrykka. For å vere sikker på at me ikkje gjer feil, har eg teke med PQ og P', sidan det då er mykje lettare å setje saman det siste uttrykket.

Alternativ notasjon

Alle skriveformane me har nytta oss av i denne artikkelen, er det som er standardisert matematisk notasjon. Ein nyttar det t.d. når ein driv med design av logiske digitale portar ved hjelp av transistorar, men det finns og andre skrivemåtar.

Først og fremst er logisk multiplikasjon, eller AND, ofte representert som , dvs. PQ ("P og Q"). Det finns ein liknande skriveform for logisk addisjon, OR-operatoren , som i PQ ("P eller Q"). Når ein nyttar desse skriveformane er det vanleg å plassere mange parantesar, for å indikere kva operator som skal utførast først, sidan det no er vanskeligare å sjå utifrå uttrykket; PQ + P' = .

Over ser du og at eg har nytta ein annan skriveform for NOT-operatoren. Det er hovudsakleg fire måtar å skrive NOT P på, nemlig -P, ¬P, P' og .

Under er det framsett ein tabell som viser dei ulike skriveformane og notasjonane du kan støte på. Merk at ein aldri blander notasjonsmåtar frå ulike kolonnar her. I dei fleste programmeringsspråk er det forskjell på boolske uttrykk og bit-uttrykk, her nyttar me boolske uttrykk.

Operator Boolsk algebra Logikk Java/C/C++/C#/PHP Delphi/VB
AND * && and
OR + || or
XOR ^^ xor
NOT -, ' , ¬ !, ~ not

Logisk ekvivalens

Ein kjem ofte over uttrykk som ser heilt ulike ut, men som uttrykker akkurat det same, og har dei same sanningstabellane. Slike uttrykk kallar me logiske ekvivalente, og bruker som oftast teiknet for å representere det. Det brukast som oftast som likhetsteiknet, og logisk notasjon. I notasjon for normal boolsk algebra brukast =.

Konklusjon

Boolsk algebra er eit svært nyttig verktøy som ein ofte får bruk for i programmering, spesielt når ein skal skrive lengre logiske uttrykk. Då er det ofte kjekt å vete korleis ein skal forkorte uttrykka best mogleg, og uttrykke dei på ein måte som krever minst mogleg av maskina som skal køyre dei.

Det er eit emne som er nyttigare i digitalteknikk, som er kunsten å designe digitale kretsar, men det er mykje ein kan dra med seg rett inn i programmering. Når ein designar digitale kretsar, er det nemlig viktig å nytte minst mogleg transistorar for å gjere ein rekneoperasjon, og ein kan spare plass, tid og pengar på å ha eit bra utgangspunkt.

Startside ] Opp ] [Søk]

Copyright © 2002 Øyvind Haugland
Sist endret:  25 mars 2017
 

  Interested in this stuff? Please write to:
 

HTML Counter            stats counter