Boolesk algebra
Från Rilpedia
| Logik, Formellt system |
|---|
| Logiska system |
Boolesk algebra, introducerades av George Boole i boken "En undersökning av tankelagarna på vilka de matematiska teorierna för logik och sannolikhet är grundade" som gavs ut år 1854. Boolesk algebra är en teknik som beskriver den klassiska logiken sanningsfunktionellt med hjälp av de två talen 1 och 0 för 'sant' resp. 'falskt'. Algebran bygger på operationerna addition, subtraktion och multiplikation, men definierar tilläggsregler till dessa för att avbilda beteendet hos de logiska operationern 'OCH' och 'ELLER'.
Valet av 1 och 0 att representera sanningsvärdena motiverades att dessa har goda egenskaper i förhållande till de matematiska operationerna då 1-0=1, 1-1=0 direkt motsvarar beteendet hos operationen 'ICKE', 0*0=0, 0*1=0, 1*0=0, 1*1=1 direkt motsvarar beteendet hos operationen 'OCH' samt 0+0=0, 0+1=1, 1+0=1, 1+1=2 motsvarar beteendet hos operationen 'ELLER' så när som på 1+1. Med regeln 1+1=1 kunde additionen modifieras så att sanningvärdena aldrig kunde bli andra än 0 eller 1. På detta sätt kunde beteendet hos den klassiska logikens sanningsfunktioner direkt avbildas. Algebraiskt fick även reglerna p*p=p samt p+p=p införas för att den klassiska logikens egenskaper skulle bibehållas.
Tilläggsreglerna 1+1=1, p+p=p och p*p=p ger ju specialvarianter av operationerna '+' och '*'. Detta motiveras inte av valet av 1 och 0 som sanningsvärden ty egenskaperna hos den klassiska logikens operationer (konnektiv) - dess sanningsfunktionalitet - kan enkelt uttryckas med vanlig addition och multiplikation:
- ~p = 1 - p
- (p & q) = pq
- (p v q) = p + q - pq
- (p xor q) = p + q - 2pq
- (p -> q) = 1 - p + pq
- (p <-> q) = 1 - p - q + 2pq
Korrigeringstermerna 'pq' i uttrycken ovan skapar oöverskådlig komplexitet när uttryck substitueras i varandra. Den booleska algebrans specialregler reducerar bort denna komplexitet:
- ~p = 1 - p ;
- (p & q) = pq ; p*p=p
- (p v q) = p + q ; p+p=p, 1+1=1
Genom dessa enkla regler kan komplexa funktioner förenklas vilket använts med stor framgång inom digitaltekniken för att beräkna det minsta antal logiska kretsar som behövs för att realisera ett visst beteende.
