Algebra booleana

Materie:Appunti
Categoria:Informatica
Download:970
Data:03.10.2008
Numero di pagine:8
Formato di file:.doc (Microsoft Word)
Download   Anteprima
algebra-booleana_4.zip (Dimensione: 15.61 Kb)
trucheck.it_algebra-booleana.doc     124.5 Kb
readme.txt     59 Bytes


Testo

L’algebra booleana
L’Algebra Booleana è un sistema che permette di trattare in forma matematica una parte del pensiero umano; ci interessa perché se il pernsiero umano può essere codificato in forma numerica, vuol dire che potrà essere tradotto in modo che risulti comprensibile al computer e questo ci permetterà di fa “pensare “ questa macchina come noi. Solamente in parte però, poiché questo tipo di algebra tratta solo un aspetto del modo di ragionare: la logica proposizionale o logica aristotelica.
Questa parte del pensiero umano è stata isolata e studiata dal filosofo greco Aristotele ed è stata di nuovo analizzata, nella metà dell’ottocento, dal matematico inglese George Bool. Utilizzando la logica aristotelica, egli ha costruito un sistema matematico detto appunto ALGEBRA BOOLEANA. Questa si occupa di formalizzare in un sistema matematico quelle che sono le proposizioni logiche, ovvero le frasi alle quali possiamo rispondere con un “vero” o “falso”. Es. “Oggi piove”; è una proposizione che può solo essere vera o falsa.
DEFINIZIONE:
Si definisce PROPOSIZIONE SEMPLICE una frase costituita da un soggetto un verbo ed un complemento e per la quale chiunque può stabilire con obbiettività se è vera o falsa.
DEFINIZIONE:
SI definisce PROPOSIZIONE COMPOSTA una proposizione che si ottiene combinando insieme delle proposizioni semplici con degli operatori logici.
Le frasi che useremo nei nostri esempi non ci interessano per il significato che hanno nella lingua italiana, ci interesserà soltanto la falsità o la verità di una preposizione, cioè il suo valore di verità. Rappresenteremo le proposizioni con le lettere minuscole dell’alfabeto.
Il “vero” è indicato con il bit 1, il “falso” con il bit 0.
DEFINIZIONE:
Si dice SISTEMA MATEMATICO una serie di conoscenze che si costruiscono a partire da degli assiomi, detti anche principi. Gli assiomi sono delle verità non verificabili ma accettabili. Chi non accetta questi principi non accetta la teoria (es. geometria di Euclide).
L’algebra booleana è una teoria che si basa sui tre principi della logica aristotelica:
1. PRINCIPIO DI IDENTITA’
2. PRINICIPIO DI NON CONTRADDIZIONE
3. PRINCIPIO DEL TERZO ESCLUSO
Il principio di identità afferma che una proposizione è uguale a se stessa: p = p
Il principio di non contraddizione afferma che se una proposizione è vera, non può contemporaneamente essere falsa.
Il principio del terzo escluso afferma che una proposizione è o vera o falsa, non esiste una terza possibilità.
E’ necessario costruire degli operatori logici che permettono di combinare insieme le proposizioni e di creare delle espressioni logiche di cui calcolare il valore di verità; così come nell’algebra si combinano numeri e simboli con operatori algebrici - come l’elevazione a potenza, la divisione ecc. - per formare un’espressione algebrica
Il valore di verità di una proposizione composta si ottiene a partire dal valore di verità delle proposizioni componenti e del funzionamento degli operatori logici.
Le operazioni logiche che studiamo sono proprio quelle che l’ALU è in grado di eseguire. Inoltre, abbiamo già visto in Excel che i criteri del filtro automatico e avanzato non sono altro che proposizioni logiche.
Gli operatori logici che studieremo sono tre:
• NOT: negazione logica
• AND: congiunzione logica (prodotto logico)
• OR: disgiunzione logica inclusiva (somma logica)
Per vedere come operano questi operatori ci si serve delle tabelle di verità degli operatori.
TABELLA DI VERITA’ DI “NOT”
NOT: Operatore unario
P : proposizione semplice
p
NOT p

1
1

TABELLA DI VERITA’ DI “AND”
AND: operatore binario
p, q: proposizioni semplici
p
q
pANDq

1

1

1
1
1
Notiamo che l’AND di due proposizioni è vero solo se sono entrambe vere
TABELLA DI VERITA’ DI “OR”
OR: operatore binario
p, q: proposizioni semplici
p
q
pORq

1
1
1

1
1
1
1
Notiamo che l’OR di due proposizioni è falso solo se sono entrambe false.
DEFINIZIONE:
Si definisce PREPOSIZIONE COMPOSTA una proposizione costituita da due o più preposizioni semplici collegate insieme da operatori logici.
Esempi:
1. Oggi la temperatura esterna è di 1° grado centigrado e nevica.
In questa frase le preposizioni componenti sono: “oggi la temperatura è di 1° grado centigrado”, e “oggi nevica”.
Le colleghiamo con l’operatore AND e otteniamo una preposizione composta.
2. Oggi non c’è il sole.
E’ una preposizione composta perché c’è la negazione. Il NOT si applica ad una sola preposizione.
3. Sabato sera vado a mangiare la pizza oppure ceno a casa.
In questa frase le preposizioni componenti sono: “sabato sera vado a mangiare la pizza” e “sabato sera ceno a casa”.
Impareremo come calcolare il valore di verità di una preposizione composta partendo dal valore di verità delle preposizioni componenti e dal funzionamento degli operatori logici.
Se ho delle preposizioni complesse, dove appaiono più operatori logici, dovrò fare dei calcoli più complessi. In ogni caso bisogna costruire una tabella di verità opportuna.
ESEMPI
1. t =NOT (p AND q)
In questo caso le preposizioni semplici sono p e q, gli operatori presenti sono: AND e NOT.
p
q
p AND q
NOT (p AND q)

1

1

1
1

1
1
1
1

Le parentesi funzionano come nell’algebra, stabiliscono e forzano la precedenza fra gli operatori logici, per sapere il valore di t bisogna costruire la tabella data sopra: avrò una colonna per i valori di p, una per quelli di q che sono le preposizioni componenti, avrò quattro righe perché ogni riga corrisponde a una delle 22 combinazioni dei valori di verità delle preposizioni p e q.
2. (a OR b) AND c
In questo caso le preposizioni composte sono a, b, c, gli operatori presenti sono: OR e AND.
a
b
c
a OR b
(a OR b) AND c

1

1

1

1
1
1
1
1

1

1

1
1
1
1
1

1

1
1
1
1
1
3. ( (NOT x) AND y) OR x
In questo caso le preposizioni composte sono x e y, gli operatori presenti sono: NOT, AND e OR
x
y
NOT x
(NOT x) AND y
( (NOT x) AND y) OR x

1

1
1
1
1
1

1
1
1

1
PROPRIETA' DEGLI OPERATORI LOGICI
A questo punto ci interessa operare sulle espressioni logiche in modo simile a quello che usiamo per operare in algebra: vogliamo imparare le regole del calcolo logico necessarie per ridurre una preposizione composta ad una preposizione più semplice o comunque diversa nella forma ma di uguale valore. Queste ci serviranno quando avremo la necessità di cercare informazioni in un insieme di informazioni che sia un archivio, una base di dati o il web; in quel caso infatti noi dovremo esprimere in forma sintetica cosa intendiamo cercare, dovremo quindi scrivere un’espressione logica che, data a un computer, dia a questo la possibilità di fare la ricerca per noi.
Ad esempio se voglio estrarre da un elenco di clienti tutti quelli della Toscana che mi hanno fatto realizzare vendite per più di 100000,00 euro, devo trasformare in qualche modo questa richiesta in una preposizione logica secondo l’Algebra Booleana in modo tale che il computer, utilizzando gli 0 e gli 1 e le tabelle di verità che abbiamo visto, sia in grado di calcolare per quali informazioni dell’elenco questa proposizione è vera e per quali falsa.
Definiamo quindi l'equivalenza tra proposizioni logiche.
DEFINIZIONE: due proposizioni logiche si dicono equivalenti quando assumono gli stessi valori di verità per le stesse combinazioni di valori di verità assunti dalle proposizioni componenti.
Il simbolo "=" viene usato per rappresentare l'equivalenza.
Quella di equivalenza è una relazione biunivoca che si stabilisce tra due proposizioni; essa gode delle tre proprietà:
1. RIFLESSIVA: ogni proposizione è equivalente a se stessa ( p=p)
2. SIMMETRICA: se p=q allora q=p
3. TRANSITIVA: se p=q e q=r allora p=r
Esempio:
volendo verificare l'equivalenza (a OR b) OR c = a OR (b OR c) sarà sufficiente costruire le tabelle di verità delle due proposizioni e controllare che esse siano uguali:
a
b
c
(a OR b)
(a OR b) OR c

1

1

1

1
1

1
1
1
1
1

1
1
1

1
1
1
1
1

1
1
1
1
1
1
1
a
b
c
(b OR c)
a OR (b OR c)

1
1
1

1

1
1

1
1
1
1
1

1
1

1
1
1
1
1

1
1
1
1
1
1
1
Le tabelle di verità delle due proposizioni sono uguali, dunque le due proposizioni sono equivalenti.
a, b, c sono le preposizioni semplici componenti.
Le righe della tabella sono 8, 23, perché due sono i possibili valori diverità di ciascuna proposizione e 3 le proposizioni.
Il risultato non deve sorprendere! L'OR di due o più proposizioni, per definizione, è falso solo quando le proposizioni componenti sono tutte false mentre è vero quando almeno una delle componenti è vera.
Elenchiamo ora le proprietà degli operatori logici che ci permettono di trasformare una preposizione logica in una preposizione equivalente.
PROPRIETA’ DEGLI OPERATORI LOGICI:
PROPRIETA’ ASSOCIATAVA DI OR:
a OR (b OR c) = (a OR b) OR c
per calcolare l'OR di tre o più proposizioni, posso accoppiarle come voglio che ottengo sempre lo stesso risultato.
PROPRIETA’ ASSOCIATIVA DI AND:
(x AND y) AND z = x AND (y AND z)
per calcolare l'AND di tre o più proposizioni, posso accoppiarle come voglio che ottengo sempre lo stesso risultato.
PROPRIETA’ COMMUTATIVA DI OR:
a OR b = b OR a
"cambiando la somma degli addendi il risultato non cambia".
PROPRIETA’ COMMUTATIVA DI AND:
x AND y = y AND x
"cambiando l’ordine dei fattori il prodotto non cambia".
PROPRIETA’ DISTRIBUTIVA DI AND RISPETTO A OR:
p AND (q OR r) = (p AND q) OR (p AND r)
PROPRIETA’ DISTRIBUTIVA DI OR RISPETTO AND:
l OR (m AND n) = (l OR m) AND (l OR n)

Verifichiamo questa proprietà costruendo le tabelle di verità delle due proposizioni
l
m
n
(m AND n)
l OR (m AND n)

1

1

1
1
1
1
1

1
1

1

1
1
1

1
1
1
1
1
1
l
m
n
(l OR m)
(l OR n)
(l OR m) AND (l OR n)

1

1

1

1

1
1
1
1
1
1

1
1
1
1

1
1
1
1
1
1

1
1
1
1
1
1
1
1
1
Le due tabelle coincidono dunque la proprietà è verificata.
LEGGI DI DE MORGAN:
1. NOT (a AND b) = (NOT a) OR (NOT b) la negazione dell'AND di due preposizioni è
equivalente all’OR delle singole negazioni.
2. NOT (x OR y) = (NOT x) AND (NOT y) la negazione dell’OR di due preposizioni è
equivalente all’AND delle singole negazioni.
Verifichiamo la validità di questa seconda legge costruendo le tabelle di verità delle due proposizioni:
x
y
(x OR y)
NOT (x OR y)

1

1
1

1

1

1
1
1

=
x
y
(NOT x)
(NOT y)
(NOT x) AND (NOT y)

1
1
1

1
1

1

1

1
1

Le due tabelle coincidono dunque la proprietà è verificata.
PROPRIETA’ DELLA DOPPIA NEGAZIONE:
NOT (NOT p) = p
“Due negazioni affermano”! Cioè negare due volte equivale a non negare affatto.
ESERCIZI
1. Fare almeno due esempi di frasi che siano proposizioni semplici ed almeno due di frasi che non lo siano.
2. Date le seguenti proposizioni composte, dire quali sono le proposizioni semplici componenti e quale il connettivo:
a) il gatto ha nove code e il cane solo tre;
b) il 14 Febbraio nevica e i ristoranti sono pieni;
c) Giovanna lavora in casa o in ufficio.
3. Date le proposizioni p = "Orazio studia" e q = "Orazio mangia un panino", scrivere in simboli le proposizioni:
a) Orazio non mangia un panino mentre studia;
b) Orazio studia o mangia un panino;
c) Orazio non studia e mangia un panino.
4. Date le proposizioni x = "Informatica è la materia più bella che studiamo a scuola" ed y = "Io amo molto leggere i fumetti", dire cosa significano le proposizioni:
a) y AND (NOT x)
b) (NOT y) OR x
c) (x OR y) AND (NOT (x AND y))
5. Trasformare le seguenti proposizioni applicando la proprietà commutativa:
a) (età >= 18) AND (NOT(patentato))
b) (città = Milano) OR (distanza < 50)
6. Trasformare le seguenti proposizioni applicando la proprietà distributiva:
a) (cognome = Rossi) AND ((nome = Giovanni) OR (nome = Maria))
b) (stipendio < 1.500.000) OR ((qualifica = segretaria) AND (anzianità > 5))
7. Calcolare il valore di verità della proposizione NOT(a AND (NOT(b OR c))) costruendone la tabella di verità.
8. La proposizione (NOT a) OR (NOT(b OR c)) è equivalente a quella data nell'esercizio 7? Spiega come hai fatto a dare la risposta.
1

Esempio