Boala algebra: istorie, teoreme și postulate, exemple
Algebra booleană sau algebra booleană este notația algebrică utilizată pentru tratarea variabilelor binare. Acesta acoperă studiile oricărei variabile care are doar 2 rezultate posibile, complementare și se exclud reciproc. De exemplu, variabilele a căror singură posibilitate este adevărată sau falsă, corectă sau incorectă, pe sau în afara sunt baza studiului algebrei booleene.
Algebra booleană formează baza electronicii digitale, ceea ce o face destul de prezentă în vremurile contemporane. Este guvernat de conceptul de porți logice, unde operațiile cunoscute în algebra tradițională sunt afectate în mod semnificativ.
istorie
Boolean algebra a fost introdusă în 1854 de către matematicianul englez George Boole (1815 - 1864), care a fost un învățat auto-predat al vremii. Preocuparea sa a apărut dintr-o dispută între Augustus De Morgan și William Hamilton, despre parametrii care definesc acest sistem logic.
George Boole a susținut că definiția valorilor numerice 0 și 1 corespunde, în domeniul logicii, cu interpretarea Nimicului și, respectiv, Universului .
Intenția lui George Boole a fost să definească, prin proprietățile algebrei, expresiile logicii propoziționale necesare pentru a face față variabilelor de tip binar.
În 1854, cele mai semnificative secțiuni ale algebrei booleene sunt publicate în cartea " O investigație a legilor gândirii pe care se bazează teoriile matematice ale logicii și ale probabilității".
Acest titlu curios va fi rezumat mai jos sub forma " Legile gândirii" ("Legile gândirii"). Titlul a sărit la faimă din cauza atenției imediate pe care a avut-o din partea comunității matematice a timpului.
În 1948, Claude Shannon a aplicat-o în proiectarea circuitelor de comutare electrică bistabile. Aceasta a servit ca o introducere în aplicarea algebrei booleene în cadrul întregii scheme electronice-digitale.
structură
Valorile elementare ale acestui tip de algebră sunt 0 și 1, care corespund FALSE și respectiv TRUE. Operațiile fundamentale în algebra booleană sunt 3:
- Operațiunea AND sau conjuncție. Reprezentată de o perioadă (.). Sinonim pentru produs
- Operațiune sau disjuncție. Reprezentată de o cruce (+). Sinonimă cu suma.
- Operația NOT sau negarea. Reprezentată de prefixul NOT (NOT A). Este, de asemenea, cunoscut ca un supliment.
Dacă un set A definește 2 legi de compoziție internă, denotată ca produs și sumă (. +), Se spune că tripla (A. +) este o algebră booleană dacă și numai dacă triplea respectivă îndeplinește condiția de a fi reticul distributiv.
Pentru a defini o rețea distributivă, trebuie îndeplinite condițiile de distribuție între operațiunile date:
. este distributivă în ceea ce privește suma + a. (b + c) = (a. b) + (a. c)
+ este distributivă în ceea ce privește produsul. a + (b, c) = (a + b). (a + c)
Elementele care alcătuiesc mulțimea A trebuie să fie binare, având valori universale sau goale.
aplicații
Scenariul său principal de aplicare este ramura digitală, unde servește la structura circuitelor care alcătuiesc operațiile logice implicate. Arta simplității circuitelor în favoarea optimizării proceselor este rezultatul aplicării și practicării corecte a algebrei booleene.
De la dezvoltarea panourilor electrice, prin transmiterea datelor, la programarea în diferite limbi, putem găsi frecvent algebra booleană în toate tipurile de aplicații digitale.
Variabilele booleene sunt foarte frecvente în structura programării. În funcție de limba de programare utilizată, vor exista operațiuni de cod structural care utilizează aceste variabile. Condiționarea și argumentele fiecărei limbaj suportă variabile booleene pentru a defini procesele.
postulate
Există teoreme care guvernează legile structurale logice ale algebrei booleene. În mod similar, există postulate pentru a cunoaște rezultatele posibile în diferite combinații de variabile binare, în funcție de operația efectuată.
Sumă (+)
Operatorul OR al cărui element logic este uniunea (U) este definit pentru variabilele binare după cum urmează:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Produs (.)
Operatorul AND al cărui element logic este intersecția (∩) este definit pentru variabilele binare după cum urmează:
0. 0 = 0
0. 1 = 0
1. 0 = 0
1. 1 = 1
Opusă (nu)
Operatorul NOT al cărui element logic este complementul (X) "este definit pentru variabilele binare după cum urmează:
NU 0 = 1
NU 1 = 0
Multe dintre postulate diferă de echivalentele lor în algebra convențională. Acest lucru se datorează domeniului variabilelor. De exemplu, adăugarea elementelor universale în algebra booleană (1 + 1) nu poate da rezultatul convențional de 2, deoarece nu aparține elementelor setului binar.
teoreme
Regula de zero și unitate
Orice operație simplă care implică un element cu variabilele binare este definită:
0 + A = A
1 + A = 1
0. A = 0
1. A = A
Puteri egale sau idempotencia
Operațiile între variabilele egale sunt definite ca:
A + A = A
A. A = A
complementarea
Fiecare operație între o variabilă și complementul ei este definită ca:
A + NOT A = 1
A. NU A = 0
Involuție sau negare dublă
Orice negare dublă va fi considerată variabilă naturală.
NU (NU A) = A
comutabil
A + B = B + A; Comutativitatea sumei.
A. B = B A; Comutativitatea produsului.
asociativ
A + (B + C) = (A + B) + C = A + B + C; Asociativitatea sumei.
A. (B.C) = (A.B). C = A B. C; Asociativitatea produselor.
distributiv
A + (B.C) = (A + B). (A + C); Distributivitatea sumei în raport cu produsul.
A. (B + C) = (A.B) + (A + C); Distributivitatea produsului în raport cu suma.
Legile de absorbție
Există multe legi de absorbție între multiple
A. (A + B) = A
A. (NU A + B) = A. B
NU A (A + B) = NU A. B
(A + B). (A + NOT B) = A
A + A. B = A
A + NU A. B = A + B
NU A + A. B = NU A + B
A. B + A. NU B = A
Teorema lui Morgan
Acestea sunt legi ale transformării, care gestionează perechi de variabile care interacționează între operațiile definite ale algebrei booleene (+).
NU (A. B) = NU A + NU
NU (A + B) = NU A. NU B
A + B = NU (NU A + NU B)
A. B = NU (NU A. Nu B)
dualitate
Toate postulatele și teoremele au facultatea de dualitate. Aceasta implică faptul că atunci când se schimbă variabilele și operațiunile, propunerea rezultată este verificată. Adică atunci când schimbăm 0 pentru 1 și AND pentru OR sau invers; se creează o expresie care va fi complet valabilă.
De exemplu, dacă luați postulatul
1. 0 = 0
Și dualitatea este aplicată
0 + 1 = 1
Se obține un alt postulat perfect valabil.
Harta lui Karnaugh
Harta Karnaugh este o diagramă folosită în algebra booleană pentru a simplifica funcțiile logice. Este alcătuită dintr-un aranjament bidimensional similar cu tabelele de adevăr ale logicii propoziționale. Datele din tabelele cu adevărat pot fi captate direct pe harta Karnaugh.
Hărțile Karnaugh pot găzdui procese de până la 6 variabile. Pentru funcțiile cu un număr mai mare de variabile, se recomandă utilizarea software-ului pentru a simplifica procesul.
Propusă în 1953 de Maurice Karnaugh, ea a fost stabilită ca un instrument fix în domeniul algebrei booleene, deoarece implementarea sa sincronizează potențialul uman cu necesitatea de a simplifica expresiile booleene, un aspect cheie în fluența proceselor digitale.
Exemple
Algebra booleană este folosită pentru a reduce porțile logice într-un circuit, unde prioritatea este de a aduce complexitatea sau nivelul circuitului la minimul său posibil de exprimare. Acest lucru se datorează întârzierii computaționale pe care o presupune fiecare ușă.
În următorul exemplu vom observa simplificarea unei expresii logice la expresia ei minimă, folosind teoremele și postulate ale algebricii booleene.
NU (AB + A + B). NU (A + NU B)
NU [A (B + 1) + B]. NU (A + NU B); Factorizarea A cu factor comun.
NU [A (1) + B]. NU (A + NU B); Prin teorema A + 1 = 1.
NU (A + B). NU (A + NU B); de Teorema A. 1 = A
(NU A. NU B). [NU A. NU (NU B)];
Prin teorema lui Morgan NOT (A + B) = NU A. NU B
(NU A. NU B). (NU A. B); Prin dublă teoremă negativă NOT (NOT A) = A
NU A. NU B. NU A. B; Gruparea algebrică
NU A. NU A. NU B. B; Comutativitatea produsului A. B = B A
NU A. NU B. B; Prin teorema A. A = A
NU A. 0; Prin teorema A. NU A = 0
0; Prin teorema A. 0 = 0
A. B. C + NOT A + A. NU B. C
A. C. (B + NU B) + NU A; Factoring (A.C) cu factor comun.
A. C. (1) + NU; Prin teorema A + NOT A = 1
A. C + NOT A; De regulă, regulă de zero și unitate 1. A = A
NU A + C ; Prin legea Morgan A + NU A. B = A + B
Pentru această soluție, legea Morgan ar trebui extinsă pentru a defini:
NU (NU A). C + NU A = NU A + C
Deoarece NU (NU A) = A prin involuție.
Simplificați funcția logică
NU A. NU B. NU C + NU A. NU B. C + NOT A. NOT C la expresia minimă
NU A. NU B. (NOT C + C) + NU A. NOT C; Factoring (NOTA A. NOT B) cu factor comun
NU A. NU B. (1) + NU A. NOT C; Prin teorema A + NOT A = 1
(NU A.) NU B) + (NOTA A. NU C); De regulă, regulă de zero și unitate 1. A = A
NU A (NU B + NOT C); Factoring NOTA cu factor comun
NU A. NU (B.C); Prin legile lui Morgan NU (A. B) = NU A + NU B
NU [A + (B. C)] Prin legile lui Morgan NU (A. B) = NU A + NU B
Oricare dintre cele 4 opțiuni cu caractere aldine reprezintă o posibilă soluție pentru a reduce nivelul circuitului
Simplificați funcția logică la expresia minimă a acesteia
(A) NU B, C + A, NU B, B, D + NU A, NU B). C
(A, NU B, C + A, 0, D + NU, NU B). C; Prin teorema A. NU A = 0
(A, NU B, C + 0 + NU A, NU B). C; Prin teorema A. 0 = 0
(A, NU B, C + NU A, NU B). C; Prin teorema A + 0 = A
A. NU B. C. C + NOT A. NU B. C; Prin distributivitatea produsului în raport cu suma
A. NU B. C + NOT A. NU B. C; Prin teorema A. A = A
NU B. C (A + NOT A) ; Factoring (NU B. C) cu factor comun
NU B. C (1); Prin teorema A + NOT A = 1
NU B. C; De regulă, regulă de zero și unitate 1. A = A
