Algebra boleana, varialbili e funzioni logiche

Algebra Booleana 1 ALGEBRA BOOLEANA: VARIABILI E FUNZIONI LOGICHE Andrea Bobbio Anno Accademico 2000-2001 Algebra Booleana 2 Calcolatore come rete logica Il calcolatore pu essere visto come una rete logica cio come o e 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 e l'appartenenza ad un livello contrassegnato alto e ad un livello contrassegnato basso. Questi livelli sono identificati tramite una coppia di simboli: 0 Low False Open 1 High True Close Algebra Booleana 3 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 e binari. Nel 1938 Shannon ha dimostrato come l'algebra booleana potesse essere presa a fondamento per la progettazione di circuiti logici digitali. Algebra Booleana 4 Elementi dell'Algebra Booleana Vengono definiti i seguenti concetti: variabili booleane operatori booleani funzioni booleane porte logiche circuiti logici - combinatori - sequenziali Algebra Booleana 5 Variabili Booleane Una variabile booleana una variabile binaria che pu assumere e o esclusivamente due valori logici che saranno denotati con 0 e 1. Se x una variabile booleana, vale quindi la seguente definizione e formale: x=0 x=1 se se x=1 x=0 Algebra Booleana 6 Operatori Booleani Si definiscono gli operatori booleani o logici fondamentali: NOT AND OR Negazione Logica Prodotto Logico Somma Logica Algebra Booleana 7 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: u not(x) x x -x Algebra Booleana 8 Negazione o Complementazione / 2 Rappresentazione dell'operazione not(x) con la tavola della verit: a x not(x) 0 1 1 0 Propriet a not(not(x)) = x 1=1 0 =1 = 0 =1 Algebra Booleana 9 Prodotto Logico (AND) Definizione informale L'operazione di prodotto logico fra due (o pi) variabili fornisce il u 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 xy xy Algebra Booleana 10 Prodotto Logico (AND) / 2 Rappresentazione dell'operazione x y con la tavola della verit: a x y xy 0 0 1 1 0 1 0 1 0 0 0 1 Propriet a x0=0 x1=x xx=x xx=0 Algebra Booleana 11 Somma Logica (OR) Definizione informale L'operazione di somm