Acasă » Electronică digitala » 07 - Algebra booleană
- Teoremele lui DeMorgan descriu echivalenţă dintre porţile cu intrări inversate şi porţile cu ieşiri inversate
- O poartă ŞI-negat este echivalentă cu o poartă SAU-negativă; O poartă SAU-negat este echivalentă cu o poartă ŞI-negativă
Definiţia teoremelor lui DeMorgan
DeMorgan a dezvoltat o serie de reguli importante în algebra liniară cu privire la complementul de grup. Prin complementul de grup ne referim la complementul unui grup de termeni, şi nu doar complementul unei singure variabile.
Ţineţi minte de la capitolul legat de porţi logice, că inversând toate intrările unei porţi, inversăm şi funcţia logică esenţială a acesteia. O poartă SAU cu toate intrările inversate (o poartă SAU-negativă) se comportă precum o poartă ŞI-negat. O poartă ŞI cu toate intrările inversate (o poartă ŞI-negativă) se comportă precum o poartă SAU-negat. Teoremele lui DeMorgan exprimă aceiaşi echivalenţă în sens invers: inversând ieşirea unei porţi, funcţia rezultată este aceiaşi cu tipul opus de poartă cu intrările inversate:
O bară deasupra termenului AB se comportă precum un simbol de grup. Acest lucru este total diferit faţă de produsul AB inversat separat (A'B'). Cu alte cuvinte, (AB)' nu este egal cu A'B'. Acest lucru are un impact profund asupra modului de evaluare şi de reducere a expresiilor booleene, după cum vom vedea.
Teorema lui DeMorgan poate fi gândită ca şi „întreruperea” complementului (bara orizontală). Atunci când simbolul complementului este rupt în doua, operaţia de sub el se modifică din adunare în înmulţire şi invers. După aplicarea teoremei, fiecare variabilă are propriul ei complement. Ca şi exemplu:
Ruperea celui mai lung complement
Când există mai multe complemente deasupra aceleiaşi expresii, nu putem întrerupe decât un complement pe rând. Cel mai uşor este să începem cu cea mai lungă linie orizontală (cea de sus). Ca şi exemplu, să considerăm expresia (A + (BC)')' redusă cu ajutorul teoremelor lui DeMorgan:
Urmând consideraţiile exprimate mai sus, aplicăm următorii paşi:
Ca şi rezultat, circuitul original este redus la un circuit format dintr-o poartă ŞI cu trei intrări, unde intrarea A este inversată printr-o poartă NU:
Ca şi contra-exemplu, nu întrerupeţi niciodată mai mult de un complement la un singur pas:
Pe cât de tentant pare, pe atât de incorect este să scurtăm paşii simplificării prin întreruperea mai multor complemente deodată. Prin urmare, nu faceţi niciodată acest lucru!
Putem simplifica expresia de mai sus şi prin întreruperea complementului scurt în primă instanţă, şi apoi a complementului lung:
Desigur, rezultatul final este acelaşi şi în acest caz. Paşii necesari pentru simplificare sunt însă mai numeroşi faţă de exemplul precedent (întreruperea complementului lung la primul pas). La pasul al treilea, în exemplul de mai sus, întreruperea complementului lung se realizează în două locuri simultan. Această operaţie matematică este permisă, şi nu este identică cu întreruperea a două complemente deodată! Interdicţia întreruperii mai multor complemente deodată nu interzice întreruperea complementului în mai multe locuri.
Menţinerea grupărilor prin intermediul parantezelor
Poate vă întrebaţi de ce am folosit paranteze în jurul sub-expresiei B' + C', din moment ce oricum le-am îndepărtat la pasul următor. Am făcut acest lucru pentru a sublinia un aspect important dar neglijat al teoremei lui DeMorgan. Din moment ce o linie orizontală lungă funcţionează ca şi simbol de grup, variabilele incluse sub aceasta trebuie să rămână grupate. În caz contrar, ordinea operaţiilor se pierde. În exemplul anterior, nu contează dacă am fi pus sau nu aceste paranteze, dar în alte cazuri s-ar putea să conteze. Să luăm un alt exemplu, menţinând parantezele:
În cazul în care nu menţinem parantezele, riscăm să obţinem un răspuns greşit:
După cum se poate observa, menţinerea grupării realizate implicit prin liniile de complementare este crucială pentru obţinerea răspunsului corect.
Simplificarea unui circuit logic - exemplu
Să aplicăm acum principiile teoremelor lui DeMorgan pentru simplificarea unui circuit cu porţi logice:
Expresia booleană echivalentă
Ca de obicei, primul pas al simplificării circuitului constă în găsirea expresiei booleene echivalente. Putem face acest lucru prin notarea sub-expresiilor la ieşirea fiecărei porţi, pe măsură ce intrările ne sunt cunoscute:
Apoi, notăm ieşirea primei porţi SAU-negat şi ieşirea porţii ŞI-negat. Atunci când aveam de-a face cu porţi inversate pe ieşire, este mai uşor să scriem prima dată expresia fără inversarea finală. Observaţi şi de pe figură faptul că săgeata indică ieşirea porţii chiar înaintea inversării (cerculeţul de la ieşire). Expresia finală, după inversare, este complementul expresiei precedente. Astfel, ne putem asigura că nu uităm introducerea complementului în cadrul expresiei:
Şi, în sfârşit, ultimul pas constă în scrierea expresiei pentru poarta SAU-negat finală:
Simplificare expresiei echivalente
Trecem apoi la reducerea acestei expresii folosind identităţile, proprietăţile, regulile şi teoremele (lui DeMorgan) algebrei booleene:
Circuitul echivalent
Circuitul echivalent al expresiei mult simplificate:
