Transcript
Prerequisiti Matematici Richiami di teoria degli insiemi
Relazioni d’ordine, d’equivalenza
Richiami di logica
Logica proposizionale, tabelle di verità, calcolo dei predicati
Importante: Principio di Induzione Teoria degli insiemi - sta alla base della semantica denotazionale Logica - sta alla base delle tecniche di specifica
Carlo Strapparava - Informatica
Prerequisiti matematici: Logica
“D’altra parte”, continuò Tweedledee, “se era così , doveva esserlo; E se fosse stato così, lo sarebbe; ma poiché non lo è, non può esserlo. Questa è logica.” Carlo Strapparava - Informatica
1
Logica proposizionale La logica proposizionale tratta combinazioni di frasi (proposizioni) a prescindere dalla loro struttura interna
Es. P = “Trento è bella” Q = “Oggi piove”
Carlo Strapparava - Informatica
Logica proposizionale Sintassi: stabilisce le regole di forma del linguaggio
True, False, simboli proposizionali: P, Q, … Negazione: ¬P Congiunzione: P ∧ Q Disgiunzione: P ∨ Q Implicazione: P ⇒ Q Equivalenza: P ⇔ Q
¬, ∧, ∨, ⇒, ⇔ si chiamano connettivi logici Le frasi formate con queste regole si chiamano formule ben formate
Carlo Strapparava - Informatica
2
Logica proposizionale Semantica: assegna significato alle formule
ben formate Il significato di una formula ben formata è un valore di verità, cioe’ un elemento dell’insieme {T,F} (indicato anche con {0,1}) P
¬P
0
1
1
0 Carlo Strapparava - Informatica
Semantica dei connettivi logici P
Q
P∧Q
P∨Q
1
1
1
1
1
1
1
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
1
1
P⇒Q P⇔Q
Una proposizione costruita su n proposizioni elementari, ammetterà ben componenti
2n
ipotesi sul valore di verità delle sue
P
Q
R
1
1
1
1
1
0
1
0
1
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0
23 = 8
Carlo Strapparava - Informatica
3
Logica proposizionale Una formula ben formata si dice valida (o
tautologia) se risulta vera sotto ogni possibile interpretazione (cioè qualunque sia l’assegnazione dei valori di verità) Es. (false ⇒ P) è una tautologia
Una formula ben formata si dice soddisfacibile
se è vera sotto qualche interpretazione (cioè esiste qualche assegnazione dei valori di verità che la rende vera) Carlo Strapparava - Informatica
Esercizio Dimostrare che (P ∧ (P ⇒ Q)) ⇒ Q è una tautologia P
Q
1
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
0
1
0
1
P ⇒ Q P ∧ (P ⇒ Q)
(P ∧ (P ⇒ Q)) ⇒ Q
Carlo Strapparava - Informatica
4
Equivalenze di formule Vediamo una serie di equivalenze di formule. Ciascuna può essere dimostrata usando la semantica dei connettivi logici e costruendo le rispettive tabelle di verità ¬true ≡ false ¬false ≡ true P ∧ true ≡ P P ∧ false ≡ false P ∨ true ≡ true P ∨ false ≡ P (false ⇒ P) ≡ true Carlo Strapparava - Informatica
Equivalenze di formule Commutatività:
i connettori ∧ ∨ e ⇔ sono commutativi Es. F ∧ G ≡ G ∧ F
Distributività:
P ∧ (G ∨ Q) ≡ (P ∧ G ) ∨ (P ∧ Q) P ∨ (G ∧ Q) ≡ (P ∨ G ) ∧ (P ∨ Q) (P ∨ G ) ⇒ Q ≡ (P ⇒ Q ) ∧ (G ⇒ Q) (P ∧ G ) ⇒ Q ≡ (P ⇒ Q ) ∨ (G ⇒ Q) P ⇒ (G ∨ Q) ≡ (P ⇒ G ) ∨ (P ⇒ Q) P ⇒ (G ∧ Q) ≡ (P ⇒ G ) ∧ (P ⇒ Q)
Carlo Strapparava - Informatica
5
Equivalenze di formule Negazione:
¬(¬P) ≡ P ¬(P ∧ Q) ≡ ¬P ∨ ¬Q ¬(P ∨ Q) ≡ ¬P ∧ ¬Q ¬(P ⇒ Q) ≡ P ∧ ¬Q
Leggi di controposizione: F ⇒ G ≡ ¬G ⇒ ¬F (¬F ⇒ G) ≡ (¬G ⇒ F) F ⇔ G ≡ ¬F ⇔ ¬G
Riduzione: P ⇒ Q ≡ ¬P ∨ Q P⇔Q≡P⇒Q∧Q⇒P Carlo Strapparava - Informatica
Calcolo dei predicati Il calcolo dei predicati estende il calcolo
proposizionale e consente di “entrare” nella struttura delle proposizioni Consente cioè di fare riferimento ad oggetti e di predicare (esprimere affermazioni) su di essi
∀x P(x) ⇒ Q(x) ∀x informatico(x) ⇒ hacker(x)
Il calcolo dei predicati consente l’uso di due quantificatori
∀ si dice quantificatore universale (si legge “per ogni”) ∃ si dice quantificatore esistenziale (si legge “esiste”)
Carlo Strapparava - Informatica
6
Calcolo dei predicati Es. ∃x informatico(x) ⇒ hacker(x) La presenza dei quantificatori pone la necessità di stabilire delle regole per la portata (in inglese scope) degli stessi Scope di un quantificatore: la parte della formula sulla quale il quantificatore influisce Se una variabile x in una formula P non è legata da nessun quantificatore, si dice che è libera in P Una formula ben formata si dice chiusa se non ha occorrenze di variabili libere
Carlo Strapparava - Informatica
Calcolo dei predicati L’insieme {x | P(x)} è detto estensione di P Alcune equivalenze: ¬∃x P(x) ≡ ∀x ¬P(x) ¬∀x P(x) ≡ ∃x ¬P(x)
Distributività: ∀x (P(x) ∧ R(x)) ≡ (∀x P(x)) ∧ (∀x R(x)) ∃x (P(x) ∧ R(x)) ≡ (∃x P(x)) ∧ (∃x R(x)) ∃x (P(x) ⇒ R(x)) ≡ (∀x P(x) ⇒ ∃x R(x))
Ridenominazione delle variabili: ∀x P(x) ≡ ∀y P(y) ∃x P(x) ≡ ∃y P(y) Carlo Strapparava - Informatica
7
Richiami di logica Letture consigliate: 1. 2.
Dispense sul sito del corso La logica può essere divertente: R. Smullyan - “Qual è il titolo di questo libro?” edizioni Zanichelli
Carlo Strapparava - Informatica
8
