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