Konsepter:Boolesk Algebra

Fra CodeWiki

Matematikeren George Boole var opprinnelig matematiker, men interesserte seg også for logikk. Circa 70 år etter Booles død fant C. Shannon et praktiskt bruksområde for Booles teorier; optimalisering av relesystemer i telefonnettet. Videre ble boolesk algebra det matematiske grunnlag for digitalteknikken. Logiske utsang (feks: Mannen er eldre enn 25 år) kan ha verdiene true (sant) eller false (usant). I logiske utsang bruker vi gjerne logiske variabler. eksempelvis: A = Mannen som er eldre enn 25 år, B = Har pollenallergi. Disse logiske variabler kan kombineres i logiske funksjoner, AND, OR og NOT (inverter)

Logiske Funksjoner

AND-funksjonen

Eksempel på AND-funksjoner

A = "Sent Søknad"
B = "Opptakskrav OK"
T = "Fått studieplass"

Poenget her er at T kan kun være sant hvis både A og B er sant. Dette kan vi skrive som en sannhetstabell

A	B	T
0	0	0
0	1	0
1	0	0
1	1	1

Vi kan også skrive det som den logiske likning: T=A*B.

OR-funksjonen

Eksempel på OR-funksjon

A = "Kjøre R4 fra Oslo"
B = "Kjøre E6 fra Oslo"
T = "Ankomme Jørstadmoen"

Poenget her er at for at T skal være sant må enten A eller B være sann.

Sannhetstabellen for dette vil være:

A	B	T
0	0	0
0	1	1
1	0	1
1	1	1

Her er det viktig å merke seg at verdiområdet vi her jobber med er 0-1. Dvs at 1+1=1 i vår logiske algebra Eventuelt kan vi sette opp en logisk likning: T = A + B

NOT-funksjonen

NOT-funksjonen er en inverterer som snur verdien til det motsatte.

A	T
0	1
1	0

Et invertert uttrykk noteres med "ikke" foran, en strek over eller med ' bak. Her er T=A' eller T=(ikke)A.

NOT AND = NAND-funksjonen

En NAND-funksjon kan vi se på som en invertert AND-funksjon. Sannhetstabellen for en NAND-funksjon er som følger:

A	B	T
0	0	1
0	1	1
1	0	1
1	1	0

Logisk likning blir T = (A*B)'

NOT OR = NOR-funksjonen

Da har vi en i utgangspunktet en OR-funksjon som inverteres.

sannhetstabellen blir slik:

A	B	T
0	0	1
0	1	0
1	0	0
1	1	0

Mens den logiske likningen blir: T=(A+B)'

EXCLUSIVE OR = XOR-funksjonen

Også kjent som EXOR-funksjon. Utgangspunktet er dette en OR-funksjon, men den er ekskusiv så den blir høy hvis det bare er en av inngangene som er høye. Med andre ord, T er true hvis enten A eller B er true, men ikke når begge er true.

Eksempel på XOR-funksjon

A = "Holder shift nede"
B = "Caps-lock er på"
T = "Stor bokstav på skjermen"

sannhetstabellen blir slik:

A	B	T
0	0	0
0	1	1
1	0	1
1	1	0

Mens den logiske likningen blir: T=(A (+) B)' som kan også skrives som: T=A' B + A B' = A x B.

Bruk av boolske funksjoner

Implementasjon av boolske funksjoner

Hvis vi skal se på boolske funksjoner satt i system kan vi se for oss en vindusviskerstyring med følgende variabler: A, B, C og M

A = 1 = Tenning PÅ
B = 1 = ViskerBryter PÅ
C=1=Visker i parkert posisjon
M=1=Viskermotor går

Vi får en sannhetstabell slik:

A	B	C	M
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Her har vi følgende likning: M = A'B'C' + ABC' + ABC = AB'C' + AB(C'+C) = AB'C' + AB = A(B'C' + B) = A(C'+B)

Noen Logiske Regneregler

For å regne med logiske likninger er det greit å vite om de mest sentrale regnereglene:

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

Inverteringsregler

(AB)' = A'+B'
(A+B)' = A'B'

Ovenfor ser vi det som kalles de Morgans teorem. Inverteringsreglene går på:

AND(og)-funksjon byttes med OR(eller)-funksjon
Ikke invers variabel byttes ut med sin inverse utgave

Forenkling av Boolske Likninger

Boolske likninger kan forenkles. Vi tar et eksempel:

T = ABC+AB'(A'C')'
T = ABC + AB'(A+C)
T = ABC + AB'+AB'C
T = A(B'+B)+AB'
T = AC+AB'

T = A(C+B')

T = A'C (A'BD)' + A'BC'D' + AB'C
T = AC(A+B'+D') + A'BC'D' + AB'C
T = A'AC+A'B'C+A'D'C + A'BC'D' + AB'C
T = B'C+A'D'C + A'BC'D'
T = B'C + A'D'(C+BC')
T = B'C+A'D'C + A'D'B

T = B'C+A'D'(B+C)

Karnaughdiagram

Ved å tegne om sannhetstabellen kan vi fremstille et Karnaughdiagram. I et slikt diagram blir de bolske variablene sortert slik at bare en variabel endres per rute. Prinsippene for opprettelse av Karnaughdiagrammer er som følger:

Skap grupper av naboceller (antallet skal være en potens av 2, eks: 2,4,8,16..)
De variablene som endrer seg fjernes

Illustrasjon av Karnaughdiagram

Hvis vi ser på sannhetstabellen ovenfor, kan vi se hvordan Karnaughdiagrammet da blir:

BC/A	00	01	11	10
0	0	0	0	0
1	1	0	1	1

Illutrasjonen til høyre viser hvordan diagrammet skal leses av, samt gruppene av nabocellene.

Ved å lese Karnaughdiagrammet kan vi finne det forenklede uttrykket uten hjelp av regnereglene, vi kan rett og slett lese det av diagrammet. Ut ifra gruppene kan vi lese følgende:

Gruppe 1: ABC + ABC' = AB(C+C') = AB
Gruppe 2: AB'C' + AB'C = AC'(B'+B) = AC'
___________________________________________
Svaret blir: AB+AC' = A(B+C')

Grunnen til at 11 kommer før 10 er at vi skal få mer oversiktlige nabogrupper slik at du kan se hvor mange variabler som forandrer seg.