Lec ţ ia 5

5. Calculul Boolean

a. Calculul cu valori booleane evidente

b. Calculul cu funcţii booleane

c. Formule de calcul prescurtat

d. Legile De Morgan

5. Calculul Boolean

a.. Calculul cu valori booleane

Valorile booleane sunt 0 şi 1 ( Adevarat si Fals ), iar efectul operaţiilor booleane

asupra acestor valori a fost deja studiat în lecţia dedicată operaţiilor booleane

(lecţia a doua ) . Din acea lecţie vom repeat şi preciza câteva concepte.

Tabela de definiţie a operaţiilor AND şi OR este :

a b c

0 0 0

0 1 0

1 0 0

1 1 1

Rezultă regulile de calcul :

0 AND 0 = 0 sau 0 x 0 = 0

0 AND 1 = 0 sau 0 x 1 = 0

1 AND 0 = 0 sau 1 x 0 = 0

1 AND 1 = 1 sau 1 x 1 = 1

a b c

0 0 0

0 1 1

1 0 1

1 1 1

Rezultă regulile de calcul :

0 OR 0 = 0 sau 0 + 0 = 0

0 OR 1 = 1 sau 0 + 1 = 1

1 OR 0 = 1 sau 1 + 0 = 1

1 OR 1 = 1 sau 1 + 1 = 1

Vom adăuga aici regulile de calcul cu negaţia Astfel am împlinit trecerea în revista

a tuturor operaţiilor booleane de bază . Iată regulile calculului cu negaţia :

NOT 0 = 1

NOT 1 = 0

NOT (NOT(1)) = 1

NON(NOT(NOT(1)))=NOT 1 = 0

Vom da un exemplu de calcul într-o Expresie Booleană . Pentru început vom

rezolva o expresie ce conţine doar valori evidente .

Notă : "a rezolva" înseamnă a efectua cât mai multe din

operaţiile expresiei date .

( 1 + 1 + 1 + 0 ) ( 1 +0 + 0 + 0 ) = ? Vom calcula separat fiecare pereche de

paranteze: 1+1+1+0 = 1 , 1+0+0+0 = 1 deci

exerciţiul devine (1)(1) = 1 . Putem scrie :

( 1 + 1 + 1 + 0 ) ( 1 +0 + 0 + 0 ) = 1

Iată un alt exemplu :

De fapt am fi putut face un mic truc care ar fi scurtat calculul în mod considerabil.

Vom nota toată expresia de sub semnul negatiei cu X . Atunci expresia devine :

(- X) + 1 = ? . Cum în orice sumă , dacă unul din termeni este 1, atunci

rezultatul este 1 .

b. Calculul cu funcţii booleane

Calculul cu funcţii booleane este o misiune cam bizară ( căci presupune

întrebarea: "Cum crezi că se pot efectua operaţii între Propoziţii Booleane, dacă nu

ştim care e conţinutul acelor propoziţii şi deci nu putem şti dacă ele sunt adevarate

sau false), dar nu o misiune imposibilă . Iată câteva considerente care ne vor ajuta

în continuare :

A este o propoziţie booleană . Nu este necesar să-i cunoştem

conţinutul pentru a şti că A = {1, 0 }. Dacă A=1, atunci (–A)=0 şi

invers . În acest caz expresia E= A+(-A) este echivalentă cu

expresia 1+0=0+1, pentrucă în orice caz , ori A ori (-A) este 1 iar

celălat termen este 0. Deci A+1 =1 (indiferent de conţinutul sau

valoarea logică a propoziţiei A, căci 1+0=1 si 1+1=1).

Din aceleaşi considerente (prezentate mai sus) avem egalitatea :

E=A x A=A . Putem verifica acest rezultat : dacă A =1 atunci

expresia devine E= 1 x 1 = 1 , dacă A=0 atunci expresia devine

E=0x0 =0. În mod evident rezultatul expresiei este egal cu

valoarea funcţiei, deci E=AxA=A .

Nu voi mai face demonstraţia (acum evidentă) a egalităţii

E=A+A=A Să consideram expresia : E = A(A + B). Dacă deschidem

parantezele vom obţine E=AA +AB , dar AA = A (după cum am

văzut mai sus) deci putem scrie E=A+AB. Acum vom face

operaţia inversă, adică vom scoate factorul comun A şi vom obţine

E=A(1+B), dar, dacă într-o sumă unul dintre termeni este 1, atunci

rezultatul sumei este 1, deci E=A(1+B)= A x 1 = A . Din acest

exerciţiu învăţăm două reguli de calcul :

(1) A(A+B)=A

(2) A + AB =A Să examinăm următoarea expresie : E = AB(A + B) . Dacă desfacem

parantezele, vom obţine E=ABA + ABB = AB + AB = AB .

Putem deci conclude că:

(3) AB(A+B)=AB Vom calcula o altă expresie E = AB[ (-A) + (-B) ] . Vom desface

parantezele E=AB(-A) + AB(-B), dar am explicat deja că

A(-A)=0 şi de asemenea B(-B)=0 ,deci expresia devine

E=0+0=0 . Vom conclude :

(4) AB[ (-A) + (-B) ]=0 Toate expresiile pe care le-am studiat mai sus, au fost compuse din

propoziţii evidente sau valori evidente. Să studiem şi o

expresie compusă din funcţii booleane: E=ax +x . Dacă

scoatem x ca factor comun obţinem E=x(a+1)=x(1)=a (regula

(2) de mai sus).

Concluzia este că în calcule, comportamentul propoziţiilor

evidente este similar cu comportamentul funcţiilor Booleane.

Să încercăm un exerciţiu mai dificil : E=AC(A+C) + AB(A+B) .Desfacem

parantezele : E= ACA + ACC + ABA + ABB =

= AC + AC + AB + AB =

= AC + AB = A(B+C)

Dacă nu primim date despre valorile propoziţiilor A,B şi C

Nu vom putea continua calculul. În acest caz vom spune că

am simplificat la maximum expresia E ( am redus numărul

de operaţii de la 7 la 3 ) .

Să calculăm expresia: E=a[b+(-c)] + c[b+(-a)] + b[c+(-a)] . Vom deschide

parantezele şi vom obţine E=ab+a(-c)+bc+c(-a)+bc+b(-a)=

= ab+b(-a) + bc+bc + a(-c) + c(-a) =

= b([a+(-a)] + bc + a(-c) + c(-a) =

= b x 0 + c[ b + (-a)] + a(-c) =

= 0 + c[ b + (-a)] + a(-c) = c[ b + (-a)] + a(-c)

Nu ştim cum se poate continua acest exerciţiu şi de aceea ne vom opri aici,

mulţumindu-ne cu o simplificare de la 11 operaţii la numai 6 operaţii.

Notă : după cum aţi observat, nu există o diferenţă fundmentală între

expresiile compuse din funcţii sau propoziţii evidente ( neavând un sistem de

referinţă ).

Acesta e si răspunsul către Sile care mi-a sesizat o greşală într-una din

lecţiile trecute (ştie el cine este ).

Să examinăm un alt exerciţiu E= (x+y)[(-x)+(-y)] . Dacă desfacem

parantezele obţinem : E= x(-x) + x(-y) +y(-x) +y(-y) =

= 0 + x(-y) +y(-x) + 0 =

= x(-y) +y(-x) ne oprim aici

Am reuşit să simplificăm expresia ? Pare că nu , căci am pornit de la o

expresie cu 5 opearţii şi am terminat tot cu 5 operaţii . Vă aduceţi aminte că

în lecţia nr. 2 am definit gradele operaţiilor booleane ? ( NOT= gr. I , AND=gr.

II , OR=gr. III ). Să facem un bilanţ : expresia iniţială avea două OR , un AND

şi două negaţii , pe când expresia finală are un OR , două AND si două negaţii .

În concluzie rezultatul este mai simplu ( are mai puţine operaţii OR ) .

c. Formule de calcul prescurtat

Vă mai amintiţi de formulele de calcul prescurtat din algebra euclidiană ? Să le

recapitulăm :

(a+b)(a-b)=a2 -b2

(a + b)2 = a2 +2ab +b2

(a - b)2 = a2 -2ab +b2

(a + b)3 = a3 +3ab2+3a2b +b3

(a - b)3 = a3 -3ab2+3a2b -b3 etc. …etc

Aşa cum stiţi formulele algebrice pe de rost şi le aplicaţi aproape în mod

automat, tot aşa va trebui să cunoaşteţi pe de rost formulele de calcul prescurtat

din Algebra Booeană . Iată care sunt aceste formule în Algebra Booleană :

X + 1 = 1 X + 0=X X + X=X

X x 1 = X X x 0 = 0 X x X = X

X(a+b) = Xa+Xb a+b = b+a ab=ba

(a+b)(a+c) = aa+ac+ab+bc

x+yz = (x+y)(x+z)xy[ (-x)+(-y) ]=0

xy(x+y)=xy

x+xy =x

x((-x)+y)=xy

x + y(-x ) = x+y Acestea sunt cele 17 relaţii de calcul prescurtat ( 16 operaţii Booleane si 17

relaţii de calcul prescurtat prezentate de G.Boole) . La acestea vom adăuga ulterior

relaţiile legilor lui De Morgan ( vezi n continuare).

Curioz : regulile de mai sus sunt cunoscute sub porecla de "Cupa lui

Micenty" după numele Profesorului Krzywiecki Micenty ( prof de mat. Univ

Ohaio, USA)care în anul 1918 a prezentat aceste reguli de calcul pe fondul

desenului unei cupe de argint gravată (am încercat şi eu să respect această

forma grafică). Acest mic curioz dovedeşte că au existat (totuşi)

matematicieni (singulari ) care au studiat Algebra Booleană chiar înaintea lui

Von Neumann (ba au şi predat-o în universităţi).

d. Legile De Morgan

Augustus De Morgan (1806-1871) a fost contemporan cu George Boole şi a fost

singurul matematician englez ( matematicienii din afara Angliei aveau scuza

barierii de limbă ) care a luat în serios algebra logică a lui G. Boole . Nu numai

că a luat în serios, ci chiar a aprofundat acest domeniu cu sârguinţă,

complentând lista celor 17 formule de calcul prescurtat cu încă două formule

esenţiale .

Augustus De Morgan a scris şi el o carte de logică matematică numită

"Trigonometria şi Algebra Dublă" (1868) în care trece în revistă toate

simbolurile matematice şi încearcă să găsească reguli de interpretare a

grupurilor de simboluri . Din această carte e greu de spus dacă De Morgan a

cunoscut algebra lui G. Boole prior scrierii propriei sale cărti, dar algebra dublă

aminteşte algebra lui Boole prin bizaritatea sa şi prin explozia de râsete pe care a

stârnit în comunitatea matematică . Cartea nu a fost acceptată de

matematicienii şi gânditorii vremii şi a ramas uitată în bibleoteci . Până azi încă

nu s-a găsit un "Von Neumann" care să scoată această carte la lumina

cunaşterii (aşa cum s-a întamplat cu ultima cartea a lui George Boole) .

Iată un citat din această carte a lui De Morgan :

"In abandoning the meaning of symbols, we

also abandon those of the words which

describe them. Thus addition is to be, for the

present, a sound void of sense. It is a mode

of combination represented by + ; when +

receives its meaning, so also will the word

addition. It is most "important that the

student should bear in mind that, with one

exception, no word nor sign of arithmetic or

algebra has one atom of meaning throughout

this chapter, the object of which is symbols,

and their laws of combination, giving a

symbolic algebra which may hereafter

become the grammar of a hundred distinct

significant algebras. If any one were to

assert that + and − might mean reward and

punishment, and A, B, C, etc., might stand

for virtues and vices, the reader might

believe him, or contradict him, as he

pleases, but not out of this chapter. The one

exception above noted, which has some

share of meaning, is the sign = placed

between two symbols as in A = B. It

indicates that the two symbols have the

same resulting meaning, by whatever steps

attained."

Augustus De Morgan

Augustus De Morgan (1806-1871)

Born

27 June 1806

Madurai, Madras Presidency, British Raj (now

India)

Died18 March 1871 (aged 64)

London, England

Vom încerca să prezentăm cele două formule a lui De MOrgan în modul cel

mai simplu şi nu în forma generală în care le-a prezentat el însuşi în anul 1870

(un an inainte de moarte).

Iată formulele (legile ) De Morgan

Aceste două formule stabilesc relaţiile dintre cele trei operaţii booleane de

bază : NOT , AND şi OR la nivelul propoziţiilor ( sau a funcţiilor booleane ) .

Urmăriţi în continuare demonstraţia următoare :

aceasta este demonstraţia legilor De Morgan pentru

trei funcţii boleane . Aceasta demonstraţie poate fi reluată şi pentru patru , cinci ,

şase … funcţii . În final putem conclude că pentru orice număr de funcţii

booleane exista relatia :

-(a1 +a2 + a3 + … + ak) = (-a1)(-a2)(-a3) … (-ak) şi deasemeni

-(a1a2a3….ak) = (-a1) + (-a2) + (-a3) + … + (-ak)Aceste două formule se pot scrie şi altfel :

Unde semnul "U" înseamnă produsul a "n" factori, iar semnul

"∩" înseamnă suma a "n" termeni .

Aceasta este forma în care DeMorgan a prezentat "legile" lui .

Pentru a înţelege importanţa formulelor lui De Morgan vom considera următorul

exerciţiu ( vă rog să nu va speriaţi de imensitatea acestui calcul, ci urmăriţi cum

această algebră logic se aseamănă cu algebra clasică ).

Considerăm următoarea expresie booleană pe care dorim s-o simplificăm :

După cum v-am prevenit , calculul este dificil şi cere îndemânare şi experienţă .

Acest execiţiu este la nivel universitar şi nu mă aştept să performaţi singuri un

asemenea exerciţiu. Dacă (însă) în viitor veţi lucra în domeniul circuitelor numerice

(ca inginer/ă) asemenea calcule pot economisi sute de mii de dolari proiectului la care

veţi lucra. Despre aceasta vom discuta n amănunt în una din următoarele noastre

lecţii .