Arhitectura Calculatoarelor

Funcţii booleene

În algebra booleană lucrăm pe mulţimea de valori booleene B={0, 1}.

O funcţie booleană cu n intrări şi m ieşiri este o funcţie matematică f:Bⁿ->B^m.

Deoarece domeniul şi codomeniul unei astfel de funcţii sunt mulţimi discrete, funcţiile booleene pot fi definite prin tabele de adevăr:

Numărul de funcţii booleene cu n intrări şi m ieşiri este |B^m|^|Bn|, adică (2^m)²ⁿ.

De exemplu, pentru n=2 variabile şi m=1 ieşiri avem 2²²=2⁴=16 funcţii booleene posibile:

Formula	Denumire
x + 0 = x
x · 1 = x
x + 1 = 1
x · 0 = 0
x + x = x	idempotenţă
x · x = x
x = x	dublă negaţie
x + x = 1	complementaritate
x · x = 0
x + y = y + x	comutativitate
x · y = y· x
(x + y) + z = x + (y + z)	asociativitate
(x · y) · z = x · (y · z)
x · (y + z) = (x · y) + (x · z)	distributivitate
x + (y · z) = (x + y) · (x + z)
x · y + x · y = x	unificare
(x + y) · ( x + y ) = x
x + x · y = x	absorbţie
x · ( x + y) = x
( x + y ) · y = x · y
( x · y ) + y = x + y
x + y = x · y	De Morgan
x · y = x + y

Forme normale

Pentru o funcţie oarecare, putem obţine forma normală disjunctivă (FND) descriind combinaţiile de valori pentru variabilele de intrare pentru care funcţia are valoarea 1, respectiv putem obţine forma normală conjunctivă descriind combinaţiile de valori pentru variabilele de intrare diferite de cele pentru care funcţia are valoarea 0.

Fie următorul exemplu de funcţie booleană:

Observăm că f(x, y, z) = 1 dacă şi numai dacă:

• x = 0 şi y = 0 şi z = 0 sau
• x = 0 şi y = 1 şi z = 0 sau
• x = 0 şi y = 1 şi z = 1 sau
• x = 1 şi y = 0 şi z = 0

Din această descriere obţinem uşor forma normală disjunctivă:

f(x, y, z) = x y z + x y z + x y z + x y z

în mod asemănător, observăm că f(x, y, z) != 0 dacă şi numai dacă:

• x != 0 sau y != 0 sau z != 1 şi
• x != 1 sau y != 0 sau z != 1 şi
• x != 1 sau y != 1 sau z != 0 şi
• x != 1 sau y != 1 sau z != 1

Din această descriere obţinem uşor forma normală conjunctivă (FNC):

f(x, y, z) = (x + y + z) (x + y +z) (x + y + z) (x + y + z)

Un set de generatori este o mulţime de operatori prin intermediul cărora poate fi exprimată orice funcţie booleană. Se poate arăta că mulţimea {NOT, AND, OR} este mulţime de generatori, deoarece orice funcţie booleană poate fi scrisă în forma normală conjunctivă (conjunţie de disjunţii) sau în forma normală disjunctivă (disjunţie de conjunţii). În plus, conform legilor De Morgan, putem deduce că doar doi dintre aceştia (NOT şi AND sau NOT şi OR) pot forma mulţimi de generatori.

Se poate arăta că exista mulţimi de generatori cu un singur element. Un astfel de caz este {NAND}. Aceasta este mulţime de generatori deoarece prin NAND putem exprima operatorii NOT, AND, OR, şi ştim despre aceştia că formează o mulţime de generatori.

Exerciţii

1. Să se demonstreze că numărul de funcţii booleene cu n intrări şi m ieşiri este (2^m)²ⁿ.
2. Să se arate că {NAND} este mulţime de generatori.
3. Folosind axiomele şi teoremele algebrei booleene, construiţi, pornind de la FNC sau FND, forme "condensate" (mai simple) pentru funcţiile booleene date prin tabelele de adevăr:

   x	y	z	f1(x, y, z)
   0	0	0	0
   0	0	1	1
   0	1	0	0
   0	1	1	0
   1	0	0	1
   1	0	1	1
   1	1	0	1
   1	1	1	1

   x	y	z	f2(x, y, z)
   0	0	0	0
   0	0	1	0
   0	1	0	0
   0	1	1	1
   1	0	0	0
   1	0	1	1
   1	1	0	1
   1	1	1	1

   x	y	z	f3(x, y, z)
   0	0	0	0
   0	0	1	0
   0	1	0	1
   0	1	1	1
   1	0	0	0
   1	0	1	1
   1	1	0	1
   1	1	1	1

---

© 2006 Marta Gîrdea