1

Corso di Informatica

(Programmazione)

Lezione 9 (7 novembre 2008)

Logica proposizionale ealgebra di Boole

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}

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 è.

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

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 “”

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

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

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

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

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

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

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

13

La tabella di verità dell’operatore di negazione logica risulta quindi essere:

A !A

V F

F V

Disgiunzione inclusiva

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…)

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

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

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

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.

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

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à)

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

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.

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

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

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!

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.

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.

28

La tabella di verità dell’operatore di negazione logica risulta quindi essere:

x -x

0 1

1 0

Negazione logica (NOT)

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).

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)

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).

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)

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

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