fmz1 sistemi basati su conoscenza cenni di logica proposizionale dott. fabio zanzotto a.a. 2001-2002
TRANSCRIPT
![Page 1: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/1.jpg)
FMZ 1
Sistemi basati su conoscenzaCenni di logica proposizionale
Dott. Fabio Zanzotto
a.a. 2001-2002
![Page 2: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/2.jpg)
FMZ 2
Semplice Teorema di Geometria
A C
B
Dato un triangolo isoscele ovvero con AB=BC, si vuole dimostrare che gli angoli  e Ĉ sono uguali.
![Page 3: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/3.jpg)
FMZ 3
Semplice Teorema: conoscenze pregresse
• Se due triangoli sono uguali, i due triangoli hanno lati ed angoli uguali (A)
• Se due triangoli hanno due lati e l’angolo sotteso uguali, allora i due triangoli sono uguali (T)
A C
B
![Page 4: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/4.jpg)
FMZ 4
Semplice Teorema: Dimostrazione
• BH bisettrice di ABC cioè ABH=HBC (T2)
Dimostrazione• AB=BC per ipotesi• ABH=HBC per T2• Il triangolo HBC è uguale al
triangolo ABH per T• Â=Ĉ per A
A C
B
H
![Page 5: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/5.jpg)
FMZ 5
Semplice Teorema: Dimostrazione
Abbiamo trasformato
T in Se AB=BC e BH=BH e ABH=HBC, allora
il triangolo ABH è uguale al triangolo HBC
A in Se triangolo ABH è uguale al triangolo
HBC, allora AB=BC e BH=BH e AH=HC e ABH=HBC e AHB=CHB e Â=Ĉ
A C
B
H
![Page 6: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/6.jpg)
FMZ 6
Semplice Teorema: FormalizzazioneObbiettivo
Razionalizzare il processo che permette affermare:
A C
B
HAB=BC Â=Ĉ
![Page 7: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/7.jpg)
FMZ 7
Abbiamo supposto che: • S={AB=BC, ABH=HBC, BH=BH}
Avevamo conoscenze pregresse:T: AB=BC BH=BH ABH=HBC trABH=trHBC
A: trABH=trHBC AB=BC BH=BH AH=HC ABH=HBC AHB=CHB Â=Ĉ
Semplice Teorema: Formalizzazione
AB=BC Â=Ĉ
![Page 8: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/8.jpg)
FMZ 8
Abbiamo costruito una catena di formule: P1: AB=BC da SP2: ABH=HBC da SP3: BH=BH da S
P4: AB=BC BH=BH ABH=HBC da P1,P2,P3 e REGOLA2
P5: trABH=trHBC da P4,T e REGOLA1
P6: AB=BC BH=BH AH=HC ABH=HBC AHB=CHB Â=Ĉ da P5,A e REGOLA1
P7: Â=Ĉ da P6 e REGOLA3
Semplice Teorema: Formalizzazione
AB=BC Â=Ĉ
![Page 9: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/9.jpg)
FMZ 9
Una dimostrazione per F è conseguenza di S
è una sequenza
DIM=P1,P2,…,Pn
dove• Pn=F• PiS oppure Pi è ottenibile da Pi1,…,Pim (con i1<i,.., im<i)
applicando una regola di inferenza
Processo di dimostrazione
S F
![Page 10: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/10.jpg)
FMZ 10
Regole di inferenza: Modus Ponens (MP)
Se piove, la strada è bagnata.
Piove.
Allora la strada è bagnata.
P B , P
BMP
![Page 11: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/11.jpg)
FMZ 11
Regole di inferenza: AND- Introduzione(AI) e AND- Eliminazione(AE)
A1,…,An
A1… An
A1… An
Ai
AND-Introduzione
AND-EliminazioneAE
AI
![Page 12: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/12.jpg)
FMZ 12
Calcolo Proposizionale Sistema (d’assiomi)
SINTASSIIngredienti:
• Un insieme di simboli L– Letterali: A1,…An
– Connettivi Logici: ,,,,(,)
• Un sottoinsieme FBF di L* detto delle formule ben formate
![Page 13: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/13.jpg)
FMZ 13
Calcolo Proposizionale Sistema (d’assiomi)
SINTASSIIngredienti:
• Un insieme ASSIOMIFBF
• Un insieme R di regole di inferenza
Abbiamo a disposizione:
• Meccanismo della dimostrazione
S F
![Page 14: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/14.jpg)
FMZ 14
Connettivi Logici
SIMBOLO
NOT ~
AND
OR
IMPLIES
IFF
![Page 15: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/15.jpg)
FMZ 15
FBF formule ben formate
• I letterali sono formule ben formate
• Se AFBF e BFBF, alloraAFBF
ABFBF
ABFBF
ABFBF
![Page 16: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/16.jpg)
FMZ 16
Assiomi (Conoscenze pregresse)
• A1: A(BA)
• A2: (A(BC))((AB)(AC))
• A3: (BA)((BA)B)
• A4: (AA)
• A5: AA
![Page 17: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/17.jpg)
FMZ 17
Esempio
Se l’unicorno è mitico, allora è immortale, ma se non è mitico allora è mortale. Se è mortale o immortale, allora è cornuto. L’unicorno è magico se è cornuto.
Domande:
a) L’unicorno è mitico?
b) L’unicorno è magico?
c) L’unicorno è cornuto?
![Page 18: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/18.jpg)
FMZ 18
Procedimento
1. Esprimere il problema in forma di logica dei predicati
2. Individuare i teoremi da dimostrare
3. Dimostrare i teoremi
![Page 19: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/19.jpg)
FMZ 19
EsempioSe l’(unicorno è mitico), allora l’(unicorno è immortale), ma se non (è mitico) allora (è mortale). Se l’(unicorno è mortale) o l’(unicorno è immortale), allora (unicorno è cornuto). L’(unicorno è magico) se l’(unicorno è cornuto).
Letterali:
UM = unicorno è mitico
UI = unicorno è immortale
UMag = unicorno è magico
UC = unicorno è cornuto
![Page 20: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/20.jpg)
FMZ 20
EsempioSe l’(unicorno è mitico)UM, allora l’(unicorno è immortale)UI, ma se non (è mitico)UM allora (è mortale)UI. Se l’(unicorno è mortale)UI o l’(unicorno è immortale)UI, allora (unicorno è cornuto)UC. L’(unicorno è magico)UMag se l’(unicorno è cornuto)UC.
Traduzione:
UMUI
UMUI
UIUIUC
UCUMag
![Page 21: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/21.jpg)
FMZ 21
Esempioa) L’unicorno è mitico?
b) L’unicorno è magico?
c) L’unicorno è cornuto?
Traduzione:
S = {UMUI, UMUI, UIUIUC, UCUmag}
a) S UM
b) S UMag
c) S UC
![Page 22: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/22.jpg)
FMZ 22
Esempio
P1: UIUIUC da S
P2: UIUI da A4
P3: UC da P1, P2 e MP
S UC
![Page 23: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/23.jpg)
FMZ 23
Esempio
P1: UIUIUC da SP2: UIUI da A4P3: UC da P1, P2 e MPP4: UCUMag da SP5: UMag da P3, P4 e MP
Esercizio: DIMOSTRARE a)
S UMag
![Page 24: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/24.jpg)
FMZ 24
Ricapitolando
• Logica Proposizionale (fin qui vista)– Permette di imbrigliare dei ragionamenti in
dei simboli– Permette di dedurre simboli da altri simboli
– Che manca?
Il concetto di Vero e di Falso
![Page 25: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/25.jpg)
FMZ 25
Logica ProposizionaleSEMANTICA
Funzione di interpretazione II: FBF{V,F}
che è composizionale ovvero:date A e B in FBFI(A) = I(A)I(AB) = I(A)I(B)I(AB) = I(A)I(B)I(AB) = I(A)I(B)
![Page 26: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/26.jpg)
FMZ 26
Logica ProposizionaleSEMANTICA
Tavole delle verità dei connettivi logici
![Page 27: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/27.jpg)
FMZ 27
Scopo del calcolo
Assumere Vere le FBF in S e verificare che F sia Vera
Logica ProposizionaleSEMANTICA
S F
![Page 28: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/28.jpg)
FMZ 28
Esempio
AA
A A AAV F V
F V V
![Page 29: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/29.jpg)
FMZ 29
Esempio
A(BA)
A B BA A(BA)
V V V V
V F V V
F V F V
F F V V
Esercizio: Provare a costruire la tabella di verità degli altri assiomi.
![Page 30: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/30.jpg)
FMZ 30
Tautologie e modelli
• Una FBF sempre vera indipendentemente dal valore dei letterali viene detta
tautologia
• Un modello di un insieme F di FBF è una particolare interpretazione I che rende vere tutte le formule in F
![Page 31: FMZ1 Sistemi basati su conoscenza Cenni di logica proposizionale Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062702/5542eb74497959361e8dcc19/html5/thumbnails/31.jpg)
FMZ 31
Osservazione
S F
S F
Semantica
Sintassi
• Chi garantisce?