STRUCTURI ALGEBRICE IMPLICATE INAREA SI OPTIMIZAREA CIRCUITELOR

STRUCTURI ALGEBRICE IMPLICATE IN PROIECTAREA SI OPTIMIZAREA CIRCUITELOR

Latice

Definitia 1. O latice este o multime L nevida, inzestrata cu o relatie binara, " ale carei elemente satisfac urmatoarele proprietati:

i.  x x, xIL, (reflexivitate);

ii.  (x y si y x) T x = y x, yIL, (antisimetrie);

iii. (x y si y z) T x z x, y, zIL, (tranzitivitate);

iv.  x, yIL, sIL astfel incat ( x s si s si ( zIL: (x z si y z))T s z,

(existenta unui cel mai mic majorant);

v. x, yIL, pIL astfel incat (p x si p y si ( zIL:(z x si z y))T z p

(existenta unui cel mai mare minorant).

Observatie: Din proprietatile (i) (ii) si (iii) si din definitia 1 rezulta ca L este o multime partial ordonata in raport cu relatia " iar din (iv) si (v) rezulta ca pentru oricare doua elemente exista un cel mai mic majorant comun si un cel mai mare minorant comun. Relativ la definitia anterioara consideram operatorii :

": L L L, x y: = p, x, y I L

si

": L L L, x y: = s, x, y I L.

Propozitia 1. Au loc urmatoarele proprietati x, y, z I L

i. x x = x, x x = x (idempotenta);

ii. x y = y x, x y = y x   (comutativitatea);

iii.  x (y z) = (x y) z,

x (y z) = (x y) z), (asociativitatea);

iv) x (x y) = x, x (x y) = x (absorbtia).

Demonstratie:

i. Din x x rezulta ca x x x. Ultima inegalitate combinata cu x x x conduce la egalitatea din enunt: x x = x. Cealalta egalitate se demonstreaza analog.

ii. Din x y y si x y x rezulta ca x y y x, iar din y x y si  y x x rezulta ca x y y x. Avand loc dubla inegalitate rezulta chiar egalitatea. Cealalta egalitate se demonstreaza analog.

iii. Din x (y z) x si x (y z) y z y rezulta ca x (y z) x y iar din y z z rezulta ca x (y z) z. Atunci rezulta mai departe ca

x (y z) (x y) z  (1)

Din (x y) z z si din (x y) z x y y rezulta ca (x y) z y z, relatie care combinata cu (x y) z x y x duce la

(x y) z x (y z)  (2).

Din (1) si (2) rezulta egalitatea dorita. Cealalta egalitate se demonstreaza analog.

iv. Din x (x y) x si din x = x x x (x y) rezulta ca x (x y) = x. Cealalta egalitate se demonstreaza analog.

Observatie: O latice se poate defini si ca o multime L nevida inzestrata cu doua operatii " si " care satisfac proprietatile din propozitia precedenta. In acest caz, relatia de ordine partiala din prima definitie se regaseste astfel:

x y: x y = x (sau x y = y

Definitia O latice se numeste distributiva daca satisface si proprietatile:

i. x (y z) = (x y) (x z) x, y, z I L;

ii. x (y z) = (x y) (x z) x, y, z I L.

Definitia 3. Intr-o latice distributiva L, un element 0IL cu proprietatile x 0 = x, x se numeste prim element al laticei, iar un element 1I L cu proprietatile x si x 1 = x se numeste ultim element al laticei.

Observatie:

Relativ la relatia de ordine dintr-o latice, primul element daca exista, are proprietatea ca xIL, x iar ultimul element tot daca exista are proprietatea ca xIL, x

Definitia 4. O multime nevida L in care s-a definit o relatie binara, ale carei elemente satisfac proprietatile (i), (ii) si (iii) si una din proprietatile (iv) sau (v) din definitia 1 se numeste semilatice.

Propozitia (Principiul dualitatii) Din orice afirmatie adevarata relativa la elementele unei latice si la operatorii " si " se deduce o alta afirmatie adevarata daca se schimba " cu " si invers.

Propozitia 3. x, y, I L avem x y = x daca si numai daca x y = y.

Demonstratie:

Implicatia "T x y = y (x y)= y;

Implicatia " x y = x (x y)= x.

Exemplu: Multimea numerelor naturale N inzestrata cu operatiile ' si ' definite de:

n m = max n, m I N;

n m = min n, m I N,

este o latice.

Demonstratie:

n m = max = max= m n

ceea ce dovedeste comutativitatea;

n (m p) = max } = max =

max{max, p} = (n m) p

ceea ce dovedeste asociativitatea;

iii. n (m n) = max {n, min }= n, ceea ce dovedeste absorbtia.

Egalitatile pereche se demonstreaza analog.

Exemplu:

Multimea numerelor naturale N inzestrata cu operatiile ' si ' definite de:

n m: = cmmdc (n, m) n, m I N;

n m: = cmmmc (n, m) n, m I N,

are de asemenea o structura de latice.

Definitia 5. Intr-o latice L care admite prim si ultim element, elementul x'I L se numeste complement al lui x I L daca si numai daca x' x = 0 si x' x =1.

Propozitia 4. Intr-o latice distributiva daca un element are un complement atunci acest complement este unic.

Demonstratie:

Fie x, y, z I L astfel incat y si z sunt complemente pentru x. Rezulta ca:

x y =1, x z =1, x y = 0, x z = 0.

Dar atunci, pe de-o parte

y (x z) = y 0 = y

si pe de alta parte

y (x z) = (y x) (y z) = 1 (y z) = y z.

Rezulta mai departe ca:

y = y z, adica z y

Analog se deduce ca y z. Si deci are loc egalitatea y = z.

Algebra booleana

Definitia 6. Se numeste algebra booleana orice latice distributiva cu prim si ultim element, in care orice element admite complement.

Din aceasta definitie rezulta imediat urmatoarea propozitie.

Propozitia 5. Intr-o algebra booleana (A, ), unde " sunt operatiile ce definesc laticea, 0 si 1 sunt primul respectiv ultimul element al laticei iar operatorul : A A pune in corespondenta lui x I A complementul sau x I A, sunt valabile urmatoarele afirmatii:

i. a b = b a, a b = b a,  a, b I A;

ii. a (b c) = (a b) c, a (b c) = (a b) c, a, b, c I A;

iii. a (a b) = a, a (a b) = a, a, b I A;

iv. a (b c) = (a b) (a c),  

a (b c) = (a b) (a c), a, b, c I A;

v. (a a) b = b, (a a) b = b, a, b I A.

Demonstratie.

Daca (i), (ii), (iii) si (iv) sunt proprietatile de comutativitate, asociativitate, absorbtie si respectiv distributivitate din definitia laticei distributive cu prim si ultim element, proprietatea (v) se demonstreaza astfel:

a a = 0 si 0 b = b implica (a a) b = b;

a a =1 si 1 b = b implica (a a) b = b.

Observatie:

Se poate defini algebra booleana independent de notiunea de latice, ca fiind o multime nevida A inzestrata cu doua operatii binare " , si o operatie unara " ce satisfac relatiile din propozitia 5. In aceasta situatie, demonstram in continuare ca a a si a a sunt elemente independente de a I A si de aceea ele vor reprezenta primul respectiv ultimul element din laticea (A,

Intr adevar, scriind prima relatie din afirmatia (v) a propozitiei 5 pentru elementele a, b b I A si apoi pentru b, a a I A obtinem:

(a a) (b b) = (b b) , (b b) (a a) = (a a), a, b I A.

Tinand cont in continuare de comutativitatea operatiei " deducem ca

a a = b b, a, b I A.

Analog, aplicand a doua relatie din afirmatia (v) a propozitiei 5 pentru elementele  a, b b I A si apoi pentru b, a a I A obtinem:

(a a) (b b) = (b b) , (b b) (a a) = (a a), a, b I A.

Tinand cont in continuare de comutativitatea operatiei ' deducem ca

a a = b b, a, b I A.

Observatie:

Din relatia (ii) din propozitia 5 rezulta ca a₁, a₂,, a_n I A elementele a₁ a₂ a_n si a₁ a₂ a_n sunt bine definite si nu depind de ordinea elementelor care intervin in compunerea lor; se noteaza respectiv .

Propozitia 6. Intr-o algebra booleana au loc:

i. a a =a, a a =a,  a I A (idempotenta);

ii. a b =a a b =b.

Demonstratie:

Rezulta imediat din propozitia 1 si propozitia 2 daca tinem cont ca algebra booleana a fost definita ca latice.

In mod echivalent avem:

i. a = a (a b) = (a a) (a b) = [a (a b)] [a (a b)] = a a;

a = a (a b) = (a a) (a b) = [a (a b)] [a (a b)] = a a;

ii.  (T) a b = (a b) b = b;

( ) a b = a (a b) = a;

Definitia 7. Daca a, b I A, A algebra booleana, spunem ca a este mai mic decat b (sau b este mai mare decat a, sau a este un minorant al lui b, sau b este un majorant al lui a, sau a este un subelement al lui b, sau a este continut in b, sau b contine a) si vom nota a b, daca a b = a, sau, echivalent a b = b. Relatia " se numeste relatie de incluziune booleana.

Observatie:

Relatia " este o relatie de ordine partiala pe A deoarece este relatia de ordine partiala din definitia laticei care este algebra booleana A. Din aceleasi motive elementul a b (respectiv a b) este cel mai mic majorant comun (respectiv cel mai mare minorant comun) al elementelor a si b.

Propozitia 7. Daca A si , atunci b este cel mai mic element care contine toate elementele. Asadar:

i. a_i b, ;

ii. a_i f, T b f.

Daca atunci c este cel mai mare element care este continut in toate elementele . Asadar:

i'. c a_i ;

ii'. g a_i T g c.

Definitia 8. Intr-o algebra booleana primul si ultimul element al laticei se numesc elementul zero respectiv elementul unitate.

Definitia 9. Algebra booleana A se numeste nedegenerata daca contine cel putin doua elemente.

Observatie:

O conditie necesara si suficienta ca o algebra booleana A sa fie degenerata este ca 1 = 0.

Propozitia 8. (Principiul dualitatii, in algebrele booleene)

Daca intr-o afirmatie adevarata privind operatiile ' ' si elementele 0 si 1 inlocuim ' cu ' cu ' cu 1 si 1 cu 0 lasand operatia ' ' neschimbata, obtinem tot o propozitie adevarata (numita duala primei propozitii).

Propozitia 9. In orice algebra booleana A, sunt adevarate urmatoarele afirmatii:

i. a =, a I A;

ii. a = b a = b, a, b I A;

iii. = a b, = a b, a, b I A, (relatiile De Morgan);

iv. a b b a a, b I A

Demonstratie:

i. Complementul unui element a I A este unic determinat deci sistemul de ecuatii booleene:

a x = 0, a x = 1

are solutia unica:

x = a .

Atunci:

a = 0, a a = 0, a =1, a a =1

implica

a = , a I A.

ii. " " este aplicatie. Deci a = b T a = b; a = b T =T a = b

Deci a = b a = b a, b I A

iii. Fie c = a b. Atunci:

(a b) c = (a b) a b) = (a a b) (b a b) = 0

(a b) c = (a b) a b) = (a a b) (b a b) = 1

ceea ce implica c = si deci = a b .

Aplicand principiul dualitatii rezulta imediat ca = a b.

a b a b = b = b a b = b b a .

Observatie:

Din propozitia precedenta se obtine

= a b , = a b,

prin urmare intersectia poate fi definita cu ajutorul reuniunii si complementarei si analog reuniunea poate fi definita cu ajutorul intersectiei si complementarei.

Observatie: Inlocuind in = a b pe b cu a rezulta ca . Prin complementare rezulta ca

Definitia 10. Pentru doua elemente a, b I A diferenta lor este data de relatia

a - b: = a b.

Observatie:

Din definitia de mai sus rezulta ca 1- a = a, a I A.

Propozitia 10. a - b = 0 a b.

Demonstratie:

Implicatia "T

a - b = 0 T a b = 0

a b = (a b) 1 = (a b) b b) = (a b) b = 0 b = b

Deci a b = b adica a b.

Implicatia "

a b T a b = a si a b = b.

a - b =a - (a b) = a () = a a b ) = 0 b = 0.

Observatie:

Exista restrictii fata de numarul elementelor pe care poate sa-l aiba multimea peste care se defineste structura de algebra booleana date de urmatoarea:

Teorema 1. (de reprezentare a lui Stone)

Orice algebra booleana este izomorfa cu un corp de parti.

Definitia 11. Pentru o multime W cu A W multimea partilor lui W, multimea K A W), K se numeste corp de parti daca si numai daca este inchisa fata de complementare si reuniune, adica:

i. A I K T C_A = W-A I K,

ii. A, B I K T A B I K.

In consecinta, orice algebra booleana finita are 2ⁿ elemente unde n este numarul atomilor algebrei (Daca A este algebra booleana atunci a I A se numeste atom daca si numai daca b I A: b a T b =0 sau b = a).

Deci se pot defini algebre booleene (B(p), ) cu p I N* elemente daca si numai daca n I N: p = 2ⁿ (adica daca si numai daca p este o putere a lui 2).

Inel boolean

Definitia 1 Se numeste inel o multime nevida I inzestrata cu doua operatii (legi de compozitie) "+" si " care verifica proprietatile:

i. a + b = b + a, a, b I I ,   (comutativitatea);

ii. a + (b + c) = (a + b) + c, a, b, c I I, (asociativitatea);

iii. I I: a + 0 = 0 + a = a, a I I, (existenta elementului neutru);

iv. a I I, -a I I: a + (-a) = (-a) + a = 0, (existenta elementului simetric);

v. a (b + c) = a b + a c, a, b, c I I,

(a + b) c = a c + b c, a, b, c I I,

(distributivitatile la dreapta si la stanga ale operatiei " fata de "+");

vi. a (b c)=(a b) c, a, b, c I I, (asociativitatea).

Definitia 13.

i. Un inel (I, +, cu proprietatea ca I I: a a = a, a I I se numeste inel cu element unitate.

ii. Un inel (I, +, cu proprietatea a b = b a, a, b I I se numeste inel comutativ.

Definitia 14.

Un inel (I, +, cu element unitate si cu proprietatea ca a a = a, a I I se numeste inel boolean.

Propozitia 11. In orice inel boolean (I, +, au loc urmatoarele proprietati:

i. a + a = 0, a I I;

ii.  a + b = 0 T a = b, a, b I I;

iii.  a b = b a, a, b I I;

a a = 0, a I I.

Demonstratie:

1 + a =(1 + a) (1 + a)=1 + a + a + a a = 1 + a + a + a T a + a = 0, a I I.

a + b = 0 implica a + (a + b) = a + 0 = a.

Pe de alta parte a +(a + b)=(a + a)+ b = 0 + b = b. Rezulta atunci ca a = b.

a + b = (a + b)(a + b) = a a + a b + b a + b b =

=(a + b) + (a b + b a)

ceea ce implica a b + b a = 0 adica a b = b a.

a 0 = a (0 + 0) = a 0 + a adica a pe de-o parte.

Analog 0 a =0 Inseamna atunci ca a a =0, a I I.

Observatie:

Implicatia de la punctul (ii) din propozitia 11 are loc si in sens invers, adica:

a, b I I, a = b a + b = 0 deoarece a + b = a + a = 0.

Propozitia 1 a + b = c b = a + c a = b + c, a, b, c I I.

Demonstratie:

Implicatia "T

a + b = c T a + (a + b) = a + c

a + (a + b) = (a + a) + b = b T b = a + c

b + c = (a + c) + c = a + (c + c) = a.

Implicatia "

a = b + c T a + c = (b + c) + c = b + (c + c) = b

T a + b = a + (a + c) = (a + a) + c = c.

Legatura dintre algebra booleana si inelul boolean

Teorema Orice algebra booleana A este un inel boolean cu urmatoarele definitii ale operatiilor de adunare si inmultire:

a + b: = (a-b) (b-a) (= (a b) (b a));

a b: = a b.

Reciproc, orice inel boolean I este o algebra booleana cu urmatoarele definitii ale operatiilor de reuniune, intersectie si complementare:

a b = a + b + a b;

a b = a b;

a = 1 + a.

Mai mult, in ambele cazuri elementul neutru fata de "+" si elementul neutru fata de " din inelul boolean coincid cu elementul zero respectiv elementul unitate din algebra booleana.

Demonstratie:

Implicatia "T": Verificam conditiile (i) - (vi) din definitia inelului boolean:

a + b = (a b) (b a) = (b a) (a b) = b + a.

= == ( b (b c)) (c (b c))= ( b b) b c) (c b) (c c) = (b c) b c).

Rezulta atunci ca:

a + (b + c) = (a ) ((b + c) a) =

= [a [(b c) b c)]] [[(b c) b c) ] a ] =

= (a (b c)) (a b c)) a (b c)) a b c)) =

= [((a b a b)) c ] [((a b) a b)) c] =

= ( c) ((a + b) c)= (a + b) + c.

a + 0 = (a a 0) = (a 0 = a 1 = a.

a + a = (a a) a a) = 0

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

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

= [(a b) a c)] a b) (a c)]= (a b a) (a b c) a a c) (a b c)= (a b c) (a b c).

Deci: a (b+c) = a b + a c. Datorita comutativitatii inmultirii intr-un inel boolean se deduce imediat ca are loc si relatia (a + b) c = a b + b c.

a (b c) = a (b c) = (a b) c = (a b) c.

a 1 = a 1 = a

a a = a a = a.

Implicatia " " consta in verificarea conditiilor din definitia algebrei booleene deci a conditiilor din propozitia 5:

i. a b = a + b +a b = b + a + b a = b a.

a b = a b = b a = b a.

ii.  a (b c) = a (b + c + b c) = a + b + c + b c + a (b + c + b c)=

= a + b + c + b c + a b + a c + a b c

(a b) c = (a + b + a b) c = a + b + a b + c + (a + b + a b) c=

= a + b + c + b c + a b + a c + a b c

a (b c) = a (b c) = a (b c) = (a b) c = (a b) c.

iii. a (a b) = a a b = a + a b + a (a b)= a + a b + a b = a.

a (a b) = a (a + b + a b)= a + a b + a b = a.

iv. a (b c)= a (b + c + b c)= a b + a c + a b c;

(a b) (b c) = a b a c = a b + a c + a b a c =

= a b + a c + a b c.

(a a) b = (a a) b = (a (1+a)) b = (a + a) b =

= a + a + b + (a + a) b = a + a + b + a b + a b = 0 + b = b

(a a) b = (a (1+a)) b = (a + 1 + a + (1+a) a) b =

(1 + a + a a) b = (1 + a + a) b = 1 b = b.

Fie 0 si 1 elementele neutre fata de "+" si " in inelul boolean si 0' si 1' elementele zero respectiv unitate in algebra booleana. Atunci:

a + 0' = (a a 0') = a 0' = a

a 1' = a 1' = a T si 1'= 1

sau

a 0 = a + 0 + a 0 = a + 0 = a T 0'

a 1 = a 1 = a T

5. Exemple reprezentative: A(X), X≠Ø; B(2), B(4), Z₂

i. Multimea partilor unei multimi.

Pentru o multime X multimea A(X) a partilor lui X inzestrata cu operatiile de reuniune, intersectie si complementare din teoria multimilor, formeaza o algebra booleana:

A (X) =;

A (X) A (X) A (X), A B=, A,BIA (X);

A (X) A (X) A (X), A B=, A,BIA (X);

: A (X) A (X), A = , A I A (X).

Propozitia 13. A (X), ) este o algebra booleana in care primul element este iar ultimul element este X, multimea totala.

Demonstratie:

Verificam conditiile din definitia algebrei booleene:

i) si ii) rezulta din asociativitatea si comutativitatea operatiilor de reuniune si intersectie a multimilor.

iii. A (A B) =A, A, B I A (X) o demonstram prin dubla incluziune:

x I A T x I A (A B) T A A (A B)

x I A (A B) T x I A sau x I A B adica x I A sau (x I A si x I B)

T x I A T A (A B) A T chiar egalitatea:

A (A B) = A A, B I P(X)

x I A T x I A B T x I A (A B) T A A (A B),

A (A B) A evident implica A (A B) = A.

iv.  A (B C) = (A B) (A C) A, B, C I A (X) o demonstram tot prin dubla incluziune:

x I A (B C) x I A si x I B C x I A si (x I B sau x I C)

x I A B sau x I A C x I (A B) (A C)

Cealalta relatie de distributivitate se deduce analog.

v. (A A) B = X B =B   A, B X;

(A A) B = X B =B A, B X.

Algebra booleana binara.

Multimea B(2) = inzestrata cu operatiile definite in tabelele 1, 2, 3

Suma logica Produsul logic Complementara

Tabelul 1. Tabelul Tabelul 3.

formeaza o algebra booleana in care primul element este 0, iar ultimul element este 1. Verificarea conditiilor ce trebuie sa fie indeplinite pentru ca (B(2), , 0, 1) sa aiba structura de algebra booleana o facem prin epuizarea tuturor valorilor ce le pot avea variabilele.

Tabelul 4.

Tabelul 4 (continuare).

Din tabelul 4 rezulta proprietatile (i), (iii) si (v) din definitia echivalenta a algebrei booleene.

Tabelul 5.

Tabelul 5 (continuare).

Din tabelul 5 rezulta asociativitatea reuniunii si distributivitatea intersectiei fata de reuniune (cealalta relatie de distributivitate se demonstreaza analog) prin confruntarea valorilor din coloanele corespunzatoare membrilor egalitatilor.

iii. Algebra booleana cu patru elemente.

B(4) = inzestrata cu operatiile definite in tabelele 6, 7, 8

Tabelul 6. Tabelul 7. Tabelul 8.

si cu 0 prim element, iar 1 ultim element, formeaza o algebra booleana.

Se pot pune in evidenta, din tabelele reuniunii si intersectiei relatiile de incluziune (de ordine) dintre elemente:

a, 0 b, 0 (0 este cel mai mic element),

a 1, b (1 este cel mai mare element),

a b sau b a nu sunt adevarate deoarece a b = 0 si a b =1 si deci nu exista relatie de ordine intre a si b. Rezulta astfel ca intr-adevar relatia de ordine ce se poate defini in general intr-o algebra booleana este doar partiala.

Verificarea conditiilor din definitia algebrei booleene se poate face ca la exemplul anterior insa cu un volum de calcule sporit.

iv. Clasa de resturi modulo

Z₂ = impreuna cu operatiile de adunare si inmultire modulo 2 are o structura de inel boolean. Tabelele operatiilor din inel sunt:

Tabelul 9. Tabelul 10.

Acest inel boolean (Z₂, A este echivalent, pe baza teoremei 1 cu o algebra booleana inzestrata cu operatiile:

a b = a b (a A b), a b = a A b, a = 1 a.

Definind concret operatiile de reuniune, intersectie si complementare se obtin tabelele:

Tabelul 11. Tabelul 1 Tabelul 13.

Din structura acestor tabele rezulta ca algebra booleana cu care este echivalent inelul claselor de resturi modulo 2 este chiar algebra booleana binara (B(2), ).

Algebra propozitiilor

6.1. Conceptul de propozitie

Calculatoarele numerice (sistemele de calcul) trateaza informatia sub forma numerica; prin urmare, structura sa fizica trebuie sa includa dispozitive capabile sa reprezinte numerele.

Este necesar in primul rand sa fie modelata cifra, iar dispozitivul corespunzator trebuie sa aiba functional un numar de stari distincte egal cu baza sistemului de numeratie.

Teoretic se pot concepe dispozitive corespunzatoare oricarei baze de sistem de numeratie, practic insa, din considerente tehnice, sunt preferabile dispozitivele bistabile (de tip inchis - deschis, magnetizat - nemagnetizat, tensiune joasa - tensiune inalta), deci dispozitivele cu 2 stari stabile.

Utilizarea dispozitivelor bistabile conduce la utilizarea preferentiala a sistemului de numeratie binar (sau in baza putere intreaga a lui 2, ceea ce implica tot utilizarea cifrelor binare 0 si 1, in grupari de triade sau tetrade).

Generalizand notiunea gramaticala de propozitie, vom considera propozitia ca exprimare a unei informatii concrete referitoare la un obiect sau fenomen.

Prin informatia continuta, o propozitie este adevarata daca si numai daca ceea ce exprima propozitia este realmente adevarat in raport cu realitatea obiectiva; in caz contrar propozitia este falsa .

Aprecierea de adevar sau fals se refera la propozitia in ansamblu, considerata ca entitate si nu la obiectivele la care aceasta se refera.

Calitatea unei propozitii de a fi adevarata sau falsa constitue valoarea logica sau valoarea de adevar a propozitiei respective .

Aplicand anumite legi (reguli precizate) din propozitii date (considerate premise sau ipoteze) se pot construi propozitii noi (numite uneori rezultate sau concluzii).

Este evident faptul ca se considera valide acele legi (reguli) care permit, prin aplicarea lor, obtinerea de propozitii-concluzii adevarate pornind de la propozitii-ipoteze de asemenea adevarate .

Legile (regulile) sunt modalitati de construire a unor propozitii din alte propozitii, intervenind nu continutul concret al propozitiilor ci valoarea lor logica sau de adevar. Stiinta acestor legi (reguli) se numeste logica.

Fiind independente de un anumit continut concret, legile respective se numesc si forme logice, iar logica, stiinta a acestor legi este numita si logica formala.

O etapa, evoluata, a logicii formale este logica simbolica sau logica matematica; logica matematica introduce in logica procedeele de calcul cu valori de adevar, accentuand abstractizarea in sensul ignorarii concretului din continutul propozitiilor .

Asadar, logica matematica este matematica valorilor de adevar, obiectul sau fiind studiul propozitiilor exclusiv din punctul de vedere al valorii lor de adevar, abstractie facand de ceea ce exprima concret aceste propozitii.

Logica matematica bivalenta are la baza algebra logicii sau algebra booleana.

Paralelismul cifra binara - propozitie logica

Sistemele de calcul (calculatoarele numerice) lucreaza cu numere reprezentate in sistemul de numeratie binar, sistem ce presupune pentru fiecare cifra doar doua valori posibile 0 si 1.

Logica matematica opereaza cu propozitii, ignorand continutul lor concret si considerand doar valoarea lor logica ce poate fi adevar sau fals.

Este sesizabil paralelismul dintre cifra binara, cu valoare 0 sau 1 si propozitia logica, cu valoare de adevar sau fals.

Pornind de la cifre, prin calcul matematic se obtin cifre-rezultat; pornind de la propozitii-ipoteze, prin legi (reguli) in domeniul logicii se obtin propozitii-concluzii.

Cifrele-rezultat pot avea doar doua valori 0 sau 1, iar propozitiile-concluzii tot doua valori, fals sau adevarat.

Rezulta de aici posibilitatea ca legile logicii sa fie modelate prin calcul matematic si reciproc; trebuie deci gasite legile logice de compunere a propozitiilor in paralel cu operatiile matematice asupra cifrelor, ceea ce permite transpunerea calculului aritmetic in calcul logic cu valori de adevar.

Construind dispozitive a caror functionare sa reprezinte modelarea unor operatii logice, exprimate prin legi logice si avand in vedere corespondenta acestora cu operatiile aritmetice, se vor realiza dispozitive de calcul binar, ceea ce reprezinta baza structurala a sistemului de calcul (a calculatorului numeric).

Analog functiilor matematice care sunt procedee de calcul asupra variabilelor independente, rezultand o valoare corespunzatoare a functiei, functiile logice (de adevar) sunt procedee de construire a unei propozitii pornind de la propozitii date, considerand insa toate propozitiile doar sub aspectul valorii lor de adevar.

Elemente de calcul propozitional

Definitia 15. Se numeste propozitie o combinatie determinata de termeni (sau simboluri) care exprima o afirmatie concreta in legatura cu un obiect sau fenomen.

Propozitiile vor fi considerate satisfacand legea tertului exclus si legea contradictiei, adica oricare propozitie este sau adevarata sau falsa si nu poate fi simultan adevarata sau falsa.

Deoarece se face abstractie de continutul si structura propozitiilor, interesand doar faptul daca ele sunt adevarate sau false, studiul propozitiilor este de fapt studiul valorilor lor de adevar (altfel spus, algebra propozitiilor este algebra valorilor lor de adevar).

Vom nota propozitiile cu litere majuscule ale alfabetului latin, iar valorile logice (de adevar), respectiv cu literele a (pentru adevarat ) si f (pentru fals).

In vorbirea curenta, din propozitii date se formeaza, utilizand asa-numitele conective de tip si, sau, daca .atunci, negatia, noi propozitii. Acestor conective le corespund in logica propozitiilor bivalente operatiile logice, care pot fi considerate conective ale valorilor de adevar.

Definitia 16. Se definesc urmatoarele operatii logice (conectori) in logica propozitiilor bivalente:

i. Conjunctia ( (echivalenta conectivului si);

C = A B, A, B, C-propozitii astfel incat C este adevarata daca si numai daca A si B sunt simultan adevarate.

ii. Disjunctia ( (echivalenta conectivului sau );

C = A B, A, B, C-propozitii; C este adevarata daca si numai daca cel putin una din propozitiile date este adevarata.

iii. Implicatia ( (echivalenta conectivului daca . atunci);

C = A B, A, B, C-propozitii; C este falsa daca si numai daca A este adevarata si B este falsa. (A se numeste ipoteza sau cauza, iar B consecinta sau efect).

iv. Negatia ( (echivalenta conectivului nu);

C = A, A, C-propozitii; C este adevarata daca si numai daca A este falsa.

v. Echivalenta ( (echivalenta conectivului daca si numai daca);

C = A B, A, B, C-propozitii; C este adevarata daca si numai daca A si B au aceeasi valoare de adevar.

vi. Nici (

C = A B, A, B, C-propozitii; C este adevarata daca si numai daca A si B sunt simultan false.

vii. Incompatibilitatea (

C = A B, A, B, C-propozitii astfel incat C este falsa daca si numai daca A si B sunt simultan adevarate. Aceste operatii logice pot fi reprezentate si sub forma tabelului urmator:

Tabelul 26.

Structura definita pe multimea propozitiilor cu ajutorul operatiilor logice de disjunctie, conjunctie si negatie este de fapt o algebra booleana binara.

Definitia 17. Se numeste propozitie elementara o propozitie cu proprietatea ca nici o parte a sa nu mai este propozitie; in caz contrar propozitia se numeste propozitie compusa.

Observatie: Operatiile logice permit obtinerea de propozitii compuse din propozitii elementare.

Definitia 18. Se numeste formula (expresie) in algebra propozitiilor orice propozitie compusa obtinuta aplicand de un numar finit de ori operatiile logice (i)-(v) din definitia 16 unor propozitii initiale, utilizand eventual parantezele rotunde; propozitiile initiale sunt sau propozitii elementare constante (reprezentate prin valorile de adevar a sau f) sau propozitii elementare variabile (care nu au precizate valorile de adevar, sunt reprezentate prin majuscule si sunt numite nedeterminate).

Definitia 19. Doua formule F₁ si F₂ construite pe aceeasi multime de propozitii elementare sunt echivalente daca si numai daca pentru orice valori logice ale propozitiilor elementare constituente iau aceleasi valori de adevar.

Observatie:

Daca formulele F₁ si F₂ sunt echivalente atunci formula F₁ F₂ ia valoarea logica a (adevarat) pentru orice valori logice ale variabilelor si reciproc.

Observatie:

Operatiile logice permit stabilirea unor echivalente care exprima proprietati ale operatiilor respective:

i. A A;  (dubla negatie);

ii. A B B A,

A B B A; (comutativitate);

iii. A (B C) (A B) C,

A (B C) (A B) C; (asociativitatea);

iv. A (B C) (A B) (A C),

A (B C) (A B) (A C);  (distributivitatea);

v. A A A,

A A A, (idempotenta);

vi. A f A;

vii. A a A;

viii. (A B) (A B) (B A);

ix. (A B) (A B) A B);

x. (A T B) A B);

xi. A B A B);

A B A B);

xii. (A B) A B,

(A B) A B;  (Legile lui de Morgan).

Valabilitatea echivalentelor din (viii) si (ix) rezulta din urmatorul tabel:

Tabelul 27.

Aceleasi proprietati semnifica faptul ca echivalenta A B se poate exprima prin implicatie si conjunctie ((A B) (B A)), sau prin conjunctie, disjunctie si negatie: ((A B) A B)).

Proprietatea (x) evidentiaza faptul ca implicatia (A B) se poate exprima prin disjunctie si negatie ( A B), justificarea ei putandu-se face prin tabelul:

Tabelul 28.

Proprietatile de la punctul (xi) exprima faptul ca conjunctia se poate scrie in functie de disjunctie si negatie iar disjunctia se poate scrie in functie de conjunctie si negatie.

Aceste posibilitati de explicitare a unor operatii logice in functie de altele dovedesc faptul ca operatiile logice definite nu sunt independente.

Daca se remarca faptul ca toate operatiile logice se pot exprima prin grupul de baza conjunctie, disjunctie, negatie (sau mai mult prin unul din grupurile conjunctie-negatie sau disjunctie-negatie) si daca se tine cont de comutativitatea, asociativitatea si distributivitatea conjunctiei si disjunctiei atunci se poate pune in evidenta analogia cu algebra; disjunctia este denumita atunci adunare logica (suma logica) iar conjunctia este denumita inmultire logica (produs logic).

Observatie: Operatiile logice conjunctie si disjunctie se numesc duale una alteia; negatia este duala negatiei. Legea dualitatii stabileste faptul ca formulele duale sunt echivalente.

Definitia 20. In multimea propozitiilor distingem urmatoarele tipuri de propozitii:

i. propozitii constante cu unica valoare de adevar a, numite si tautologii (legi logice);

ii.   propozitii constante cu unica valoare f, numite si contradictii;

iii. propozitii realizabile care sunt adevarate cel putin in anumite conditii.

Problema care se pune in continuare este problema decidabilitatii adica problema stabilirii, printr-un numar finit de operatii, daca o formula data este realizabila sau nu, daca este identic adevarata sau nu.

Reprezentarea formulelor sub asa-numite forme normale simplifica foarte mult problema decidabilitatii.

Definitia 21. Se numeste produs elementar (suma elementara) un produs (o suma) de variabile si/sau negatii ale variabilelor.

Propozitia 14. i. Pentru ca un produs elementar sa fie identic fals este necesar si suficient ca el sa contina cel putin doi factori, unul fiind negatia celuilalt.

ii. Pentru ca o suma elementara sa fie identic adevarata este necesar si suficient ca ea sa contina cel putin doi termeni, unul fiind negatia celuilalt.

Demonstratie:

i. Fie F = p₁, p.. p_k un produs elementar de k factori (variabile sau negatii de variabile);

Suficienta:

Presupunem ca exista astfel incat i j si p_i = p_j. Atunci pentru orice valori de adevar ale variabilelor valoarea de adevar a produsului este f deoarece p_j = a implica p_i = p_j = a = f implica F = f iar p_j = f implica F = f.

Necesitatea:

Presupunem ca F s f adica , pentru orice valori de adevar ale variabilelor, valoarea de adevar a formulei (a produsului) este f.

Presupunem prin absurd ca nu exista doi indici astfel incat p_i = p_j. Atunci dand tuturor variabilelor valoare de adevar a, in produs neexistand negatii ale variabilelor rezulta ca valoarea de adevar a produsului este a, ceea ce evident contrazice ipoteza.

ii. Demonstratia este analoga demonstratiei de la (i):

Suficienta:

Fie F = p₁ + p₂ + + p_k o suma elementara de variabile sau negatii ale variabilelor. Presupunem ca exista astfel incat p_i = p_j (i j)s daca p_j = a atunci evident F = a (deoarece A + a = a, A formula). Daca p_j = f implica p_i = p_j = a adica F = a. Deoarece p_j poate lua doar aceste doua valori si deoarece in ambele situatii, independent de valorile de adevar ale celorlalte variabile, suma elementara F este adevarata, rezulta imediat ca F s a

Necesitatea:

Fie F s a. Presupunem ca F contine doar variabile (adica nu exista i j, : p_i = p_j), atunci dand valoarea logica de adevar f tuturor variabilelor rezulta F = f ceea ce contrazice ipoteza ca F s a. Deci presupunerea facuta este falsa iar propozitia este complet demonstrata.

Definitia 2 i. Fiind data o formula, numim forma normala disjunctiva (FND) a formulei date o formula echivalenta cu aceasta si care este o suma de produse elementare construite din aceleasi variabile ca si formula data.

ii. Se numeste forma normala conjuctiva (FNC) a formulei date o formula echivalenta cu aceasta, care este un produs de sume elementare construite din aceleasi variabile ca si formula data.

Observatie

In baza interdependentei operatiilor logice, a proprietatilor acestora si a legii dualitatii rezulta ca orice formula are cel putin o FND si o FNC

Observatie:

i. Pentru ca o formula sa fie identic adevarata este necesar si suficient ca fiecare factor al FNC a formulei date sa aiba cel putin o pereche de termeni astfel incat unul sa fie negatia celuilalt.

ii.Pentru ca o formula sa fie identic falsa este necesar si suficient ca fiecare   termen al FND a formulei date sa aiba cel putin o pereche de factori astfel incat unul sa fie negatia celuilalt.

Valabilitatea acestor afirmatii rezulta din propozitia 13.

Definitia 23. i. Se numeste forma normala disjunctiva perfecta (FNDP) a unei formule date care contine un numar dat de variabile distincte, o FND a formulei respective care satisface conditiile:

- nu contine doi termeni identici,

- nici un termen nu contine doi factori identici,

- nici un termen nu contine simultan un factor si negatia sa,

- in fiecare termen este prezenta fiecare variabila sau negatia sa.

ii. Similar, se numeste forma normala conjunctiva perfecta (FNCP) a unei formule date, o FNC a acesteia care satisface urmatoarele conditii:

- nu contine doi factori identici,

- nici un factor nu contine doi termeni identici,

- nici un factor nu contine simultan un termen si negatia sa,

- in fiecare factor este prezenta fiecare variabila sau negatia sa.

Observatie:

Pentru orice formula neidentic falsa se poate gasi o FNDP si pentru orice formula neidentic adevarata se poate gasi o FNCP, aceste forme fiind intotdeauna unice. Atunci, evident, pentru o formula neconstanta exista si sunt unice FNDP si FNCP corespunzatoare.

Un algoritm de determinare a FNDP a unei formule date contine urmatoarele etape:

i. Determinarea unui FND pentru formula data (folosind explicitarile operatiilor logice in functie de conjunctie, disjunctie si negatie si proprietatea de distributivitate a conjunctiei fata de disjunctie);

ii. Introducerea variabilelor care lipsesc in fiecare termen in baza echivalentei T xT x T unde T este termenul iar x este variabila care lipseste;

iii. Eliminarea termenilor identici sau a factorilor identici dintr-un termen (pe baza proprietatii de idempotenta);

iv.  Eliminarea termenilor care contin simultan un factor si negatia sa, acesti termeni fiind expresii identic false care nu afecteaza valoarea de adevar a formulei (propozitia 13).

Algoritmul de determinare a FNCP a unei formule date este similar, in etapa a (ii)-a folosindu-se echivalenta T (x T) ( x T).

O problema de diagnosticare

Presupunem ca analizam un ansamblu de fenomene generate de diverse cauze, a caror influenta asupra fiecarui fenomen al ansamblului, considerat izolat, o cunoastem. Tinand seama de interdependentele variate care pot exista intre diverse cauze (practic in numar destul de mare) si diversele fenomene (efecte) ce pot apare, este foarte greu de precizat in ce conditii un fenomen este bine determinat de un ansamblu de cauze si de asemenea nu este imediata determinarea modului in care o anumita cauza poate determina diverse fenomene (efecte).

Daca multimea cauzelor care influenteaza un fenomen oarecare este relativ redusa, problema este rezolvabila, fara mari dificultati, utilizand elemente de logica matematica. Situatiile mai generale in care apare un numar considerabil de cauze si efecte, sunt de asemenea rezolvabile cu ajutorul sistemelor de calcul.

Problema pe care o vom aborda, datorita interdependentelor dintre cauze si efecte, este de fapt o problema de decizie, deci o problema de alegere a variantei optime (variantelor optime) dintr-o multime de variante posibile.

Consideram cazul cand existenta a m cauze X_i (i=1,2,.,m) poate determina producerea fenomenelor Y_j (j=1,2,.,n).

Fie

Y_j propozitia: "sistemul z se afla in starea Y_j";

Y_j propozitia: "sistemul z nu se afla in starea Y_j";

X_i propozitia: "cauza X_j actioneaza asupra sistemului z";

X_i propozitia: "cauza X_j nu actioneaza asupra sistemului z".

Presupunem ca legaturile "cauze-efecte (stari)" sunt reprezentate de un sistem de formule de forma:

f_i (X₁,., X_m, Y₁,., Y_n) f (i = 1,2,.,p)

g_j (X₁,., X_m, Y₁,., Y_n) a (j = 1,2,.,q)

unde p, q I N.

Tinand seama de (1) si (1') echivalenta

(X_i X_i) (Y_j Y_j) a  (2)

devine

a (2')

unde

a_iI i = 1,2,.,m;

b_jI j = 1,2,.,n;

si

X¹ = X, X⁰ = X

Din (2') deducem ca exista a a a_m b b b_nI astfel ca

a

adica

. a

ceea ce exprima faptul ca starea este posibil sa fie determinata de cauza .

Rezumat

Structurile algebrice de baza implicate in proiectarea si optimizarea circuitelor sunt laticile, algebrele booleene si inelele booleene.

O latice este o multime nevida, inzestrata cu o relatie binara (reflexiva, antisimetrica si tranzitiva), ale carei oricare doua elemente admit un cel mai mare minorant si un cel mai mic majorant. Echivalent, o latice poate fi definita si ca o multime nevida inzestrata cu doua operatii comutative, asociative, idempotente care satisfac totodata si relatiile de absorbtie. Un principiu al dualitatii are loc in orice latice: din orice afirmatie adevarata relativa la elementele unei latice si la operatorii din definitie se deduce, prin inversarea operatorilor, o alta afirmatie adevarata.

Se numeste algebra booleana orice latice distributiva cu prim si ultim element, in care orice element admite complement. Primul si ultimul element din latice se vor numi element "zero" si respectiv element "unitate" ale algebrei booleene. Existenta complementelor permite definirea unui operator unar de complementariere (negare). Principiul dualitatii intr-o algebra booleana va impune, suplimentar, ca negatiile sa ramana neschimbate, iar constantele 0 si 1 sa se inverseze.

Inelul boolean este un inel (cu operatia aditiva comutativa, asociativa, cu element neutru si cu toate elementele simetrizabile; cu operatia multiplicativa asociativa si distributiva fata de operatia aditiva) cu element unitate (element neutru fata de operatia multiplicativa) in care operatia multiplicativa este idempotenta (orice element multiplicat cu el insusi ramane neschimbat).

Structurile de algebra booleana si inel boolean sunt echivalente: orice algebra booleana poate fi organizata ca un inel boolean si reciproc, orice inel boolean poate fi organizat ca o algebra booleana. Mai mult, in ambele cazuri, elementele neutre din inelul boolean coincid cu elementul zero respectiv elementul unitate din algebra booleana.

Exemple reprezentative de algebre/inele booleene: multimea partilor unei multimi A(X), algebra booleana binara B(2), algebra booleana cuaternara B(4), inelul claselor de resturi modulo 2 Z

Se numeste propozitie o combinatie determinata de termeni (sau simboluri) care exprima o afirmatie concreta in legatura cu un obiect sau fenomen. In cadrul logicii propozitiilor, propozitiile satisfac legea tertului exclus si legea contradictiei. Calculul propozitiilor se refera la a forma, din propozitii date, utilizand anumite conective (si, sau, daca .atunci, negatia) noi propozitii. Generalizand notiunea de propozitie, se considera propozitia o exprimare a unei informatii concrete referitoare la un obiect sau fenomen. Paralelismul cifra binara (0 sau 1) - propozitie logica (adevarata sau falsa) poate fi extins prin exprimarea prin legi logice a operatiilor aritmetice binare care la randul lor modeleaza matematic dispozitivele tehnice bistabile (de tip inchis - deschis, magnetizat - nemagnetizat, tensiune joasa - tensiune inalta).