algebra booleană

Algebra booleană ( de asemenea , numit algebra booleană sau booleene zăbrele), în matematică și matematică logica , este ramura de algebra în care variabilele își poate asuma doar adevărate și false valori ( valori de adevar ), în general , notate respectiv ca 1 și 0.

fundal

Conceput în 1847 la University College Cork de George Boole în cartea sa Analiza matematică a logicii de a scrie logica propozitiilor în formă algebrică și dezvoltat de el în 1854 într - o investigație a legilor de gândire, algebra Boole a fost fundamental în domeniul digital , electronica , în cazul în care în proiectarea de circuite electronice teoremelor dedusă din axiomele care stau la baza algebra sunt de o mare importanță, cum ar fi teorema Shannon din 1940 care arată cum să se descompună un complex boolean funcție în funcții mai simple, sau pentru a obține o expresie canonică dintr - o adevăr de masă . Algebra booleană joacă un rol de o importanță fundamentală în informatică , atât de mult , astfel încât fiecare modernă limbaj de programare definește operatorii logici în cadrul acestuia; este , de asemenea , utilizat în setul teorie și probabilitate .

Descriere

Operațiunile fundamentale nu sunt afară și scădere , dar operatorii logici : conjuncția sau produsul logic indicat cu ∧ sau AND ; disjunctia sau suma logică indicată cu ∨ sau OR ; negarea sau complementării indicate cu ¬ sau NU . Cu acest formalism putem descrie relațiile logice într - un mod similar cu ceea ce face algebra obișnuită cu relațiile numerice: combinația de AND, OR și NU permite să dezvolte orice funcție booleană și , prin urmare , cei trei operatori logici formează un set complet funcțional.

Definiție formală

Matematic, algebra booleană este orice latice înzestrat cu proprietăți, cum ar fi distributivitate, existența minime și maxime și existența complementului: algebra booleană este cryptomorphic , adică asociată biunivocally și în așa fel încât să fie logic echivalentă unei parțial ordonate reticulară ansamblu . Pe de altă parte, fiecare algebra booleană se dovedește a fi cryptomorphic la un anumit tip de inel, numit un inel boolean . Structura poate fi specificată prin grupuri și inele sau prin structuri cristaline într - un mod complet echivalent.

Mai precis, vorbim despre boolean algebra referire la un set K pe care operațiunile sumei logice (+, OR) și produs logic (*, SI) sunt definite, adică o triplă $(K,+,*)$ ${\ Displaystyle (K, +, *)}$ $(K, +, *)$ , Care constituie o rețea în care proprietatea distributiv, existența minime și maxime și existența complementul sunt de asemenea îndeplinite.

În detaliu, avem o algebră booleană când su $(K,+,*)$ ${\ Displaystyle (K, +, *)}$ $(K, +, *)$ următoarele proprietăți sunt îndeplinite:

comutabil: $a+b=b+a\qquad a*b=b*a$ ${\ Displaystyle a + b = b + a \ prototipurilor a * b = b * a}$ $a + b = b + a \ prototipurilor a * b = b * o$

Asociativ: $a+(b+c)=(a+b)+c\qquad a*(b*c)=(a*b)*c$ ${\ Displaystyle a + (b + c) = (a + b) + c \ prototipurilor a * (b * c) = (a * b) * c}$ $a + (b + c) = (a + b) + c \ prototipurilor a * (b * c) = (a * b) * c$

Absorbţie: $a+(a*b)=a\qquad a*(a+b)=a$ ${\ Displaystyle a + (a b *) = a \ prototipurilor a * (a + b) = a}$ $a + (a b *) = a \ prototipurilor a * (a + b) = a$

Distributiv: $a*(b+c)=(a*b)+(a*c)\qquad a+(b*c)=(a+b)*(a+c)$ ${\ Displaystyle a * (b + c) = (a * b) + (a c *) \ prototipurilor a + (b * c) = (a + b) * (a + c)}$ $a * (b + c) = (a * b) + (a c *) \ prototipurilor a + (b * c) = (a + b) * (a + c)$

Idempotence

a+a=a\qquad a*a=a

{\ Displaystyle a + a = a \ prototipurilor a * a = a}

a + a = o \ prototipurilor a * a = a

Existența minimă și maximă: $a*0=0\qquad a+1=1$ ${\ Displaystyle a * 0 = 0 \ prototipurilor a + 1 = 1}$ $a * 0 = 0 \ prototipurilor a + 1 = 1$

existența complementul: $a*{\overline {a}}=0\qquad a+{\overline {a}}=1$ ${\ Displaystyle a * {\ overline {a}} = 0 \ prototipurilor a + {\ overline {a}} = 1}$ ${\ Displaystyle a * {\ overline {a}} = 0 \ prototipurilor a + {\ overline {a}} = 1}$

Modul în care sunt listate proprietățile dorește să evidențieze simetria care există între cei doi operatori, care este apoi la originea legii dualității și a altor proprietăți foarte importante. În listarea axiomele, complementul a fost indicată cu o cratimă pe variabila (care este typographically dificil de realizat, chiar dacă acesta este cel mai bun notația); complementul poate fi, de asemenea, indicat cu un „!“ (semn de exclamare) , înainte de variabila boolean (notația tipică de programare în C și C ++), cu un slash înainte de variabila sau chiar cu semnul minus înainte de a fi , atunci când aceasta nu este o notație echivocă. Complementul corespunde operației logice NU.

O observație finală se referă la faptul că primele 4 proprietăți se referă la structuri cristaline în general, iar cele rămase sunt tipice boolean algebra, deci care va fi indicat cu sextuple $(K,+,*,!,0,1)$ ${\ Displaystyle (K, +, *,!, 0,1)}$ ${\ Displaystyle (K, +, *,!, 0,1)}$ . Având în vedere formularea generală, din acest moment ne referim la algebra primordială, pe care o consideră $K=\{0,1\}$ ${\ K displaystyle = \ {0,1 \}}$ ${\ K displaystyle = \ {0,1 \}}$ , Adică, setul pe care se bazează boolean algebra este compusă numai din minime și maxime.

Legea dualitatii și unele proprietăți ce derivă din axiomele acum observate cu dovezile relative sunt acum listate; Pe lângă aceste consecințe, există două teoreme importante ale boolean algebra care sunt teoremele De Morgan și teorema Shannon . Teoremele că Demonstrăm acum sunt valabile pentru orice „parte a realității“ care satisface axiomele acestei algebra abstractă și, în special, vor fi aplicabile în algebra de seturi , în algebra logicii propozițiilor și în algebra circuite.

Legea dualitatii

Din orice identitate booleană alta poate fi tras de dualitate , adică, prin înlocuirea fiecărui operator și elemente de 0 și 1 cu dual respectiv: dualul + este *, dual de la 0 este 1 (dovada acestui fapt este următorul paragraf ), dualul a este , în general! a (a negată, NU a).

Datorită acestei legi, putem vedea modul în care cele 14 postulatele dată pentru a defini algebra booleană nu sunt independente unele de altele: în special, vom vedea că PX și PX „(pentru X = 1, ..., 7) sunt una dual al celuilalt.

Complemente de 0 și 1

0 și 1 sunt complementare între ele: să dovedim acest lucru, trebuie doar să verificați definiția complementului, adică,

a*{\overline {a}}=0\qquad a+{\overline {a}}=1

{\ Displaystyle a * {\ overline {a}} = 0 \ prototipurilor a + {\ overline {a}} = 1}

o * \ overline a = 0 \ prototipurilor a + \ overline a = 1

Vezi imediat asta

1*0=0\qquad 1+0=1

{\ Displaystyle 1 * 0 = 0 \ prototipurilor 1 + 0 = 1}

{\ Displaystyle 1 * 0 = 0 \ prototipurilor 1 + 0 = 1}

prin aplicarea, respectiv proprietățile minime și cea maximă și teorema declarat acum se dovedește astfel.

Menționăm că, din cauza modului în care această algebră este structurată, această dovadă ne - a permis să demonstreze pornind de la axiomele că elementul neutru există și este unic (prin urmare , existența nu este postulat și unicitatea este inerentă existenței fiind doar 2 valori el lucrează cu, ceea ce nu este valabil și pentru alte tipuri de algebră și alte structuri algebrice).

Convoluţie

Prin negarea același element de două ori, obținem același element (logica aristotelica: o dublă corespunde negare la o declarație).

Pentru a demonstra acest lucru, este suficient să se ia în considerare axioma existenței complementul considerate pe două elemente a și b = A!:

a*{\overline {a}}=0\qquad a+{\overline {a}}=1

{\ Displaystyle a * {\ overline {a}} = 0 \ prototipurilor a + {\ overline {a}} = 1}

o * \ overline a = 0 \ prototipurilor a + \ overline a = 1

b*{\overline {b}}={\overline {a}}*!{\overline {a}}=0\qquad b+{\overline {b}}={\overline {a}}+!{\overline {a}}=1

{\ Displaystyle b * {\ overline {b}} = {\ overline {a}} *! {\ Overline {a}} = 0 \ prototipurilor b + {\ overline {b}} = {\ overline {a}} +! {\ overline {a}} = 1}

b * \ overline b = \ overline o *! \ overline a = 0 \ prototipurilor b + \ overline b = \ overline un +! \ overline a = 1

Deoarece proprietatea comutativă este valabilă și deoarece complementul există unic, se poate deduce cu ușurință că $!{\overline {a}}=a$ ${\ Displaystyle! {\ Overline {a}}} = a$ $! \ Overline a = a$ , Care este ceea ce au vrut să dovedească.

elemente neutre

0 este elementul neutru al sumei (disjuncție logică, ∨, OR) și 1 este elementul neutru al produsului (conjuncție logică, ∧, SI).

Pentru demonstrație, este suficient pentru a exploata proprietatea, datorită absorbției la care deducem că:

a+(a*0)=a\qquad a*(a+1)=a

{\ Displaystyle a + (a * 0) = a \ prototipurilor a * (a + 1) = a}

a + (a * 0) = o \ prototipurilor a * (a + 1) = a

Acum, exploatarea proprietatea maximă și minimă pentru care o * 0 = 0 și a + 1 = 1, este ușor de dedus că:

a+0=a\qquad a*1=a

{\ Displaystyle a + 0 = o \ prototipurilor a * 1 = a}

a + 0 = o \ prototipurilor a * 1 = a

care este ceea ce trebuia să fie afișate.

Absorbția complement ( a doua teorema de absorbție)

Absorbția complementul spune că

a+{\overline {a}}*b=a+b

{\ Displaystyle a + {\ overline {a}} * b = a + b}

a + \ overline a * b = a + b

Pentru a demonstra acest lucru, este suficient să se aplice proprietatea distributiv conform căreia:

a+{\overline {a}}*b=(a+{\overline {a}})*(a+b)

{\ Displaystyle a + {\ overline {a}} * b = (a + {\ overline {a}}) * (a + b)}

a + \ overline a * b = (a + \ overline a) * (a + b)

apoi, menționând că un +! a = 1, iar 1 este elementul neutru al produsului logic, teorema este demonstrată.

Prin legea dualității este , de asemenea înțeles că există o teoremă dublă la ceea ce va fi:

{\overline {a}}*(a+{\overline {b}})={\overline {a}}*{\overline {b}}

{\ Displaystyle {\ overline {a}} * (a + {\ overline {b}}) = {\ overline {a}} * {\ overline {b}}}

\ Overline a * (a + \ overline b) = \ overline o * \ overline b

Această teoremă poate fi luată ca fiind adevărată prin acceptarea validității legii dualității, sau se poate demonstra într-un mod destul de similar cu cel anterior. Se observă că, în scris , expresia dublă, prioritatea de aplicare a operațiunilor trebuiau să fie respectate și , prin urmare, între paranteze un +! B a doua expresie sunt necesare.

Teorema singur element

De sine $x+y=a$ ${\ Displaystyle x + y = a}$ $x + y = a$ Și $xy=0$ ${\ Displaystyle xy = 0}$ $xy = 0$ , Atunci y este unic (sau chiar x este unic , pentru că noi vedem că, din moment ce proprietatea comutativă este valabilă, rolul lui x și y în expresii este același lucru).

Pentru dovada, se presupune în mod absurd că există două valori distincte y și z care satisfac cele două expresii, și anume

x+y=x+z=a\qquad xy=xz=0

{\ Displaystyle x + y = x + z = o \ prototipurilor xy = xz = 0}

x + y = x + z = o \ prototipurilor xy = xz = 0

De asemenea, fiind faptul că

xy=x{\overline {x}}+xy=x({\overline {x}}+y)\qquad xz={\overline {x}}x+xz=x({\overline {x}}+z)

{\ Displaystyle xy = x {\ overline {x}} + xy = x ({\ overline {x}} + y) \ prototipurilor xz = {\ overline {x}} x + xz = x ({\ overline {x }} + z)}

xy = x \ overline x + xy = x (\ overline x + y) \ prototipurilor xz = \ overline xx + xz = x (\ overline x + z)

aceasta a fost obținută

xy=xz=0\Rightarrow x({\overline {x}}+y)=x({\overline {x}}+z)\Rightarrow {\overline {x}}+y={\overline {x}}+z

{\ Displaystyle xy = xz = 0 \ rightarrow x ({\ overline {x}} + y) = x ({\ overline {x}} + z) \ rightarrow {\ overline {x}} + y = {\ overline {x}} + z}

xy = xz = 0 \ rightarrow x (\ overline x + y) = x (\ overline x + z) \ rightarrow \ overline x + y = \ overline x + z

În ultima etapă, principiul echivalenței egalități a fost exploatată și x nu a fost simplificat, care nu a fost dovedită și nu poate fi dovedită în această algebră. Deci, ceea ce ai acum este că

x+y=x+z\qquad {\overline {x}}+y={\overline {x}}+z

{\ Displaystyle x + y = x + z \ prototipurilor {\ overline {x}} + y = {\ overline {x}} + z}

x + y = x + z \ prototipurilor \ overline x + y = \ overline x + z

Înmulțind membru de membru și utilizând proprietatea distributiv, avem:

(x+y)*({\overline {x}}+y)=x{\overline {x}}+xy+{\overline {x}}y+y=0+(x+{\overline {x}})y+y=y=(x+z)*({\overline {x}}+z)=z

{\ Displaystyle (x + y) * ({\ overline {x}} + y) = x {\ overline {x}} + xy + {\ overline {x}} y + y = 0 + (x + {\ overline {x}}) y + y = = y (x + z) * ({\ overline {x}} + z) = z}

(X + y) * (\ overline x + y) = x \ overline x + xy + \ overline xy + y = 0 + (x + \ overline x) y + y = = y (x + z) * (\ overline x + z) = z

adică y = z și, prin urmare, elementul care îndeplinește cele două relații scrise mai sus este unic.

Principiul de eliminare

Așa cum am menționat mai devreme, în Boolean Algebra principiile de eliminare nu sunt valabile, adică, nu este valabil faptul că:

x+y=x+z\Rightarrow y=z\qquad xy=xz\Rightarrow y=z

{\ Displaystyle x + y = x + z \ rightarrow y = z \ prototipurilor xy = xz \ rightarrow y = z}

x + y = x + z \ rightarrow y = z \ prototipurilor xy = xz \ rightarrow y = z

Este adevărat că y = z numai dacă aceste două expresii scrise acum se mențin simultan.

Singurul lucru care poate fi spus în schimb, dacă numai prima expresie susține că:

x+y=x+z\Rightarrow {\overline {x}}y={\overline {x}}z

{\ Displaystyle x + y = x + z \ rightarrow {\ overline {x}} y = {\ overline {x}} z}

x + y = x + z \ rightarrow \ overline xy = \ overline xz

Funcții booleene

Același subiect în detaliu: funcția booleană .

Algebra booleană este tratamentul universal a două state algebra și modelele acestei teorii, numită algebre Boolean. Se ocupă algebra universală cu studierea familia de operații pe un set, numit setul fundamental al familiei algebrice și, în cazul boolean structura algebrică , acest lucru conține doar valorile 0 și 1. În practică, boolean algebre afacere cu tratamentul funcțiilor booleene ale căror principale noțiuni sunt acum mentionate: studiul acestor funcții este fundamentală astăzi pentru studiul circuitelor și rețele logice, prin urmare , scopurile lor practice , pot fi văzute imediat, dar importanța acestor structuri algebrice nu este limitat numai la acest lucru , deoarece este , de asemenea , fundamentală în studiul de propuneri și seturi, care sunt argumente un pic mai abstracte , dar la fel de valabile și importante.

Numărul de argumente care necesită o operație definită pe setul fundamental este numit arity (un plus, de exemplu, este o operație de aritate 2, de asemenea , numit o operație binară): o operație pe {0,1} de aritate n can trebuie aplicat pentru fiecare din cele 2 valori posibile pentru ⁿ argumentele sale ( de exemplu , este suficient să se calculeze dispozițiile 2 elemente de pe n locuri), de exemplu , dacă avem o operație de aritate 3, având în vedere că K = {0 , 1}, posibilele argumente sunt 000.001.010.011.100.101.110.111 care sunt 8.

Pentru fiecare alegere de argumente operațiunea poate produce doar rezultatele 0 și 1 și pentru aceasta există 2 ^{2 ⁿ} operațiuni de n argumente: Prin urmare , acest număr corespunde numărului total de funcții posibile de n variabile în boolean algebra.

Algebra bistatală are 2 operații fără argumente (2 ^{2 ⁰⁾} , care returnează valorile 0 și 1 fără a examina argumente, și 4 operațiuni cu un singur argument (2 ^{2 ^1):} există două operații posibile (2 ¹ ), identitatea și negația și , prin urmare , total operațiunile sunt 4 după cum urmează 0 → 0 (id.), 0 → 1 (Neg.), 1 → 0 (Neg.), 1 → 1 (id.). Apoi , există 16 operații binare , 256 operații ternare, 65,536 operații cuaternare și așa mai departe.

Deoarece algebra el vorbește despre se bazează pe un set finit, o funcție poate fi reprezentată ca și în formă algebrică (adică compoziția AND, OR și NOT), sub formă de tabel, adică cu un tabel în care fiecare componență a „intrare“ variabile (folosind o terminologie mai informatic) de ieșire (sau chiar ieșirile) corespunde: toate funcțiile, inclusiv cele ale altor algebre, poate teoretic fi reprezentat de tabele , dar în cazul în care setul pe care se bazează algebră este infinit (de exemplu, setul de numere reale) nu este un mod convenabil de a studia funcția; pentru boolean algebra, folosind tabele este o modalitate utilă de a studia funcțiile și, de exemplu, permite cu ușurință construirea de circuite și rețele logice în aplicații electronice. Un exemplu de tabele are în vedere operații binare pe care le-am văzut deja să fie de 16:

LA	B.	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	F11	f12	F13	F14	F15
0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

O familie , de asemenea , numit indicele, este indexat de un set de indicatori , care , în cazul unei familii de operațiuni care constituie o algebră sunt numite simboluri de operare și constituie limbajul algebrei în cauză. Operațiunea indexat de un anumit simbol se numește interpretarea acestui simbol, și fiecare simbol definește numărul unic de argumente ale interpretărilor sale posibile respective. În cazul considerat există o corespondență unu-la-unu între simbol și interpretare. Algebra booleană are atâtea simboluri sunt posibile operații numite simboluri de operare Boolean, chiar dacă puține operațiuni au simboluri convenționale, cum ar fi! pentru negație, + pentru colaborare și * pentru disjuncție. În general, ⁿ f _{i este} i-lea simbol al n argumente. In ultimul exemplu considerat, în schimb, un simbol este dată pentru fiecare dintre cele 16 funcții posibile sau este posibil de asemenea să-și exprime fiecare funcție ca o combinație adecvată a simbolurilor convenționale fundamentale, adică, AND (*), OR (+) si nu (!).

funcţia dublă

Având o funcție $f(x_{1},x_{2},\dots ,x_{n})$ ${\ F displaystyle (X_ {1}, X_ {2}, \ dots, X_ {n})}$ $f (X_ {1}, X_ {2}, \ dots, X_ {n})$ în orice formă se numește o funcție dublă de $f$ ${\ displaystyle f}$ $f$ și este indicat cu $\delta f$ ${\ Displaystyle \ delta f}$ $\ Delta f$ o funcție care are forma dublă de $f$ ${\ displaystyle f}$ $f$ , de exemplu:

y={\overline {a}}+b*(c+0)\qquad duale=a*({\overline {b}}+{\overline {c}}*1)

{\ Y displaystyle = {\ overline {a}} + b * (c + 0) \ prototipurilor dublu = a * ({\ overline {b}} + {\ overline {c}} * 1)}

{\ Y displaystyle = {\ overline {a}} + b * (c + 0) \ prototipurilor dublu = a * ({\ overline {b}} + {\ overline {c}} * 1)}

Forma dublă trebuie să respecte prioritatea aplicării funcționării formularului de pornire, pentru acest motiv, în cazul în care nu au existat între paranteze , deoarece și primează asupra RUP, atunci când și devine SAU și sau devine și, poate exista o au nevoie de paranteze.

O altă observație foarte importantă este faptul că variabilele, și nu constantele 0 și 1, pot, de asemenea, nu poate fi negata, deoarece, în orice caz, variabila trebuie să își asume toate valorile posibile și, prin urmare, dacă există negație sau nu, funcția nu se schimbă : în cazul văzut mai sus , atunci funcția dublă poate fi scrisă

duale={\overline {a}}*(b+c*1)

{\ = Dublă displaystyle {\ overline {a}} * (b + c * 1)}

dublu = \ overline a * (b + c * 1)

în cazul în care observăm că constanta a fost negată. Această observație poate fi important la proiectarea unei rețele logice, deoarece înseamnă economisire NU porți, sau chiar, în general, în expresia algebrică este întotdeauna util să aibă mai puține operații de făcut.

Bazele

Un set complet funcțional este un set de operații a căror compoziție permite obținerea tuturor operațiunilor care fac parte din algebra și uneori acestea sunt menționate cu baza termenul, utilizat într - un sens diferit decât bazele spatiilor vectoriale . Cele trei baze principale utilizate în boolean algebra sunt:

Zăbrele , o bază logică introdusă în secolul al 19 - lea de către George Boole , Charles Sanders Peirce și alți matematicieni care au căutat o formalizare algebrică a proceselor logice.
Inelul Boolean , o (non-aritmetică) bază introdusă în secolul 20 de către Ivan Ivanovic Žegalkin și Marshall Piatra care vine de la algebra abstractă .
NAND baza, provenind din faptul că , prin operațiunea NAND, este posibil să se obțină toate operațiunile de pe setul {0,1}. Această bază este utilizată în special în configurația circuitelor logice în electronica digitală .

Elementele comune zăbrele și inel sunt constantele 0 și 1 și o operație binară asociativă și comutativă, care în baza grilajului se numește întâlnire, din termenul întâlni limba engleză și notate între două elemente x și y prin simbolul x ∧ y, în timp ce în baza inelului se numește înmulțire și xy denotat. Baza grilajului are de asemenea operațiile algebrice de unire x ∨ y și complement ¬ x, în timp ce baza a inelului are suplimentar (non-aritmetică) operație plus x ⊕ y sau x + y.

Reticul

In baza grilajului unei algebrei booleene (A, $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ , $\vee$ ${\ displaystyle \ vee}$ $\ vee$ ) Asociază un set parțial ordonate (A, $\leq$ ${\ displaystyle \ leq}$ $\ leq$ ), Definind:

$a\leq b\Leftrightarrow a=a\wedge b$ ${\ Displaystyle a \ leq b \ Leftrightarrow a = a \ pană b}$ $a \ leq b \ Leftrightarrow a = a \ pană b$

care este, de asemenea, echivalentă cu

b=a\vee b

{\ Displaystyle b = a \ vee b}

b = a \ vee b

De asemenea , este posibil să se asocieze o algebra booleana cu un grilaj distributiv (A, $\leq$ ${\ displaystyle \ leq}$ $\ leq$ ), Considerat ca un set parțial ordonat, cu un element minim 0 și un element de maxim 1, în care fiecare element x are un complementar $\neg x$ ${\ Displaystyle \ Neg x}$ $\ Neg x$ astfel încât

x\wedge \neg x=0

{\ Displaystyle x \ wedge \ Neg x = 0}

x \ wedge \ Neg x = 0

Și

x\vee \neg x=1

{\ Displaystyle x \ vee \ Neg x = 1}

x \ vee \ Neg x = 1

Aici $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ Și $\vee$ ${\ displaystyle \ vee}$ $\ vee$ sunt utilizate pentru a desemna inf și sup a două elemente. Dacă există complementele, atunci ele sunt unice.

Inel

Baza inel algebrei booleene generic (A, $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ , $\vee$ ${\ displaystyle \ vee}$ $\ vee$ ) Este definit ca (A, +, *), definind a + b: = (a $\wedge \neg$ ${\ Displaystyle \ wedge \ Neg}$ $\ Pană \ NEG$ b) $\vee$ ${\ displaystyle \ vee}$ $\ vee$ (b $\wedge \neg$ ${\ Displaystyle \ wedge \ Neg}$ $\ Pană \ NEG$ a). In acest inel elementul neutru coincide cu suma de 0 algebrei booleene, în timp ce elementul neutru al înmulțirii este 1 element al algebrei booleene. Acest inel are proprietatea că * a = o pentru fiecare o în A; inele cu această proprietate sunt numite inele boolean .

Pe de altă parte , având în vedere un inel A Boolean, acesta poate fi transformat într - o algebrei booleene prin definirea x $\vee$ ${\ displaystyle \ vee}$ $\ vee$ y = x + y - x $\cdot$ ${\ displaystyle \ cdot}$ $\ cdot$ y și x $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ y = x $\cdot$ ${\ displaystyle \ cdot}$ $\ cdot$ y. Din moment ce aceste două operații sunt inversul reciproc, se poate spune că fiecare inel boolean este cryptomorphic de o algebră booleană și vice-versa. Mai mult, o funcție f: A $\rightarrow$ ${\ displaystyle \ rightarrow}$ $\ sageata dreapta$ B este un morfism între algebre booleene dacă și numai dacă este un morfism între inele Boolean. Categoria de inele Boolean și algebre booleene sunt echivalente.

Un inel ideal de boolean algebra A este un subset I astfel încât pentru fiecare x, y în I avem x $\vee$ ${\ displaystyle \ vee}$ $\ vee$ y în I și pentru fiecare o într - un A $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ x în I. Această noțiune de coincide ideali cu noțiunea de inel ideală în inele Boolean. Un ideal I A se numește prim dacă $\neq$ ${\ displaystyle \ neq}$ $\ neq$ A și în cazul în care un $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ b în I implică întotdeauna o în I sau b în I. Un ideal I A se spune că este maximal dacă $\neq$ ${\ displaystyle \ neq}$ $\ neq$ A și dacă idealul propriu - zis doar ce conține I este un sine. Această notație coincide cu notația teoretică a primului idealul și idealul maximal în inelul Boolean A.

Dualul un ideal este un filtru. Un filtru din boolean algebra A este un subset F astfel încât pentru fiecare x, y în F avem x $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ y în F și pentru fiecare o în A dacă $\vee$ ${\ displaystyle \ vee}$ $\ vee$ x = a , atunci a este în F.

Complementarea Prin urmare , operațiunea * aplicat la subseturi trimite idealurile în filtre și vice - versa: dacă B este o algebră booleană și $I\subseteq B$ ${\ Displaystyle I \ subseteq B}$ $I \ subseteq B$ un ideal al lui (propriu), atunci ${\tilde {I}}=\{x^{*}:x\in I\}$ ${\ Displaystyle {\ tilda {I}} = \ {x ^ {*}: x \ în I \}}$ ${\ Tilde I} = \ {x ^ {*}: x \ în I \}$ este (propriu) filtru dublu al I. Dacă în schimb $F\subseteq B$ ${\ Displaystyle F \ subseteq B}$ $F \ subseteq B$ este un filtru (propriu), ${\tilde {F}}=\{x^{*}:x\in F\}$ ${\ Displaystyle {\ tilda {F}} = \ {x ^ {*}: x \ în F \}}$ ${\ Tilde F} = \ {x ^ {*}: x \ în F \}$ (propriu) idealul dublu de F.

accident vascular cerebral Sheffer

Accidentul vascular cerebral de bază Sheffer sau NAND se bazează pe NOT și AND operații , prin care este posibil să se obțină toate operațiunile Boolean. O algebră booleană poate fi definită atât prin faptul că nu și AND și prin faptul că nu și OR, fiind posibil să se definească sau prin intermediul NU și ȘI precum și prin intermediul NOT și OR:

a~AND~b=~NOT~(~NOT~a~OR~~NOT~b)

{\ Displaystyle a ~ I ~ b = ~ NOT ~ (~ NU ~ o ~ OR ~~ NU ~ b)}

a ~ I ~ b = ~ NOT ~ (~ NU ~ o ~ SAU NU ~~ ~ b)

a~OR~b=~NOT~(~NOT~a~AND~~NOT~b)

{\ Displaystyle un ~ OR ~ b = ~ NOT ~ (~ NU ~ o ~ I ~~ NU ~ b)}

o ~ OR ~ b = ~ NOT ~ (~ NU ~ o ~ I ~~ NU ~ b)

Colectarea tuturor subseturi de un anumit set , care este setul de piese sau set de mediu, echipat cu operațiunile de unire , intersecție și complementarea de seturi, care joacă rolul de OR, AND și NOT , respectiv, constituie o algebră booleană .

Mai formal, în cazul în care B este un set format de cel puțin 2 elemente, algebra boolean având B ca suport este structura algebrică constând din B, prin două operații binare pe B, OR și AND , printr - o operațiune unar NU pe B și de la elementul 0 B, care se bucură de următoarele proprietăți:

Simetria de AND: $\forall a,b\in B:a~AND~b=b~AND~a$ ${\ Displaystyle \ forall a, b \ în B: a ~ I ~ b = b ~ I ~ a}$ $\ FORALL a, b \ în B: a ~ I ~ b = b ~ I ~ o$
Simetria de SAU: $\forall a,b\in B:a~OR~b=b~OR~a$ ${\ Displaystyle \ forall a, b \ în B: a ~ OR ~ b = b ~ OR ~ a}$ $\ FORALL a, b \ în B: a ~ OR ~ b = b ~ OR ~ o$
Involuția NOT: $\forall a\in B:NOT(NOT(a))=a$ ${\ Displaystyle \ forall un \ în B: NU (NOT (a)) = a}$ $\ Forall un \ în B: NU (NU (a)) = a$
Legile lui De Morgan : $\forall a,b\in B:NOT(a~OR~b)=NOT(a)~AND~NOT(b)$ ${\ Displaystyle \ forall a, b \ în B: NU (a ~ OR ~ b) = NU (a) ~ I ~ NOT (b)}$ $\ FORALL a, b \ în B: NU (a ~ OR ~ b) NU = (a) ~ I ~ NOT (b)$

Setul B este de asemenea delimitată de mai jos, fiind:

\forall a\in B:a~AND~\mathbf {0} =\mathbf {0} ;~a~OR~\mathbf {0} =a

{\ Displaystyle \ forall un \ în B: a ~ I ~ \ mathbf {0} = \ mathbf {0}; ~ o ~ OR ~ \ mathbf {0} = a}

\ Forall un \ în B: a ~ I ~ {\ mathbf {0}} = {\ mathbf {0}}; ~ o ~ OR ~ {\ mathbf {0}} = a

Elementul 1 este definit ca negației sau complement, de la 0: 1: = NOT (0). De aceea, mulțimea B este mărginită de mai sus, fiind:

\forall a\in B:a~OR~\mathbf {1} =\mathbf {1} ;a~AND~\mathbf {1} =a

{\ Displaystyle \ forall un \ în B: un ~ OR ~ \ mathbf {1} = \ mathbf {1}, a ~ I ~ \ mathbf {1} = a}

\ Forall un \ în B: un ~ OR ~ {\ mathbf {1}} = {\ mathbf {1}}; un ~ I ~ {\ mathbf {1}} = a

și în special

0 AND 1 = 0; 0 OR 1 = 1

De asemenea , definim, ca o operațiune derivată din cele anterioare, exclusiv binar sau operator, notat XOR:

\forall a,b\in B:a~XOR~b:=(a~OR~b)~AND~(NOT(a~AND~b))

{\ Displaystyle \ forall a, b \ în B: a ~ XOR ~ b: = (a ~ OR ~ b) ~ I ~ (NU (a ~ I ~ b))}

\ FORALL a, b \ în B: a ~ XOR ~ b: = (a ~ OR ~ b) ~ I ~ (NU (a ~ I ~ b))

În această algebră a simetrice diferență corespunde operatorului XOR:

\forall a,b\in B:a~XOR~b=b~XOR~a

{\ Displaystyle \ forall a, b \ în B: a ~ XOR ~ b = b ~ XOR ~ a}

\ FORALL a, b \ în B: a ~ XOR ~ b = b ~ XOR ~ o

În electronică, NAND logica poarta este format din n intrări și o ieșire care merge la nivelul 0 numai în cazul în care n intrări merge la nivelul 1. Aceasta corespunde la conexiunea serie de AND poarta și NU poarta .

Operatori booleni

Același subiect în detaliu: Poarta logică .

Am văzut că operatorii de algebra booleană pot fi reprezentate în diferite moduri, dar ele sunt de multe ori scrise pur și simplu ca AND, OR și NU, care este scrierea le folosim acum să vorbim despre operatori boolean. În descrierea circuitelor, NAND (NU SI), NOR (SAU NU), XOR (SAU exclusiv) și XNOR (exclusiv NU SAU) , poate fi de asemenea utilizat.

Diferitele simbologiile pentru a reprezenta operatorii sunt alese în funcție de domeniul în care unul lucrări: matematicieni folosesc de multe ori simbolul + pentru OR, și × sau * pentru AND, ca și în unele privințe acești operatori lucrează într - un mod similar cu adăugarea și multiplicarea. Negația NU este adesea reprezentat printr-o linie trasată deasupra argumentul negației, adică expresia a fi negată. Sau în informatică simbolul | este utilizat sau || pentru RUP, & o && pentru AND, și ~ o! pentru NU (de exemplu, A sau B și C nu este egal cu A | B & ~ C sau A + B * C!). Dacă el se referă la operatori cu simbolurile de adunare și înmulțire și apoi intenționează negația ca și cum ar fi o „exponentiala“, este ușor de reținut ordinea de aplicare a operatorilor: în primul rând negațiile sunt aplicate, atunci ands și apoi RUP.

În proiectarea de circuite electronice, operatorii scurt NAND (AND negata), NOR (SAU negate) și XNOR (XOR negate) sunt de asemenea folosite: acești operatori, cum ar fi XOR, sunt combinații ale celor trei operatori de bază și sunt folosite doar pentru a face notația mai simplă.

Operatori:

NU - simboluri alternative: x, ~, ¬ ,! (în C , C ++ , C # și JavaScript )
ȘI - simboluri alternative: *, $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ , &, && (în C , C ++ , C # și JavaScript ), DAR (atunci când este utilizat în conjuncție cu NOT)
OR - simboluri alternative: +, $\vee$ ${\ displaystyle \ vee}$ $\ vee$ , |, || (în C , C ++ , C # și JavaScript )
XOR simboluri alternative -: ⊕, ${\dot {\lor }}$ ${\ displaystyle {\ dot {\ lor}}}$ ${\ dot {\ lor}}$ , ∨, ^, EOR, Orr
NAND - simbol alternativ: ↑
NOR - simbol alternativ: ↓
XNOR - simbol alternativ: ≡, EQU

valori:

true - simboluri alternative: true, 1, ON, YES (DA), ridicată
false - simboluri alternative: false, 0, OPRIT, NO, redus

În digital electronică un pic 1 este definit ca fiind adevărate, atât în intrare și de ieșire, care durează de obicei valoarea de 5 V , în timp ce un bit 0 este definit ca fiind fals, atât în intrare și de ieșire, care ia valoarea 0 V.

Următoarele sunt cele mai comune și operatorii lor porți logice :

NU

Același subiect în detaliu: Inverter .

Operatorul nu returnează inversul valorii de intrare. O concatenare NU poate fi simplificată, cu un singur NU în cazul în care numărul de repetiții este impar sau cu nici unul în cazul în care numărul de repetiții este chiar. Inoltre la porta logica NOT possiede una sola variabile binaria.

A	NOT A
0	1
1	0

Spesso, al fine di semplificare espressioni complesse, si usano operatori brevi che uniscono l'operazione di NOT ad altre: questi operatori sono NOR (OR + NOT), NAND (AND + NOT), XNOR (XOR + NOT). La negazione, in questi casi, viene applicata dopo il risultato dell'operatore principale (OR, AND, XOR).

Il simbolo di una porta NOT è

Buffer

Buffer è la negazione del risultato dell'operazione NOT; restituisce il valore uguale a quello in entrata. Il Buffer non è un vero e proprio operatore, poiché in realtà non manipola l'informazione che riceve, bensì la lascia passare invariata; il Buffer dunque è semplificabile con un collegamento privo di operatori.

A	Buffer A
0	0
1	1

Il simbolo di una porta Buffer è:

composta da un NOT in serie a un altro NOT.

La ragione per cui si parla di questo "pseudo-operatore" è data da questioni di sincronia dei segnali : quando si tratta di circuiti e reti logiche in modo più approfondito si rende necessario considerare anche il tempo in cui il segnale arriva e l'elemento buffer viene interpretato in questi casi come un ritardo applicato a un certo segnale.

AND

L'operazione AND restituisce come valore 1 se tutti gli elementi hanno valore 1, mentre restituisce 0 in tutti gli altri casi come ad esempio quando una porta è alta mentre le altre sono basse e può essere messa in serie. Tale operazione è anche detta prodotto logico. Di seguito la tabella rappresenta l'operatore AND nel caso di due entrate, ma la definizione data ora è generalizzata a n ingressi:

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

Siccome questa operazione gode della proprietà associativa, è possibile realizzare un'operazione logica AND con un numero di proposizioni arbitrarie concatenando varie AND a due ingressi, per esempio:

$p_{1}\wedge (p_{2}\wedge (p_{3}\wedge p_{4}))$ $p_{1}\wedge (p_{2}\wedge (p_{3}\wedge p_{4}))$ $p_{1}\wedge (p_{2}\wedge (p_{3}\wedge p_{4}))$

Nei circuiti digitali , la porta logica AND è un meccanismo comune per avere un segnale di vero se un certo numero di altri segnali sono tutti veri.

Nella teoria degli insiemi corrisponde all' intersezione .

Il simbolo di una porta AND è:

OR

L'operazione logica OR restituisce 1 se almeno uno degli elementi è 1, mentre restituisce 0 in tutti gli altri casi. Tale operazione è anche detta somma logica. Di seguito la tabella rappresenta l'operatore OR nel caso di due entrate, ma la definizione data ora è generalizzata a n ingressi:

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

Siccome questa operazione gode della proprietà associativa, è possibile realizzare un'operazione logica OR con più ingressi concatenando varie OR a due ingressi, per esempio:

$(p_{1}\vee p_{2})\vee (p_{3}\vee p_{4})$ $(p_{1}\vee p_{2})\vee (p_{3}\vee p_{4})$ $(p_{1}\vee p_{2})\vee (p_{3}\vee p_{4})$

Nei circuiti digitali , la porta logica OR è un meccanismo comune per avere un segnale alto se almeno un segnale è alto e un segnale basso se e solo se tutti i segnali sono bassi.

Nella teoria degli insiemi corrisponde all' unione .

Il simbolo di una porta OR a due ingressi è:

XOR

L'operatore XOR, detto anche EX-OR, OR esclusivo o somma modulo 2 , restituisce 1 se e solo se il numero degli operandi uguali a 1 è dispari , mentre restituisce 0 in tutti gli altri casi. La tabella rappresenta il caso in cui gli operatori siano 2, poi in generale ci si riferisce a questo operatore come operatore di disparità .

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

Nella teoria degli insiemi corrisponde alla differenza simmetrica . Per passare nella forma canonica SP (somma di prodotti) basta applicare la regola:

A⊕B $=A*!B+!A*B$ ${\displaystyle =A*!B+!A*B}$ $=A*!B+!A*B$

dove ⊕ è il simbolo di XOR.

Il simbolo di una porta XOR è:

NAND

L'operatore NAND, la negazione del risultato dell'operazione AND, restituisce 0 se e solo se tutti gli elementi sono 1, mentre restituisce 1 in tutti gli altri casi.

A	B	A NAND B
0	0	1
0	1	1
1	0	1
1	1	0

Il simbolo di una porta NAND è:

La porta NAND è composta da una porta NOT in serie ad una AND.

Utilizzando le leggi di De Morgan , è possibile convertire una porta OR in NAND. Vale, dunque, la seguente relazione: $A\lor B={\overline {{\overline {A}}\land {\overline {B}}}}={\overline {A}}\uparrow {\overline {B}}$ $A\lor B={\overline {{\overline {A}}\land {\overline {B}}}}={\overline {A}}\uparrow {\overline {B}}$ $A\lor B={\overline {{\overline {A}}\land {\overline {B}}}}={\overline {A}}\uparrow {\overline {B}}$

NOR

L'operatore NOR, la negazione del risultato dell'operazione OR, restituisce 1 se e solo se tutti gli elementi sono 0, mentre restituisce 0 in tutti gli altri casi.

A	B	A NOR B
0	0	1
0	1	0
1	0	0
1	1	0

Il simbolo di una porta NOR è:

composta da un NOT in serie a un OR.

Utilizzando le leggi di De Morgan , è possibile convertire una porta AND in NOR. Vale, dunque, la seguente relazione: $A\land B={\overline {{\overline {A}}\lor {\overline {B}}}}={\overline {A}}\downarrow {\overline {B}}$ $A\land B={\overline {{\overline {A}}\lor {\overline {B}}}}={\overline {A}}\downarrow {\overline {B}}$ $A\land B={\overline {{\overline {A}}\lor {\overline {B}}}}={\overline {A}}\downarrow {\overline {B}}$

XNOR

L'operatore XNOR, detto anche EX-NOR o EQU, è la negazione del risultato dell'operazione XOR; nella sua versione a due elementi restituisce 1 se tutti gli elementi sono uguali a 1 oppure se tutti gli elementi sono uguali a 0. Questo operatore viene generalizzato a n ingressi come operatore di parità , cioè è un'operazione che restituisce il valore 1 se il numero di 1 in ingresso è pari .

A	B	A XNOR B
0	0	1
0	1	0
1	0	0
1	1	1

Il simbolo di una porta XNOR è:

composta da un NOT in serie a un XOR.

Algebra dei circuiti

Come hanno mostrato già i primi studi pionieristici di J. Piesch ^[1] , l'Algebra di Boole si presta bene allo studio degli insiemi, delle proposizioni e dei circuiti. Ci si vuole soffermare su come quest'algebra diventa uno strumento per l'analisi e la sintesi delle reti di commutazione (in elettrotecnica il termine viene usato per indicare un cambio d'ordine della chiusura di due o più contatti elettrici, in telecomunicazioni ha un'accezione diversa).

L'algebra booleana consente di descrivere in forma algebrica le funzioni dei circuiti componenti e delle reti, fornendo altresì i metodi per la realizzazione del progetto logico: è stabilita quindi una corrispondenza biunivoca fra espressioni algebriche e reti di commutazione. La corrispondenza è facilmente realizzabile avendo già parlato di Operatori booleani : si parte ad esempio da un'espressione algebrica per realizzare un circuito, basta sostituire a ogni operatore logico la corrispondente porta logica e applicare agli ingressi di queste opportunamente le variabili booleane in gioco; inoltre, avendo visto l'esistenza di porte logiche come ad esempio la XOR, che sono combinazioni degli operatori booleani elementari AND, OR e NOT, è possibile manipolare opportunamente un'espressione algebrica in modo da utilizzare il minor numero possibile di porte nella realizzazione del circuito. Viceversa un circuito può essere espresso da una funzione y=f(x1,x2,...xn) dove y è l'uscita, le x sono le entrate e la funzione f è una combinazione di porte logiche.

Nell'algebra dei circuiti si associa il valore 0 al livello logico basso e il valore 1 al livello logico alto . In una visione semplificata il valore 0 corrisponde nella pratica a una tensione di 0 V mentre il valore 1 corrisponde a 5 V, oppure 3,5 V o addirittura 1,5 V: il motivo per cui si preferisce associare il valore alto a 5 V piuttosto che a 1,5 V è che la tensione nella pratica non è stabile e perciò il valore 0 si può "confondere" con il valore 1 causando una perdita di informazione ; d'altra parte però, una tensione di 1,5 V per indicare il valore alto significa minor dispendio di energia ed è un vantaggio molto significativo.

Volendo approfondire il discorso sui valori logici alto e basso e sulla loro realizzazione pratica, si può dire che, a seconda della tecnologia ci sono diversi range di valori possibili: per esempio, la tecnologia TTL associa il valore logico 0 a una tensione compresa tra 0 V e 0,8 V, tra 0 e 2 V c'è una banda vietata , cioè un insieme di valori che non devono essere assunti, e il valore logico 1 è associato al range di valori 1,5 V - 5 V. Come si è accennato, la tecnologia odierna spinge sull'abbassare la soglia dei 5 V cercando di stabilizzare sempre di più il potenziale.

Esempi

Questa algebra ha applicazioni nella logica , dove 0 è interpretato come "falso", 1 come "vero", $\vee$ $\vee$ $\vee$ è OR , $\wedge$ $\wedge$ $\wedge$ è AND e $\neg$ $\neg$ $\neg$ è NOT . Le espressioni che coinvolgono le variabili e le operazioni booleane rappresentano forme dichiarative; due espressioni possono essere equivalenti utilizzando i suddetti assiomi se e soltanto se le forme dichiarative corrispondenti sono logicamente equivalenti . L'algebra booleana binaria, inoltre, è usata per il disegno di circuiti nell' ingegneria elettronica ; qui 0 e 1 rappresentano le due condizioni differenti di un bit in un circuito digitale , in genere bassa e alta tensione . I circuiti sono descritti da espressioni che contengono delle variabili e due espressioni sono uguali per tutti i valori delle variabili se e soltanto se i circuiti corrispondenti hanno la stessa funzione di trasferimento . Ogni combinazione dei segnali in ingresso in uscita dal componente può essere rappresentata da un'adeguata espressione booleana

L'algebra booleana a due stati è inoltre importante nella teoria generale delle algebre booleane, perché un'equazione che coinvolge parecchie variabili è generalmente vera in ogni algebra booleana se e soltanto se è vera nell'algebra booleana a due stati. Ciò può, per esempio, essere usato per indicare che le seguenti leggi ( teorema del consenso ) sono generalmente valide in ogni algebra booleana:

$(a\vee b)\wedge (\neg a\vee c)\wedge (b\vee c)=(a\vee b)\wedge (\neg a\vee c)$ $(a\vee b)\wedge (\neg a\vee c)\wedge (b\vee c)=(a\vee b)\wedge (\neg a\vee c)$ $(a\vee b)\wedge (\neg a\vee c)\wedge (b\vee c)=(a\vee b)\wedge (\neg a\vee c)$

$(a\wedge b)\vee (\neg a\wedge c)\vee (b\wedge c)=(a\wedge b)\vee (\neg a\wedge c)$ $(a\wedge b)\vee (\neg a\wedge c)\vee (b\wedge c)=(a\wedge b)\vee (\neg a\wedge c)$ $(a\wedge b)\vee (\neg a\wedge c)\vee (b\wedge c)=(a\wedge b)\vee (\neg a\wedge c)$

Il raggruppamento di un generico insieme S , forma un'algebra booleana con le due operazioni $\vee$ $\vee$ $\vee$ = unione e $\wedge$ $\wedge$ $\wedge$ = intersezione . Il più piccolo elemento 0 è l' insieme vuoto e il più grande elemento 1 è l' insieme S stesso.
L' insieme di tutti i sottoinsiemi di un insieme S che sono limitati è un'algebra booleana.
Per ogni numero naturale n , l'insieme di tutti i divisori positivi di n forma un reticolo distributivo se scrive $a\leq b$ $a\leq b$ $a\leq b$ per a divide b . Questo reticolo è un'algebra booleana se e soltanto se per ogni n non vi sono divisori quadrati . Il più piccolo elemento, che in generale si indica con lo 0, in questa algebra booleana è il numero naturale 1; mentre l'elemento che usualmente indica con l'1 in questi insiemi è l'elemento "n".
Altri esempi di algebre booleane sono dati dagli spazi topologici : se X è uno spazio topologico, allora l'insieme di tutti i sottoinsiemi di X che siano aperti o chiusi formano un'algebra booleana con le operazioni $\vee$ $\vee$ $\vee$ = unione e $\wedge$ $\wedge$ $\wedge$ = intersezione .
Se R è un anello arbitrario dove è definito un insieme idempotente tipo:

A = { a in R : a ² = a e a $\cdot$ $\cdot$ $\cdot$ x = x $\cdot$ $\cdot$ $\cdot$ a per ogni x in R }

L'insieme A diventa un'algebra booleana con le operazioni a $\vee$ $\vee$ $\vee$ b = a + b − a $\cdot$ $\cdot$ $\cdot$ b e a $\wedge$ $\wedge$ $\wedge$ b = a $\cdot$ $\cdot$ $\cdot$ b .

Omomorfismi e isomorfismi

Un omomorfismo tra due algebre booleane A e B è una funzione f : A $\rightarrow$ $\rightarrow$ $\rightarrow$ B tale che per ogni a , b in A :

f ( a $\vee$ $\vee$ $\vee$ b ) = f ( a ) $\vee$ $\vee$ $\vee$ f ( b )
f ( a $\wedge$ $\wedge$ $\wedge$ b ) = f ( a ) $\wedge$ $\wedge$ $\wedge$ f ( b )
f (0) = 0
f (1) = 1

Da queste proprietà segue anche f ( $\neg$ $\neg$ $\neg$ a ) = $\neg$ $\neg$ $\neg$ f ( a ) per ogni a in A. Ogni algebra booleana, con la definizione di omomorfismo, forma una categoria . Un isomorfismo da A su B è un omomorfismo da A su B che è biiettivo . L'inverso di un isomorfismo è ancora un isomorfismo, e le due algebre booleane A e B si dicono isomorfe . Dal punto di vista della teoria dell'algebra booleana, due algebre booleane isomorfe non sono distinguibili, ma differiscono soltanto nella notazione dei loro elementi.

Espressioni booleane

All'interno di ciascuna algebra di Boole, dato un insieme di variabili e le operazioni correlate, è possibile definire delle espressioni che vengono ad assumere un determinato valore ottenibile anche sotto forme diverse. Possono esistere cioè delle espressioni che, pur essendo differenti, si rivelino equivalenti. Oltre al fatto che le espressioni booleane assumono una particolare importanza per quanto riguarda il calcolo proposizionale , in cui le variabili sono proposizioni legate tramite congiunzioni, disgiunzioni, negazioni e altre operazioni più complesse, possono esistere moltissime altre espressioni, accomunate sempre dalle proprietà e dagli assiomi booleani, nelle quali si sostituisce spesso l'operazione + (comunemente detta somma) con ∨ e * (comunemente detta prodotto) con ∧ e in cui la complementazione è indicata col simbolo ' .

Per poter presentare nel modo più efficiente un'espressione booleana, la si riduce in somma di prodotti fondamentali o forma normale disgiuntiva . Un prodotto fondamentale è un prodotto in cui ciascuna variabile, o il suo complemento, appaia una sola volta e rigorosamente fuori da parentesi o complementazioni complesse.
Ad esempio, date le variabili x, y, z all'interno di un'algebra di Boole, sono prodotti fondamentali

P(x,y,z) = xy
P(x,y,z) = x'yz'

Mentre non sono prodotti fondamentali

yyz
yy'z
(xy)'

È così possibile avere una somma di prodotti fondamentali, forma in cui ogni espressione può essere ridotta, ma che non è unica. Un esempio è: xy + xz + z'. Nel momento in cui ogni singola variabile, o il suo complemento, siano contenuti in tutti i prodotti fondamentali della forma normale disgiuntiva, si ha allora una somma di prodotti fondamentali completa o forma normale disgiuntiva completa . Tale scrittura è unica, pertanto se due espressioni sono equivalenti avranno la stessa forma normale disgiuntiva completa.

Se si desidera invece che un'espressione sia scritta nel modo più corto possibile, allora la si esprime in somma di implicanti prime o minimali (Minimizzazione di Quine-McQluskey). Un' implicante prima (o minimale) rispetto a un'espressione è un prodotto fondamentale che non altera l'espressione se sommato per intero a essa, cioè restituisce un risultato equivalente a quella iniziale; sommando un prodotto strettamente contenuto nell'implicante, tuttavia, non si ottiene un'equivalenza.
Per individuare tutte le implicanti prime, esistono varie tecniche, tra cui il metodo del consenso , che si basa sull'applicazione ciclica delle proprietà di assorbimento, idempotenza, involuttività e di De Morgan accompagnate a ogni passo dall'opportuna addizione di un consenso. Dati due prodotti fondamentali, se solo e solo se una variabile appare in uno di essi non negata e nell'altro negata si chiama consenso il risultato della moltiplicazione delle restanti variabili. Ad esempio:

dati P = xyz, Q = x'z il consenso sarà C = yzz = yz
dati P = xy' Q= xy il consenso sarà C = xx = x
dati P = xyz e Q = x'yz' non esiste consenso, in quanto due diverse variabili appaiono una volta negate e una volta no.

La somma di implicanti prime è unica, pertanto due espressioni equivalenti avranno la stessa. Nel momento in cui, completando ogni singola implicante prima, l'apporto all'espressione di una o più di esse è inutile in quanto contenuta nelle altre, la si può eliminare ottenendo la più essenziale delle scritture, la forma minimale . Essa, pur essendo comoda, ha l'inconveniente di non essere unica, e dunque di non consentire l'individuazione di equivalenze tra più espressioni.

Rappresentazione delle algebre booleane

Si può dimostrare che ogni reticolo booleano finito è isomorfo al reticolo booleano di tutti i sottoinsiemi di un insieme finito. Di conseguenza, il numero di elementi di ogni reticolo booleano finito ha un sostegno che contiene un numero di elementi uguale a una potenza di 2 .

Marshall Stone ha enunciato il celebre teorema di rappresentazione per le algebre booleane dimostrando che ogni algebra booleana "A" è isomorfa a tutte le algebre booleane aperte-chiuse in un certo spazio topologico compatto non connesso di Hausdorff .

Note

^ ( DE ) H. Piesch, H. Sequenz, Die Österreichischen Wegbereiter der Theorie der Elektrischen Schaltungen (I pionieri austriaci della teoria della commutazione elettrica), Elecktrotechnik & Maschinenbau, Vol. 75, pp. 241-245

Bibliografia

Giuseppe Calabrese, Le basi dell'elettronica - L'algebra di Boole , Milano, Editoriale Delfino, 1973.
Giuseppe Calabrese, L'algebra di Boole. La logica applicata agli automatismi , Milano, Editoriale Delfino, 1974.
( EN ) Steven Givant e Paul Halmos, Introduction to Boolean Algebras , Undergraduate Texts in Mathematics, Springer , 2009, ISBN 978-0-387-40293-2 .
( EN ) George Boole , An Investigation of the Laws of Thought , Prometheus Books, 2003 [1854] , ISBN 978-1-59102-089-9 .
( EN ) Steven Givant e Paul Halmos, Introduction to Boolean Algebras , Undergraduate Texts in Mathematics, Springer , 2009, ISBN 978-0-387-40293-2 .
( EN ) John A. Camara, Electrical and Electronics Reference Manual for the Electrical and Computer PE Exam , Professional Publications Inc., 2010, p. 41, ISBN 978-1-59126-166-7 .

Voci correlate

06-XX , sezione primaria dello schema di classificazione MSC 2000
Algebra di insiemi
Connettivo logico
Diagramma di Venn
Forma canonica
Funzione booleana
Mappa di Karnaugh
Operazione bit a bit
Porta logica
Sistema formale
Sistema numerico binario
Tabella della verità
Teorema dell'assorbimento
Teorema di Shannon
Teoremi di De Morgan
Teoria degli insiemi
Algebra di Robbins

Altri progetti

Wikiversità contiene risorse su algebra di Boole
Wikimedia Commons contiene immagini o altri file su algebra di Boole

Collegamenti esterni

Algebra di Boole , su sapere.it , De Agostini .
( EN ) Algebra di Boole , su Enciclopedia Britannica , Encyclopædia Britannica, Inc.
( EN ) Opere riguardanti Algebra di Boole , su Open Library , Internet Archive .
Introduzione alla logica Booleana ( PDF ), su matematicamente.it .
Panoramica sull'Algebra Booleana ( PDF ), su wwwusers.di.uniroma1.it .
Facoltà di Ingegneria Energetica - Univ. del Sannio - Elementi di Informatica: Algebra di Boole 2008/2009 ( PDF ), su ing.unisannio.it . URL consultato il 13 agosto 2012 (archiviato dall' url originale il 24 dicembre 2012) .
Corso di Laurea a distanza - Fondamenti di Informatica: Algebra di Boole, Operatori Logici, Teoremi Fondamentali ( PDF ), su corsiadistanza.polito.it .
Descrizione dell'algebra booleana su Okpedia , su okpedia.it .

Controllo di autorità	Thesaurus BNCF 17741 · LCCN ( EN ) sh85003429 · GND ( DE ) 4146280-4 · BNF ( FR ) cb119793249 (data) · BNE ( ES ) XX4576349 (data) · NDL ( EN , JA ) 00560863

Portale Elettronica

Portale Informatica

Portale Matematica

[1] ( DE ) H. Piesch, H. Sequenz, Die Österreichischen Wegbereiter der Theorie der Elektrischen Schaltungen (I pionieri austriaci della teoria della commutazione elettrica), Elecktrotechnik & Maschinenbau, Vol. 75, pp. 241-245

[1]

V · D · M Elettronica digitale
Componenti	Circuito combinatorio · Circuito integrato · Porta logica · Circuito sequenziale
Teoria	Segnale discreto · Algebra di Boole · Sintesi logica · Logica computazionale · Logica di ottimizzazione · Architettura dei calcolatori · Elaborazione numerica dei segnali
Progettazione	Register transfer level · Formal equivalence checking · Circuiti sincroni · Circuiti asincroni · Automa a stati finiti
Applicazioni	Hardware · Audio digitale · Fotografia digitale · Video digitale · Letteratura elettronica · Telecomunicazione

LA	B.	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	F11	f12	F13	F14	F15
0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

LA	B.	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	F11	f12	F13	F14	F15
0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

LA	B.	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	F11	f12	F13	F14	F15
0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1