Fondamenti di Informatica 2
Linguaggi e Complessit
`
a : Logica I Parte
Lucidi di M.Schaerf e A.Marchetti Spaccamela
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 1
Fondamenti di Informatica 2: Logica
} Indice degli argomenti
• Introduzione: Motivazioni, Prove, Ragionamenti e loro conseguenze
• Logica Proposizionale: sintassi
• Il calcolo proposizionale: semantica
• Il calcolo proposizionale: dimostrazioni nel calcolo
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 2
Logica: Motivazioni
} La LOGICA e la disciplina che studia le condizioni di correttezza delragionamento
} Occorre dire, anzitutto, quale oggetto riguardi ed a quale disciplina spettila presente indagine, che essa cio riguarda la dimostrazione e spetta allascienza dimostrativa: in seguito, bisogna precisare cosa sia la premessa, cosasia il termine, cosa sia il sillogismo... [Aristotele]
} Esempio di sillogismo (sillogismo = connessione di idee, ragionamento)
• Tutti gli uomini sono mortali
• Socrate e un uomo
• Socrate e mortale
EquivalentementeDato che Tutti gli uomini sono mortali e che Socrate e un uomo possiamoconcludere che Socrate e mortale
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 3
Logica: Motivazioni
} Non tutti i sillogismi sono validi. Ad esempio
• Tutti gli animali sono mortali
• Socrate e mortale• Socrate e un animale
• Tutti gli dei sono immortali
• Gli uomini non sono dei
• Gli uomini sono mortali
I due sillogismi precedenti sono errati: la conclusione non deriva logicamentedalle premesse
} Obiettivi di questa parte:- presentare la logica proposizionale, una (piccola) parte della logica- presentare in modo formale i concetti di prova cosı come si utilizzano nellalogica proposizionale
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 4
Cosa e una dimostrazione, una prova astuta
} Cosa e un teorema in matematica?Teorema di Pitagora: Se a, b, c sono lati di un triangolo rettangolo alloraa
2 + b
2 = c
2
Familiare? SI Ovvio? No
- 4 triangoli rettangoli con cateti lunghi a e b e un quadrato di lato b� a
!
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 5
Cosa e una dimostrazione, una prova astuta
} Teorema di Pitagora: Se a, b, c sono lati di un triangolo rettangolo alloraa
2 + b
2 = c
2
- 4 triangoli rettangoli con cateti lunghi a e b e un quadrato con lato lungob� a hanno area complessiva pari a c
2
!
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 6
Cosa e una dimostrazione, una prova astuta-2
} Teorema di Pitagora: Se a, b, c sono lati di un triangolo rettangolo alloraa
2 + b
2 = c
2
- 4 triangoli rettangoli con cateti lunghi a e b e un quadrato con lato lungoa hanno area complessiva pari a a
2 + b
2. Quindi c2 = a
2 + b
2!
!
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 7
Una dimostrazione sbagliata
} Consideriamo la seguente sequenza di uguaglianze:
1 =p1 =
r
(�1)(�1) =r
(�1)r
(�1) = (r
(�1))2 = �1
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 8
Conseguenze di una dimostrazione sbagliata
} Consideriamo la seguente sequenza di uguaglianze:
1 =p1 =
r
(�1)(�1) =r
(�1)r
(�1) = (r
(�1))2 = �1
} Dopo aver dimostrato che 1 = �1 otteniamo anche• 1
2
= �1
2
(moltiplica per 1
2
i membri della uguagl. precedente)• 2 = 1 (somma 3
2
ad ambedue i termini dell’uguagl. precedente)
} Conseguenze di 2 = 1Dato che io e il Papa siamo chiaramente 2 possiamo concludere che io e ilPapa siamo 1, cioe io e il Papa siamo la stessa persona ed io sono il Papa![Bertrand Russel]
} Morale:Le conseguenze di una prova sbagliata possono essere paradossaliperche una prova errata permette di fare a↵ermazioni chiaramente errate!
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 9
Logica: Motivazioni
} La LOGICA e la disciplina che studia le condizioni di correttezza delragionamento
} Occorre dire, anzitutto, quale oggetto riguardi ed a quale disciplina spettila presente indagine, che essa cio riguarda la dimostrazione e spetta allascienza dimostrativa: in seguito, bisogna precisare cosa sia la premessa, cosasia il termine, cosa sia il sillogismo... [Aristotele]
} Noi ci limiteremo alla Logica ProposizionaleNota anche come Calcolo Proposizionale ci permette di ragionare sulla veritadi semplici proposizioni
} Obiettivo
• Formalizzare i nostri ragionamenti (limitandoci alle proposizioni)• Esaminare le regole che ci permettono di stabilire la verita o la falsita diuna a↵ermazione
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 10
Logica e informatica
} Nel XIX secolo sono state in matematica sono state proposte notazionimatematiche (algebriche) per trattare le operazioni della logica (GeorgeBoole)
} Questo ha consentito, negli anni 1900-1930, di applicare la logica aifondamenti della matematica, arrivando a interessanti controversie e a capirei limiti della matematica (Frege, Russel, Godel ed altri)
} In matematica, la logica usata principalmente per esprimere asserti inmodo non ambiguo
} La logica matematica ha profondi legami con linformatica (ed in partico-lare nella programmazione e in intelligenza artificiale
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 11
Logica proposizionale
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 12
Logica proposizionale
} Linguaggio matematico per ragionare sulla verita o falsita di proposizioni
} Composto da una sintassi (regole per costruire le frasi) e da una semantica(regole per assegnare un significato)
} Esempio di frase
• piove, fa-caldo, fa-caldo^(e)¬(non)piove, piove_(o)sole• costituito da proposizioni atomiche (piove, fa-caldo, sole . . .) e da propo-sizioni complesse (fa-caldo ^ ¬piove, piove _ sole . . .)
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 13
Logica proposizionale: Alfabeto
} Linguaggio matematico per ragionare sulla verita o falsita di proposizioni
• Un insieme non vuoto (finito o numerabile) di simboli proposizionali A ={A,B, . . . , P,Q, . . .};
• Le costanti proposizionali >, ? (per denotare il vero TRUE e il falsoFALSE);
• I connettivi (detti anche operatori) proposizionali ¬ (unario), ^ e _ (bi-nari);
• I simboli separatori ‘(’ e ‘)’.
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 14
Logica proposizionale: Formule
} Formule (dette anche proposizioni)
L’insieme Prop delle formule ben formate o formule del linguaggio propo-sizionale e l’insieme definito induttivamente come segue:
1. Le costanti e i simboli proposizionali sono formule;
2. Se ↵ e una formula (¬↵) e una formula;
3. Se ↵ e � sono due formule, (↵ ^ �) e (↵ _ �) sono formule.
Nel seguito useremo la convenzione di denotare i simboli proposizionali conle lettere maiuscole (A, B, . . .) e le formule proposizionali con le letteregreche minuscole (↵, �, . . . ).
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 15
Semantica: Sistema di valutazione
} Definiamo il dominio e gli operatori che ci permetteranno di dare unasemantica (significato) alle nostre proposizioni.
} Il sistema di valutazione della logica proposizionale e costituito daldominio B= {0, 1}, dove il simbolo 1 denota il valore di verita e 0 il valore difalsita ed un insieme di operatori (tabelle di verita ) su questo dominio Op={Op¬,Op^,Op_} uno per ogni connettivo del linguaggio con Op¬ : B 7! Be Op^ e Op_ : B ⇥ B 7! B.Dove: Op¬(1) = 0 e Op¬(0) = 1
Op^:
↵ � ↵ ^ �
1 1 11 0 00 1 00 0 0
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 16
Op_:
↵ � ↵ _ �
1 1 11 0 10 1 10 0 0
} Le operazioni ^ e _ sono commutative e associative. Infatti e facilemostrare che per ogni assegnazione ai simboli proposizionali ↵, �, � abbiamoche
↵ ^ � = � ^ ↵
↵ _ � = � _ ↵_e(↵ ^ �) ^ � = ↵ ^ (� ^ �)(↵ _ �) _ � = ↵ _ (� _ �)
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 17
Semantica: Valutazione booleana
} Un’assegnazione booleana V ai simboli proposizionali A e una funzionetotale: V : A 7! {1, 0}.
} Una valutazione booleana IV : Prop 7! {1, 0} e l’estensione a Prop
di un’assegnazione booleana, cioe
IV (A) = V(A) se A 2 A;
IV (>) = 1;
IV (?) = 0;
IV (¬↵) = Op¬(IV (↵));IV (↵ ^ �) = Op^(IV (↵), IV (�)).IV (↵ _ �) = Op_(IV (↵), IV (�)).
Data V , si puo facilmente dimostrare che l’estensione IV esiste ed e unica.Notate che e una definizione ricorsiva (ricorsione strutturale).
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 18
Esempio
} Tre amici, Antonio, Bruno e Carla, sono incerti se andare in pizzeria.Introduciamo tre proposizioni:
A : Antonio va in pizzeria, B: Bruno va in pizzeria, C: Carla va in pizzeria
} Il giorno dopo sappiamo che:Antonio non va in pizzeria, Bruno va in pizzeria, Carla va in pizzeriaFormalmente abbiamo la valutazione V : A = 0, B = 1, C = 1
} Data V valutiamo le formule↵: Tutti e tre sono andati in pizzeria ↵ = A ^B ^ C
�: Almeno due sono andati in pizzeria � = (A^B)_ (A^C)_ (B ^C)
Applicando le regole mostrare che IV (↵) = 0 e che IV (�) = 1
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 19
Tautologie e contraddizioni
Definizioni:} Una formula proposizionale ↵ e soddisfatta da una valutazione booleanaIV se IV (↵) = 1.
} Una formula proposizionale ↵ e soddisfacibile se e soddisfatta da unaqualche valutazione booleana IV .
} Una formula proposizionale ↵ e una tautologia se e soddisfatta da ognivalutazione booleana IV .
} Una formula proposizionale ↵ e una contraddizione se non e soddisfattada nessuna valutazione booleana IV .Una formula ↵ e una tautologia se e solo se ¬↵ e una contraddizione.
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 20
Esempi
} ↵ = A _ (¬A) e una tautologia
A ¬A A _ ¬A1 0 10 1 1
} � = A ^ (¬A) e una contraddizione
A ¬A A ^ ¬A1 0 00 1 0
} Con riferimento all’esempio precedente dei tre amici in pizzeria: la formulaA ^ B ^ C e soddisfacibile (ma non e una tautologia)Infatti la formula e vera quando tutti e tre vanno in pizzeria, cioe per lavalutazione V per cui A = B = C = 1 abbiamo IV (A ^B ^ C) = 1.Inoltre per ogni altra valutazione V 0, V 0 6= V abbiamo che IV 0(A^B^C) = 0
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 21
Equivalenza logica
Definizioni:
} ↵ implica logicamente � (denotato ↵ ) �) se e solo se per ogni valu-tazione booleana IV , ogniqualvolta IV (↵) = 1 anche IV (�) = 1.
} Esercizio: ↵ implica logicamente � (denotato ↵ ) �) se e solo ↵ ! �
e una tautologia
} ↵ e � sono logicamente equivalenti o tautologicamente equivalenti (de-notato ↵ ⌘ �) se e solo se IV (↵) = IV (�) per ogni valutazione booleanaIV .} Esercizio: ↵ e � sono logicamente equivalenti o tautologicamente equiv-alenti (denotato ↵ ⌘ �) se e solo↵ implica logicamente � e � implica logicamente ↵
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 22
Altri connettivi: 1
} Siamo in grado di rappresentare la congiunzione e la disgiunzione diproposizioni, ma siamo in grado di denotare la nozione di implicazione traproposizioni ?
• Il fatto che una proposizione ↵ implica un’altra � viene denotato con↵ ! �
• Quale e il suo operatore (tabella di verita ) Op! ?
Op!:
↵ � ↵ ! �
1 1 11 0 00 1 10 0 1
} NOTA: Nel caso in cui l’antecedente (↵) dell’implicazione sia falso,l’implicazione e vera.
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 23
Altri connettivi: 2
} Possiamo ora introdurre anche l’operatore ↵ $ �, che denota la relazioneche le due formule (↵ e �) si implicano vicendevolmente (↵ ! � e � ! ↵).Il conseguente operatore Op$ e cosı definito:
Op$:
↵ � ↵ $ �
1 1 11 0 00 1 00 0 1
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 24
Definibilita di connettivi
Dato un insieme di connettivi C e un connettivo c 62 C per cui si abbia unafunzione di verita f
c
= Op
c
, si dice che c si deriva dai (oppure si definisce intermini dei) connettivi di C se esiste una formula proposizionale F costruitausando solo i connettivi di C tale che f
c
⌘ f
F
.
Esempio:Il connettivo ^ si puo definire in termini di {¬,_} nel seguente modo:(↵ ^ �) ⌘ ¬(¬↵ _ ¬�). Infatti si puo facilmente verificare che per ognivalore di ↵ e � le due funzioni ↵ ^ � e ¬(¬↵ _¬�) hanno lo stesso valore.
↵ � ¬↵ ¬� ¬↵ _ ¬� ¬(¬↵ _ ¬�) ↵ ^ �
1 1 0 0 0 1 11 0 0 1 1 0 00 1 1 0 1 0 00 0 1 1 1 0 0
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 25
Definibilita di connettivi: esempi
(↵ ! �) ⌘ (¬↵ _ �)
(↵ _ �) ⌘ (¬↵ ! �)
(↵ _ �) ⌘ ¬(¬↵ ^ ¬�)(↵ ^ �) ⌘ ¬(¬↵ _ ¬�)(↵ ^ �) ⌘ (((↵ ! ?) ! ?) ! (� ! ?)) ! ?
¬↵ ⌘ ↵ ! ?? ⌘ ↵ ^ ¬↵
(↵ $ �) ⌘ (↵ ! �) ^ (� ! ↵)
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 26
Precedenza operatori
} la massima precedenza a ¬, poi, nell’ordine, ai connettivi ^,_, !, $.
} Esempi
La formula ¬↵ ^ ¬�viene parentetizzata come ((¬↵) ^ (¬�)).La formula ↵ ^ � _ �
viene parentetizzata come ((↵ ^ �) _ �).
La formula ¬↵ ^ ¬� ! � ^ � ^ ✏
viene parentetizzata come (((¬↵) ^ (¬�)) ! (� ^ (� ^ ✏))).
La formula ¬↵ ^ (¬� ! �) ^ � ^ ✏
viene parentetizzata come ((¬↵) ^ ((¬�) ! �) ^ (� ^ ✏)).
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 27
Leggi 1
La definizione dei connettivi implica diverse equivalenze logiche che sonovalide per ogni formula ↵ e �
1. Idempotenza:
↵ ^ ↵ ⌘ ↵
↵ _ ↵ ⌘ ↵
2. Associativita:
↵ ^ (� ^ �) ⌘ (↵ ^ �) ^ �
↵ _ (� _ �) ⌘ (↵ _ �) _ �
↵ $ (� $ �) ⌘ (↵ $ �) $ �
3. Commutativita:
↵ ^ � ⌘ � ^ ↵
↵ _ � ⌘ � _ ↵
↵ $ � ⌘ � $ ↵
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 28
Leggi 2
1. Distributivita:
↵ ^ (� _ �) ⌘ (↵ ^ �) _ (↵ ^ �)
↵ _ (� ^ �) ⌘ (↵ _ �) ^ (↵ _ �)
2. Assorbimento:
↵ ^ (↵ _ �) ⌘ ↵
↵ _ (↵ ^ �) ⌘ ↵
3. Doppia negazione:
¬¬↵ ⌘ ↵
4. Leggi di De Morgan:
¬(↵ ^ �) ⌘ ¬↵ _ ¬�¬(↵ _ �) ⌘ ¬↵ ^ ¬�
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 29
Leggi 3
1. Terzo escluso:
↵ _ ¬↵ ⌘ >2. Contrapposizione:
↵ ! � ⌘ ¬� ! ¬↵3. Contraddizione:
↵ ^ ¬↵ ⌘ ?.
} Queste leggi si possono verificare costruendo una tabella di verita e veri-ficare che per ogni valore delle variabili otteniamo i valori delle due funzionia destra e a sinistra di ⌘ sono uguali
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 30
Funzioni booleane e insiemi di connettivi
Definizione:Sia ↵ una formula contenente esattamente n atomi distinti A
1
, A
2
, . . . , A
n
;la funzione f
↵
: {0, 1}n 7! {0, 1} tale che f↵
(v1
, v
2
, . . . , v
n
) = IV (↵)dove V e l’interpretazione per cui V(A
i
) = v
i
per ogni i = 1, 2, . . . , n edetta la funzione di verita (o funzione booleana) associata ad ↵.
Quindi, ogni proposizione del calcolo proposizionale definisce una funzionen-aria (o connettivo n-ario), dove n e il numero degli atomi distinti che inessa compaiono.
Per ogni n esistono 22n
funzioni booleane distinte (cioe tante quanti sono isottoinsiemi di {0, 1}n). Nel caso di n = 2 esistono 16 connettivi distinti.
Noi ne abbiamo introdotti 4, non indipendenti, nel senso che alcuni sonoesprimibili in termini di altri.
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 31
Completezza di insiemi di connettivi
} Un insieme di connettivi logici C si dice completo se e solo se, datauna qualunque f : {0, 1}n 7! {0, 1} esiste una formula proposizionale ↵
costruita mediante i connettivi dell’insieme C tale che f ⌘ f
↵
.
} Teorema: L’insieme {¬,^,_} e completo.Prova: in due passi1. Usando ¬ e ^ si puo dimostrare come realizzare una funzione di n variabiliche e sempre falsa tranne per un singola assegnazione di valori di verita .2. Data una funzione f che e 1 per k diversi valori di verita (V
1
,V2
, ...,Vk
),utilizzando il passo 1 precedente per ogni i, i = 1, 2, ..k si definisce lafunzione f
i
che e 1 per Vi
ed e sempre 0 altrimenti. La funzione f e datada: f
1
_ f
2
_ ... _ f
k
.
Esercizi:Mostrare che gli insiemi {¬,^}, {¬,_} , {nand} e {nor} sono completi.Sugg. Il teorema precedente a↵erma che {¬,^,_} e completo. Pertanto esu�ciente mostrare come realizzare l’insieme di operatori {¬,^,_}
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 32
Esempio 1
} Tre amici, Antonio, Bruno e Corrado, sono incerti se andare in pizzeria.Introduciamo tre proposizioni:
A : Antonio va in pizzeria, B: Bruno va in pizzeria, C: Carla va in pizzeria(A e 1 se Anotnio va in pizzeria, 0 altrimenti)
} Si sa che:Se Carla va in pizzeria, allora ci va anche Antonio: C ! A
eSe Antonio va in pizzeria allora ci va anche Bruno: A ! B
Formalmente abbiamo la formula: (C ! A) ^ (A ! B)
} Consideriamo ora le asserzioni1. Tutti e tre vanno in pizzeria: equivale a ↵ = A ^ B ^ C
2. Se Carla va in pizzeria anche Bruno va in pizzeria: � = C ! B
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 33
Esempio 1
} Domanda 1:Sapere che se Carla va in pizzeria ci va anche Antonio e che se Antonio vain pizzeria ci va anche Bruno, e su�ciente per a↵ermare cheTutti e tre vanno in pizzeria?
Formalmente ci chiediamo se (C ! A) ^ (A ! B) implica logicamenteA ^ B ^ C
} Risposta: No(C ! A) ^ (A ! B) NON implica logicamente A ^ B ^ C. Infatti
Consideriamo V per cui A = B = C = 0Con questa assegnazione (C ! A) ^ (A ! B) e soddisfatta. InfattiIV (C ! A) = 1 (infatti se C = 0 l’implicazione C ! A e vera)analogamente IV (A ! B) = 1Quindi IV ((C ! A) ^ (A ! B)) = 1Poiche IV (A ^ B ^ C) = 0 concludiamo che (C ! A) ^ (A ! B) NONimplica logicamente A ^ B ^ C
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 34
Esempio 1, cont.
} Dimostrare che (C ! A) ^ (A ! B) implica logicamente A ^ B ^ C
equivale a dimostrare che la seguente formula e una tautologia[(C ! A) ^ (A ! B)] ! (A ^B ^ C) (*)
} La formula (*) e soddisfacibile ma non e una tautologia.Infatti abbiamo visto che la valutazione V per cui A = B = C = 0 soddisfa(C ! A) ^ (A ! B) e ma (A ^ B ^ C) non e soddisfatta.
} Se consideriamo V 0 per cui A = B = C = 1 possiamo verificare che laformula (*) e soddisfatta.Infatti e su�ciente osservare che A ^ B ^ C e soddisfatta e, quindi, ancheIV 0[((C ! A) ^ (A ! B)) ! (A ^ B ^ C)] = 1
} In conclusione possiamo a↵ermare cheSapere che se Carla va in pizzeria ci va anche Antonio e che se Antonio vain pizzeria ci va anche Bruno, non implica logicamente che tutti e tre sianoandati in pizzeria, ma possiamo dire che e possibile che tutti e tre sianoandati in pizzeria
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 35
Esempio 2
} Domanda 2:sapere che se Carla va in pizzeria ci va anche Antonio e che se Antonio vain pizzeria ci va anche Bruno, e su�ciente per a↵ermare cheSe Carla e andata in pizzeria anche Bruno e andato in pizzeria?
Formalmente ci chiediamo se (C ! A) ^ (A ! B) implica logicamenteC ! B
} Risposta: SIA questo scopo possiamo ricostruire una tabella che verifica il valore dellaformula per tutte le possbili assegnazioni di valori ad A, B e C. In questomodo dobbiamo verificare che la formula sia vera per 23 = 8 possibili valoridi verita .
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 36
A B C C ! A A ! B (C ! A) ^ (A ! B) C ! B
0 0 0 1 1 1 11 0 0 1 0 0 10 1 0 1 1 1 11 1 0 1 1 1 10 0 1 0 1 0 01 0 1 1 0 0 00 1 1 0 1 0 11 1 1 1 1 1 1
E’ facile vedere che ogni qualvolta IV (C ! B = 1) abbiamo cheIV (C ! A) ^ (A ! B) = 1
Si noti inoltre che quando IV (C ! A) ^ (A ! B) = 0 allora IV (C ! B
puo essere 1 o 0
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 37
Esempio, cont. 2
} Possiamo pertanto rispondere alla Domanda 2:sapere che se Carla va in pizzeria ci va anche Antonio e che se Antonio vain pizzeria ci va anche Bruno, e logicamente equivalente aSe Carla e andata in pizzeria anche Bruno e andato in pizzeria
} Abbiamo visto che (C ! A) ^ (A ! B) implica logicamente C ! B
Questa proprieta e nota come transitivita dell’implicazione
} Si noti la somiglianza con il sillogismo su Socrate
• Se A implica B
• e B implica C
• allora possiamo a↵ermare che A implica C
Nota: La di↵erenza e che nel caso del sillogismo su Socrate la prima a↵er-mazione non e una formula atomica ma riguarda un insieme di atomi (Tuttigli uomini sono mortali)
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 38
Esempio 2, cont.
} Possiamo pertanto rispondere alla Domanda 2:sapere che se Carla va in pizzeria ci va anche Antonio e che se Antonio vain pizzeria ci va anche Bruno, e e logicamente equivalente aSe Carla e andata in pizzeria anche Bruno e andato in pizzeria
} Dobbiamo dimostrare se (C ! A) ^ (A ! B) ⌘ (C ! B)Abbiamo visto che (C ! A) ^ (A ! B) ) C ! B
L’equivalenza e vera se vale anche la seguente implicazione(C ! B) ) ((C ! A) ^ (A ! B))
Consideriamo V = (A = 1, B = 0, C = 0).Abbiamo IV (C ! B) = 1, ma IV (A ! B) = 0. Quindi(C ! B) non implica logicamente ((C ! A) ^ (A ! B))
Fondamenti di Informatica 2, Linguaggi e Complessita : Logica I Parte Lucidi di M.Schaerf e A.Marchetti Spaccamela 39
Top Related