Reti Combinatorie E Algebra Di Boole

Reti Combinatorie E Algebra

Di Boole

Programma

 Funzioni di commutazione

 Espressioni e reti

 Algebra di commutazione

 Espressioni POS/SOP

 Reti all-NAND e all-NOR

Funzioni Di Commutazione

Sistema Digitale

Immagazzinamento Elaborazione

Funzioni Di Commutazione

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

0 1 1 0 1 0 0 1 a_i b_i c_i s_i

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

0 0 0 1 0 1 1 1 a_i b_i c_i c_i+1

c_i a_i b_i

s_i c_i+1

Funzioni Di Commutazione

c₀ a₀ b₀

s₀ c₁

a₁ b₁

s₁ c₂

a₂ b₂

s₂ c₃

a₃ b₃

s₃ c₄

Funzioni Di Commutazione

Una funzione di commutazione è una funzione binaria di variabile binaria.

0 1 000

001

010

011 100 101 110 111

Funzioni Di Commutazione

0 1

1 0 f₀ f₁ f₂ f₃

1 1 0

1 0 0

Funzioni di una variabile

) (x NOT

__x

Funzioni costanti Funzione Identità

Funzioni Di Commutazione

0 0 0 1 1 0 1 1

0 0 1 0

g₀ g₁ g₂ g₃ g₄ g₅ g₆ g₇ g₈ g₉ g₁₀ g₁₁ g₁₂ g₁₃ g₁₄ g₁₅ 0

0 1 1 0

0 0 1 0 0 0 0

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1 x₁ x₀

Funzioni di due variabili

) (x₁x₀

AND XOR(x₁x₀) OR(x₁x₀) NOR(x₁x₀) NAND(x₁x₀)

Funzioni Di Commutazione

Utilizzeremo la funzione di una variabile NOT )

(x

NOT ^__x

Utilizzeremo le due funzioni di due variabili AND e OR )

, (x₁ x₀ AND

) ,

(x₁ x₀ OR

0 1x x

0

1 x

x 

Espressioni E Reti

1. I terminali di input sono reti combinatorie

2. Se N₁ e N₂ sono reti combinatorie allora lo sono anche:

N₁ N₂ N₁ N₂ N₁ N₂

Espressioni E Reti

1. Le variabili e le costanti sono espressioni booleane

2 1E

E E₁  E₂ E^__₁ E^__₂

2. Se e sono espressioni booleane allora lo sono anche:E₁ E₂

Espressioni E Reti

1 x₃ x₂ x₁

x₃ x₁

x₁ x₂ x₁ x₂

x₁ x₂ x₃ x₁ + x₃

(x₁ + x₃ )1

Ogni rete di commutazione data calcola una funzione di commutazione

x₁ x₂ x₃ + (x₁ + x₃ )1

Espressioni E Reti

Data una funzione di commutazione esiste una rete combinatoria che la calcola

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

0 1 1 0 1 0 0 1 a_i b_i c_i s_i

Espressioni E Reti

Introduciamo la

Algebra di Commutazione

Un’algebra di commutazione è un insieme B di elementi (espressioni booleane) contenente le costanti 0 ed 1 con le seguenti operazioni:

1. Due operazioni binarie, AND e OR, che sono commutative, associative, idempotenti e godono delle proprietà di

assorbimento e di distributività reciproca.

2. Una operazione unaria, COMPLEMENTO (o NOT), con le proprietà di involuzione, complementarietà e legge di De Morgan

3. Le costanti 0 e 1 godono delle proprietà:

NOT(0) = 1

x 1=x x+0=x

Espressioni E Reti

Espressioni E Reti

Assioma: Ciascuna espressione assume il valore 0 o il valore 1 per ogni assegnazione dei valori alle sue variabili.

1. x = x 2. x y= y x 3. x x = x

5. x (y+z)= x y + x z 4. x x= 0

6. x (x+y)= x

7. (x y) z= x (y z)

Principio di dualità:

Data una espressione valida, otteniamo un’altra espressione valida:

1. Scambiando AND ed OR

Espressioni E Reti

4 2 3

1 4 3

2

1 ( )]

[x  x x  x x x  x x

Consideriamo la seguente espressione

per essa possiamo ricavare due forme standard

3 2

3

1x x x

x  

SOP POS

) )(

(x₁  x₂  x₄ x₂  x₃  x₄

4 2 3

1 4 3

2

1 ( )]

[x  x x  x x x  x x

4 2

3 1 4 3 2

1 ( )]

[x  x x x x x  x  x

4 2

3 1 4

3 2

1 ( )]

[x  x x x  x x  x  x

4 2

3 1 3 2 4

3 2

1 )

(x  x x x  x x x x  x  x

4 2

3 1 3 2 3

4 3 2 3

1x x x x x x x x x x x

x    







4 2

3

1x x x

x  

Espressioni E Reti

4 2 3

1 4 3

2

1 ( )]

[x  x x  x x x  x x

4 2

3

1x x x

x  

4 2

3 2

1 )( )

(x  x x  x  x

) )(

(x₁  x₂  x₄ x₃  x₂  x₄

Espressioni E Reti

Reti all-NAND

La funzione NAND ha la seguente tavola

0 0 0 1 1 0 1 1 x₁ x₀

1 1 1 0

E’ possibile mostrare che una qualunque espressione logica si può calcolare con una rete che utilizza la sola porta NAND.

Reti all-NAND

L’insieme AND, OR, NOT è un insieme funzionalmente completo

Occorre quindi mostrare che con l’utilizzo della sola porta NAND posso realizzare le tre funzioni AND, OR, NOT

Reti all-NAND

La prova discende dalle seguenti relazioni:

NAND(x,x)=NOT(AND(x,x))=NOT(x):

NAND(NAND(x, y), NAND(x, y)) =

NOT(AND(NAND(x, y), NAND(x, y)) = NOT(NAND(x,y) =

AND(x, y):

NAND(NAND(x, x), NAND(y, y)) =

NOT(AND(NAND(x, x), NAND(y, y)) = NOT(AND(NOT(x),NOT(y)) =

Reti all-NOR

In maniera del tutto analoga è possibile mostrare che una

qualunque espressione logica si può calcolare con una rete che utilizza la sola porta NOR.