Den boolske algebra eller den boolske beregning er den del af matematik, der beskæftiger sig med en tilgang algebraisk den logiske opfattelse med hensyn til variabler , af operatorer og funktioner på logiske variabler, som tillader brug af algebraiske teknikker til at håndtere toværdige udtryk for beregningen af propositioner . Det blev startet i 1854 af den britiske matematiker George Boole . I dag finder boolsk algebra mange applikationer inden for datalogi og i design af elektroniske kredsløb .
Det blev først brugt til telefonskifte kredsløb af Claude Shannon .
Den boolske algebra af logiske funktioner gør det muligt at modellere logisk ræsonnement ved at udtrykke en “tilstand” som en funktion af betingelser. For eksempel, hvis vi studerer udtrykket Kommunikation og udtrykket Pick up;
Kommunikation = sender OG modtager
Kommunikation ville være "SAND", hvis både afsender- og modtagervariablerne var aktive (dette er en logisk funktion afhængigt af afsender- og modtagervariablerne )Afhentning = (Ringning OG beslutning om at svare) ELLER Beslutning om at ringe
At afhente ville være “SAND”, enten hvis du hører ringetonen samtidigt OG du beslutter at svare , eller ( ELLER ) hvis du blot beslutter at ringe .Boolsk algebra er et domæne, der er fælles for tre discipliner, og vi møder forskellige notationer for at betegne det samme objekt. I resten af artiklen vil vi angive de forskellige notationer, men vi vil have ret til at opretholde en vis homogenitet.
Vi kalder B det sæt, der består af to elementer kaldet sandhedsværdier {TRUE, FALSE}. Dette sæt er også bemærket
med for og for .
Notationen foretrækkes i det følgende .
På dette sæt kan vi definere to binære love (eller operationer), AND og OR love, og en unary operation, negationen (eller komplementet).
For alle de følgende eksempler og egenskaber,
ET lov tabel | ||
b \ a | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Det defineres som følger: a OG b er SAND, hvis og kun hvis a er SAND, og b er SAND.
Denne lov bemærkes også:
I det følgende foretrækkes betegnelsen “ ”.
Tabellen i denne lov (analog med en tilføjelses- eller multiplikationstabel ) er ikke en sandhedstabel .
Lovens tabel ELLER | ||
b \ a | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
Det defineres som følger: a ELLER b er SAND, hvis og kun hvis a er SAND, eller b er SAND. (Især hvis en er sandt og b er også sandt, så en ELLER b er sandt.)
Denne lov bemærkes også:
Vil blive foretrukket i følgende notation men pleje vil blive taget hensyn til, at denne lov er ikke den sædvanlige tilføjelse i Z / 2 Z . Dette er grunden til, i matematik og i matematisk logik , notationen ikke bruges til at betegne "eller inklusive": den er forbeholdt " eller eksklusiv ", en operation, der (sammenføjet med "og") gør enhver algebra af boolsk en boolsk ring , især en Z / 2 Z - algebra .
Fornægtelsen af a er SAND, hvis og kun hvis a er FALSK.
Negationen af a bemærkes:
Notationen foretrækkes i det følgende .
Vi får derefter og .
Operatører er påvirket af flere almindelige egenskaber:
Derudover har hver operatør et neutralt element og et absorberende element :
Forenklinger er mulige som:
den konsensus teorem gælder for operatører af boolsk algebra:
Endelig følger de princippet om komplementaritet:
Vi finder derefter alle de egenskaber, der giver B en struktur af boolsk algebra .
PrioritetFor at forenkle skrifterne er det sædvanligt, at de boolske operationer er underlagt de samme prioritetsregler som de sædvanlige aritmetiske operationer: AND-funktionen (logisk multiplikation) har således prioritet over OR-funktionen (logisk sum). Så:
Det er stadig muligt at placere parenteser i beregningerne for at ændre rækkefølgen af operationer.
De Morgans sætning
De Morgans første lov (disjunction negation)
udtrykkes ved følgende ligestilling
I begge tilfælde vil udtrykket kun være SAND, |
De Morgans anden lov (benægtelse af sammenhængen)
I begge tilfælde vil udtrykket kun være FALSK, |
Matematisk en logisk funktion eller logisk operator er et program til B n i B .
I elektronik er en logikfunktion en sort boks, der modtager et bestemt antal logiske variabler som input, og som udsender en logisk variabel afhængigt af inputvariablerne. Artiklen logisk funktion forklarer, hvordan man konstruerer de sorte kasser med nogle grundlæggende funktioner.
En sandhedstabel gør det muligt at specificere tilstanden for output i henhold til tilstandene for input. Det karakteriserer den logiske funktion.
Enhver sandhedstabel og derfor enhver logisk funktion kan beskrives ved hjælp af de tre grundlæggende operationer:
Vi beviser også, at der er nøjagtige logiske funktioner i parametre. Det er faktisk tilstrækkeligt at overveje alle mulige sandhedstabeller eller at overveje udviklingen af en funktion af parametre.
De kommer fra de tre grundlæggende operationer og definerer derefter
|
|
|
|
Dette er de to variable logiske funktioner. Blandt disse er der nogle tilstrækkeligt interessante til at få et navn.
Eksklusiv adskillelseXOR sandhedstabel | ||
på | b | a b |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Den OR, der hidtil er undersøgt, skal forstås på følgende måde: "den ene eller den anden eller begge dele". Det kaldes også “inklusive ELLER”. Den eksklusive OR (eller XOR for 'e X clusive OR' ) forstås som: "det ene eller det andet, men ikke begge dele".
a XOR bVi kan også definere det med en modulo på en almindelig sum :
Det "eksklusive eller" betegnes undertiden med det aritmetiske tegn ( forskelligt fra ). Funktionelt, det bruger også en + omgivet: .
Ejendom - Enhver sandhedstabel, enhver logisk funktion, kan beskrives ved hjælp af konstant 1 og de to operationer: eksklusiv disjunktion og konjunktion, fordi:og
ÆkvivalensEQV sandhedstabel | ||
på | b | a b |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Den ækvivalens (betegnet ækv eller XNOR) er sandt, hvis de to indgange har samme værdi og falsk ellers. Det er negationen af det "eksklusive eller".
Den ækvivalens kan skrivesÆkvivalens bemærkes ofte af tegnet . Det kan også bemærkes “==” på visse sprog (C, C ++, PHP ...) og “⊙” i elektronik.
InddragelseIMP sandhedstabel | ||
på | b | a b |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Denne handling er ikke kommutativ . a er en tilstrækkelig betingelse for b, hvilket er en nødvendig betingelse for a.
Men
Tegning:
Fra udsagnet ”HVIS jeg bor i (storby) Frankrig, SÅ bor jeg i Europa. » , Vi kan udlede « HVIS jeg ikke bor i Europa, SÅ bor jeg ikke i Frankrig. » Men ikke « HVIS jeg ikke bor i Frankrig, SÅ bor jeg ikke i Europa. » Fordi jeg kan bo i Europa andre steder end i Frankrig uden at modsige den oprindelige erklæring.
HæmningINH sandhedstabel | ||
på | b | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
Hvis a er SAND, er udtrykket SAND, Bortset fra hvis b er SAND.
Denne handling er ikke kommutativ.
Sandhedstabel til at løsne | ||||||||||||||||||||||||||||||||||||||||||
på | b | vs. | d | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 1 | 1 |
Lovlighed Afhentning = (Ringning OG beslutning om at svare) ELLER Beslutning om at ringe oversætter følgende konkrete situation: Vi opfanger en telefon, når vi beslutter at kalde en person, eller når telefonen ringer , og vi beslutter at besvare .
Den består af tre variabler:
variablen d = "Pick up" er en logisk funktion af de 3 foregående og kan skrives d = ab + c
Sandhedstabellen for denne funktion d er så følgende (til højre):
Sandhedstabel af stall2 | ||||||||||||||||||||||||||||||||||||||||||
på | b | vs. | d2 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 1 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 1 | 1 |
Tabellen angiver en absurd situation: Når du beslutter at ringe til nogen, og telefonen ringer uden at du vil svare, vil du alligevel tage op. En modifikation af tabellen som modsat ville rette op på denne absurditet. Denne tabel svarer til en logisk funktion Pick up d2 eller d2, der kan bestemmes og forenkles med .
Fire-variabel logikfunktionEn god elev spekulerer på, om det er klogt at gå ud en nat. Han skal beslutte i henhold til fire variabler:
Denne studerende er i stand til at rejse, hvis:
Det logiske udtryk for at afslutte i henhold til tilstanden for variablerne a, b, c og d kan derfor skrives som følger:Afslut =
En logisk funktion kan bestemmes
Eksempel: I eksemplet med "Pick up2" viser tabellæsningen, at den er lig med når eller eller eller .Dette gør det muligt at definere d2 efter
Det er muligt at finde et udtryk, der minimerer antallet af udtryk og antallet af bogstaver i hvert udtryk. Dette er målet med nogle tekniske som metoden Quine-McCluskey , Karnaugh-diagrammerne , konsensusmetoden , dobbeltpolarisering ...
Eksempel (fortsat): det foregående beløb kan reduceres ved faktorisering af de første to termer med og faktorisering af de sidste to termer med
Logiske udtryk er ofte repræsenteret i datalogi som en træstruktur .
Forskellige undertræer (eller grene) er fastgjort til et første toppunkt (rod). De blindgyde-hjørner kaldes blade.
Hvert indre toppunkt svarer til en "hvis så ellers " boolsk vælger , som reducerer et spørgsmål til to enklere underspørgsmål, muligvis reduceret til 1 / sand eller 0 / falsk.
Evalueringen af en funktion f afhængig af en variabel q valgt til det første spørgsmål er derefter , hvilket fører til to uafhængige udtryk for .
Enten ; vi kan skrive
Træerne afhænger af udtrykket og rækkefølgen af spørgsmålene. For det samme udtryk vil nogle spørgeskemaer være enklere end andre.