Componenti di un sistema...

35
1 Componenti di un sistema KNOWLEDGE-BASED IL DATABASE DESCRIVE LA SITUAZIONE CORRENTE NELLA DETERMINAZIONE DELLA SOLUZIONE AL PROBLEMA. LA FORMALIZZAZIONE DEL PROBLEMA DEFINISCE LE REGOLE DI TRASFORMAZIONE CHE GENERANO NUOVE ASSERZIONI A PARTIRE DA QUELLE ESISTENTI. IL SISTEMA DI CONTROLLO DECIDE QUALE REGOLA USARE PER TRASFORMARE IL DATABASE, IN MODO DA GIUNGERE, DOPO VARIE ITERAZIONI, ALLA SOLUZIONE DEL PROBLEMA …CONSIDERAZIONE CIASCUN COMPONENTE È FORTEMENTE DIPENDENTE DAL DOMINIO IN ESAME. DYNAMIC DATABASE PROBLEM FORMALIZATION CONTROL STRATEGY

Transcript of Componenti di un sistema...

Page 1: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

1

Componenti di un sistemaKNOWLEDGE-BASED

IL DATABASE DESCRIVE LA SITUAZIONE CORRENTE NELLA DETERMINAZIONE DELLA SOLUZIONE AL PROBLEMA.

LA FORMALIZZAZIONE DEL PROBLEMA DEFINISCE LE REGOLE DI TRASFORMAZIONE CHE GENERANO NUOVE ASSERZIONI A PARTIRE DA QUELLE ESISTENTI.

IL SISTEMA DI CONTROLLO DECIDE QUALE REGOLA USARE PER TRASFORMARE IL DATABASE, IN MODO DA GIUNGERE, DOPO VARIE ITERAZIONI, ALLA SOLUZIONE DEL PROBLEMA

…CONSIDERAZIONE

CIASCUN COMPONENTE È FORTEMENTE DIPENDENTE DAL DOMINIO IN ESAME.

DYNAMICDATABASE

PROBLEMFORMALIZATION

CONTROLSTRATEGY

Page 2: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

2

RAPPRESENTAZIONE SSR:LO SPAZIO DEGLI STATI

STATI: STRUTTURE DATI IN GRADO DI DESCRIVERE LA CONDIZIONE DEL PROBLEMA IN UN PASSO DEL PROCESSO RISOLUTIVO

OPERATORI: FUNZIONI CHE, DATO UN QUALSIASI STATO DEL PROBLEMA, NE DETERMINANO I SUCCESSORI

STATO INIZIALE: STATO DA CUI SI INTENDE FAR PARTIRE IL PROCESSO RISOLUTIVO

STATI FINALI: STATI RISOLUTIVI DEL PROBLEMA

Page 3: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

3

ESEMPIO: L’8 PUZZLE

STATI :CONFIGURAZIONI DEL PUZZLE (MATRICE 3x3)

OPERATORI :N = SPOSTA IL BIANCO A NORD SEIL BIANCO NON È IN RIGA 1

S = SPOSTA IL BIANCO A SUD SEIL BIANCO NON È IN RIGA 3

E = SPOSTA IL BIANCO A EST SEIL BIANCO NON È IN COLONNA 3

O = SPOSTA IL BIANCO A OVEST SEIL BIANCO NON È IN COLONNA 1

647 1 52 3 8

Page 4: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

4

ESEMPIO: L’8 PUZZLE

STATO INIZIALE:UNA PREFISSATA CONFIGURAZIONE DEL PUZZLE

STATO FINALE:

647 1 52 3 8

214 5 67 8

3

Page 5: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

5

REGOLE DI RISCRITTURA PER L’8 PUZZLE

Page 6: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

6

UNA PORZIONE DELL’ALBERO DI RICERCA DEL GIOCO DEL “QUINDICI”

Page 7: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

7

UN SECONDO ESEMPIO: GLI SCACCHI

IL DATABASE DINAMICO DEFINISCE LO STATO CORRENTE DELLA PARTITA (POSIZIONE DEI PEZZI, PEZZI MANGIATI, …)

LA FORMALIZZAZIONE DEL PROBLEMADEFINISCE :

– LE REGOLE DI SPOSTAMENTO DEI PEZZI– LE REGOLE GENERALI DI GIOCO (PARTITA

PAREGGIATA, VINTA, REGOLE DI SCACCO)– IL VALORE DEI PEZZI (ASSOLUTO O CONTESTUALE)

IL SISTEMA DI CONTROLLO… SULLA BASE DELLO STATO CORRENTE DEL SISTEMA, DELSOTTOBIETTIVO CORRENTE, E DELLE REGOLE DI SPOSTAMENTO, DETERMINA LA MOSSA PIÙ CONVENIENTE

Page 8: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

8

UN TERZO ESEMPIO: L’INTEGRAZIONE SIMBOLICA

IL DATABASE DINAMICO CONTIENE LO STATO DI AVANZAMENTO DELLA INTEGRAZIONE

LA FORMALIZZAZIONE DEL PROBLEMADEFINISCE

– REGOLE DI INTEGRAZIONE

• SOSTITUZIONE• FORMULE RICORRENTI• PER PARTI

– REGOLE DI CALCOLO ANALITICO

• DIFFERENZIAZIONE • DERIVAZIONE• …

IL SISTEMA DI CONTROLLO

… ANALIZZANDO IL DATABASE DECIDE SE È APPLICABILE UNA DELLE REGOLE DI INTEGRAZIONE E IN CASO AFFERMATIVO, DETERMINA I NUOVI SOTTOPROBLEMI DI INTEGRAZIONE DA RISOLVERE

Page 9: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

9

SISTEMI FORMALI

INTERPRETAZIONE DI UN SISTEMA FORMALE

CORRETTEZZA DI UN SISTEMA FORMALE

COMPLETEZZA DI UN SISTEMA FORMALE

TEORIA DEI PROGRAMMI LOGICI

Page 10: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

10

UN SISTEMA FORMALE È COMPOSTO DI:

• ASSIOMI: VERITÀ NON DIMOSTRABILI

• REGOLE DI DERIVAZIONE (O DI INFERENZA): PERMETTONO DI RICAVARE NUOVE VERITÀ A PARTIRE DA QUELLE PREESISTENTI

OGNI VERITÀ (DIMOSTRABILE O MENO) È DETTA TEOREMA

FISSATO UN TEOREMA DA DIMOSTRARE, IL PROCEDIMENTO DI APPLICAZIONE SUCCESSIVA DELLE REGOLE DI INFERENZA PER DERIVARLO A PARTIRE DAGLI ASSIOMI È DETTO PROBLEM SOLVING

INTRODUZIONE AI SISTEMI FORMALI

Page 11: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

11

UN SISTEMA FORMALE NASCE CON L’OBIETTIVO DI DESCRIVERE UNA PARTE DEL MONDO REALE

NEL MONDO REALE ABBIAMO “OGGETTI”, “RELAZIONI TRA OGGETTI”, PROPOSIZIONI CHE ESPRIMONO PROPRIETÀ CHE POSSONO ESSERE VERE O FALSE

UN SISTEMA FORMALE HA INVECE ASSIOMI E TEOREMI DERIVABILI DA ESSI MEDIANTE REGOLE DI INFERENZA (O DERIVAZIONE)

INTERPRETAZIONE DI UN SISTEMA FORMALE

Page 12: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

12

OGGETTI

RELAZIONI TRA OGGETTI

PROPOSIZIONI SEMPRE VERE

SIMBOLI

ASSIOMI

REGOLE DI INFERENZA

MONDO REALE

SISTEMA FORMALE

ISOMORFISMO

TEOREMI DERIVABILI

RELAZIONI DIMOSTRABILI

???

UN ISOMORFISMO TRA S.F. E MONDO REALE REALIZZA UNA CORRISPONDENZA TRA:

GLI OGGETTI DEL MONDO REALE CON I SIMBOLI USATI NEL S.F. (VARIABILI E/O COSTANTI)

LE PROPOSIZIONI SEMPRE VERE NEL MONDO REALE E GLI ASSIOMI DEL S.F.

LE RELAZIONI DIMOSTRABILI TRA GLI OGGETTI DEL MONDO REALE E REGOLE DI INFERENZA

ISOMORFISMO TRA S.F. E MONDO REALE

Page 13: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

13

L’ISOMORFISMO ASSEGNA UN “SIGNIFICATO” AI SIMBOLICIOÈ AGLI ASSIOMI E ALLE REGOLE D’INFERENZA DEL SISTEMA FORMALE

IL SISTEMA FORMALE PERMETTE DI DERIVARE TEOREMI CON LA PROCEDURA DI ESPANSIONE SENZA TENERE CONTO DELL’ISOMORFISMO, OVVERO IN MANIERA STUPIDA, SENZA COSCIENZA DEL SIGNIFICATO DELLA DIMOSTRAZIONE

L’ISOMORFISMO APPLICATO AL CONTRARIO PERMETTE DI ASSEGNARE SIGNIFICATO AI TEOREMI DERIVATI DAL S.F. PER OTTENERE DELLE PROPOSIZIONI VERE DEL MONDO REALE

… CONCLUSIONE

SI DERIVANO PROPOSIZIONI VERE DEL MONDO REALE SENZA CAPIRE COSA SI STA FACENDO.

… PERTANTO

Page 14: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

14

SIMBOLI DEL SISTEMA PG- P

- G

-

ASSIOMI DEL SISTEMA PGa1) SE x È UNA STRINGA DI ALLORA x P G x È UN ASSIOMA

IN EFFETTI a1) ESPRIME UN INSIEME INFINITO DI ASSIOMI AL VARIARE DELLA LUNGHEZZA DELLA STRINGA x.

REGOLE DEL SISTEMA PGR1) SE: x P y G z È VERA, ALLORA:

x P y G z CON x, y E z STRINGHE DI

UN PRIMO ESEMPIO: IL SISTEMA PG

Page 15: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

15

P G

P G

P G

P G

P G

P G

P G P G

P G

P G

P G

P G

RICAPITOLANDO

TEOREMI NON DERIVABILI:

P G

P G

P G

P G

TEOREMI DERIVABILI:

P G

P G

P G

R1

R1

R1

R1

R1

R1

X = Y = Z =

X = Y = Z =

X = Y = Z =

X = Y = Z =

APPLICHIAMO LA PROCEDURA DI DERIVAZIONE:

X = Y = Z =

Page 16: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

16

ISOMORFISMO OGGETTI/SIMBOLI

1

2

3

:

P +

G =UN POSSIBILE ISOMORFISMO TRA PROPOSIZIONI VEREDEL MONDO REALE. ED ASSIOMI DEL SISTEMA FORMALE

DETTO X UN INTERO QUALSIASI, IL SUO SUCCESSIVO È OTTENUTO SOMMANDOGLI 1:

1 + 1 = 2 P G

2 + 1 = 3 P G

3 + 1 = 4 P G

:

UN POSSIBILE ISOMORFISMO TRA PROPOSIZIONI DERIVABILIDEL MONDO REALE ED I TEOREMI DERIVATI DAL S.F.

SE x + y = z x + y + 1 = z + 1

x P y G z x P y G z

1 + 2 = 3 1 + (2+1) = 4 P G P G

1 + 3 = 4 1 + (3+1) = 5 P G P G

:

:

SVELIAMO L’ISOMORFISMO

Page 17: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

17

STRINGHE BEN FORMATE

COME CLASSIFICARE, ALLA LUCE DELLO ISOMORFISMO QUESTE PROPOSIZIONI ?

3 + 2 = 7 P G

2 + 2 + 2 + 2 = 8 P P P G

LE STRINGHE BEN FORMATE DI UN SISTEMA FORMALE SONO QUELLE STRINGHE CHE, INTERPRETATE SIMBOLO PER SIMBOLO, DANNO LUOGO AD ENUNCIATI CORRETTI DAL PUNTO DI VISTA GRAMMATICALE.

TRA LE STRINGHE BEN FORMATE VI SONO I TEOREMI, DEFINITI A PARTIRE DA UNO SCHEMA DI ASSIOMI E DALLE PRODUZIONI.

TUTTE LE ADDIZIONI DI DUE ADDENDI CON RISULTATO ERRATO SONO STRINGHE BEN FORMATE, MA NON SONO TEOREMI.

ESEMPIO DI STRINGA NON BEN FORMATA

2 + 2 + 2 + 2 = 8 P P P G

ESEMPIO DI STRINGA BEN FORMATA CHE NON È UN TEOREMA:

3 + 2 = 7 P G

Page 18: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

18

UN SECONDO ISOMORFISMO

ISOMORFISMO OGGETTI/SIMBOLI

1

2

3

:

P =

G sottratto daUN POSSIBILE ISOMORFISMO TRA PROPOSIZIONI VERE DEL M.R. ED ASSIOMI DEL S.F.

DETTO X UN INTERO QUALSIASI, ESSO È OTTENUTO DAL SUO SUCCESSIVO SOTTRAENDOGLI 1:

1 = 1 sottratto da 2 P G

2 = 1 sottratto da 3 P G

3 = 1 sottratto da 4 P G

:UN POSSIBILE ISOMORFISMO TRA PROPOSIZIONI DERIVABILIDEL M.R. E TEOREMI DERIVATI DAL S.F.

SE x = y sottratto da z => x = y + 1 sottratto da z + 1

x P y G z x P y G z

1 = 2 sottratto da 3 1 = (2+1) sottratto da 4

P G P G

1 = 3 sottratto da 4 1 = (3+1) sottratto da 5

P G P G

:

:

Page 19: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

19

OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA UTILIZZANDO OPPORTUNE REGOLE DI TRASFORMAZIONE.

LA STRINGA INIZIALE È MI

LA STRINGA FINALE È MU

LE REGOLE DI INFERENZA SONO:

R1: SE LA STRINGA TERMINA CON I SI PUÒ AGGIUNGERE UNA UALLA FINE

MI MIU

R2: DATA UNA STRINGA Mx (CON x STINGA QUALSIASI) SI PUÒOTTENERE LA STRINGA Mxx

MIU MIUIU

R3: SI POSSONO SOSTITUIRE TRE I CONSECUTIVE CON UNA U

MIIIU MUU

R4: SI POSSONO ELIMINARE DUE U CONSECUTIVE IN UNA STRINGA

MUUUI MUI

IL GIOCO MU

Page 20: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

20

ALBERO DEI TEOREMI GENERATO APPLICANDO LA PROCEDURA DI DERIVAZIONE

MIUIUIUIU

MI

MIU

MIUIU

MII

MIIU

MIIUIIU

MIIII

MIIIIU MIIIIIIII MIU MUI

R1

R1

R1

R2

R2

R2 R2 R2 R3 R3

R2

ALLA STRINGA INIZIALE MI E AD OGNI ALTRO TEOREMA DERIVATO, IL MOTORE APPLICA UN PROCEDIMENTO DETTO DI UNIFICAZIONE CON LE REGOLE. ESSO CONSISTE NELL’EFFETTUARE UNA OPPORTUNA SOSTITUZIONE CHE RENDA LA PRECONDIZIONE DI UNA REGOLA UGUALE ALLA (UNIFICABILE CON LA) STRINGA CORRENTEMENTE IN ESAME. SE L’UNIFICAZIONE RIESCE, LA REGOLA È APPLICABILE ALLA STRINGA IN ESAME E DA TALE APPLICAZIONE UN NUOVO TEOREMA VIENE DERIVATO.

Page 21: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

21

RAGIONAMENTO INTERNO AL SISTEMA FORMALE

IL RAGIONAMENTO È INTERNO QUANDO SI UTILIZZANO

SOLTANTO LE REGOLE ESPLICITAMENTE DEFINITE DAL

SISTEMA FORMALE.

... UNA PROCEDURA DI DERIVAZIONE DI TEOREMI

P0: INSERIRE GLI ASSIOMI NEL DATABASE

P1: APPLICARE OGNI REGOLA APPLICABILE AI TEOREMI

PRESENTI NEL DATABASE OTTENENDO NUOVI TEOREMI

P2: VERIFICARE CHE TRA I NUOVI TEOREMI PRODOTTI NON

VI SIA QUELLO DESIDERATO; SE È COSÌ AGGIUNGERE TALI

TEOREMI AL DATABASE E RIESEGUIRE IL PASSO P1;

ALTRIMENTI LA SOLUZIONE È STATA TROVATA

Page 22: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

22

RAGIONAMENTO ESTERNO AL SISTEMA FORMALE

RAGIONARE ESTERNAMENTE AL SISTEMA SIGNIFICA

RAGIONARE SULLE REGOLE CHE COSTITUISCONO IL

SISTEMA FORMALE, VALUTANDONE CRITICAMENTE

GLI EFFETTI

ESEMPI

E1) IL SISTEMA FORMALE INTRODOTTO PRODURRÀ

SOLTANTO TEOREMI CHE INIZIANO PER M ( TUTTE LE

REGOLE NON PERMETTONO DI ELIMINARE LA M )

E2) LE REGOLE R1 E R2 HANNO L’EFFETTO DI

ALLUNGARE LA STRINGA, R3 ED R4 DI ACCORCIARLA

Page 23: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

23

USCENDO DAL SISTEMA SIAMO IN GRADO DI RISPONDERE A QUESITI PIÙ EFFICACEMENTE DI QUANTO NON SI FACCIA ESCLUSIVAMENTE CON LE PROCEDURE DI DERIVAZIONE.

USCENDO DAL SISTEMA SI POSSONO RICAVARE REGOLE IMPORTANTI CHE POSSONO, ACCANTO ALLE PRECEDENTI, COSTITUIRE UN NUOVO SISTEMA FORMALE PIÙ “INTELLIGENTE”

ESEMPIO

POSSO AGGIUNGERE LE REGOLE E1 ED E2 OTTENENDO UN NUOVO SISTEMA FORMALE CHE RISPONDE A DOMANDE DEL TIPO:

È POSSIBILE OTTENERE DA MIU LA STRINGA UI ?

SISTEMA FORMALE

SF1

REGOLE INTERNE

DI SF1

REGOLE INTERNE DI

SF∅∅∅∅

REGOLE ESTERNE DI

SF∅∅∅∅

SISTEMA FORMALE

SF∅∅∅∅

REGOLE ESTERNE DI

SF∅∅∅∅

UOMO

IMPLICAZIONI

Page 24: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

24

RIASSUMENDO

IL CICLO DI DEFINIZIONE E UTILIZZO DI UN

SISTEMA FORMALE EVOLVE TRA LE FASI DI:

•DEFINIZIONE DEI SIMBOLI

•DEFINIZIONE CONTEMPORANEA DELL’ ISOMORFISMO

•DERIVAZIONE DI TEOREMI DAL SISTEMA FORMALE

•APPLICAZIONE ALL’INVERSO DELL’ISOMORFISMO PER OTTENERE PROPOSIZIONI VERE DAL MONDO REALE A PARTIRE DAI TEOREMI OTTENUTI.

Page 25: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

25

IL SISTEMA PG, CON LA PRIMA INTERPRETAZIONE DATA, ÈCOERENTE.

OGNI SUO SISTEMA DERIVATO, COME:

P G

ESPRIME, IN BASE ALL’INTERPRETAZIONE DATA UNA VERITÀARITMETICA

3 + 2 = 5 P G

IL SISTEMA È COMPLETO RISPETTO ALLE ADDIZIONI CON UN UNICO SEGNO + . INFATTI UNA QUALSIASI VERITÀ DEL MONDO REALE ÈSEMPRE DERIVABILE DAL SISTEMA FORMALE

... IL CHE ASSICURA CHE APPLICANDO ALL’INVERSO L’ ISOMORFISMO, SI OTTENGONO PROPOSIZIONI VERE DAL MONDO REALE A PARTIRE DA TEOREMI DERIVANTI DAL SISTEMA FORMALE

IL SISTEMA PG

Page 26: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

26

COERENZA E COMPLETEZZA

UN SISTEMA FORMALE CON LA SUA INTERPRETAZIONE SI

DICE COERENTE SE OGNI TEOREMA DA ESSO DERIVATO

INTERPRETATO (MEDIANTE L’ISOMORFISMO) ESPRIME UNA

PROPOSIZIONE VERA DEL MONDO REALE

UN SISTEMA FORMALE CON LA SUA INTERPRETAZIONE È

DETTO COMPLETO SE TUTTE LE PROPOSIZIONI VERE DEL

MONDO REALE SONO ESPRESSE DA TEOREMI DERIVATI DAL

SISTEMA FORMALE..

Page 27: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

27

COERENZA E COMPLETEZZA

•SE IL SISTEMA FORMALE È COERENTE E NON COMPLETO E

RISPONDE NO AD UNA DOMANDA, NON È CREDIBILE, PERCHÉ

LA SOLUZIONE PUÒ ESISTERE MA NON ESSERE

FORMALIZZATA NEL SISTEMA FORMALE, CIOÈ UN SF

COERENTE È CREDIBILE SOLO SUL SI.

•SE IL SISTEMA FORMALE È COMPLETO E NON COERENTE E

RISPONDE SI AD UNA DOMANDA, NON È CREDIBILE, PERCHÉ

NON TUTTE LE SUE DERIVAZIONI SONO VERE (POTREBBE

NON ESSERE COERENTE). CIOÈ UN SF COMPLETO È

CREDIBILE SUL NO.

Page 28: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

28

COERENZA ED INTERPRETAZIONI

SUPPONIAMO DI ASSEGNARE AL SISTEMA FORMALE PG UNA TERZA INTERPRETAZIONE:

* 1 P +** 2 G ≥

OTTENENDO UN SISTEMA CHE CON LA SUA INTERPRETAZIONE È ANCORA COERENTE.

SUPPONIAMO DI AGGIUNGERE AL SISTEMA FORMALE PG UN ALTRO SCHEMA DI ASSIOMI

x P G x CON x STRINGA DI

IL NUOVO SISTEMA FORMALE È COERENTE RISPETTO ALLA NUOVA INTERPRETAZIONE

P G 2 + 1 ≥ 2

MA INCOERENTE RISPETTO ALLA PRIMA INTERPRETAZIONE

P G 2 + 1 = 2

... CONCLUSIONI…

Page 29: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

29

... COMPLETEZZA

IL NUOVO SISTEMA FORMALE CON LA NUOVA

INTERPRETAZIONE È COERENTE MA NON È

COMPLETO!

SI CONSIDERI LA PROPOSIZIONE

2 + 1 ≥ 1

IL CORRISPONDENTE TEOREMA:

P G

NON È DERIVABILE DAL SISTEMA FORMALE

Page 30: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

30

IL CRITERIO DI TEOREMATICITÀ

LA PROCEDURA DI DECISIONE È TALE DA FAR RICAVARE

TUTTI I POSSIBILI TEOREMI DAGLI ASSIOMI DI PARTENZA

CRITERIO DI TEOREMATICITÀ

PROCEDERE FINO A QUANDO VIENE PRODOTTA LA STRINGA

IN QUESTIONE; QUANDO CIÒ AVVIENE, SI SA CHE ESSA È UN

TEOREMA; SE CIÒ NON AVVIENE MAI, VUOL DIRE CHE ESSA È

NON È UN TEOREMA.

PROBLEMA

IL CRITERIO DI TEOREMATICITÀ PUÒ RISPONDERE IN UN

TEMPO INFINITO

SE ESISTE UN CRITERIO DI TEOREMATICITÀ LA CUI

APPLICAZIONE DURA DA UN LASSO DI TEMPO FINITO DI

TEMPO, ALLORA DETTO CRITERIO SI CHIAMA

PROCEDURA DI DECISIONE

Page 31: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

31

... IMPLICAZIONI

L’ASSENZA DI UNA PROCEDURA DI DECISIONE

COMPROMETTE LA REALIZZAZIONE DI UN SISTEMA

AUTOMATICO DI RISOLUZIONE DI PROBLEMI PER IL

SISTEMA FORMALE IN CONSIDERAZIONE

LA PROCEDURA DI DECISIONE, DIPENDENTE DAL

SISTEMA FORMALE, VA AGGIUNTA A COMPLETAMENTO

DELLA PROCEDURA DI DERIVAZIONE DI TEOREMI

Page 32: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

32

TEOREMA DI GÖDEL

TUTTE LE ASSIOMATIZZAZIONICOERENTI CONTENGONO

PROPOSIZIONI INDECIDIBILI

IN ALTRI TERMINI, TALE TEOREMA AFFERMA CHE

SE SI VUOL COSTRUIRE UN S.F. IN CUI TUTTI I TEOREMI

CORRISPONDANO A PROPOSIZIONI VERE, TALE SISTEMA

CONTERRÀ PROPOSIZIONI CHE NON È POSSIBILE NÉ

CLASSIFICARE COME TEOREMI, NÉ STABILIRNE LA FALSITÀ

(PROPOSIZIONI INDECIDIBILI).

VICEVERSA, SE SI VUOL PROGETTARE UN S.F. CHE NON

CONTENGA PROPOSIZIONI INDECIDIBILI, TALE SISTEMA DEVE

ESSERE INCOERENTE, OVVERO ESISTERANNO TEOREMI AI

QUALI CORRISPONDERANNO FALSITÀ DEL MONDO REALE.

Page 33: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

33

TEOREMA DI GÖDEL: UNA RAPPRESENTAZIONE GRAFICA

Page 34: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

34

S.F. COERENTI (figura pagina precedente)

IL RIQUADRO PIÙ ESTERNO RAPPRESENTA L’INSIEME DI TUTTE LE STRINGHE.

IL RIQUADRO SUCCESSIVO RAPPRESENTA QUELLO DI TUTTE LE STRINGHE BEN FORMATE IN ACCORDO AL SISTEMA FORMALE IN ESAME.

L’INSIEME DEI TEOREMI È ILLUSTRATO COME UN ALBERO CHE SI SVILUPPA DA UN TRONCO (IL QUALE RAPPRESENTA L’INSIEME DEGLI ASSIOMI).

I RAMI SCANDAGLIANO LA REGIONE DELIMITANTE (INSIEME DELLE VERITÀ), SENZA MAI RIUSCIRE AD OCCUPARLA TUTTA.

L’IMMAGINE SPECULARE DELL’ALBERO DEI TEOREMI RAPPRESENTA L’INSIEME DELLE NEGAZIONI DEI TEOREMI: TUTTE FALSE E TUTTAVIA INCAPACI NEL LORO INSIEME DI ESAURIRE LO SPAZIO DEGLI ENUNCIATI FALSI.

Page 35: Componenti di un sistema KNOWLEDGE-BASEDwebuser.unicas.it/destefano/IA_docs/01_sistemi_formali.pdf · OBIETTIVO DEL GIOCO È QUELLO DI OTTENERE UNA STRINGA A PARTIRE DA UN’ALTRA

35

ESEMPI DI SISTEMI INCOERENTI

“QUESTA PROPOSIZIONE È FALSA”