FUNCȚIILE LOGICE ȘI ALGEBRA LOGICII (ALGEBRA BOOLEANĂ)
Funcțiile logice și cum să le scrieți
În dispozitivele electronice digitale se folosesc elemente ale căror semnale de intrare și ieșire pot lua doar două valori: o unitate logică „1” și un zero logic „O”. Astfel de elemente, numite logice, efectuează cele mai simple operații cu astfel de numere binare.
Pentru a descrie algoritmii de operare și structura circuitelor logice, se folosește o algebră logică simplă, sau algebră booleană, numită după matematicianul irlandez D. Boole, care a dezvoltat-o la mijlocul secolului al XIX-lea. Se bazează pe trei operații logice de bază: negația logică sau operația NOT (inversie), adunarea logică sau operația SAU (disjuncție) și înmulțirea logică sau operația AND (conjuncție).
Operația NOT pe variabila x este scrisă ca .
Operația SAU pe două variabile x și y este scrisă cax+ y, iar operația și cax • y.
De fapt, fiecare operație logică definește funcția argumentelor (variabilelor) sale. Prin urmare, putem vorbi despre funcțiile de disjuncție, conjuncție și inversare.
Numărul de argumente ale funcțiilor de disjuncție și conjuncție poate fi arbitrar (mai mult de două).
O anumită funcție logică poate fi dată în formă algebrică sau sub forma unui tabel de adevăr.
O formă algebrică sau expresie booleană este o formulă constând din variabile logice conectate prin operații AND, OR și NOT, de exemplu:
f(x1, x2, x3)= x1* x2* x3+( x1+ x2) * (x1*x3).
Ca și în expresiile algebrice obișnuite, parantezele sunt folosite pentru a specifica ordinea operațiilor. Se presupune că operația AND precede operația SAU.
Un tabel de adevăr este un tabel care conține toate combinațiile posibile de valori de intrare.variabilele și valorile corespunzătoare ale funcției logice. Deci, pentru o funcție logicăn de variabile, tabelul de adevăr conține 2 n rânduri șin + 1 coloane, așa cum se arată în tabelul din fig. 1.
Evident, valoarea funcției logicef(x1,x2. xn)din fiecare linie va lua valoarea 0 sau 1 în funcție de valorile variabilelor logice de intrare.
Deoarece expresia booleană și tabelul de adevăr corespunzător descriu aceeași funcție, este posibil să treceți de la o formă de descriere la alta.
Tabelele de adevăr ale funcțiilor logice ȘI, SAU, NU sunt prezentate în Fig.2.
Funcția ȘI Funcția SAU Funcția HE
Să construim un tabel de adevăr (Fig. 3) pentru expresia booleană de mai sus
f(x1, x2, x3)= x1* x2* x3+( x1+ x2) * (x1*x3).
Pentru a construi un tabel, trebuie să calculați valoarea funcțieif(x1,x2,x3)pentru fiecare dintre cele opt combinații de valori ale variabilei de intrare.
f(0,0,0) = 0•0•0+(0+0)•(0+0)=0+0•(0+1)=0+0=0
f(1,1,1)=1•1•1+(1+1)•(1+1)=1+1•(1+0)=1+1•1=1 +1=1.
Tabelul de adevăr poate fi folosit și pentru a compune o expresie algebrică (booleană). În acest caz, expresia algebrică este scrisă folosind forma normală disjunctivă perfectă (SDNF) sau forma normală conjunctivă perfectă (SKNF).
Pentru a reprezenta funcția logicăFsub formă de SDNF, este necesar să se compună suma (disjuncția) produselor (conjuncțiile) a valorilor funcției logice Fi și minterms mi și numărul de termenin este egal cu numărul de rânduri din tabelul de adevăr, adică de ex.
Mintermul mi este produsul logic al tuturor variabilelor, iar variabilele egale cu zero sunt scrise cu inversare.
Deci pentru tabelul de adevăr (vezi Fig. 3) putem scrie următoarelemioterme:
Prin urmare, funcția logică F dată de tabelul de adevăr are următorul SDNF:
=x1• x2• x3+ x1• x2• x3+ x1• x2• x3+ x1• x2• x3+ x1• x2• x3
Astfel, pentru a scrie o funcție sub formă de SDNF, puteți folosi următoarea regulă: trebuie să scrieți cât mai mulți termeni disjunctivi, care sunt conjuncții (produse) ale tuturor variabilelor, de câte ori funcția ia valoarea 1, iar variabilele egale cu zero se scriu cu inversare.
Pentru a reprezenta funcția logicăF sub forma SKNF, este necesar să se compună produsul (conjuncția) sumelor (disjuncțiilor) valorilor funcției logice Fi și maxterms ki, iar numărul de produse n este egal cu numărul de rânduri din tabelul de adevăr, t e.
Maxterm ki este suma logică a tuturor variabilelor, iar variabilele egale cu 1 sunt scrise cu inversare.
Deci, pentru tabel (vezi Fig. 3), putem scrie următoarele maxime:
Prin urmare, funcția logică F dată de tabelul de adevăr este descrisă de următorul SKIF:
Astfel, pentru a scrie o funcție sub forma SKNF, se folosește următoarea regulă: trebuie să scrieți cât mai mulți termeni conjunctivi, care sunt disjuncții (sume) ale tuturor variabilelor, de câte ori funcția ia valoarea 0, iar variabilele sunt egale. la unu sunt scrise cu inversare.
Bazele algebrei logicii
Cele mai importante teoreme care reflectă relațiile de bază ale algebrei logicii sunt date în tabel (Fig. 4).
Este ușor de observat că toate teoremele (cu excepția celei 5) sunt reprezentate printr-o pereche de relații, fiecare dintre acestea obținută prin înlocuirea operațiilor ȘI cu SAU, operația SAU cu ȘI, 1 logic cu 0 logic și 0 logic cu 1 logic. TeoremeAlgebra booleană are o proprietate de simetrie cunoscută sub numele de principiul dualității.
Corectitudinea tuturor teoremelor de mai sus este ușor de demonstrat prin enumerarea tuturor posibilităților, adică prin metoda inducției perfecte. Deoarece variabilele din algebra booleană iau doar două valori, numărul tuturor combinațiilor posibile de valori variabile este mic, iar verificarea teoremelor pentru fiecare combinație nu este dificilă.