Algebra Booleana
Claudia Raibulet
[email protected]
Esercizi

Si determini qual e’ il maggiore tra i seguenti
valori rappresentati in MS e poi anche in CA2:
•
•
•
00111 ? 10001
101 ? 11101
01010 ? 10101
Algebra 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)
Algebra 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.
Algebra booleana

Una funzione booleana F, funzione di variabili booleane,
v1,v2,...,vn si indica:
F ( v1 , v2 , , vn )

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à
Algebra 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
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
F
1
1
0
0
0
1
1
1
Algebra 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
o
supera sia il compito di esonero sia la prova orale
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
Algebra 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
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
S
0
0
0
1
0
1
0
1
Operatori 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
…
AND


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
OR


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
NOT


Viene indicato con il simbolo sopra la variabile
da negare (es. a )
Si applica ad un solo operando (operatore unario) e
produce un valore in accordo alle seguenti regole:
o 0 1
o

1 0
Il risultato è il valore opposto (la negazione) di
quello dell’operando; ovvero, se l’operando è falso
l’uscita è vera e viceversa
NAND

E’ equivalente ad un operatore AND negato
A NAND B  A AND B

Si applica a due operandi e produce un valore in accordo alle
seguenti regole:
o
o
o
o

0 NAND 0 = 1
0 NAND 1 = 1
1 NAND 0 = 1
1 NAND 1 = 0
Il risultato è falso se entrambi gli operandi sono veri
NOR

E’equivalente ad un operatore OR negato
___________
A NOR B  A OR B

Si applica a due operandi e produce un valore in accordo alle
seguenti regole:
o
o
o
o

0 NOR 0 = 1
0 NOR 1 = 0
1 NOR 0 = 0
1 NOR 1 = 0
Il risultato è vero se entrambi gli operandi sono falsi
Esercizi

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
Rappresentazione 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
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Rappresentazione delle immagini

BitMaP - codifica dei pixel (profondita’ colore)
•
•
•
•
•
•
1 bit
4 bit
8 bit
16 bit
24 bit
32 bit
Immagine b/n
Immagine 16 Colori o Livelli Grigio
Immagine 256 Colori o Livelli Grigio
Immagine 64K Colori
Immagine 16M Colori (True Color)
Immagine 16M Colori + Alpha Channel
Rappresentazione delle immagini

BitMaP: Formati di memorizzazione:


RAW: matrice dell'insieme di punti
TIFF(Tagged Image File Format): etichette
che descrivono proprietà seguite dai dati (24 bit,
LZW, …)

GIF(Graphic Interchange Format): brevetto
compuserve, possibile immagazzinare più immagini
(schema di compressione LZW)

JFIF(JPEG File Interchange Format):
implementa JPEG, presenza pixel trasparenti e
interlacciamento

BMP(BitMaP): sviluppato da Microsoft e IBM per
windows ed OS/2 (non è compresso!)

PCX(PC Paintbrush): formato supportato da
numerose applicazioni Microsoft (supporta RLE)
Formati
compressi
Rappresentazione delle immagini

Vettoriali: descrizione dell'immagine attraverso elementi
grafici di alto livello (progettazione meccanica, elettronica
architettonica, …)
Circle 98 66 50
Polyline 0 48
88 152 88 48
0 48
Rappresentazione 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)
Rappresentazione delle immagini

Vettoriali: formati di memorizzazione

PostScript: formato brevettato da Adobe per la
rappresentazione dei documenti (linguaggio per stampanti)

EPS (Encapsuled PostScript): usato per trasferire disegni tra
applicazioni PostScript

PDF (Portable Document File): usato per la descrizione di
documenti e immagini (include ps e navigazione
ipertestuale)

DXF (Drawing Exchange Format): usato per il progetto
meccanico (proprietario Autodesk)

IGES (Initial Graphics Exchange Specifications): dati
geometrici e topologici realizzati con programmi 3D
Rappresentazione 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)
Elaborazione 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
Codifica dei suoni
Rappr. Analogica –
analoga alla quantità
fisica in esame; continuita’
nel tempo e continuita’ nelle
ampiezze
Rappr. Digitale –
Campionatura
dell’onda sonora;
Discretizzazione
nel tempo, discretizzazione
nelle ampiezze
Elaborazione dei suoni

Dopo la digitalizzazione ... come per le immagini
è possibile
• eliminare parte del suono (es. rumori di fondo)
• modificare il suono (es. voci distorte)
• ...