Il ragionamento classico
La logica
• Si basa su una grammatica che consente di derivare da un insieme di proposizioni iniziali date come vere (ASSIOMI) tutte le proposizioni con essi congruenti (TEOREMI).
• Una grammatica è un insieme di regole formali che consente di decidere se una proposizione è ben formata oppure no.
La logica
• La logica è costruita a partire da due classi di oggetti:
• Termini: denotano gli oggetti di cui si parla
• Costanti predicative o predicati: denotano relazioni tra oggetti (in un numero qualsiasi)
La logica
• Si chiama formula atomica la proposizione ottenuta applicando un predicato ad uno o più termini.
• Esempi: cane(Milù) un argomento uccide(Bruto, Cesare) due
argomenti
I Linguaggi L1 e L2
• Esistono due livelli di linguaggio logico:
• L1 o logica delle proposizioni (Logica Booleana o aritmetica)• L2 o logica dei predicati (Logica matematica)
Il Linguaggio L1 oCalcolo proposizionale
• La ‘grammatica’ della logica del primo ordine (Linguaggio L1) è definita dalla Tavola di Verità di 4 simboli che consentono di formare formule complesse a partire da formule atomiche.
• Questi simboli si chiamano connettivi logici.
I connettivi logici
• La negazione ()• L’unione ()• La disgiunzione ()• L’implicazione ()
Definizione dei connettivi logici
A B A AB AB AB
1 1 0 1 1 1
1 0 0 1 0 0
0 1 1 1 0 1
0 0 1 0 0 1
Interpretazione di una formula atomica
Per attribuire un valore di verità ad una formula atomica (dire se una certa proposizione è vera o falsa) è necessario fissare una interpretazione relativamente ad un dominio
Interpretazione di una formula atomica
Esempio: cane(Milù) ha valore 1 se nel nostro ‘mondo’ esiste un cane di nome Milù, ovvero se Milù appartiene all’insieme dei cani del nostro ‘mondo’.
Algebra degli insiemi di Boole
Attribuire un valore di verità ad una proposizione quindi è equivalente a dire se un certo elemento appartiene ad un dato insieme.
E’ possibile riformulare il linguaggio L1 in termini di operazioni tra insiemi.
Algebra degli insiemi di Boole
La negazione corrisponde all’operazione di complemento ad uno:
A A AA
Algebra degli insiemi di Boole
L’unione corrisponde all’operazione di unione di insiemi
A A A B
Algebra degli insiemi di Boole
La disgiunzione corrisponde all’operazione di intersezione di insiemi
A A B
Algebra degli insiemi di Boole
L’implicazione è sempre vera tranne quando A è vera e B è falsa, quindi è sempre vera tranne che per la porzione ‘colorata’ di A:
A B
Definizione di algebra (ad usum delphini)
Un algebra è un insieme chiuso di elementi su cui è definita una operazione di somma e di prodotto per uno scalare che godono delle proprietà ‘standard’ della somma e del prodotto…(commutatività, esistenza dell’elemento neutro…)
Tautologie e Teorie Logiche
Una formula logica si definisce tautologica o logicamente valida se è sempre vera, a prescindere dalle interpretazioni dei termini che in essa compaiono.
L’insieme degli assiomi e di tutte le tautologie che da essi si possono derivare si chiama TEORIA LOGICA.
Linguaggio L2: la logica dei predicati
Si ottiene a partire da L1 ampliando la ‘grammatica’ con l’introduzione di due nuovi simboli:
Il quantificatore esistenziale: e il quantificatore universale:
Significato del quantificatore universale
x A(x) si legge per ogni individuo x è vero A(x). x è una variabile (o simbolo non terminale), cioè un valore che sostituisce un termine generico.
L’espressione x A(x) si chiama formula quantificata universalmente.
Significa che A(x) è vero qualunque sia il termine che sostituisce x in un dato dominio.
Significato del quantificatore esistenziale
x A(x) si legge esiste x tale che A(x) è vero.
L’espressione x A(x) consente di affermare che in un certo dominio esisrte almeno un individuo che possiede la proprietà A.
Apparato deduttivo
È un insieme di procedure che consentono di derivare dagli assiomi di una teoria tutti i teoremi (formule non contraddittorie con gli assiomi) che appartengono alla teoria stessa.
Dimostrare un teorema significa decidere se una data formula appartiene o no ad una teoria.
Apparato deduttivo
Un apparato deduttivo è costituito da regole per realizzare inferenze corrette
ovvero non fallaci.
Le principali regole di inferenza sono 2:Modus PonensRegola di particolarizzazione
Modus ponens
A AB B
Se A è vera e A implica B allora per definizione di implicazione è vera B
Regola di particolarizzazione
x A(x) A(t)
Consente di derivare istanze o esempi specifici da una formula quantificata universalmente.
Il calcolo automaticoo ragionamento formale
Utilizza l’apparato deduttivo del Linguaggio L2 per dimostrare teoremi ovvero per riconoscere tutte le formule che fanno implicitamente parte di una data Teoria logica.
DOMANDA: Esiste una verifica meccanica per definire qualunque verità matematica?
I limiti del ragionamento formaleDato un sistema di assiomi (…) si
pongono due questioni rilevanti:1) Problema della coerenza: Da questo
sistema potrà mai essere dedotta una affermazione contraddittoria?
2) Problema della completezza: è possibile derivare tutte le proposizioni vere in modo automatico a partire dagli assiomi?
I limiti del ragionamento formaleDOMANDA: La logica è un sistema
coerente e completo? Hilbert, Università di Bologna, 1928
RISPOSTA: NOPrimo Teorema di Incompletezza di GödelVienna, Accademia delle Scienze, 1930
Genio e… regolatezza1 Usando una codifica data associo ad
ogni espressione formale un numero naturale
2 Quindi una espressione formale che dice qualcosa sui numeri naturali dice qualcosa su altre espressioni formali
3 Esiste l’espressione formale G che dice di se stessa: “Io non sono formalmente dimostrabile”
Genio e… regolatezza4 Allora delle due l’una:• G è vera e allora esiste una
espressione non formalmente dimostrabile e il sistema (aritmetico, quindi L1) è incompleto
• G è falsa e allora abbiamo dedotto una proposizione contraddittoria usando una inferenza valida. Quindi il sistema è incoerente.
I limiti del calcolo classicoQuindi il calcolo classico NON basta a se
stesso e non si può automatizzare il ragionamento matematico.
Qualcosa resta fuori…
Un nuovo tipo di matematicaTuttavia l’uso del calcolatore ha permesso
di risolvere problemi matematici ritenuti insolubili utilizzando strategie esaustive e cioè analizzando una ad una tutte le alternative possibili. Per esempio:
il matematico definisce la forma che necessariamente deve avere una soluzione e il calcolatore esamina tutte le soluzioni di quella forma.
Dalla logica al senso comune
Aspetti del ragionamento di senso comune non considerati dal ragionamento logico classico:
Verità che cambiano nel tempoNecessarietà o obbligatorietà di una azione
Questi aspetti conducono all’evoluzione del formalismo logico e all’introduzione delle LOGICHE MODALI
Logica deontica
Si usa per formalizzare conoscenze relative all’ambito giuridico (ciò che è permesso, ciò che lecito…)
Usa gli operatori modali O e P:• O indica ciò che è obbligatorio• P indica ciò che è permesso
Assiomi della Logica deontica
Definiscono il senso degli operatori P e O:PA ¬O ¬A
OAPAGli assiomi indicano che sono permesse
tutte e sole le cose che non sono esplicitamente vietate e che ciò che è obbligatorio deve essere anche permesso
Logica Temporale Modale
Si utilizza soprattutto nella pianificazione di azioni. L’idea è di costruire una successione di mondi ciascuno dei quali rappresenta lo stato delle cose ad un certo istante di tempo:
t1, t2, t3, t4….
m1, m2, m3, m4….
Logica Temporale Modale
Gli operatori introdotti sono del tipo�, , o�A significa A è vero da ora in poi A significa A sarà vero da un qualche t
futuro in poioA significa A sarà vero dal prossimo
istante di tempo in poi