Algebra Booleana: Variabili e Funzioni Logiche, Appunti di Informatica

Algebra Booleana

1 Algebra Booleana ALGEBRA BOOLEANA: VARIABILI E FUNZIONI LOGICHE Andrea Bobbio Anno Accademico 2000-20012

Calcolatore come rete logica

Il calcolatore può essere visto come una rete logica cioè come un insieme di dispositivi chiamati porte logiche opportunamente connessi. Le porte logiche sono dispositivi capaci di eseguire operazioni logiche su segnali binari. I segnali binari sono livelli di tensione. Il valore esatto della tensione del segnale non è significativo: conta l'appartenenza ad un livello contrassegnato alto e ad un livello contrassegnato basso. Questi livelli sono identificati tramite una coppia di simboli: 0 1 Low High False True Open Close3

Algebra Booleana

Le tecniche di composizione delle porte logiche in una rete sono derivate da una particolare algebra operante su variabili binarie e chiamata Algebra Booleana (o Switching Algebra). L'algebra Booleana prende il nome dal matematico inglese George Boole (1815-1864) autore del testo The mathematical analysis of logic. A lui è legato lo sviluppo della logica simbolica e degli operatori binari. Nel 1938 Shannon ha dimostrato come l'algebra booleana potesse essere presa a fondamento per la progettazione di circuiti logici digitali.4

Elementi dell'Algebra Booleana

Vengono definiti i seguenti concetti: o variabili booleane ¿ operatori booleani o funzioni booleane porte logiche » circuiti logici - combinatori - sequenziali5

Variabili Booleane

Una variabile booleana è una variabile binaria che può assumere esclusivamente due valori logici che saranno denotati con 0 e 1. Se x è una variabile booleana, vale quindi la seguente definizione formale: x=0 x=1 se se x = 06

Operatori Booleani

Si definiscono gli operatori booleani o logici fondamentali: NOT Negazione Logica AND Prodotto Logico OR Somma Logica7

Negazione o Complementazione

Definizione informale

Trattasi di una operazione unaria che restituisce il valore logico opposto a quello della variabile di ingresso. Rappresentazione come operatore Per rappresentare il complemento di una variabile x vengono usate varie notazioni. Fra le più comunemente usate ricordiamo: not(x) x x − x8

Negazione o Complementazione / 2

Rappresentazione dell'operazione not(x) con la tavola della verità

x not (x) 0 1 1 0

Proprietà

not(not(x)) = x Ī = 1 0 = 1 = 0 = 19

Prodotto Logico (AND)

Definizione informale

L'operazione di prodotto logico fra due (o più) variabili fornisce il valore logico 1 se e solo se tutte le variabili assumono valore logico 1. Rappresentazione come operatore Per rappresentare il prodotto logico di due variabili x e y si usa la notazione: x and y x . y xy10

Prodotto Logico (AND) / 2

Rappresentazione dell'operazione x · y con la tavola della verità

x y x. y 0 0 0 0 1 0 1 0 0 1 1 1

Proprietà

x.0 = 0 x . 1 = x x . x = x x.x=011

Somma Logica (OR)

Definizione informale

L'operazione di somma logica fra due (o più) variabili fornisce il valore logico 1 se e solo se almeno una delle variabili assume valore logico 1. Rappresentazione come operatore Per rappresentare la somma logica di due variabili x e y si usa la notazione: xor y x+y12

Somma Logica (OR) / 2

Rappresentazione dell'operazione x + y con la tavola della verità

x y x + y 0 0 0 0 1 1 1 0 1 1 1 1

Proprietà

x +0 = x x + 1 = 1 x+ x = x x + x = 113

Porte Logiche

Le porte logiche sono dispositivi elettronici capaci di eseguire op- erazioni logiche su variabili booleane. A A · B B A A + B B A A14

Porta AND

A A · B B Alcune proprietà della porta AND. A 0 A.0= 0 0 A A A ·1 = A 1 A A A . A = A A A 0 A. A = 0 A15

Porta OR

A B A + B Alcune proprietà della porta OR. A A A + 0 = A 0 A 1 A+ 1 = 1 1 A A A + A = A A A 1 A + A = 1 A16

Proprietà dell'algebra Booleana

Le proprietà degli operatori logici NOT, AND e OR, permettono di stabilire le seguenti proprietà.

Idempotenza

x + x = x x . x = x

Elemento nullo (forcing function)

x+ 1 = 1 x.0= 0

Proprietà Commutativa

x+y =y+ x x.y=y .x

Proprietà Associativa

x + (y + z) = (x + y) + 2 = x + y + z x . (y . z) = (x . y) . z = x . y . z17

Reciprocità dei Teoremi dell'algebra Booleana

Le proprietà che valgono per l'operatore + valgono anche per l'operatore · purchè si scambino gli 1 con gli 0 (e viceversa).18

Teoremi dell'algebra Booleana

Distributività

La proprietà distributiva vale sia rispetto alla somma di prodotti (come nell'algebra ordinaria) che rispetto al prodotto di somme. x . y + x . z = x . (y + z) (x + y) . (x + z) = x + y · z19

Teoremi dell'algebra Booleana

Verifica dei teoremi di distributività mediante la tavola della verità

x y z xy xy + xz y+ z x(y + z) 00 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 x y z yz x+yz x+ y x+ z (x+y)(x+z) 00 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 120

Teoremi dell'algebra Booleana

Assorbimento

Il teorema dell'assorbimento può assumere varie forme. x + (x . y) = x x . (x + y) = x (x + y) . y = x . y x. y+y = x+y21

Teoremi dell'algebra Booleana

Teoremi di De Morgan

x . y = x + y x+y = x.y22

Teoremi dell'algebra Booleana

Legge di Cancellazione

Nell'algebra booleana non vale la legge di cancellazione Dall'espressione: x+y = x+z non è possibile dedurre: y = 223

Teoremi dell'algebra Booleana

Legge di Cancellazione

Si dimostra la non validità della legge di cancellazione medi- ante la tavola della verità. x y z x+y x+z x+y=x+zy=z 000 0 0 1 1 001 0 1 0 0 010 1 0 0 0 011 1 1 1 1 100 1 1 1 1 101 1 1 1 0 110 1 1 1 0 111 1 1 1 124

Algebra degli Insiemi

L'Algebra degli insiemi (o Teoria degli insiemi) è formalmente identica all'algebra booleana a condizione che: -> Le variabili logiche siano interpretate come possibili sottoin- siemi di un insieme universo U . => Il prodotto logico · (AND) sia interpretato come l'operazione di intersezione fra insiemi. => La somma logica + (OR) sia interpretata come l'operazione di unione fra insiemi. => Il valore 1 (elemento neutro rispetto a .) sia sosti- tuito dall'insieme universo U (elemento neutro rispetto all'intersezione). => Il valore 0 (elemento neutro rispetto a +) sia sostituito dall'insieme vuoto ¢ (elemento neutro rispetto all'unione). È quindi possibile dimostrare le proprietà e i teoremi dell'algebra booleana ricorrendo alla rappresentazione degli insiemi medianti diagrammi di Venn.25

Operazione di nand logico

Definizione informale

L'operazione di nand logico è l'operazione negata dell'operazione and. Il simbolo nand è una contrazione di not and. Quindi l'operazione di nand logico fra due (o più) variabili fornisce il valore logico 1 se almeno una delle variabili assume il valore logico 0. Rappresentazione come operatore Per rappresentare il nand logico non esiste un simbolo specifico. x nand y A B A · B26

Operazione nand logico / 2

Rappresentazione dell'operazione x nand y con la tavola della verità

x y x nand y 0 0 1 0 1 1 1 0 1 1 1 0

Proprietà

x nand 0 = 1 x nand 1 = x x nand x = x x nand x = 1 x nand y = x . y27

Porta NAND

Con il solo operatore NAND, si possono rappresentare gli opera- tori NOT, AND e OR. A A Da A . A = A A A A A . B = A . B B A A · B B A A . B = A + B B A A + B B28

Operazione di nor logico

Definizione informale

L'operazione di nor logico è l'operazione negata dell'operazione or. Il simbolo nor è una contrazione di not or. Quindi l'operazione di nor logico fra due (o più) variabili fornisce il valore logico 1 se nessuna delle variabili assume il valore logico 1. Rappresentazione come operatore Per rappresentare il nor logico non esiste un simbolo specifico. x nor y A B A + B C29

Operazione nor logico / 2

Rappresentazione dell'operazione x nor y con la tavola della verità

x y x nor y 0 0 1 0 1 0 1 0 0 1 1 0

Proprietà

x nor 0 = x x nor 1 = 0 x nor x = x x nor x = 0 x nory = x+y30

Porta NOR

Con il solo operatore NOR, si possono rappresentare gli operatori NOT, AND e OR. A A O A + A = A A C A A + B = A · B B A A · B B A A+B=A +B O B B A A + B31

Operazione di or esclusivo (exor) / 1

Definizione informale

L'operazione di or esclusivo (exor) fra due (o più) variabili fornisce il valore logico 1 se il numero delle variabili che assumono valore logico 1 è dispari. Rappresentazione come operatore Per rappresentare l'operatore exor si usa comunemente la seguente notazione: roy x exor y A B A@B32

Operazione or esclusivo (exor) / 2

Rappresentazione dell'operazione x exor y con la tavola della verità

x y roy 0 0 0 0 1 1 1 0 1 1 1 0

Proprietà

xe0= x x01 = x xox=0 xox=1 xey=roy33

Operazione or esclusivo (exor) / 3

Proprietp

xey=x. y+x . y l'operatore exor può essere visto come un comparatore di uguaglianza: if x = y then x @ y = 0 else x @ y = 1 l'operatore exor può essere visto come un invertitore control- lato: if x = 0 then x @y = y else x @ y = y34

Exor come invertitore controllato

Mettendo una variabile x come ingresso di una porta exor, si può ottenere in uscita il valore x stesso forzando il secondo ingresso a 0, o il valore complementato & forzando il secondo ingresso a 1. x x x 0 1 x 0 xe0= x 0 0 0 1 0 1 x 1 x01= x 0 1 1 1 1 035

Exor come comparatore di uguaglianza

Si abbiano due parole di 4 bit (x3 x2 x1 x0) e (y3 92 91 30). La rete logica in figura verifica se le due parole sono uguali e diverse: in particolare se l'uscita è 0 le parole sono uguali, se l'uscita è 1 le parole sono diverse. X3 y3 X2 0 uguali y2 X1 1 diversi y1 X0 y036

Exor come verificatore di parità

Si abbia una parola di 8 bit con bit di parità (x7 x6 X5 x4 x3 x2 x1 20 xp). La rete logica in figura verifica se il numero totale di 1 della parola è pari o dispari: in particolare se l'uscita è 0 il numero di 1 è pari, se l'uscita è 1 il numero di 1 è dispari. X7 X6 X5 X4 X3 U X2 X1 X0 Xp