Den boolske algebra eller boolske beregningen, er den delen av matematikken som omhandler en tilnærming algebraisk det logiske synet når det gjelder variabler , av operatører og funksjoner på logiske variabler, som tillater bruk av algebraiske teknikker for å håndtere toverdige uttrykk for beregningen proposisjoner . Den ble startet i 1854 av den britiske matematikeren George Boole . I dag finner boolsk algebra mange applikasjoner innen informatikk og design av elektroniske kretser .
Den ble først brukt til telefonomkoblingskretser av Claude Shannon .
Den boolske algebra av logiske funksjoner gjør det mulig å modellere logisk resonnement , ved å uttrykke en "tilstand" som en funksjon av forhold. For eksempel hvis vi studerer uttrykket Kommunikasjon og uttrykket Pick up;
Kommunikasjon = sender OG mottaker
Kommunikasjon vil være "SANT" hvis både avsender- og mottakervariablene var aktive (dette er en logisk funksjon avhengig av avsender- og mottakervariablene )Pick up = (Ringer OG beslutter å svare) ELLER Beslutning om å ringe
Å hente ville være “SANT” enten hvis du hører ringingen samtidig OG du bestemmer deg for å svare , eller ( ELLER ) hvis du bare bestemmer deg for å ringe .Boolsk algebra er et domene som er felles for tre fagområder, og vi møter forskjellige notasjoner for å betegne det samme objektet. I resten av artikkelen vil vi indikere de forskjellige notasjonene, men vi vil ha rett til å opprettholde en viss homogenitet.
Vi kaller B i settet består av to elementer som kalles sannhetsverdier {true, false}. Dette settet er også lagt merke til
med for og for .
Notasjonen vil bli favorisert i det følgende .
På dette settet kan vi definere to binære lover (eller operasjoner), AND og OR-lovene, og en unary operasjon, negasjonen (eller komplementet).
For alle følgende eksempler og egenskaper,
ET lovtabell | ||
b \ a | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Det er definert som følger: a OG b er SANT hvis og bare hvis a er SANT og b er SANT.
Denne loven er også bemerket:
I det følgende vil merkingen “ ” bli favorisert .
Tabellen til denne loven (analog med en tilleggs- eller multiplikasjonstabell ) er ikke en sannhetstabell .
Lovens tabell ELLER | ||
b \ a | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
Det er definert som følger: a ELLER b er SANT hvis og bare hvis a er SANT eller b er SANT. (I særdeleshet, hvis en er sann og b gjelder også, da en OR b er sann).
Denne loven er også bemerket:
Preferanse vil bli gitt i det følgende notasjon , men omsorg vil bli tatt av det faktum at denne loven er ikke den vanlige tillegg i Z / 2 Z . Dette er grunnen til at, i matematikk og i matematisk logikk , ikke notasjonen brukes til å betegne "eller inkluderende": den er reservert for " eller eksklusiv ", en operasjon som (sammenføyet med "og") gjør noen algebra av boolsk en boolsk ring , spesielt en Z / 2 Z - algebra .
Negasjonen av a er SANT hvis og bare hvis a er FALSK.
Negasjonen av a bemerkes:
Notasjonen vil bli favorisert i det følgende .
Vi får da og .
Operatører påvirkes av flere vanlige egenskaper:
I tillegg har hver operatør et nøytralt element og et absorberende element :
Forenklinger er mulig som:
den konsensus teoremet gjelder for operatører av boolsk algebra:
Til slutt følger de prinsippet om komplementaritet:
Vi finner da alle egenskapene som gir B en struktur av boolsk algebra .
PrioritetFor å forenkle skriftene er det vanlig at de boolske operasjonene er underlagt de samme prioritetsreglene som de vanlige aritmetiske operasjonene: AND-funksjonen (logisk multiplikasjon) har altså prioritet over OR-funksjonen (logisk sum). Så:
Det er fortsatt mulig å plassere parenteser i beregningene for å endre rekkefølgen på operasjoner.
De Morgans teorem
De Morgans første lov (disjunksjon negasjon)
uttrykkes av følgende likhet
I begge tilfeller vil uttrykket bare være SANT |
De Morgans andre lov (negasjon av sammenhengen)
I begge tilfeller vil uttrykket bare være FALSK |
Matematisk, en logisk funksjon eller logisk operator er en applikasjon til B n i B .
I elektronikk er en logikkfunksjon en svart boks som mottar et visst antall logiske variabler som inngang og som sender ut en logisk variabel avhengig av inngangsvariablene. Artikkelen logisk funksjon forklarer hvordan du kan lage de svarte boksene på noen grunnleggende funksjoner.
En sannhetstabell gjør det mulig å spesifisere tilstanden til utgangen i henhold til tilstandene til inngangene. Det karakteriserer den logiske funksjonen.
Enhver sannhetstabell, og derfor enhver logisk funksjon, kan beskrives ved hjelp av de tre grunnleggende operasjonene:
Vi viser også at det er nøyaktig logiske funksjoner av parametere. Det er faktisk tilstrekkelig å vurdere alle mulige sannhetstabeller, eller å vurdere utviklingen av en funksjon av parametere.
De kommer fra de tre grunnleggende operasjonene og definerer deretter
|
|
|
|
Dette er de to variable logiske funksjonene. Blant disse er det noen som er tilstrekkelig interessante for å få et navn.
Eksklusiv disjunksjonXOR sannhetstabell | ||
på | b | a b |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
OR studert så langt bør forstås på følgende måte: "den ene eller den andre eller begge deler". Det kalles også “inkluderende ELLER”. Den eksklusive OR (eller XOR for 'e X clusive OR' ) forstås som: "det ene eller det andre, men ikke begge deler".
a XOR bVi kan også definere det med en modulo på en vanlig sum :
Det "eksklusive eller" er noen ganger betegnet med det aritmetiske tegnet ( forskjellig fra ). Funksjonelt, bruker den også en + omringet: .
Eiendom - Enhver sannhetstabell, hvilken som helst logisk funksjon, kan beskrives ved hjelp av konstant 1 og de to operasjonene: eksklusiv adskillelse og konjunktion, fordi:, og
LikestillingEQV-sannhetstabell | ||
på | b | a b |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Den ekvivalens (betegnet ekv eller XNOR) er sann hvis to innganger har samme verdi og falsk ellers. Det er negasjonen av det "eksklusive eller".
Den likeverdighet kan skrivesLikhet er ofte merket av tegnet . Det kan også noteres “==” på visse språk (C, C ++, PHP ...) og “⊙” i elektronikk.
InvolveringIMP-sannhetstabell | ||
på | b | a b |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Denne operasjonen er ikke kommutativ . a er en tilstrekkelig forutsetning for b, som er en nødvendig forutsetning for a.
Men
Tegning:
Fra uttalelsen “HVIS jeg bor i (storby) Frankrike, SÅ bor jeg i Europa. » , Vi kan utlede « HVIS jeg ikke bor i Europa, så bor jeg ikke i Frankrike. » Men ikke « HVIS jeg ikke bor i Frankrike, så bor jeg ikke i Europa. » Fordi jeg kan bo i Europa andre steder enn i Frankrike, uten å motsette den opprinnelige uttalelsen.
InhiberingINH sannhetstabell | ||
på | b | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
Hvis a er SANT, er uttrykket SANT, Bortsett fra hvis b er SANT.
Denne operasjonen er ikke kommutativ.
Sannhetstabell for å hekte av | ||||||||||||||||||||||||||||||||||||||||||
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 |
Lovlighet Pick up = (Ringer OG beslutter å svare) ELLER Beslutning om å ringe oversetter følgende praktiske situasjon: Vi tar opp en telefon når vi bestemmer oss for å ringe noen eller når telefonen ringer og vi bestemmer oss for å svare .
Den består av tre variabler:
variabelen d = "Pick up" er en logisk funksjon av de tre foregående og kan skrives d = ab + c
Sannhetstabellen til denne funksjonen d er da følgende (til høyre):
Sannhetstabellen til 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 indikerer en absurd situasjon: når du bestemmer deg for å ringe noen og telefonen ringer uten at du vil svare, vil du ta opp uansett. En modifisering av tabellen som motsatt vil rette opp denne absurditeten. Denne tabellen tilsvarer en logisk funksjon Pick up d2 eller d2 som kan bestemmes og forenkles med .
Fire-variabel logikkfunksjonEn god student lurer på om det er lurt å gå ut en natt. Han må bestemme i henhold til fire variabler:
Denne studenten vil kunne dra hvis:
Det logiske uttrykket for å avslutte i henhold til tilstanden til variablene a, b, c og d kan derfor skrives som følger:Avslutt =
En logisk funksjon kan bestemmes
Eksempel: I eksemplet med "Pick up2", tabellen lest viser som tilsvarer når eller eller eller .Dette gjør det mulig å definere d2 etter
Det er mulig å finne et uttrykk som minimerer antall ord og antall bokstaver i hvert begrep. Dette er målet for noen tekniske som metoden Quine-McCluskey , Karnaugh-diagrammer , konsensusmetoden , dobbel polarisering ...
Eksempel (fortsettelse): den forrige summen kan reduseres ved faktorisering av de to første begrepene med og faktorisering av de to siste begrepene med
Logiske uttrykk blir ofte representert i informatikk som en trestruktur .
Ulike undertrær (eller grener) er festet til et første toppunkt (rot). Uendelige hjørner kalles blader.
Hvert indre toppunkt tilsvarer en "hvis da ellers " boolsk velger , som reduserer et spørsmål til to enklere underspørsmål, muligens redusert til 1 / sant eller 0 / usant.
Evalueringen av en funksjon f avhengig av en variabel q valgt for det første spørsmålet er da , noe som fører til to uavhengige uttrykk for .
Enten ; vi kan skrive
Trærne avhenger av uttrykk og rekkefølge på spørsmålene. For det samme uttrykket vil noen spørreskjemaer være enklere enn andre.