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