corso di informatica (programmazione)
DESCRIPTION
Corso di Informatica (Programmazione). Lezione 9 (7 novembre 2008) Logica proposizionale e algebra di Boole. Introduzione. Logica proposizionale studio del significato delle proposizioni connesse dai connettivi logici Algebra di Boole - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/1.jpg)
1
Corso di Informatica
(Programmazione)
Lezione 9 (7 novembre 2008)
Logica proposizionale ealgebra di Boole
![Page 2: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/2.jpg)
2
Introduzione
Logica proposizionale
studio del significato delle proposizioni connesse dai connettivi logici
Algebra di Boole
struttura algebrica codificata da George Boole (1815-1864) che manipola
grandezze binarie {0,1}
![Page 3: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/3.jpg)
3
IntroduzioneLogica
studio del processo di pensiero che parte da premesse e giunge a conclusioni
Proposizione dichiarazione a cui può essere
associato un valore di verità (VERO o FALSO, V o F).
Ad esempio “Il cane di Marco è nero” è una proposizione, mentre “Che ore sono?” non lo è.
![Page 4: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/4.jpg)
4
Connettivi logiciNel seguito si:
indicheranno le proposizioni tramite lettere dell’alfabeto maiuscolo
indicherà il valore di verità di una proposizione P tramite la notazione v(P). Quindi v(P)=V se P è vera, v(P)=F se P è falsa
Ad esempio la proposizione “Roma è la capitale d’Italia” può essere indicata con la lettera R e quindi:
R=“Roma è la capitale d’Italia” v(R) vale V
![Page 5: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/5.jpg)
5
Connettivi logiciI principali connettivi (operatori) logici sono:
congiunzione logica “and”, “e”, “&”, Λ
disgiunzione inclusiva “or”, “o”, “|”, V
disgiunzione esclusiva “xor”, V
negazione logica “not”, “!”,
implicazione logica “”
coimplicazione logica “”
![Page 6: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/6.jpg)
6
Congiunzione logicaDate due proposizioni A e B, l’operatore di congiunzione logica produce la proposizione C=A&B che è VERA se e solo se A e B sono entrambe VERE. Negli altri casi C è FALSA.
Ad esempio se A=“Roma è la capitale d’Italia” (A è VERA, cioè v(A)=V) e B=“Milano si trova in Francia” (B è FALSA, cioè v(B)=F), allora la proposizione C=A&B=“Roma è la capitale d’Italia e Milano si trova in Francia” è FALSA, cioè v(C)=F
![Page 7: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/7.jpg)
7
La tabella di verità dell’operatore di congiunzione logica risulta quindi essere:
A B A & B
V V V
V F F
F V F
F F F
Congiunzione logica
![Page 8: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/8.jpg)
8
Disgiunzione inclusivaDate due proposizioni A e B, l’operatore di disgiunzione inclusiva produce la proposizione C=A|B che è VERA se e solo se almeno una proposizione tra A e B è VERA. Negli altri casi C è FALSA.
Ad esempio se A=“Roma è la capitale d’Italia” (A è VERA, cioè v(A)=V) e B=“Milano si trova in Francia” (B è FALSA, cioè v(B)=F), allora la proposizione C=A|B=“Roma è la capitale d’Italia o Milano si trova in Francia” è VERA, cioè v(C)=V
![Page 9: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/9.jpg)
9
La tabella di verità dell’operatore di disgiunzione inclusiva risulta quindi essere:
A B A | B
V V V
V F V
F V V
F F F
Disgiunzione inclusiva
![Page 10: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/10.jpg)
10
Disgiunzione esclusivaDate due proposizioni A e B, l’operatore di disgiunzione esclusiva produce la proposizione C=A xor B che è VERA se e solo se una proposizione tra A e B è VERA. Negli altri casi C è FALSA.
Ad esempio se A=“Roma è la capitale d’Italia” (A è VERA, cioè v(A)=V) e B=“Milano si trova in Lombardia” (B è VERA, cioè v(B)=V), allora la proposizione C=A xor B=“Roma è la capitale d’Italia oppure Milano si trova in Lombardia” è FALSA, cioè v(C)=F
![Page 11: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/11.jpg)
11
La tabella di verità dell’operatore di disgiunzione esclusiva risulta quindi essere:
A B A xor B
V V F
V F V
F V V
F F F
Disgiunzione inclusiva
![Page 12: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/12.jpg)
12
Negazione logica
Data una proposizione A, l’operatore di negazione logica produce la proposizione C=!A che è VERA se e solo se A è FALSA.
Ad esempio se A=“Roma è la capitale di Francia” (A è FALSA, cioè v(A)=F), allora la proposizione C=!A=“Roma non è la capitale di Francia” è VERA, cioè v(C)=V
![Page 13: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/13.jpg)
13
La tabella di verità dell’operatore di negazione logica risulta quindi essere:
A !A
V F
F V
Disgiunzione inclusiva
![Page 14: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/14.jpg)
14
Implicazione logicaDate due proposizioni A e B, l’operatore di implicazione logica produce la proposizione C=AB che è FALSA se e solo A è VERA e B è FALSA. Negli altri casi C è VERA.
Ad esempio se A=“Fuori piove”, B=“Fuori ci sono nuvole”, e si ha che v(A)=V e v(B)=F, allora C=AB=“Fuori piove allora è falso che fuori ci sono nuvole” è palesemente FALSO (quando piove ci sono sempre le nuvole…)
![Page 15: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/15.jpg)
15
La tabella di verità dell’operatore di implicazione logica risulta quindi essere:
A B A B
V V V
V F F
F V V
F F V
Implicazione logica
![Page 16: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/16.jpg)
16
Coimplicazione logicaDate due proposizioni A e B, l’operatore di coimplicazione logica produce la proposizione C=AB che è VERA se e solo A e B sono entrambe VERE o entrambe FALSE. Negli altri casi C è FALSA.
Ad esempio se A=“Il triangolo ha angoli alla base uguali”, B=“Il triangolo è isoscele”, e si ha che v(A)=F e v(B)=F, allora C=AB=“Il triangolo non ha angoli alla base uguali allora il triangolo non è isoscele” è VERA
![Page 17: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/17.jpg)
17
La tabella di verità dell’operatore di coimplicazione logica risulta quindi essere:
A B A B
V V V
V F F
F V F
F F V
Coimplicazione logica
![Page 18: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/18.jpg)
18
Implicazione e coimplicazione logica
Se due proposizioni A e B sono legate da implicazione logica (A B), si dice che A è condizione sufficiente per B e B è condizione necessaria per A.
Se due proposizioni A e B sono legate da coimplicazione logica (A B), si dice che A è condizione necessaria e sufficiente per B.
![Page 19: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/19.jpg)
19
La formula
Una formula f è una combinazione di simboli di proposizioni tramite connettivi (operatori) logici. Ad una formula è associato un valore di verità v(f) che dipende dai valori di verità delle proposizioni atomiche (proposizioni che non possono essere scomposte in ulteriori proposizioni più piccole)
A & B è un esempio di formula
![Page 20: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/20.jpg)
20
La sintassi di una formulaL’alfabeto delle formule è composto da:
i simboli delle proposizioni
i simboli dei connettivi logici
parentesi tonde (per eliminare ambiguità)
![Page 21: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/21.jpg)
21
La sintassi di una formulaLa grammatica delle formule definisce
le regole di buona formazione. Esse sono:
1. un simbolo di proposizione è una formula ben formata (abbreviato FBF)
2. se f è una formula ben formata, allora la sua negazione !f è una FBF
3. se f e f’ sono FBF, allora fopf’) (dove “op” è uno dei connettivi logici) è una FBF
4. niente altro è una FBF
![Page 22: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/22.jpg)
22
La sintassi di una formulaAd esempio la formula f=(A & (!B)) | C
è una FBF in quanto, in virtù della regola 1, A, B e C sono FBF. Inoltre anche !B è una FBF in virtù della regola 2. Infine, per la regola 3 sono FBF anche le formule A & !B e la formula F=(A & (!B)) | C .
Invece la formula f’=A & (& B) non è una FBF.
![Page 23: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/23.jpg)
23
La semantica di una formulaAd una formula f (che sia FBF) può
essere associato un valore di verità attraverso la funzione di valutazione v:
v: L {V,F}
che mappa l’insieme delle formule ben formate L all’insieme {V,F}. La funzione v si basa sulle tabelle di verità dei connettivi logici visti in precedenza. Quindi data f, v(f) è il valore di verità associato a f
![Page 24: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/24.jpg)
24
La semantica di una formulaEsempio:
f=(A & (!B)) | C
posto che sia v(A)=V, v(B)=V e v(C)=F
si ha:
v(!B)=F
v(A & (!B))=F
v(f)=v((A & (!B)) | C)=F
![Page 25: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/25.jpg)
25
La semantica di una formulaSi dice che una formula f è:
una tautologia se è sempre v(f)=V
una contraddizione se è sempre v(f)=F
Ad esempio:
f=A & (notA) v(f)=F sempre!
f’=A ! (notA) v(f’)=V sempre!
![Page 26: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/26.jpg)
26
Algebra di BooleL’algebra di Boole si basa su:
variabili booleane che possono assumere uno dei valori compresi nell’insieme {0,1}
operatori booleani di negazione logica (NOT)
di prodotto logico (AND)
di somma logica (OR)
etc.
![Page 27: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/27.jpg)
27
Negazione logica (NOT)L’operazione di negazione logica (o complementazione) restituisce il valore opposto rispetto alla variabile x in ingresso.
Data la variabile booleana x, la sua negazione logica si indica con –x, x, x’ oppure not(x). Se x vale 1, allora –x vale 0; se x vale 0, allora –x vale 1.
![Page 28: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/28.jpg)
28
La tabella di verità dell’operatore di negazione logica risulta quindi essere:
x -x
0 1
1 0
Negazione logica (NOT)
![Page 29: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/29.jpg)
29
Prodotto logico (AND)L’operazione di prodotto logico, tra due variabili x e y, restituisce 1 se x e y hanno entrambe valore 1. In tutti gli altri casi restituisce 0.
Date le variabili booleane x e y, il prodotto logico di x e y si indica con x y, xy oppure con (x and y).
![Page 30: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/30.jpg)
30
La tabella di verità dell’operatore di prodotto logico risulta quindi essere:
x y xy
1 1 1
1 0 0
0 1 0
0 0 0
Prodotto logico (AND)
![Page 31: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/31.jpg)
31
Somma logica (OR)L’operazione di somma logica, tra due variabili x e y, restituisce 1 se almeno una tra x e y ha valore 1. In tutti gli altri casi restituisce 0.
Date le variabili booleane x e y, la somma logica di x e y si indica con x+y oppure con (x or y).
![Page 32: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/32.jpg)
32
La tabella di verità dell’operatore di somma logica risulta quindi essere:
x y x+y
1 1 1
1 0 1
0 1 1
0 0 0
Somma logica (OR)
![Page 33: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/33.jpg)
33
Prodotti e somme notevoli
X 0=0
X 1=x
X x=x
x (-x)=0
x+0=x
x+1=1
x+x=x
x+(-x)=1
![Page 34: Corso di Informatica (Programmazione)](https://reader035.vdocumenti.com/reader035/viewer/2022081503/56814d4f550346895dba82d1/html5/thumbnails/34.jpg)
34
Proprietà dell’algebra booleana Proprietà di idempotenza della somma e del prodotto x+x=x e xx=x
Proprietà dell’elemento nullo della somma e del prodotto x+1=1 e x0=0
Proprietà commutativa della somma e del prodotto x+y=y+x e xy=yx
Proprietà associativa della somma e del prodotto x+(y+z)=(x+y)+z=x+y+z e x(yz)=(xy)z=xyz