Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
IDEMPOTENZA
≡
P v P v Q P v Q
≡
P P Q P Q
∧ ∧ ∧
DISTRIBUTIVITA’
≡
P ( Q v R ) ( P Q ) v ( P R )
∧ ∧ ∧
≡
P ( Q R ) ( P Q ) ( P R )
v ∧ v ∧ v
FORMA NORMALE NEGATA (FNN)
Una formula F è in forma normale negata quando in F la negazione si applica solo ad atomi.
FORMA NORMALE CONGIUNTA (FNC)
Una formula F è in forma normale congiunta quando è una congiunzione di disgiunzioni di letterali.
FORMA NORMALE DISGIUNTA (FND)
Una formula F è in forma normale disgiunta quando è una disgiunzione di congiunzioni di letterali.
LIMITAZIONI DEL METODO DELLE TAVOLE DI VERITA’
1) Permette di riconoscere solo conseguenze tautologiche, non conseguenze logiche in generale;
n
2) Con n variabili proposizionali si creano 2 configurazioni.
DEDUZIONE NATURALE
Le prove si possono rappresentare come alberi.
SOTTOPROVE: pezzi di prova all’interno di altre prove.
CAMMINO:
In una sequenza di archi [(v ,v ), (v ,v ), (v ,v ), (v ,v )] per ogni i >= 1 il nodo v d’arrivo dell’arco i-esimo è
1 2 2 3 i i+1 n-1 n 1
il nodo sorgente dell’arco (i+1)esimo CONCATENAZIONE
ALBERO
Grafo diretto (con archi orientati) dove c’è un vertice distinto detto “radice” con la proprietà che per ogni
altro vertice esiste ed è unico il cammino dalla radice al vertice. Negli alberi i vertici si chiamano nodi.
A radice
C nodo
B sottoalbero
D E F foglie
Il sottoalbero è una parte di un albero che è a sua volta un albero.
REITERAZIONE
In una prova è permesso ripetere una formula (premessa o derivata).
PROVE COME ALBERI
- I nodi sono etichettati da formule
- La radice è etichettata dalla conclusione
- Le foglie sono etichettate dalle premesse
- Le sottoprove sono sottoalberi
SCARICARE LE PREMESSE
Si possono scaricare premesse assunte come ipotesi temporanee quando la sottoprova che le
assume è conclusa;
Non è permesso usare formule di una sottoprova completata le cui premesse sono state scaricate,
al di fuori della sottoprova stessa.
REGOLE / CRITERI PER COSTRUIRE LE PROVE
STRATEGIE DI PROVA da dimostrazioni automatiche
TATTICHE DI PROVA da dimostrazioni interattive
1- Chiedersi se la congettura sia vera (umano);
2- Cercare un controesempio (umano) se si trova allora si scarta la congettura e si può cercare di
dimostrare la negazione della congettura;
3- Partire dalle congetture (meccanico) goals.
CONNETTIVI LOGICI NEL LINGUAGGIO NATURALE
La logica è un linguaggio formale, molto più semplice di un linguaggio naturale. Ci sono infatti congiunzioni
appartenenti al linguaggio naturale che non corrispondono a connettivi logici. Anche quando sembra
esserci corrispondenza, essa è solo parziale.
Es1:
“perché” Essendo una congiunzione che introduce una causale non si può costruire una tavola di verità,
perciò non ha connettivi in logica.
Es2:
L’implicazione nel linguaggio naturale non segue la tavola di verità costruita per l’implicazione logica.
BI-CONDIZIONALE (condizionale bi-direzionale, equivalenza, doppia
implicazione) P Q
“P se e solo se Q” , “P è equivalente a Q”, …
Relazione binaria con proprietà:
- RIFLESSIVA
- SIMMETRICA
- TRANSITIVA
- SOSTITUTIVA
TEOREMA DI DEDUZIONE P |- Q
Dimostrazione di Q da P, fatta per dimostrare che Q è conseguenza logica di P ( P |= Q ). Scrivere ‘P |= Q’
vuol dire che in tutte le circostanze in cui P è vero anche Q è vero.
P |- Q se e solo se |= P Q
P |- Q se e solo se |= P Q
P |= Q
In tutte le circostanze in cui P è vera allora Q è vera, quindi ‘ P Q ’ è vera. In tutte le circostanze in cui P è
falsa, ‘ P Q ’ è vera. ‘ P Q ’ è vera in tutte le circostanze (‘|= P Q ’).
|= P Q
‘ P Q ’ è vera in tutte le circostanze, per ogni circostanza in cui P è vera, ‘ P Q ’ è vera, perché è vera in
tutte le circostanze (‘ P |= Q ’ ).
IMPLICATURE CONVERSAZIONALI
1) La disgiunzione viene letta come ESCLUSIVA quando non lo è
Un’implicazione nel linguaggio naturale non è una vera implicazione, ma un’implicatura conversazionale, se
la conversazione può continuare in un modo che nega l’implicazione.
Es: “Con il panino si ha diritto ad una insalata o ad una zuppa.”
2) “A meno che” viene letto come “se e solo se”
Es: “Aldo è a casa a meno che Chiara sia in biblioteca.”
¬InBiblioteca(chiara) Acasa(Aldo) ___________ CORRETTA IN LOGICA
¬InBiblioteca(chiara) Acasa(Aldo) _________ NON CORRETTA IN LOGICA
3) “Solo se” viene letto come “se e solo se”
Es: “Puoi mangiare il dolce solo se prima finisci la minestra.”
Mangiare(dolce) Finita(minestra) ___________ CORRETTA IN LOGICA
Mangiare(dolce) Finita(minestra) _________ NON CORRETTA IN LOGICA
Finita(minestra) Mangiare(dolce) Mangiare(dolce) Finita(minestra)
0 0 1
0 1 0
1 0 1
1 1 1
ADEGUATEZZA O COMPLETEZZA VERO-FUNZIONALE DEI CONNETTIVI
1) QUANTI CONNETTIVI POSSIAMO AVERE IN UN LINGUAGGIO LOGICO?
|A| = n , |B| = k , allora :
A B = { f | f: A B }
n
|A B| = k
2) QUALI SONO GLI INSIEMI DI CONNETTIVI ADEGUATI O COMPLETI?
Non conviene minimizzare l’insieme dei connettivi perché eliminandone alcuni è molto più complicato
costruire prove.
Es: ELIMINAZIONE DELLA CONGIUNZIONE
∧
P Q Intro
∧
P Q ∧
Con l’uso dell’introduzione della congiunzione si può creare “P Q” in un solo passaggio. Se non si potesse usare
questo connettivo: ⊥ ⊥
¬ Intro ¬ Intro
P P Q Q
⊥ ⊥ v elim
¬P v ¬Q ⊥ ¬ Intro
¬(¬P v ¬Q)
La prova risulta notevolmente appesantita senza l’uso del connettivo logico ‘∧’.
Esempi di insiemi completi: ∧,
{ ¬ }
∧,
{ ¬ }
{ v , ¬ }
⊥
{ , }
PROPRIETA’ IMPLICAZIONE
P Q ≡ ¬Q ¬P Contropositivo
P Q ≡ ¬P v Q
∧
¬ (P Q) ≡ P ¬Q
∧ (Q P)
P Q ≡ (P Q)
∧ ∧
P Q ≡ (P Q) v (¬P ¬Q)
DOPPIA IMPLICAZIONE
Introduzione
P Q
Π Π
Q P Intro
P Q
Eliminazione
P P Q Elim
Q
Oppure
P P Q Elim
P SISTEMA DI DEDUZIONE F
, ,
∧, ⊥,
- Regole di introduzione ed eliminazione di V, ¬, = ;
- Ragionamento valido: se tutte le premesse sono vere allora la conclusione è vera;
- Ragionamento corretto: ragionamento valido le cui premesse sono vere;
- Insieme di connettivi completi/adeguati: quando permettono di esprimere qualsiasi altro
connettivo;
PROPRIETA’ DI UN SISTEMA DI DEDUZIONE
Un sistema di deduzione si dice corretto quando da delle premesse (P) si arriva a una conclusione
(S). Perciò si potrà dire che la conclusione è conseguenza logica delle premesse. Ogni dimostrazione
in F è un ragionamento valido;
es: se P |- S allora P |= S
Un sistema di deduzione F si dice completo quando esiste l’implicazione opposta, cioè si riesce a
dimostrare una cosa vera;
es: se P |= S allora P |- S
S è conseguenza tautologica di P quando nella tavola di verità congiunta S è vera ovunque dove P è
vera. QUANTIFICATORI
Nel linguaggio naturale sono elementi che determinano una quantità.
ES: “ognuno”, “tutti”, “ciascuno”, “tre”, “la maggior parte”
Nella logica al primo ordine ci sono:
∀
“ ” “per ogni”;
∃
“ ” “esiste”;
QUANTIFICATORI E VARIABILI
Una variabile si dice: ∀x
- LEGATA se cade nel campo di applicazione di un quantificatore; Piccolo(x)
- LIBERA se non cade nel campo di applicazione di un quantificatore; Piccolo(x)
OCCORRENZA DELLE VARIABILI
Se una variabile è legata, non ha importanza come si chiami perché l’importante è il quantificatore.
Data una formula F:
Var(F) : variabili che occorrono in F;
Libere(F) : variabili libere in F;
Legate(F) : variabili legate in F;
es:
F Var(F) = Libere(F)
∧
Libere(F G) Libere(F) U Libere(G)
Libere(∀x F) Libere(F) – {x}
INTERPRETAZIONE DI VARIABILI LEGATE
∀xF soddisfatta se esiste almeno un elemento nel dominio del modello per cui F è soddisfatta;
∃xF soddisfatta se per tutti gli elementi nel dominio del modello è soddisfatta;
Si dice formula universale soddisfatta a vuoto se l’antecedente è falsa, quindi l’implicazione è vera.
4 FORMULE QUANTIFICATE UNIVERSALMENTE
1. Tutti i P sono Q
2. Alcuni P sono Q
3. Nessun P è Q
4. Alcuni P non sono Q
Perché si chiama logica al primo ordine?
Si chiama così perché i quantificatori non si applicano a funzioni e predicati ma solo a oggetti e individui.
∅
ENUNCIATO: formula dove tutte le variabili sono quantificate. Libere(F) =
FORMA VERO-FUNZIONALE DI UNA FORMULA
Si ottiene sostituendo le sottoformule quantificate e gli atomi con atomi proporzionali.
∀x
Es: Cubo(x) v Piccolo(x) A v B
TAUTOLOGIA
Un enunciato è una tautologia se e solo se la sua formula vero funzionale è una tautologia.
LOGICA PROPOSIZIONALE LOGICA AL PRIMO ORDINE GENERALE
Tautologia Validità al primo ordine Verità logica
Conseguenza tautologica Conseguenza logica al primo ordine Conseguenza logica
Equivalenza tautologica Equivalenza logica al primo ordine Equivalenza logica
Solo con assiomi si possono riconoscere tautologie in logica al primo ordine.
ASSIOMI DELL’IDENTITA’
∀x
1) x = x
∀x,∀y
2) x = y y = x
∀x,∀y,∀z ∧
3) x = y y = z x = z
∀x,∀y
4) x = y P(x) = P(y)
METODO ASSIOMATICO: scrivere formule che si assumono vere e che descrivono il significato dei predicati.
POSTULATI DI SIG