arhitectura calculatoarelor — seminarul 1

A R H I T E C T U R A C A L C U L A T O A R E L O R

E M I N A R U L 1

U P R I N S

Funcţii booleene.Axiomele şi teoremele algebrei booleeneForme normaleGeneratoriExerciţii

U N C Ţ I I B O O L E E N E

Î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:Bn->Bm.

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

x y f(x, y)

0 0 1

0 1 0

1 0 1

1 1 1

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

n.

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

x y f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

id 0 x AND y x y x XOR y x OR y x NOR y x = y NOT y y=>x NOT x x=>y x NAND y id 1

A X I O M E L E Ş I T E O R E M E L E A L G E B R E I B O O L E E N E

Formula Denumire

x + 0 = x

x · 1 = x

x + 1 = 1

x · 0 = 0

Arhitectura Calculatoarelor — Seminarul 1 http://thor.info.uaic.ro/~marta/caos/S1/

1 of 3 21.11.2011 20:03

x + x = xidempotenţă

x · x = x

x = x dublă negaţie

x + x = 1complementaritate

x · x = 0

x + y = y + xcomutativitate

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 = xunificare

(x + y) · ( x + y ) = x

x + x · y = x

absorbţiex · ( x + y) = x

( x + y ) · y = x · y

( x · y ) + y = x + y

x + y = x · yDe Morgan

x · y = x + y

F O R M E N O R M A L E

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

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

x y z f(x, y, z)

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 0

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

x = 0 şi y = 0 şi z = 0 saux = 0 şi y = 1 şi z = 0 saux = 0 şi y = 1 şi z = 1 saux = 1 şi y = 0 şi z = 0

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


2 of 3 21.11.2011 20:03

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

Sus|Index

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 şix != 1 sau y != 0 sau z != 1 şix != 1 sau y != 1 sau z != 0 şix != 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)

G E N E R A T O R I

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 degeneratori deoarece prin NAND putem exprima operatorii NOT, AND, OR, şi ştim despre aceştia că formează o mulţime degeneratori.

X E R C I Ţ I I

Să se demonstreze că numărul de funcţii booleene cu n intrări şi m ieşiri este (2m)2n.1.

Să se arate că {NAND} este mulţime de generatori.2.

Folosind axiomele şi teoremele algebrei booleene, construiţi, pornind de la FNC sau FND, forme "condensate" (maisimple) pentru funcţiile booleene date prin tabelele de adevăr:

3.

© 2006 Marta Gîrdea


3 of 3 21.11.2011 20:03

arhitectura calculatoarelor — seminarul 1

Documents