Algebra booleană - Boolean algebra

În matematică și logică matematică , algebra booleană este ramura algebrei în care valorile variabilelor sunt valorile adevărului adevărat și fals , de obicei notate 1 și respectiv 0. În loc de algebră elementară , unde valorile variabilelor sunt numere și operațiile prime sunt adunare și multiplicare, operațiile principale ale algebrei booleene sunt conjuncția ( și ) notată ca ∧, disjuncția ( sau ) notată ca ∨ și negația ( nu ) notat ca ¬. Prin urmare, este un formalism pentru descrierea operațiilor logice , în același mod în care algebra elementară descrie operațiile numerice.

Algebra booleană a fost introdusă de George Boole în prima sa carte The Mathematical Analysis of Logic (1847) și a fost expusă mai pe larg în An Investigation of the Laws of Thought (1854). Conform lui Huntington , termenul „algebră booleană” a fost sugerat pentru prima dată de Sheffer în 1913, deși Charles Sanders Peirce a dat titlul „O algebră booleană cu o constantă” primului capitol din „Cea mai simplă matematică” în 1880. Algebra booleană are a fost fundamental în dezvoltarea electronicii digitale și este prevăzut în toate limbajele de programare moderne . Este, de asemenea, utilizat în teoria și statisticile mulțimilor .

Istorie

Un precursor al boolean algebra a fost Gottfried Wilhelm Leibniz e algebra conceptelor . Algebra de concepte a lui Leibniz este echivalentă deductiv cu algebra booleană a mulțimilor.

Algebra lui Boole a precedat evoluțiile moderne din algebra abstractă și logica matematică ; este însă văzut ca legat de originile ambelor domenii. Într-un cadru abstract, algebra booleană a fost perfecționată la sfârșitul secolului al XIX-lea de Jevons , Schröder , Huntington și alții, până când a ajuns la concepția modernă a unei structuri matematice (abstracte) . De exemplu, observația empirică conform căreia se pot manipula expresii în algebra mulțimilor , prin traducerea lor în expresii în algebra lui Boole, este explicată în termeni moderni spunând că algebra mulțimilor este o algebră booleană (rețineți articolul nedefinit ). De fapt, MH Stone a demonstrat în 1936 că fiecare algebră booleană este izomorfă pentru un câmp de mulțimi .

În anii 1930, în timp ce studia circuitele de comutare , Claude Shannon a observat că se poate aplica regulile algebrei lui Boole în acest cadru și a introdus algebra de comutare ca o modalitate de a analiza și proiecta circuite prin mijloace algebrice în ceea ce privește porțile logice . Shannon avea deja la dispoziție aparatul matematic abstract, astfel el a aruncat algebra de comutare ca algebră booleană cu două elemente . În setările moderne de inginerie a circuitelor, este foarte puțin necesar să se ia în considerare alte algebre booleene, astfel „algebra de comutare” și „algebra booleană” sunt adesea utilizate în mod interschimbabil.

Punerea în aplicare eficientă a funcțiilor booleene este o problemă fundamentală în proiectarea de logica combinationale circuite. Instrumentele moderne de automatizare a proiectării electronice pentru circuitele VLSI se bazează adesea pe o reprezentare eficientă a funcțiilor booleene cunoscute sub numele de diagrame ( ordonate reduse) de decizie binară (BDD) pentru sinteza logică și verificarea formală .

Propozițiile logice care pot fi exprimate în calculul propozițional clasic au o expresie echivalentă în algebra booleană. Astfel, logica booleană este uneori folosită pentru a indica calculul propozițional efectuat în acest mod. Algebra booleană nu este suficientă pentru a capta formule logice folosind cuantificatori , ca cei din logica de ordinul întâi .

Deși dezvoltarea logicii matematice nu a urmat programul lui Boole, legătura dintre algebra și logica sa a fost pusă mai târziu pe un teren ferm în cadrul logicii algebrice , care studiază și sistemele algebrice ale multor alte logici. Problema determinării dacă variabilele unui anumit boolean cu formula (propozițională) pot fi atribuite în așa fel încât să facă formula evalueze la adevărat se numește problema satisfiabilitate Boolean (SAT), și este de o importanță pentru informatică teoretică , fiind prima problemă arătată a fi NP-completă . Modelul de calcul strâns legat , cunoscut sub numele de circuit boolean, leagă complexitatea timpului (a unui algoritm ) de complexitatea circuitului .

Valori

În timp ce expresiile denotă în principal numere în algebră elementară, în algebră booleană, ele denotă valorile adevărului false și adevărate . Aceste valori sunt reprezentate cu biții (sau cifre binare), respectiv 0 și 1. Ele nu se comportă ca numerele întregi 0 și 1, pentru care 1 + 1 = 2 , dar pot fi identificate cu elementele câmpului cu două elemente GF (2) , adică modul aritmetic întreg 2 , pentru care 1 + 1 = 0 . Adunarea și multiplicarea joacă apoi rolurile booleene ale XOR (exclusiv-sau) și ȘI (conjuncție), respectiv, cu disjuncție x ∨ y (inclusiv-sau) definibil ca x + y - xy .

Algebra booleană se ocupă și de funcții care își au valorile în setul {0, 1}. O secvență de biți este frecvent utilizată pentru astfel de funcții. Un alt exemplu comun este subseturi de un set E : la un subset F de E , se poate defini funcția indicator care ia valoarea 1 pe F și 0 în afara F . Cel mai general exemplu sunt elementele unei algebre booleene , toate cele de mai sus fiind instanțe ale acesteia.

Ca și în cazul algebrei elementare, partea pur ecuațională a teoriei poate fi dezvoltată, fără a lua în considerare valorile explicite pentru variabile.

Operațiuni

Operațiuni de bază

Operațiile de bază ale algebrei booleene sunt conjuncția , disjuncția și negația . Aceste operații booleene sunt exprimate cu operatorii binari corespunzători AND , și OR și operatorul unar NU , denumiți în mod colectiv ca operatori booleni .

Operațiile booleene de bază pentru variabilele x și y sunt definite după cum urmează:

Alternativ, valorile lui x ∧ y , x ∨ y și ¬ x pot fi exprimate prin tabelarea valorilor lor cu tabele de adevăr după cum urmează:

Dacă valorile de adevăr 0 și 1 sunt interpretate ca numere întregi, aceste operații pot fi exprimate cu operațiile obișnuite de aritmetică (unde x + y folosește adunarea și xy folosește multiplicarea), sau prin funcțiile minime / maxime:

${\ displaystyle {\ begin {align} x \ wedge y & = xy = \ min (x, y) \\ x \ vee y & = x + y-xy = \ max (x, y) \\\ neg x & = 1 -x \ end {align}}}$

S-ar putea considera că doar negația și una dintre celelalte două operații sunt de bază, datorită următoarelor identități care permit definirea conjuncției în termeni de negație și disjuncție și invers ( legile lui De Morgan ):

${\ displaystyle {\ begin {align} x \ wedge y & = \ neg (\ neg x \ vee \ neg y) \\ x \ vee y & = \ neg (\ neg x \ wedge \ neg y) \ end {align} }}$

Operațiuni secundare

Cele trei operații booleene descrise mai sus sunt denumite de bază, ceea ce înseamnă că pot fi luate ca bază pentru alte operații booleene care pot fi construite din ele prin compoziție, modul în care operațiile sunt combinate sau compuse. Operațiunile compuse din operațiile de bază includ următoarele exemple:

Condițional material :	${\ textstyle x \ rightarrow y = \ neg {x} \ vee y}$
SAU exclusiv ( XOR ):	${\ textstyle x \ oplus y = \ neg (x \ equiv y) = (x \ vee y) \ wedge \ neg (x \ wedge y) = (x \ vee y) \ wedge (\ neg x \ vee \ neg y) = (x \ wedge \ neg y) \ vee (\ neg x \ wedge y)}$
Echivalență logică :	${\ textstyle x \ equiv y = \ neg {(x \ oplus y)} = (x \ wedge y) \ vee (\ neg x \ wedge \ neg y)}$

Aceste definiții dau naștere următoarelor tabele de adevăr, care dau valorile acestor operații pentru toate cele patru intrări posibile.

Operațiuni secundare. tabelul 1

${\ displaystyle x}$	${\ displaystyle y}$	${\ displaystyle x \ rightarrow y}$	${\ displaystyle x \ oplus y}$	${\ displaystyle x \ equiv y}$
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

Condițional material

Prima operație, x  →  y , sau C xy , se numește implicație materială . Dacă x este adevărat, atunci valoarea lui x  →  y este considerată a fi a lui y (de exemplu, dacă x este adevărat și y este fals, atunci x  →  y este, de asemenea, falsă). Dar dacă x este fals, atunci valoarea lui y poate fi ignorată; cu toate acestea, operația trebuie să returneze o anumită valoare booleană și există doar două opțiuni. Deci, prin definiție, x  →  y este adevărat atunci când x este fals. ( logica relevanței sugerează această definiție, vizualizând o implicație cu o premisă falsă ca altceva decât adevărat sau fals.)

SAU exclusiv ( XOR )

A doua operație, x  ⊕  y , sau J xy , se numește exclusivă sau (adesea prescurtată ca XOR) pentru a o deosebi de disjuncție ca fiind tipul inclusiv. Exclude posibilitatea ca ambele x și y să fie adevărate (de exemplu, a se vedea tabelul): dacă ambele sunt adevărate, atunci rezultatul este fals. Definit în termeni de aritmetică este adunarea unde mod 2 este 1 + 1 = 0.

Echivalența logică

A treia operație, complementul exclusiv sau, este echivalența sau egalitatea booleană: x  ≡  y , sau E xy , este adevărată exact când x și y au aceeași valoare. Prin urmare, x  ⊕  y, ca complement al acestuia, poate fi înțeles ca x  ≠  y , fiind adevărat chiar atunci când x și y sunt diferite. Astfel, omologul său în mod aritmetic 2 este x + y . Partea echivalentă a modului aritmetic 2 este x + y + 1.

Având în vedere doi operanzi, fiecare cu două valori posibile, există 2 ² = 4 combinații posibile de intrări. Deoarece fiecare ieșire poate avea două valori posibile, există un total de 2 ⁴ = 16 posibile operații booleene binare . Orice astfel de operație sau funcție (precum și orice funcție booleană cu mai multe intrări) poate fi exprimată cu operațiile de bază de mai sus. Prin urmare, operațiunile de bază sunt complete funcțional .

Legile

O lege a algebrei booleene este o identitate precum x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z între doi termeni booleeni, unde un termen boolean este definit ca o expresie construită din variabile și constantele 0 și 1 folosind operațiile ∧, ∨ și ¬. Conceptul poate fi extins la termeni care implică alte operații booleene cum ar fi ⊕, → și ≡, dar astfel de extensii nu sunt necesare în scopurile în care legile sunt aplicate. Astfel de scopuri includ definiția unei algebre booleene ca orice model al legilor booleene și ca mijloc de derivare a unor noi legi din vechi ca în derivarea lui x ∨ ( y ∧ z ) = x ∨ ( z ∧ y ) din y ∧ z = z ∧ y (așa cum este tratat în § Algebra booleană axiomatizantă ).

Legile monotone

Algebra booleană îndeplinește multe dintre aceleași legi ca și algebra obișnuită atunci când se potrivește ∨ cu adunare și ∧ cu înmulțire. În special următoarele legi sunt comune ambelor tipuri de algebră:

Asociativitatea :${\ displaystyle \ vee}$		${\ displaystyle x \ vee (y \ vee z)}$	${\ displaystyle = (x \ vee y) \ vee z}$
Asociativitatea :${\ displaystyle \ wedge}$		${\ displaystyle x \ wedge (y \ wedge z)}$	${\ displaystyle = (x \ wedge y) \ wedge z}$
Comutativitatea :${\ displaystyle \ vee}$		${\ displaystyle x \ vee y}$	${\ displaystyle = y \ vee x}$
Comutativitatea :${\ displaystyle \ wedge}$		${\ displaystyle x \ wedge y}$	${\ displaystyle = y \ wedge x}$
Distributivitate peste :${\ displaystyle \ wedge}$${\ displaystyle \ vee}$		${\ displaystyle x \ wedge (y \ vee z)}$	${\ displaystyle = (x \ wedge y) \ vee (x \ wedge z)}$
Identitate pentru :${\ displaystyle \ vee}$		${\ displaystyle x \ vee 0}$	${\ displaystyle = x}$
Identitate pentru :${\ displaystyle \ wedge}$		${\ displaystyle x \ wedge 1}$	${\ displaystyle = x}$
Anihilator pentru :${\ displaystyle \ wedge}$		${\ displaystyle x \ wedge 0}$	${\ displaystyle = 0}$

Următoarele legi sunt valabile în algebra booleană, dar nu și în algebra obișnuită:

Anihilator pentru :${\ displaystyle \ vee}$		${\ displaystyle x \ vee 1}$	${\ displaystyle = 1}$
Idempotența :${\ displaystyle \ vee}$		${\ displaystyle x \ vee x}$	${\ displaystyle = x}$
Idempotența :${\ displaystyle \ wedge}$		${\ displaystyle x \ wedge x}$	${\ displaystyle = x}$
Absorbție 1:		${\ displaystyle x \ wedge (x \ vee y)}$	${\ displaystyle = x}$
Absorbție 2:		${\ displaystyle x \ vee (x \ wedge y)}$	${\ displaystyle = x}$
Distributivitate peste : ${\ displaystyle \ vee}$${\ displaystyle \ wedge}$		${\ displaystyle x \ vee (y \ wedge z)}$	${\ displaystyle = (x \ vee y) \ wedge (x \ vee z)}$

Luarea x = 2 în a treia lege de mai sus arată că nu este o lege obișnuită a algebrei, deoarece 2 × 2 = 4 . Restul de cinci legi pot fi falsificate în algebra obișnuită luând toate variabilele la 1. De exemplu, în Legea absorbției 1, partea stângă ar fi 1 (1 + 1) = 2 , în timp ce partea dreaptă ar fi 1 ( si asa mai departe).

Toate legile tratate până acum au fost pentru conjuncție și disjuncție. Aceste operații au proprietatea că modificarea oricărui argument fie lasă ieșirea neschimbată, fie ieșirea se schimbă în același mod cu intrarea. În mod echivalent, schimbarea oricărei variabile de la 0 la 1 nu duce niciodată la ieșirea din 1 la 0. Operațiunile cu această proprietate sunt considerate a fi monotone . Astfel, axiomele de până acum au fost toate pentru logica booleană monotonă. Nonmonotonitatea intră prin complement ¬ după cum urmează.

Legile nonmonotone

Operația de completare este definită de următoarele două legi.

${\ displaystyle {\ begin {align} & {\ text {Complementation 1}} & x \ wedge \ neg x & = 0 \\ & {\ text {Complementation 2}} & x \ vee \ neg x & = 1 \ end {align} }}$

Toate proprietățile negației, inclusiv legile de mai jos, decurg din cele două legi de mai sus.

Atât în ​​algebra obișnuită, cât și în cea booleană, negația funcționează prin schimbul de perechi de elemente, de unde în ambele algebre satisface legea dublei negații (numită și legea involuției)

${\ displaystyle {\ begin {align} & {\ text {Double negation}} & \ neg {(\ neg {x})} & = x \ end {align}}}$

Dar întrucât algebra obișnuită satisface cele două legi

${\ displaystyle {\ begin {align} (- x) (- y) & = xy \\ (- x) + (- y) & = - (x + y) \ end {align}}}$

Algebra booleană satisface legile lui De Morgan :

${\ displaystyle {\ begin {align} & {\ text {De Morgan 1}} & \ neg x \ wedge \ neg y & = \ neg {(x \ vee y)} \\ & {\ text {De Morgan 2} } & \ neg x \ vee \ neg y & = \ neg {(x \ wedge y)} \ end {align}}}$

Completitudine

Legile enumerate mai sus definesc algebra booleană, în sensul că ele implică restul subiectului. Completarea legilor 1 și 2, împreună cu legile monotone, sunt suficiente în acest scop și, prin urmare, pot fi luate ca un posibil set complet de legi sau axiomatizarea algebrei booleene. Fiecare lege a algebrei booleene urmează logic din aceste axiome. Mai mult, algebrele booleene pot fi apoi definite ca modelele acestor axiome așa cum sunt tratate în § algebre booleene .

Pentru a clarifica, scrierea legilor suplimentare ale algebrei booleene nu poate da naștere la consecințe noi ale acestor axiome și nici nu poate exclude niciun model al acestora. În contrast, într-o listă a unora dintre aceleași legi, dar nu toate, ar fi putut exista legi booleene care nu urmau din cele de pe listă și, în plus, ar fi existat modele ale legilor enumerate care nu erau algebre booleene.

Această axiomatizare nu este în niciun caz singura sau chiar neapărat cea mai naturală, dat fiind că nu am acordat atenție dacă unele dintre axiome au urmat de la altele, ci pur și simplu am ales să ne oprim când am observat că avem suficiente legi, tratate în continuare în § Axiomatizarea Algebra booleană . Sau noțiunea intermediară de axiomă poate fi ignorată cu totul prin definirea unei legi booleene direct ca orice tautologie , înțeleasă ca o ecuație care se aplică tuturor valorilor variabilelor sale peste 0 și 1. Toate aceste definiții ale algebrei booleene pot fi dovedite a fi echivalente.

Principiul dualității

Principiu: Dacă {X, R} este un poset , atunci {X, R (invers)} este de asemenea un poset.

Nu există nimic magic în alegerea simbolurilor pentru valorile algebrei booleene. Am putea redenumi 0 și 1 pentru a spune α și β și, atâta timp cât am făcut-o în mod constant pe tot parcursul, ar fi totuși algebră booleană, deși cu unele diferențe cosmetice evidente.

Dar să presupunem că redenumim 0 și 1 la 1 și respectiv 0. Apoi ar fi în continuare algebră booleană și, în plus, ar funcționa pe aceleași valori. Totuși, nu ar fi identic cu algebra noastră booleană inițială, deoarece acum găsim ∨ care se comportă așa cum se făcea ∧ și invers. Deci, există încă câteva diferențe cosmetice care arată că ne-am jucat cu notația, în ciuda faptului că folosim încă 0 și 1.

Dar dacă, pe lângă schimbarea numelor valorilor, schimbăm și numele celor două operații binare, acum nu mai există nici o urmă a ceea ce am făcut. Produsul final nu se distinge complet de ceea ce am început. Am putea observa că coloanele pentru x ∧ y și x ∨ y din tabelele adevărului s-au schimbat de loc, dar acest comutator este imaterial.

Când valorile și operațiunile pot fi asociate într-un mod care lasă tot ceea ce este important neschimbat atunci când toate perechile sunt comutate simultan, numim membrii fiecărei perechi dual între ei. Astfel 0 și 1 sunt duale, iar ∧ și ∨ sunt duale. Dualitatea Principiul , de asemenea , numit De Morgan dualitate , afirmă că algebra booleană este neschimbat , atunci când toate perechile duble sunt interschimbate.

O schimbare pe care nu a trebuit să o facem ca parte a acestui schimb a fost completarea. Spunem că complementul este o operație autoduală . Operația x de identitate sau de nimic (copierea intrării în ieșire) este, de asemenea, autoduală. Un exemplu mai complicat de operație autoduală este ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) . Nu există nicio operație binară autoduală care să depindă de ambele argumente. O compoziție de operații autoduale este o operație autoduală. De exemplu, dacă f ( x , y , z ) = ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) , atunci f ( f ( x , y , z ), x , t ) este un sine -operarea duală a patru argumente x , y , z , t .

Principiul dualității poate fi explicat dintr-o perspectivă a teoriei grupului prin faptul că există exact patru funcții care sunt mapări unu-la-unu ( automorfisme ) ale setului de polinoame booleene înapoi la sine: funcția de identitate, funcția de complement, funcția duală și funcția contradictorie (completată dual). Aceste patru funcții formează un grup sub compoziție funcțională , izomorfă cu patru grupuri Klein , care acționează asupra setului de polinoame booleene. Walter Gottschalk a remarcat că, în consecință, un nume mai adecvat pentru fenomen ar fi principiul (sau pătratul ) quaternalității .

Reprezentări schematice

Diagrame Venn

O diagramă Venn poate fi utilizată ca reprezentare a unei operații booleene utilizând regiuni umbrite suprapuse. Există o regiune pentru fiecare variabilă, toate circulare în exemplele de aici. Interiorul și exteriorul regiunii x corespund valorilor 1 (adevărat) și 0 (fals) pentru variabila x . Umbrirea indică valoarea operației pentru fiecare combinație de regiuni, cu întuneric care indică 1 și lumină 0 (unii autori folosesc convenția opusă).

Cele trei diagrame Venn din figura de mai jos reprezintă conjuncția x ∧ y , disjuncția x ∨ y și complementul ¬ x .

Pentru conjuncție, regiunea din ambele cercuri este umbrită pentru a indica faptul că x ∧ y este 1 când ambele variabile sunt 1. Celelalte regiuni sunt lăsate nesombrate pentru a indica că x ∧ y este 0 pentru celelalte trei combinații.

A doua diagramă reprezintă disjuncția x ∨ y prin umbrirea acelor regiuni care se află în interiorul oricărui cerc sau al ambelor. A treia diagramă reprezintă complementul ¬ x prin umbrirea regiunii care nu se află în interiorul cercului.

Deși nu am arătat diagramele Venn pentru constantele 0 și 1, acestea sunt banale, fiind respectiv o cutie albă și o cutie întunecată, nici una care să conțină un cerc. Cu toate acestea, am putea pune un cerc pentru x în acele casete, caz în care fiecare ar denota o funcție a unui argument, x , care returnează aceeași valoare independent de x , numită funcție constantă. În ceea ce privește rezultatele lor, constantele și funcțiile constante nu pot fi distinse; diferența este că o constantă are argumente, numit zeroary sau nullary operație, în timp ce o funcție constantă ia un argument, pe care îl ignoră, și este o unară operație.

Diagramele Venn sunt utile în vizualizarea legilor. Legile de comutativitate pentru ∧ și ∨ pot fi văzute din simetria diagramelor: o operație binară care nu a fost comutativă nu ar avea o diagramă simetrică, deoarece schimbarea x și y ar avea ca efect reflectarea diagramei pe orizontală și orice eșec al comutativității ar avea apoi apar ca un eșec de simetrie.

Idempotența lui ∧ și ∨ poate fi vizualizată glisând cele două cercuri împreună și observând că zona umbrită devine apoi întregul cerc, atât pentru ∧ cât și pentru ∨.

Pentru a vedea prima lege a absorbției, x ∧ ( x ∨ y ) = x , începeți cu diagrama din mijloc pentru x ∨ y și rețineți că porțiunea zonei umbrite în comun cu cercul x este întreaga cercului x . Pentru a doua lege a absorbției, x ∨ ( x ∧ y ) = x , începeți cu diagrama din stânga pentru x ∧ y și rețineți că umbrirea întregului cerc x are ca rezultat umbrirea doar a cercului x , deoarece umbrirea anterioară era în interior x cerc.

Legea dublei negații poate fi văzută prin completarea umbririi din a treia diagramă pentru ¬ x , care nuanțează cercul x .

Pentru a vizualiza prima lege a lui De Morgan, (¬ x ) ∧ (¬ y ) = ¬ ( x ∨ y ), începeți cu diagrama de mijloc pentru x ∨ y și completați umbrirea acesteia astfel încât doar regiunea din afara ambelor cercuri să fie umbrită, care este ceea ce descrie partea dreaptă a legii. Rezultatul este același ca și cum am umbra acea regiune care este atât în ​​afara cercului x , cât și în afara cercului y , adică conjuncția exteriorului lor, ceea ce descrie partea stângă a legii.

A doua lege a lui De Morgan, (¬ x ) ∨ (¬ y ) = ¬ ( x ∧ y ), funcționează la fel cu cele două diagrame schimbate.

Prima lege complementară, x ∧¬ x = 0, spune că interiorul și exteriorul cercului x nu au suprapunere. A doua lege complementară, x ∨¬ x = 1, spune că totul este fie în interiorul, fie în afara cercului x .

Porți logice digitale

Logica digitală este aplicarea algebrei booleene de 0 și 1 la hardware-ul electronic constând din porți logice conectate pentru a forma o diagramă de circuit . Fiecare poartă implementează o operație booleană și este reprezentată schematic printr-o formă care indică operația. Formele asociate cu porțile pentru conjuncție (porțile AND), disjuncția (porțile OR) și complementul (invertoarele) sunt după cum urmează.

Liniile din stânga fiecărei porți reprezintă fire sau porturi de intrare . Valoarea intrării este reprezentată de o tensiune pe cablu. Pentru așa-numita logică „activ-înalt”, 0 este reprezentat de o tensiune aproape de zero sau „masă”, în timp ce 1 este reprezentat de o tensiune apropiată de tensiunea de alimentare; activ-scăzut inversează acest lucru. Linia din dreapta fiecărei porți reprezintă portul de ieșire, care în mod normal urmează aceleași convenții de tensiune ca și porturile de intrare.

Complementul este implementat cu o poartă invertor. Triunghiul denotă operația care copiază pur și simplu intrarea în ieșire; cercul mic de pe ieșire denotă inversiunea efectivă care completează intrarea. Convenția de a pune un astfel de cerc pe orice port înseamnă că semnalul care trece prin acest port este completat pe parcurs, indiferent dacă este un port de intrare sau de ieșire.

Dualitate Principiul sau legile De Morgan , poate fi înțeleasă ca afirmând că completarea toate cele trei porturi ale unei porți se convertește la o poartă SAU și invers, așa cum se arată în figura 4 de mai jos. Completarea ambelor porturi ale unui invertor lasă însă operațiunea neschimbată.

Mai general, unul poate completa oricare dintre cele opt subseturi ale celor trei porturi ale unei porți AND sau OR. Cele șaisprezece posibilități rezultate dau naștere la doar opt operații booleene, și anume la cele cu un număr impar de 1 în tabelul lor de adevăr. Există opt astfel, deoarece „bit-bit-out” poate fi 0 sau 1 și poate merge în oricare dintre cele patru poziții din tabelul adevărului. Există șaisprezece operații booleene binare, aceasta trebuie să lase opt operații cu un număr par de 1 în tabelele lor de adevăr. Două dintre acestea sunt constantele 0 și 1 (ca operații binare care ignoră ambele intrări); patru sunt operațiile care depind nontrivial de exact una dintre cele două intrări ale acestora, și anume x , y , ¬ x și ¬ y ; iar celelalte două sunt x ⊕ y (XOR) și complementul său x ≡ y .

Algebre booleene

Termenul "algebră" desemnează atât un subiect, și anume subiectul algebrei , cât și un obiect, și anume o structură algebrică . În timp ce cele de mai sus au abordat subiectul algebrei booleene, această secțiune tratează obiecte matematice numite algebre booleene, definite în deplină generalitate ca orice model al legilor booleene. Începem cu un caz special al noțiunii definibile fără referire la legi, și anume algebre concrete booleene, și apoi dăm definiția formală a noțiunii generale.

Algebre booleene din beton

O algebra booleană beton sau domeniu de seturi este orice set nevid de subseturi ale unui anumit set X închise în cadrul operațiunilor stabilite a uniunii , intersecție , și se completează în raport cu X .

(Ca o parte, din punct de vedere istoric, X a trebuit să fie, de asemenea, non-gol pentru a exclude algebra booleană degenerată sau cu un singur element, care este singura excepție de la regula conform căreia toate algebrele booleene îndeplinesc aceleași ecuații, deoarece algebra degenerată satisface fiecare ecuație. Cu toate acestea, această excludere intră în conflict cu definiția pur ecuațională preferată a "algebrei booleene", neexistând nici o modalitate de a exclude algebra cu un singur element folosind doar ecuații - 0 ≠ 1 nu contează, fiind o ecuație negată. Prin urmare, autorii moderni permit degenerarea Algebra booleană și lăsați X să fie gol.)

Exemplul 1. Puterea set 2 ^X din X , care constă din toate subgrupurile de X . Aici X poate fi orice set: gol, finit, infinit sau chiar nenumărat .

Exemplul 2. Setul gol și X . Această algebră cu două elemente arată că o algebră booleană concretă poate fi finită chiar și atunci când constă din subseturi ale unui set infinit. Se poate observa că fiecare domeniu de subseturi de X trebuie să conțină setul gol și X . Prin urmare, nu este posibil un exemplu mai mic, în afară de algebra degenerată obținută luând X ca gol, astfel încât să facă setul gol și X să coincidă.

Exemplul 3. Mulțimea seturilor finite și cofinite de numere întregi, unde o mulțime cofinită este una omițând doar numeroase numere întregi. Aceasta este în mod clar închisă sub complement și este închisă sub unire deoarece uniunea unei mulțimi cofinite cu orice mulțime este cofinită, în timp ce unirea a două mulțimi finite este finită. Intersecția se comportă ca uniunea cu „finite” și „cofinite” schimbate.

Exemplul 4. Pentru un exemplu mai puțin banal al punctului făcut de Exemplul 2, luați în considerare o diagramă Venn formată din n curbe închise partiționând diagrama în 2 ⁿ regiuni și lăsați X să fie setul (infinit) al tuturor punctelor din plan, nu pe orice curbă, dar undeva în diagramă. Interiorul fiecărei regiuni este astfel un subset infinit de X și fiecare punct din X se află exact într-o regiune. Apoi, setul tuturor celor 2 ^{2 n} uniuni posibile de regiuni (inclusiv setul gol obținut ca uniune a setului gol de regiuni și X obținut ca uniune a tuturor celor 2 ⁿ regiuni) este închis sub uniune, intersecție și complement față de X și, prin urmare, formează o algebră booleană concretă. Din nou avem multe subseturi finite ale unui set infinit care formează o algebră booleană concretă, cu Exemplul 2 care apare ca cazul n = 0 fără curbe.

Subseturi ca vectori de biți

Un subset Y al lui X poate fi identificat cu o familie indexată de biți cu setul de indexuri X , bitul indexat cu x ∈ X fiind 1 sau 0 în funcție de x ∈ Y sau nu . (Aceasta este așa-numita noțiune funcțională caracteristică a unui subset.) De exemplu, un cuvânt de computer pe 32 de biți este format din 32 de biți indexați de setul {0,1,2, ..., 31}, cu 0 și 31 indexarea biților de ordine joasă și respectiv înaltă. Pentru un exemplu mai mic, dacă X = { a, b, c } unde a, b, c sunt privite ca poziții de biți în această ordine de la stânga la dreapta, cele opt subseturi {}, { c }, { b }, { b , c }, { a }, { a , c }, { a , b } și { a , b , c } din X pot fi identificați cu vectorii de biți respectivi 000, 001, 010, 011, 100, 101, 110 și 111. Vectorii de biți indexați de setul de numere naturale sunt secvențe infinite de biți, în timp ce cei indexați de reali în intervalul unitar [0,1] sunt împachetați prea dens pentru a putea scrie în mod convențional, dar totuși formează bine - familii indexate definite (imaginați-vă să colorați fiecare punct al intervalului [0,1] fie negru, fie alb independent; punctele negre formează apoi un subset arbitrar de [0,1]).

Din acest punct de vedere al vectorului de biți, o algebră booleană concretă poate fi definită în mod echivalent ca un set non-gol de vectori de biți, toți de aceeași lungime (mai general, indexați de același set) și închise sub operațiile vectorului de biți în biți ∧, ∨ și ¬, ca în 1010∧0110 = 0010, 1010∨0110 = 1110 și ¬1010 = 0101, realizările vectorului de biți ale intersecției, uniunii și respectiv complementului.

Algebra prototipică booleană

Mulțimea {0,1} și operațiile sale booleene, așa cum sunt tratate mai sus, pot fi înțelese ca fiind cazul special al vectorilor de biți cu lungimea unu, care prin identificarea vectorilor de biți cu subseturi pot fi înțelese și ca cele două subseturi ale unui singur element a stabilit. Numim aceasta algebra prototipică booleană, justificată de următoarea observație.

Legile satisfăcute de toate algebrele booleene concrete nedegenerate coincid cu cele satisfăcute de algebra prototipică booleană.

Această observație este ușor dovedită după cum urmează. Cu siguranță, orice lege satisfăcută de toate algebrele booleene concrete este satisfăcută de cea prototipică, deoarece este concretă. Dimpotrivă, orice lege care eșuează pentru o anumită algebră booleană concretă trebuie să fi eșuat la o anumită poziție de bit, caz în care acea poziție oferă în sine un contraexemplu de un bit pentru legea respectivă. Nedegenerarea asigură existența a cel puțin unei poziții de biți, deoarece există un singur vector de biți gol.

Scopul final al secțiunii următoare poate fi înțeles ca eliminarea „concretului” din observația de mai sus. Cu toate acestea, vom atinge acest obiectiv prin observația surprinzător de puternică că, până la izomorfism, toate algebrele booleene sunt concrete.

Algebre booleene: definiția

Algebrele booleene pe care le-am văzut până acum au fost toate concrete, constând din vectori de biți sau echivalent din subseturi ale unor seturi. O astfel de algebră booleană constă dintr-un set și operații pe acel set care pot fi arătate pentru a satisface legile algebrei booleene.

În loc să arătăm că legile booleene sunt îndeplinite, putem în schimb să postulăm o mulțime X , două operații binare pe X și o operație unară și să cerem ca aceste operații să satisfacă legile algebrei booleene. Elementele lui X nu trebuie să fie vectori de biți sau subseturi, ci pot fi orice. Aceasta duce la o definiție abstractă mai generală .

O algebră booleană este orice set cu operații binare ∧ și ∨ și o operație unară ¬ pe aceasta satisfăcând legile booleene.

În sensul acestei definiții, este irelevant modul în care operațiunile au ajuns să satisfacă legile, fie prin fiat, fie prin dovadă. Toate algebrele booleene concrete îndeplinesc legile (mai degrabă prin dovadă decât prin fiat), de unde fiecare algebră booleană concretă este o algebră booleană conform definițiilor noastre. Această definiție axiomatică a unei algebre booleene ca set și anumite operații care îndeplinesc anumite legi sau axiome prin fiat este întru totul analogă definițiilor abstracte de grup , inel , câmp etc. caracteristice algebrei moderne sau abstracte .

Având în vedere orice axiomatizare completă a algebrei booleene, cum ar fi axiomele pentru o rețea distributivă complementară , o condiție suficientă pentru ca o structură algebrică de acest fel să satisfacă toate legile booleene este aceea că îndeplinește doar acele axiome. Următoarea este, prin urmare, o definiție echivalentă.

O algebră booleană este o rețea distributivă complementară.

Secțiunea despre axiomatizare enumeră alte axiomatizări, dintre care oricare poate fi făcută la baza unei definiții echivalente.

Algebre booleene reprezentabile

Deși fiecare algebră booleană concretă este o algebră booleană, nu orice algebră booleană trebuie să fie concretă. Fie n un întreg pozitiv fără pătrat , unul care nu este divizibil cu pătratul unui întreg, de exemplu 30 dar nu 12. Operațiile celui mai mare divizor comun , cel mai mic multiplu comun și împărțirea în n (adică ¬ x = n / x ), se poate arăta că satisface toate legile booleene atunci când argumentele lor variază peste divizorii pozitivi ai lui n . Prin urmare, acești divizori formează o algebră booleană. Acești divizori nu sunt subseturi ale unei mulțimi, făcând divizorii lui n o algebră booleană care nu este concretă conform definițiilor noastre.

Totuși, dacă reprezentăm fiecare divizor al lui n prin mulțimea factorilor săi primiți, vom constata că această algebră booleană neconcretă este izomorfă față de algebra booleană concretă formată din toate seturile de factori primi ai lui n , cu uniunea corespunzătoare celei mai mici comune multiple, intersecția la cel mai mare divizor comun și complement la divizarea în n . Deci acest exemplu, deși nu este concret din punct de vedere tehnic, este cel puțin „moral” concret prin această reprezentare, numită izomorfism . Acest exemplu este o instanță a noțiunii următoare.

O algebră booleană se numește reprezentabilă atunci când este izomorfă pentru o algebră booleană concretă.

La următoarea întrebare evidentă se răspunde pozitiv după cum urmează.

Fiecare algebră booleană este reprezentabilă.

Adică, până la izomorfism, algebrele booleene abstracte și concrete sunt același lucru. Acest rezultat destul de netivial depinde de teorema ideală primară booleană , un principiu de alegere puțin mai slab decât axioma alegerii și este tratată mai detaliat în articolul Teorema reprezentării lui Stone pentru algebrele booleene . Această relație puternică implică un rezultat mai slab, întărind observația din subsecțiunea anterioară la următoarea consecință ușoară a reprezentabilității.

Legile satisfăcute de toate algebrele booleene coincid cu cele satisfăcute de algebra prototipică booleană.

Este mai slab în sensul că nu implică în sine reprezentabilitatea. Algebrele booleene sunt speciale aici, de exemplu o algebră relațională este o algebră booleană cu structură suplimentară, dar nu este cazul ca fiecare relație algebră să fie reprezentabilă în sensul adecvat algebrelor relaționale.

Axiomatizarea algebrei booleene

Definiția de mai sus a unei algebre booleene abstracte ca set și operații care satisfac „legile” booleene ridică întrebarea, care sunt acele legi? Un răspuns simplu este „toate legile booleene”, care pot fi definite ca toate ecuațiile care sunt valabile pentru algebra booleană de 0 și 1. Deoarece există infinit de multe astfel de legi, acesta nu este un răspuns teribil de satisfăcător în practică, ceea ce duce la următoarea întrebare: este suficient să se impună doar numeroase legi?

În cazul algebrelor booleene, răspunsul este da. În special numeroasele ecuații pe care le-am enumerat mai sus sunt suficiente. Spunem că algebra booleană este finit axiomatizabilă sau bazată finit.

Această listă poate fi redusă încă? Din nou, răspunsul este da. Pentru început, unele dintre legile de mai sus sunt implicate de unele dintre celelalte. Un subgrup suficient al legilor de mai sus constă în perechile legilor de asociativitate, comutativitate și absorbție, distributivitatea ∧ peste ∨ (sau cealaltă lege a distributivității - una este suficientă) și cele două legi complementare. De fapt, aceasta este axiomatizarea tradițională a algebrei booleene ca o rețea distributivă complementară .

Prin introducerea unor legi suplimentare care nu sunt enumerate mai sus, devine posibilă scurtarea listei; de exemplu, cu bara verticală reprezentând operația de cursă Sheffer , axioma unică este suficientă pentru axiomatiza complet algebra booleană. De asemenea, este posibil să găsiți axiome unice mai lungi folosind operații mai convenționale; vezi Axiome minime pentru algebra booleană . ${\ displaystyle ((a \ mid b) \ mid c) \ mid (a \ mid ((a \ mid c) \ mid a)) = c}$

Logica propozițională

Logica propozițională este un sistem logic care este intim conectat la algebra booleană. Multe concepte sintactice ale algebrei booleene trec la logica propozițională doar cu modificări minore în notație și terminologie, în timp ce semantica logicii propoziționale este definită prin algebre booleene într-un mod în care tautologiile (teoremele) logicii propoziționale corespund teoremelor ecuaționale ale algebrei booleene .

Sintactic, fiecare termen boolean corespunde unei formule propoziționale a logicii propoziționale. În această traducere între algebra booleană și logica propozițională, variabilele booleene x, y ... devin variabile propoziționale (sau atomi ) P, Q , ..., termenii booleni precum x ∨ y devin formule propoziționale P ∨ Q , 0 devine fals sau ⊥ , și 1 devine adevărată sau T . Este convenabil, atunci când faceți referire la propoziții generice, să utilizați literele grecești Φ, Ψ, ... ca metavariabile (variabile în afara limbajului calculului propozițional, utilizate atunci când se vorbește despre calculul propozițional) pentru a desemna propoziții.

Semantica logicii propoziționale se bazează pe atribuțiile de adevăr . Ideea esențială a atribuirii adevărului este că variabilele propoziționale sunt mapate la elementele unei algebre booleene fixe, iar apoi valoarea de adevăr a unei formule propoziționale care utilizează aceste litere este elementul algebrei booleene care se obține calculând valoarea Termen boolean corespunzător formulei. În semantica clasică, se folosește doar algebra booleană cu două elemente, în timp ce în semantica cu valoare booleană sunt considerate algebre booleene arbitrare. O tautologie este o formulă propozițională căreia i se atribuie valoarea de adevăr 1 prin fiecare atribuire de adevăr a variabilelor sale propoziționale unei algebre booleene arbitrare (sau, în mod echivalent, fiecare atribuire de adevăr către cele două elemente algebră booleană).

Această semantică permite o traducere între tautologiile logicii propoziționale și teoremele ecuaționale ale algebrei booleene. Fiecare tautologie Φ a logicii propoziționale poate fi exprimată ca ecuația booleană Φ = 1, care va fi o teoremă a algebrei booleene. În schimb, fiecare teoremă Φ = Ψ a algebrei booleene corespunde tautologiilor (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) și (Φ∧Ψ) ∨ (¬Φ∧¬Ψ). Dacă → este în limba aceste ultime tautologii pot fi scrise și ca (Φ → Ψ) ∧ (Ψ → Φ), sau ca două teoreme separate Φ → Ψ și Ψ → Φ; dacă ≡ este disponibil atunci se poate utiliza tautologia unică Φ ≡ Ψ.

Aplicații

O aplicație motivantă a calculului propozițional este analiza propozițiilor și argumentelor deductive în limbajul natural. În timp ce propoziția „dacă x = 3 atunci x +1 = 4” depinde de semnificațiile unor simboluri precum + și 1, propoziția „dacă x = 3 atunci x = 3” nu; este adevărat doar în virtutea structurii sale și rămâne adevărat dacă „ x = 3” este înlocuit cu „ x = 4” sau „luna este făcută din brânză verde”. Forma generică sau abstractă a acestei tautologii este „dacă P atunci P ”, sau în limbajul algebrei booleene, „ P → P ”.

Înlocuirea lui P cu x = 3 sau orice altă propoziție se numește instanțierea lui P prin propoziția respectivă. Rezultatul instanțierii P într-o propoziție abstractă se numește o instanță a propoziției. Astfel „ x = 3 → x = 3” este o tautologie în virtutea faptului că este o instanță a tautologiei abstracte „ P → P ”. Toate aparițiile variabilei instanțiate trebuie instanțiate cu aceeași propoziție, pentru a evita prostii precum P → x = 3 sau x = 3 → x = 4.

Calculul propozițional restricționează atenția asupra propozițiilor abstracte, cele construite din variabilele propoziționale utilizând operații booleene. Instanțierea este încă posibilă în cadrul calculului propozițional, dar numai prin instanțierea variabilelor propoziționale prin propoziții abstracte, cum ar fi instanțierea Q cu Q → P în P → ( Q → P ) pentru a obține instanța P → (( Q → P ) → P ).

(Disponibilitatea instanțierii ca parte a mecanismului calculului propozițional evită necesitatea metavariabilelor în limbajul calculului propozițional, deoarece variabilele propoziționale obișnuite pot fi considerate în limbaj pentru a indica propoziții arbitrare. nefiind parte a limbajului calculului propozițional, ci mai degrabă parte a aceluiași limbaj pentru a vorbi despre acesta în care este scrisă această propoziție, unde trebuie să putem distinge variabilele propoziționale și instanțierile lor ca fiind entități sintactice distincte.)

Sisteme deductive pentru logica propozițională

O axiomatizare a calculului propozițional este un set de tautologii numite axiome și una sau mai multe reguli de inferență pentru a produce noi tautologii din vechi. O dovadă într-un sistem de axiome A este o succesiune finită de propoziții, care este fie o instanță a unei axiome a lui A, fie urmată de o regulă a lui A din propozițiile care apar mai devreme în demonstrație (prin care se interzice raționamentul circular). Ultima propoziție este teorema demonstrată de dovadă. Fiecare segment inițial ne vid al unei dovezi este el însuși o dovadă, de unde fiecare propoziție dintr-o dovadă este ea însăși o teoremă. O axiomatizare este solidă atunci când fiecare teoremă este o tautologie și completă atunci când fiecare tautologie este o teoremă.

Calcul succesiv

Calculul propozițional este organizat în mod obișnuit ca un sistem Hilbert , ale cărui operații sunt doar cele ale algebrei booleene și ale căror teoreme sunt tautologii booleene, acei termeni booleni egali cu constanta booleană 1. O altă formă este calculul secvențial , care are două tipuri, propoziții ca în ordinare calcul propozițional și perechi de liste de propoziții numite secvențe , cum ar fi A ∨ B , A ∧ C , ... A , B → C , .... Cele două jumătăți ale unui succesor se numesc antecedent și respectiv succedent. Metavariabilul obișnuit care denotă un antecedent sau o parte a acestuia este Γ și pentru un succesor Δ; astfel Γ, A Δ ar desemna un succes al cărui succesor este o listă Δ și al cărui antecedent este o listă Γ cu o propoziție suplimentară A anexată după aceasta. Antecedentul este interpretat ca conjuncția propozițiilor sale, succedentul ca disjuncție a propozițiilor sale și secvența însăși ca implicarea succesorului de către antecedent. ${\ displaystyle \ vdash}$ ${\ displaystyle \ vdash}$

Îmbunătățirea diferă de implicație prin faptul că, în timp ce aceasta din urmă este o operație binară care returnează o valoare într-o algebră booleană, prima este o relație binară care deține sau nu. În acest sens, implicarea este o formă externă de implicație, adică externă algebrei booleene, gândindu-se la cititorul secvenței ca fiind, de asemenea, externă și interpretează și compară antecedente și succese în unele algebre booleene. Interpretarea naturală a este ca ≤ în ordinea parțială a algebrei booleene definite de x ≤ y tocmai când x ∨ y = y . Această abilitate de a amesteca implicația externă și implicația internă → într-o singură logică se numără printre diferențele esențiale dintre calculul secvențial și calculul propozițional. ${\ displaystyle \ vdash}$${\ displaystyle \ vdash}$

Aplicații

Algebra booleană ca calcul al a două valori este fundamentală pentru circuitele computerizate, programarea computerelor și logica matematică și este, de asemenea, utilizată în alte domenii ale matematicii, cum ar fi teoria mulțimilor și statistica.

Calculatoare

La începutul secolului al XX-lea, mai mulți ingineri electrici au recunoscut intuitiv că algebra booleană era analogă comportamentului anumitor tipuri de circuite electrice. Claude Shannon a dovedit în mod formal că un astfel de comportament era logic echivalent cu algebra booleană în teza sa de master din 1937, O analiză simbolică a circuitelor de releu și de comutare .

Astăzi, toate computerele moderne de uz general își îndeplinesc funcțiile folosind logica booleană cu două valori; adică circuitele lor electrice sunt o manifestare fizică a logicii booleene cu două valori. Acestea realizează acest lucru în diferite moduri: ca tensiuni pe fire în circuite de mare viteză și dispozitive de stocare capacitive, ca orientări ale unui domeniu magnetic în dispozitive de stocare feromagnetice, ca găuri în cartoane perforate sau bandă de hârtie etc. (Unele computere timpurii foloseau circuite sau mecanisme zecimale în loc de circuite logice cu două valori.)

Desigur, este posibil să codați mai mult de două simboluri într-un mediu dat. De exemplu, s-ar putea folosi respectiv 0, 1, 2 și 3 volți pentru a codifica un alfabet cu patru simboluri pe un fir sau găuri de diferite dimensiuni într-o carte perforată. În practică, constrângerile strânse de viteză mare, dimensiuni reduse și putere redusă se combină pentru a face din zgomot un factor major. Acest lucru face dificilă distincția între simboluri atunci când există mai multe simboluri posibile care ar putea apărea pe un singur site. Mai degrabă decât să încerce să facă distincția între patru tensiuni pe un fir, designerii digitali s-au stabilit pe două tensiuni pe fir, mare și mic.

Computerele folosesc circuite booleene cu două valori din motivele de mai sus. Cele mai comune arhitecturi de calculatoare folosesc secvențe de valori booleene, numite biți comandat, de 32 sau 64 de valori, de exemplu 01101000110101100101010101001011. Când programarea în cod mașină , limbaj de asamblare , precum și anumite alte limbaje de programare , programatori lucra cu structura digitală de nivel scăzut lung ale registre de date . Aceste registre funcționează pe tensiuni, unde zero volți reprezintă 0 boolean, iar o tensiune de referință (adesea +5 V, +3,3 V, +1,8 V) reprezintă boolean 1. Astfel de limbaje acceptă atât operații numerice, cât și operații logice. În acest context, „numeric” înseamnă că computerul tratează secvențele de biți ca numere binare (bazează două numere) și execută operații aritmetice precum adunarea, scăderea, înmulțirea sau divizarea. „Logică” se referă la operațiile logice booleene de disjuncție, conjuncție și negație între două secvențe de biți, în care fiecare bit dintr-o secvență este pur și simplu comparat cu omologul său din cealaltă secvență. Prin urmare, programatorii au opțiunea de a lucra și de a aplica regulile fie ale algebrei numerice, fie ale algebrei booleene, după cum este necesar. O caracteristică esențială de diferențiere între aceste familii de operații este existența operațiunii de transport în prima, dar nu în a doua.

Logică cu două valori

Alte domenii în care două valori sunt o alegere bună sunt legea și matematica. În conversațiile relaxate de zi cu zi, sunt acceptate răspunsuri nuanțate sau complexe, cum ar fi „poate” sau „doar în weekend”. În situații mai concentrate, cum ar fi o instanță de judecată sau matematică bazată pe teoreme, totuși se consideră avantajos să formulăm întrebări astfel încât să admitem un răspuns simplu da-sau-nu - este inculpatul vinovat sau nevinovat, propunerea este adevărată sau falsă —Și pentru a interzice orice alt răspuns. Oricât de mare ar fi o cămașă de forță care s-ar putea dovedi în practică pentru respondent, principiul întrebării simple da-nu a devenit o trăsătură centrală atât a logicii judiciare, cât și a logicii matematice, făcând logica cu două valori merită organizarea și studiul în sine.

Un concept central al teoriei mulțimilor este apartenența. Acum, o organizație poate permite mai multe grade de membru, cum ar fi începător, asociat și complet. Cu seturi, totuși, un element este fie în interior, fie în exterior. Candidații la calitatea de membru într-un set funcționează la fel ca firele de pe un computer digital: fiecare candidat este fie membru, fie nemembr, la fel cum fiecare fir este fie ridicat, fie scăzut.

Algebra fiind un instrument fundamental în orice domeniu supus tratamentului matematic, aceste considerații se combină pentru a face algebra a două valori de importanță fundamentală pentru hardware-ul computerului, logica matematică și teoria mulțimilor.

Logica cu două valori poate fi extinsă la logica cu mai multe valori , în special prin înlocuirea domeniului boolean {0, 1} cu intervalul de unitate [0,1], caz în care nu se iau doar valorile 0 sau 1, orice valoare între și inclusiv 0 și 1 poate fi presupus. Algebric, negația (NU) este înlocuită cu 1 -  x , conjuncția (ȘI) este înlocuită cu înmulțirea ( ), iar disjuncția (OR) este definită prin legea lui De Morgan . Interpretarea acestor valori ca valori logice de adevăr dă naștere unei logici cu mai multe valori, care formează baza pentru logica fuzzy și logica probabilistică . În aceste interpretări, o valoare este interpretată ca „gradul” adevărului - în ce măsură o propoziție este adevărată sau probabilitatea ca propoziția să fie adevărată. ${\ displaystyle xy}$

Operații booleene

Aplicația originală pentru operațiile booleene era logica matematică , unde combină valorile adevărului, adevărat sau fals, ale formulelor individuale.

Limbaj natural

Limbile naturale, cum ar fi engleza, au cuvinte pentru mai multe operații booleene, în special conjuncție ( și ), disjuncție ( sau ), negare ( nu ) și implicație ( implică ). Dar nu este sinonim cu și nu . Atunci când sunt folosite pentru a combina afirmații situaționale precum „blocul este pe masă” și „pisicile beau lapte”, care sunt naiv fie adevărate, fie false, semnificațiile acestor conectivități logice au adesea semnificația omologilor lor logici. Cu toate acestea, cu descrieri de comportament precum „Jim a intrat prin ușă”, se începe să observăm diferențe precum eșecul comutativității, de exemplu, conjuncția „Jim a deschis ușa” cu „Jim a intrat prin ușă” în această ordine este nu echivalează cu conjuncția lor în cealaltă ordine, deoarece și înseamnă de obicei și apoi în astfel de cazuri. Întrebările pot fi similare: ordinea „Este cerul albastru și de ce este cerul albastru?” are mai mult sens decât ordinea inversă. Comenzile conjunctive despre comportament sunt ca niște afirmații comportamentale, cum ar fi să te îmbraci și să mergi la școală . Comenzi disjunct astfel de dragoste mă sau lasă - mă sau pește sau tăiate momeală tind să fie asimetrice prin implicația că o alternativă este mai puțin preferabilă. Substantivele conexe, cum ar fi ceaiul și laptele , descriu, în general, agregarea ca fiind asociată în timp ce ceaiul sau laptele este o alegere. Cu toate acestea, contextul poate inversa aceste simțuri, deoarece în alegerile dvs. sunt cafeaua și ceaiul, ceea ce înseamnă de obicei același lucru cu alegerile dvs. sunt cafeaua sau ceaiul (alternative). Negarea dublă ca în „Nu-mi place laptele” înseamnă rareori literalmente „Îmi place laptele”, ci transmite mai degrabă un fel de acoperire, ca și cum ar însemna că există o a treia posibilitate. „Not not P” poate fi interpretat în mod vag ca „cu siguranță P” și, deși P implică în mod necesar „not not P ”, conversația este suspectă în limba engleză, la fel ca și cu logica intuiționistă . Având în vedere utilizarea extrem de idiosincratică a conjuncțiilor în limbile naturale, algebra booleană nu poate fi considerată un cadru de încredere pentru interpretarea lor.

Logica digitală

Operațiile booleene sunt utilizate în logica digitală pentru a combina biții transportați pe fire individuale, interpretându-le astfel peste {0,1}. Când un vector de n porți binare identice este utilizat pentru a combina doi vectori de biți fiecare din n biți, operațiile de biți individuali pot fi înțelese colectiv ca o singură operație pe valori dintr-o algebră booleană cu 2 ⁿ elemente.

Teorie naivă a mulțimilor

Naiv teoria mulțimilor interpretează operații booleene ca acționând pe subseturi ale unui anumit set de X . După cum am văzut mai devreme, acest comportament este paralel cu combinațiile coordonate ale vectorilor de biți, cu unirea a două seturi corespunzătoare disjuncției a doi vectori de biți și așa mai departe.

Plăci video

Algebra booleană gratuită cu 256 de elemente pe trei generatoare este implementată pe afișaje de computer bazate pe grafică raster , care utilizează bit blit pentru a manipula regiuni întregi constând din pixeli , bazându-se pe operațiile booleene pentru a specifica cum ar trebui combinată regiunea sursă cu destinația, de obicei cu ajutorul unei a treia regiuni numită mască . Plăcile video moderne oferă toate cele 2 ^{2 3}  = 256 operații ternare în acest scop, alegerea operației fiind un parametru pe un octet (8 biți). Constantele SRC = 0xaa sau 10101010, DST = 0xcc sau 11001100 și MSK = 0xf0 sau 11110000 permit să se scrie operații booleene precum (SRC ^ DST) și MSK (adică XOR sursa și destinația și apoi ȘI rezultatul cu masca) direct ca o constantă care denotă un octet calculat la momentul compilării, 0x60 în exemplul (SRC ^ DST) și MSK, 0x66 dacă doar SRC ^ DST, etc. într-un mod uniform care necesită un hardware remarcabil de mic și care necesită timp complet independent de complexitatea expresiei.

Modelare și CAD

Sistemele de modelare solidă pentru proiectarea asistată de computer oferă o varietate de metode pentru construirea obiectelor din alte obiecte, combinarea prin operații booleene fiind una dintre ele. În această metodă, spațiul în care există obiecte este înțeles ca un set S de voxeli (analogul tridimensional al pixelilor în grafica bidimensională) și formele sunt definite ca subseturi de S , permițând obiectelor să fie combinate ca seturi prin unire, intersecție etc. O utilizare evidentă este construirea unei forme complexe din forme simple, pur și simplu ca unire a acestora din urmă. O altă utilizare este în sculptură înțeleasă ca îndepărtarea materialului: orice operație de măcinare, frezare, rutare sau găurire care poate fi efectuată cu mașini fizice pe materiale fizice poate fi simulată pe computer cu operația booleană x  ∧ ¬ y sau x  -  y , care în teoria mulțimilor este diferența de mulțime, eliminați elementele lui y din cele ale lui x . Astfel, având în vedere două forme, una care urmează să fie prelucrată, iar cealaltă materialul care trebuie îndepărtat, rezultatul prelucrării primelor pentru îndepărtarea celei din urmă este descris pur și simplu ca diferența setată a acestora.

Căutări booleene

Interogările motoarelor de căutare folosesc, de asemenea, logica booleană. Pentru această aplicație, fiecare pagină web de pe Internet poate fi considerată a fi un „element” al unui „set”. Următoarele exemple utilizează o sintaxă acceptată de Google .

• Citatele duble sunt utilizate pentru a combina cuvinte separate în spațiu alb într-un singur termen de căutare.
• Spațiul alb este utilizat pentru a specifica ȘI logice, deoarece este operatorul implicit pentru alăturarea termenilor de căutare:

"Search term 1" "Search term 2"

• Cuvântul cheie OR este utilizat pentru OR logic:

"Search term 1" OR "Search term 2"

• Un semn minus prefixat este utilizat pentru NU logic:

"Search term 1" −"Search term 2"

Vezi si

Referințe

Surse

• Mano, Morris; Ciletti, Michael D. (2013). Design digital . Pearson. ISBN 978-0-13-277420-8.

Lecturi suplimentare

• J. Eldon Whitesitt (1995). Algebra booleană și aplicațiile sale . Publicații Courier Dover. ISBN 978-0-486-68483-3. Introducere adecvată pentru studenți în domenii aplicate.
• Dwinger, Philip (1971). Introducere în algebrele booleene . Würzburg: Physica Verlag.
• Sikorski, Roman (1969). Algebre booleene (ed. 3 / e). Berlin: Springer-Verlag. ISBN 978-0-387-04469-9.
• Bocheński, Józef Maria (1959). O precizie a logicii matematice . Tradus din edițiile franceză și germană de Otto Bird. Dordrecht, Olanda de Sud: D. Reidel.

Perspectiva istorica

• George Boole (1848). „ Calculul logicii ”, Cambridge and Dublin Mathematical Journal III: 183–98.
• Theodore Hailperin (1986). Logica și probabilitatea lui Boole: o expunere critică din punctul de vedere al algebrei contemporane, logicii și teoriei probabilității (ediția a II-a). Elsevier. ISBN 978-0-444-87952-3.
• Dov M. Gabbay, John Woods, ed. (2004). Ascensiunea logicii moderne: de la Leibniz la Frege . Manual de istorie a logicii. 3 . Elsevier. ISBN 978-0-444-51611-4., mai multe capitole relevante de Hailperin, Valencia și Grattan-Guinness
• Calixto Badesa (2004). Nașterea teoriei modelelor: teorema lui Löwenheim în cadrul teoriei rudelor . Princeton University Press. ISBN 978-0-691-05853-5., capitolul 1, "Algebra claselor și calculul propozițional"
• Burris, Stanley, 2009. The Algebra of Logic Tradition . Enciclopedia Stanford a filosofiei .
• Radomir S. Stankovic; Jaakko Astola (2011). De la logica booleană la circuite de comutare și automate: către tehnologia informațională modernă . Springer. ISBN 978-3-642-11681-0.

linkuri externe

• Capitolul Boolean Algebra din All About Circuits
• Cum funcționează lucrurile - Logică booleană
• Știință și tehnologie - Algebră booleană Arhivat 16-02-2013 la Wayback Machine conține o listă și o dovadă a teoremelor și legilor booleene.