algebra booleana claudia raibulet [email protected]
TRANSCRIPT
![Page 2: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/2.jpg)
EserciziEsercizi
Si determini qual e’ il maggiore tra i seguenti valori rappresentati in MS e poi anche in CA2:
• 00111 ? 10001
• 101 ? 11101
• 01010 ? 10101
![Page 3: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/3.jpg)
Algebra booleanaAlgebra booleana Deve il suo nome a Boole che ne formalizzò le regole L’algebra booleana opera su variabili (“logiche” o
“booleane”) che possono assumere solamente due valori
1/0, vero/falso, on/off, chiuso/aperto
Il valore 1 è solitamente associato alla condizione logica vero (true, on, chiuso), mentre lo 0 è associato alla condizione logica falso (false, off, aperto)
![Page 4: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/4.jpg)
Algebra booleanaAlgebra booleana E’ adatta per rappresentare “eventi binari”, cioè
condizioni che possono assumere solo due valori• Esempio
Una lampadina può essere accesa (a questa condizione si associa il valore 1 o vero) oppure spenta (valore 0 o falso).
Le funzioni che operano sulle variabili booleane sono dette funzioni booleane e possono produrre anch’esse solo i valori 0 e 1.
![Page 5: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/5.jpg)
Algebra booleanaAlgebra booleana
Una funzione booleana F, funzione di variabili booleane, v1,v2,...,vn si indica:
Può essere definita in vari modi:
• uno di questi consiste nello specificare i valori di F per tutte le possibili combinazioni delle variabili da cui essa dipende. Tale elenco di combinazioni viene detto tabella della verità
),,,( 21 nvvvF
![Page 6: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/6.jpg)
Algebra booleanaAlgebra booleana Esempio
F(v1,v2,v3) può essere definita come:
Ogni variabile booleana può assumere due valori, quindi, con n variabili si possono avere 2n possibili combinazioni
v3 v2 v1 F00
00
01
11
00
11
01
00
11
00
01
01
11
11
01
11
![Page 7: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/7.jpg)
Algebra booleana - esercizioAlgebra booleana - esercizio Esempio di descrizione di un evento mediante una
funzione booleana Un allievo passa l’esame se si verifica almeno una delle
seguenti condizioni:o supera sia il compito di esonero sia la prova oraleo non supera l’esonero, ma è sufficiente alla prova scritta di un
appello regolare e supera la prova orale
• Si può assegnare ad ogni evento una variabile booleana:
a esonero
b scritto regolare
c prova orale
![Page 8: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/8.jpg)
Algebra booleana - esercizioAlgebra booleana - esercizio Con 3 variabili booleane ci sono 8
(23) possibili combinazioni Si noti che per superare l’esame,
cioè S = 1, bisogna aver sostenuto e superato l’orale e l’esonero e/o lo scritto regolare
A stretto rigore di logica la condizione a = 0, b = 0, c = 1 non può verificarsi, in quanto si può accedere all’orale solo dopo aver superato una delle prove precedenti (o entrambe)
a b c S00
00
01
00
00
11
01
01
11
00
01
01
11
11
01
01
![Page 9: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/9.jpg)
Operatori logiciOperatori logici Le variabili booleane possono essere combinate da
operatori logici Tali operatori restituiscono anch’essi un valore
logico Gli operatori sono:
• AND
• OR
• NOT
• NAND
• NOR
• …
![Page 10: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/10.jpg)
ANDAND
Viene denotato dal simbolo • (da non confondere con il simbolo di prodotto aritmetico) e spesso sottinteso
Si applica a due operandi e produce un valore in accordo alle seguenti regole:• 0 • 0 = 0
• 0 • 1 = 0
• 1 • 0 = 0
• 1 • 1 = 1
Il risultato è vero se entrambi gli operandi sono veri
![Page 11: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/11.jpg)
OROR Viene denotato dal simbolo + (da non confondere
con il simbolo di addizione aritmetica) Si applica a due operandi e produce un valore in
accordo alle seguenti regole:• 0 + 0 = 0• 0 + 1 = 1• 1 + 0 = 1• 1 + 1 = 1
Il risultato è vero se almeno uno degli operandi è vero
![Page 12: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/12.jpg)
NOTNOT Viene indicato con il simbolo sopra la variabile
da negare (es. ) Si applica ad un solo operando (operatore unario) e
produce un valore in accordo alle seguenti regole:o o
Il risultato è il valore opposto (la negazione) di quello dell’operando; ovvero, se l’operando è falso l’uscita è vera e viceversa
01
10
a
![Page 13: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/13.jpg)
NANDNAND E’ equivalente ad un operatore AND negato
Si applica a due operandi e produce un valore in accordo alle seguenti regole:
o 0 NAND 0 = 1o 0 NAND 1 = 1o 1 NAND 0 = 1o 1 NAND 1 = 0
Il risultato è falso se entrambi gli operandi sono veri
BABA ANDNAND
![Page 14: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/14.jpg)
NORNOR E’equivalente ad un operatore OR negato
Si applica a due operandi e produce un valore in accordo alle seguenti regole:
o 0 NOR 0 = 1o 0 NOR 1 = 0o 1 NOR 0 = 0o 1 NOR 1 = 0
Il risultato è vero se entrambi gli operandi sono falsi
___________
ORNOR BABA
![Page 15: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/15.jpg)
EserciziEsercizi Dati i seguenti problemi, si chiede di scrivere la tabella
della verita’ dell’espressione logica che soddisfa le specifiche del problema, ricavare la funzione booleana corrispondente:
1. Una lampadina si accende quando si verifica almeno una delle seguenti condizioni:
– l’interruttore A e’ chiuso
– l’interruttore A non e’ chiuso, ma sono chiusi gli interruttori B e C
2. L’aria condizionata e’ funzionante quando si verificano tutte e tre le seguenti condizioni:
– i finestrini sono chiusi
– il treno e’ in movimento
– l’interruttore dell’aria condizionata e’ azionato
![Page 16: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/16.jpg)
Rappresentazione delle immaginiRappresentazione delle immagini BitMaP - scomposizione (discretizzazione) dell'immagine in
elementi di informazione poi codificati • Matrice di punti detti pixel (Picture Element)
• Qualità caratterizzata dalla risoluzione (numero di pixel per unità di misura)
• Elevato spazio occupato in memoria per avere buone risoluzioni
• Non è possibile un'eccessivo ZOOM perché non si notano più dettagli, si notano solo i pixel
0 0 0 0 0 00 0 0
0 0 0 0 0 00 0 0
0 0 0 0 0 01 0 0
0 0 0 0 1 01 0 0
0 0 0 1 0 01 0 0
0 0 1 0 0 01 0 0
0 1 0 0 0 01 0 0
1 0 0 0 0 01 0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
![Page 17: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/17.jpg)
Rappresentazione delle immaginiRappresentazione delle immagini
BitMaP - codifica dei pixel (profondita’ colore)• 1 bit Immagine b/n
• 4 bit Immagine 16 Colori o Livelli Grigio
• 8 bit Immagine 256 Colori o Livelli Grigio
• 16 bit Immagine 64K Colori
• 24 bit Immagine 16M Colori (True Color)
• 32 bit Immagine 16M Colori + Alpha Channel
![Page 18: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/18.jpg)
Rappresentazione delle immaginiRappresentazione delle immagini BitMaP: Formati di memorizzazione:
RAW: matrice dell'insieme di punti
TIFF(Tagged Image File Format): etichetteche descrivono proprietà seguite dai dati (24 bit,LZW, …)
GIF(Graphic Interchange Format): brevettocompuserve, possibile immagazzinare più immagini(schema di compressione LZW)
J FIF(J PEG File Interchange Format):implementa J PEG, presenza pixel trasparenti einterlacciamento
BMP(BitMaP): sviluppato da Microsoft e IBM perwindows ed OS/2 (non è compresso!)
PCX(PC Paintbrush): formato supportato danumerose applicazioni Microsoft (supporta RLE)
Formati compressi
![Page 19: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/19.jpg)
Rappresentazione delle immaginiRappresentazione delle immagini Vettoriali: descrizione dell'immagine attraverso elementi
grafici di alto livello (progettazione meccanica, elettronica architettonica, …)
Circle 98 66 50Polyline 0 48 88 152 88 48 0 48
![Page 20: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/20.jpg)
Rappresentazione delle immaginiRappresentazione delle immagini Vettoriali: codifica elementi di alto livello
• Figure geometriche semplici parametriche
• Rappresentazione compatta dell’informazione
• Indipendenza dal dispositivo di visualizzazione e dalla sua risoluzione
• Partano da un modello quindi e’ possibile avere un qualsiasi fattore di zoom
• Poco adatto a foto e immagini naturali, usato per la descrizione ad alto livello di informazione grafica
Conversione BitMaP – Vettoriali
• Facile da vettoriali a bitmap
• Complessa l’estrazione di elementi di alto livello dalle bitmap (sopratutto per immagini naturali)
![Page 21: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/21.jpg)
Rappresentazione delle immaginiRappresentazione delle immagini Vettoriali: formati di memorizzazione
PostScript: formato brevettato da Adobe per larappresentazione dei documenti (linguaggio per stampanti)
EPS (Encapsuled PostScript): usato per trasferire disegni traapplicazioni PostScript
PDF (Portable Document File): usato per la descrizione didocumenti e immagini (include ps e navigazioneipertestuale)
DXF (Drawing Exchange Format): usato per il progettomeccanico (proprietario Autodesk)
IGES (Initial Graphics Exchange Specifications): datigeometrici e topologici realizzati con programmi 3D
![Page 22: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/22.jpg)
Rappresentazione delle immaginiRappresentazione delle immagini
Tecniche di compressione:• Le immagini possono richiedere molto spazio per la loro
memorizzazione
Esempi di tecniche di compressione• 000000000011 10 volte 0, 2 volte 1
• Memorizzazione non di tutti i bit (riduzione di fedeltà rispetto all’originale ma spesso non è percepibile dall’occhio umano)
![Page 23: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/23.jpg)
Elaborazione delle immaginiElaborazione delle immagini
Dopo la digitalizzazione un’immagine può essere modificata modificando la sequenza di bit che la rappresenta
Ad esempio• Modifica dei colori
• Eliminazione oggetti rappresentati o loro sostituzione
• Trasmissione criptata delle pay-TV
![Page 24: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/24.jpg)
Codifica dei suoniCodifica dei suoniRappr. Analogica – analoga alla quantità fisica in esame; continuita’ nel tempo e continuita’ nelle ampiezze
Rappr. Digitale – Campionatura dell’onda sonora;Discretizzazione nel tempo, discretizzazionenelle ampiezze
![Page 25: Algebra Booleana Claudia Raibulet raibulet@disco.unimib.it](https://reader036.vdocumenti.com/reader036/viewer/2022081516/5542eb5a497959361e8c6ee2/html5/thumbnails/25.jpg)
Elaborazione dei suoniElaborazione dei suoni
Dopo la digitalizzazione ... come per le immagini è possibile• eliminare parte del suono (es. rumori di fondo)
• modificare il suono (es. voci distorte)
• ...