Post on 01-May-2015
transcript
Casazza Andrea3EA
I.I.S. Maserati
IndiceIndice
Chi é Cosa ha fatto Cosa serve la sua teoria
Contenuti dell’algebra di Boole Esempi applicativi
Chi èChi è
Boole, George: nasce il 2 novembre 1815 a Lincoln (Lincolnshire, Gran Bretagna). George Boole muore nel 1864 a Ballintemple (County
Cork, Irlanda).
info
Cosa ha fattoCosa ha fatto Sviluppò assieme ad Auguste De Morgan la
logica matematica moderna e il metodo simbolico. Boole e De Morgan costruirono l'algebra della logica (o algebrea booleana), staccando la logica dalla filosofia (Logica Aristotelica) e legandola alla matematica.
info
Cosa serve la sua teoriaCosa serve la sua teoriaBoole ha voluto sviluppare una logica basata su due simboli, mentre per esempio la matematica si basa su un sistema di dieci cifre, per sviluppare la logica con il minor numero di simboli possibili. Solo nel secolo successivo questa logica assolutamente astratta e speculativa è stata impiegata nella costruzione dei primi computer.
info
Porte logichePorte logicheNell'affrontare l'algebra di Boole, bisogna tener
presente che siamo nella logica e non in un sistema di numerazione; la logica lavora, infatti, con due soli valori: 0 e 1 (non intesi come numeri!)
Le variabili logiche sono indicate generalmente con lettere maiuscole A, B, C, ...
Gli operandi principali sono tre:
1. la negazione o NOT (¯ oppure !) 2. la somma logica o OR ( + ) 3. il prodotto logico o AND ( • )
info
Porte logichePorte logicheLe possibili combinazioni tra le porte principali
sono: L'operatore NAND (cioè
la negazione del risultato dell'operazione AND)
L'operatore NOR, (cioè la negazione del risultato dell'operazione OR)
L'operatore XOR (detto anche OR esclusivo)
L'operatore XNOR (cioè la negazione del risultato dell'operazione XOR)
info
Porta logica ANDPorta logica ANDL' operazione AND (letteralmente e in
inglese) restituisce 1 (vero) se e solo se tutti gli operandi hanno valore 1 (vero), altrimenti
restituisce 0 (falso).
Nei circuiti digitali, la porta logica AND è un meccanismo comune per avere un
segnale di vero se un certo numero di altri segnali sono tutti veri.
info
Porta logica ORPorta logica ORL' operazione logica OR (letteralmente o in
inglese) restituisce 1 (vero) se almeno uno degli elementi è 1 (vero); altrimenti dicibile: OR
restituisce 0 (falso) se e solo se tutti gli operandi sono 0 (falso).
info
Porta logica NOTPorta logica NOTL'operatore NOT Restituisce il valore inverso di quello in entrata. Una concatenazione di NOT è semplificabile con un solo NOT in caso di dispari
ripetizioni o con nessuno nel caso di pari.
info
Funzioni logicheFunzioni logicheLe funzioni possono essere scritte sia in forma
canonica che non. Si ha la forma canonica quando ogni termine è
composto da tutte le variabili dela funzione.Es. di forma canonica: Y = ABC + A!BC + !A!
BC Es. di forma non canonica: Y = ABC + A!C +
AB!C (nel secondo termine è assente la variabile B).
info
Funzione booleanaFunzione booleanaIn matematica, una funzione booleana è una funzione
F(b1, b2, ..., bn)
di un numero n di variabili booleane bi che assumono valori nello spazio booleano B = {0, 1}, cosi come F
assume valori in B. Con un insieme di n variabili esistono funzioni possibili. Le funzioni booleane sono
inoltre importanti poiché sono isomorfe ai circiuti digitali cioè un circuito digitale può essere espresso tramite un’espressione booleana e viceversa, esse dunque svolgono un ruolo chiave nel progetto dei circuiti
digitali, ma trovano anche applicazione nella crittografia e nelle telecomunicazioni.
info
Funzioni booleaneFunzioni booleaneLe funzioni booleane fondamentali
sono la AND (solitamente indicata con il segno meno: - ), la OR (solitamente indicata con il segno più: +) e la NOT (solitamente indicata con il segno ¬ );
dalla combinazione delle funzioni boolene fondamentali si ottengono
tutte le altre possibili funzioni. Poiché le variabili possono assumere solo i valori 0 o 1 una funzione booleana con n variabili di input ha solo 2n
combinazioni possibili e può essere descritta dando una tabella, detta
tabella di verità, con 2n righe.info
ProprietàProprietàLe operazioni di somma e prodotto sono
commutative. Per ogni coppia di elementi x ed y appartenenti all’insieme A, si ha: (x ⊕ y) = (y
⊕ x); (x ⊗ y) = (y ⊗ x) • La somma è distributiva rispetto al prodotto e questo è distributivo rispetto alla somma. Per ogni
coppia di elementi x ed y appartenenti all’insieme A, si ha: (x ⊕ (y ⊗ z)) = (x ⊕ y) ⊗ (x ⊕ z); (x ⊗ (y ⊕ z)) = (x ⊗ y) ⊕ (x ⊗ z);
info
ProprietàProprietàO è l'elemento neutro per la
somma ed I è l'elemento neutro per il prodotto. Esistono
due elementi O, I tali che: per ogni elemento x appartenente
all’insieme A, x ⊕ O = x; x ⊗ I = x • Ogni elemento x
dell'insieme A ammette un complemento x' che è unico e
si indica con ∼ x. Per ogni elemento x appartenente
all’insieme A, esiste un elemento x' tale che: x ⊕ x' = I; x ⊗ x' = 0 Simboli usati per il complemento
sono: x' = ∼ x = xinfo
Variabili e costanti Variabili e costanti booleanebooleane
Tutti i simboli matematici consueti, possono essere usati per indicare uno dei due valori booleani, (O, I);
es. : A, B, C, oppure x, y, z, ....., oppure, ancora, x0, x1, x2,....... Se un simbolo è associato sempre allo
stesso valore booleano, esso rappresenta una costante. Se, invece esso può assumere volta per volta l'uno o l'altro dei due
possibili valori, esso rappresenta una variabile booleana.
info
Forma canonicaForma canonicaAbbiamo visto che è possibile
esprimere le funzionibooleane tramite la sua espressione
analitica oppure tramite la tabella di verità.
Le funzioni booleane possono essere scritte in vari modi ma
vi sono delle espressioni che vengono considerate standard.
Per far ciò definiamo i mintermini e i maxtermini
info
MinterminiMinterminiConsiderando una riga della tabella di verità sidefinisce mintermine il prodotto delle variabilibooleane relative a tal riga prese in forma diretta ocomplementata a seconda se assumono valore 1 o 0.
info
MaxterminiMaxterminiSi definisca maxtermine la somma delle
variabilibooleane prese in forma diretta o
negata a seconda seassumono valore 0 o 1.
Con n variabili abbiamo mintermini e maxtermini
info
Teorema di De MorganTeorema di De MorganDimostrazione del Teorema di DeMorgan
tramite tabella diVerità.
info
Mappa di KarnaughMappa di KarnaughLa mappa di Karnaugh è una metodologia esatta di sintesi di reti combinatorie a uno o più livelli. Queste sono una rappresentazione di una funzione booleana in modo da mettere in evidenza le coppie di mintermini o di maxtermini a distanza di Hamming unitaria (ovvero che differiscono di un solo bit). Siccome derivano da una meno intuitiva visione multidimensionale delle funzioni booleane in campo cartesiano, le mappe di Karnaugh risultano effettivamente applicabili a funzioni fino a 5 - 6 variabili.
info