- Istorie
- Structura
- Aplicații
- postulate
- Suma (+)
- Produs (.)
- Opus (NU)
- teoreme
- Regula zero și unitate
- Puteri egale sau idempotență
- complementarea
- Involuție sau negare dublă
- comutabil
- Asociativ
- distributiv
- Legile absorbției
- Teorema lui Morgan
- Dualitate
- Harta Karnaugh
- Exemple
- Simplificați funcția logică
- Simplificați funcția logică la cea mai simplă formă
- Referințe
Algebra Boolean sau algebra booleană este notație algebrică folosită pentru tratarea variabilelor binare. Acoperă studiile oricărei variabile care are doar 2 rezultate posibile, complementare și care se exclud reciproc. De exemplu, variabilele a căror singură posibilitate este adevărată sau falsă, corectă sau incorectă, pornită sau oprită stau la baza studiului algebrei booleane.
Algebra booleană constituie baza electronică digitală, ceea ce o face destul de prezentă astăzi. Este guvernată de conceptul de porți logice, în care operațiunile cunoscute din algebra tradițională sunt afectate în special.
Sursa: pexels.com
Istorie
Algebra booleană a fost introdusă în 1854 de matematicianul englez George Boole (1815 - 1864), care era un savant autodidact al vremii. Preocuparea sa a apărut dintr-o dispută existentă î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, interpretării Nimic și, respectiv, Univers.
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 booleane au fost publicate în cartea „O investigație a legilor gândirii pe care se bazează teoriile matematice ale logicii și probabilității”.
Acest titlu curios ar fi rezumat mai târziu ca „Legile gândirii” („Legile gândirii”). Titlul s-a ridicat la faimă datorită atenției imediate pe care a primit-o din partea comunității matematice a vremii.
În 1948, Claude Shannon a aplicat-o la proiectarea circuitelor electrice de comutare bistabile. Aceasta a servit ca o introducere în aplicarea algebrei booleane în cadrul întregii scheme electronice-digitale.
Structura
Valorile elementare din acest tip de algebră sunt 0 și 1, care corespund FALSE, respectiv ADEVĂRAT. Operațiile fundamentale în algebra booleană sunt 3:
- funcționare ȘI conjuncție. Reprezentat de o perioadă (.). Sinonim al produsului.
- Operare SAU disjuncție. Reprezentat printr-o cruce (+). Sinonim al sumei.
- NU funcționează sau neagă. Reprezentat prin prefixul NOT (NU A). Este, de asemenea, cunoscut sub numele de complement.
Dacă într-un set A 2 legi de compoziție internă sunt definite notate ca produs și sumă (. +), Se spune că triplul (A. +) Este o algebră booleană dacă și numai dacă triplul menționat îndeplinește condiția de a fi o grătară distributiv.
Pentru a defini o grilă distributivă, trebuie îndeplinite condițiile de distribuție între operațiunile date:
. este distributiv în raport cu 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 setul A trebuie să fie binare, astfel încât să aibă valori de univers sau de vid.
Aplicații
Principalul său scenariu de aplicație este ramura digitală, unde servește la structurarea circuitelor care alcătuiesc operațiile logice implicate. Arta simplității circuitului în favoarea optimizării proceselor este rezultatul aplicării și practicii corecte a algebrei booleane.
De la elaborarea de panouri electrice, trecând prin transmisia de date, până la atingerea programării în diferite limbaje, putem găsi frecvent algebra booleană în toate tipurile de aplicații digitale.
Variabilele booleane sunt foarte frecvente în structura programării. În funcție de limbajul de programare utilizat, vor fi operațiuni structurale în codul care utilizează aceste variabile. Condiționalele și argumentele fiecărei limbi admit variabile booleane pentru a defini procesele.
postulate
Există teoreme care guvernează legile logice structurale ale algebrei booleane. În același mod, există postulate pentru a cunoaște rezultatele posibile în diferite combinații de variabile binare, în funcție de operația efectuată.
Suma (+)
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
unu . 0 = 0
unu . 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 omologii lor din algebra convențională. Acest lucru se datorează domeniului variabilelor. De exemplu, adăugarea de elemente universale în algebra booleană (1 + 1) nu poate da rezultatul convențional al 2, deoarece nu aparține elementelor setului binar.
teoreme
Regula 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
unu . A = A
Puteri egale sau idempotență
Operațiunile între variabile egale sunt definite ca:
A + A = A
LA . A = A
complementarea
Orice operație între o variabilă și complementul acesteia este definită ca:
A + NU A = 1
LA . NU A = 0
Involuție sau negare dublă
Orice dubla negație va fi considerată ca variabilă naturală.
NOT (NOT A) = A
comutabil
A + B = B + A; Commutativitatea sumei.
LA . B = B. LA ; Commutativitatea produsului.
Asociativ
A + (B + C) = (A + B) + C = A + B + C; Asociativitatea sumei.
LA . (B. C) = (A. B). C = A. B. C; Asociativitatea produsului.
distributiv
A + (B. C) = (A + B). (A + C); Distributivitatea sumei față de produs.
LA . (B + C) = (A. B) + (A + C); Distributivitatea produsului în raport cu suma.
Legile absorbției
Există multe legi de absorbție printre mai multe referințe, unele dintre cele mai cunoscute sunt:
LA . (A + B) = A
LA . (NU A + B) = A. B
NU A (A + B) = NU A. B
(A + B). (A + NU B) = A
A + A. B = A
A + NU A. B = A + B
NU A + A. B = NU A + B
LA . B + A. NU B = A
Teorema lui Morgan
Sunt legi de transformare, care gestionează perechi de variabile care interacționează între operațiunile definite ale algebrei booleane (+.).
NU (A. B) = NU A + NU B
NU (A + B) = NU A. NU B
A + B = NU (NU A + NU B)
LA . B = NU (NU A. NU B)
Dualitate
Toate postulatele și teoremele au facultatea dualității. Aceasta implică faptul că prin schimbarea variabilelor și operațiilor, propunerea rezultată este verificată. Adică atunci când se schimbă 0 pentru 1 și AND pentru OR sau invers; este creată o expresie care va fi, de asemenea, complet valabilă.
De exemplu, dacă se ia postulatul
unu . 0 = 0
Și dualitatea este aplicată
0 + 1 = 1
Se obține un alt postulat perfect valid.
Harta Karnaugh
Harta Karnaugh este o diagramă folosită în algebra booleană pentru a simplifica funcțiile logice. Constă dintr-un aranjament bidimensional similar cu tabelele de adevăr ale logicii propoziționale. Datele din tabelele de adevăr pot fi capturate direct pe harta Karnaugh.
Harta Karnaugh poate găzdui procese de până la 6 variabile. Pentru funcțiile cu un număr mai mare de variabile, se recomandă utilizarea de software pentru a simplifica procesul.
Propus în 1953 de Maurice Karnaugh, a fost constituit ca un instrument fix în domeniul algebrei booleane, deoarece implementarea sa sincronizează potențialul uman cu nevoia de a simplifica expresiile booleane, un aspect cheie în fluiditatea proceselor digitale.
Exemple
Algebra booleană este utilizată pentru a reduce porțile logice într-un circuit, unde prioritatea este de a aduce complexitatea sau nivelul circuitului la cea mai mică expresie posibilă. Acest lucru se datorează întârzierii de calcul pe care o presupune fiecare poartă.
În exemplul următor vom observa simplificarea unei expresii logice la expresia ei minimă, folosind teoremele și postulatele algebrei booleane.
NU (AB + A + B). NU (A + NU B)
NU. NU (A + NU B); Factorizarea A cu un factor comun.
NU. 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). ;
Prin teorema lui Morgan NU (A + B) = NU A. NU B
(NU A. NU B). (NU A. B); Prin teorema dublei negații NU (NU A) = A
NU A. NU B. NU A. B; Gruparea algebrică.
NU A. NU A. NU B. B; Commutativitatea produsului A. B = B. LA
NU A. NU B. B; După teorema A. A = A
NU A. 0; După teorema A. NU A = 0
0; După teorema A. 0 = 0
LA . B. C + NU A + A. NU B. C
LA . C. (B + NU B) + NU A; Factoring (A. C) cu un factor comun.
LA . C. (1) + NU A; Prin teorema A + NU A = 1
LA . C + NU A; Prin regula teoremei zero și a unității 1. A = A
NU A + C ; Prin legea lui Morgan A + NU A. B = A + B
Pentru această soluție, legea lui Morgan trebuie 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 + NU A. NU se reduce la expresia sa minimă
NU A. NU B. (NU C + C) + NU A. NU C; Factoring (NU A. NU B) cu factor comun
NU A. NU B. (1) + NU A. NU C; Prin teorema A + NU A = 1
(NU A. NU B) + (NU A. NU C); Prin regula teoremei zero și a unității 1. A = A
NU A (NU B + NU C); Factoring NU este un factor comun
NU A. NU (B.C); Conform legilor Morgan NU (A. B) = NU A + NU B
NU 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 cea mai simplă formă
(A. NU B. C + A. NU B. B. D + NU A. NU B). C
(A. NU B. C + A. 0. D + NU A. NU B). C; După teorema A. NU A = 0
(A. NU B. C + 0 + NU A. NU B). C; După teorema A. 0 = 0
(A. NU B. C + NU A. NU B). C; Prin teorema A + 0 = A
LA . NU B. C. C + NU A. NU B. C; Prin distribuția produsului în raport cu suma
LA . NU B. C + NU A. NU B. C; După teorema A. A = A
NU B. C (A + NU A) ; Factoring (NU B. C) cu factor comun
NU B. C (1); Prin teorema A + NU A = 1
NU B. C; Prin regula teoremei zero și a unității 1. A = A
Referințe
- Algebra booleană și aplicațiile sale J. Eldon Whitesitt. Editura Continental, 1980.
- Matematică și Inginerie în Informatică. Christopher J. Van Wyk. Institutul de Științe și Tehnologie Calculatoare Biroul Național de Standarde. Washington, DC 20234
- Matematică pentru informatică. Eric Lehman. Google Inc.
F Thomson Leighton Departamentul de Matematică și Laborator de Informatică și AI, Institutul de Tehnologie Massachussetts; Akamai Technologies. - Elemente de analiză abstractă. Dr. Mícheál O'Searcoid. Departamentul de matematică. Colegiul universitar Dublin, Beldfield, Dublind.
- Introducere în logică și în metodologia științelor deductive. Alfred Tarski, New York Oxford. Presa Universitatii Oxford.