Programmi logici

Pagina base

1 di 3

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/index.html

Il Progetto

UL 1 AI, Mente, Cervello

UL 4 Programmi logici Introduzione Destinatari Prerequisiti Obiettivi Strumenti Metodi Tempi Bibliografia

UL 2 Reti neurali

UL 3 Robot

UL 4 UL 5 Programmi Sistemi logici esperti

UL 6 Problem solving

UL 8 UL 7 Progetti Analisi del con le testo DCG

FAQ

download

Presentazione dell'Unità di lavoro Introduzione La programmazione logica, non prevista dai programmi ministeriali per i corsi Brocca Scientifici o Scientifici Tecnologici, può inserirsi nei curricula in modo proficuo, allo scopo di perseguire l'acquisizione di un sapere unitario: la logica formale può avere ricadute formative di rilevante spessore, per il suo ruolo unificante delle culture umanistica, scientifica, tecnologica.

L'unità di lavoro presenta un percorso centrato sulla programmazione logica, che propone anche spunti di approfondimento pluridisciplinare in merito ai Attività: collegamenti con Storia dell'Arte e con Matematica : le figure "impossibili" di M.C.Escher in cui troviamo trasformazioni geometriche, successioni, il Programmazione concetto di infinito. Offre inoltre allo studente la possibilità di comprendere i logica fondamenti teorici alla base di questo paradigma di programmazione e di Intelligenza approfondirli attraverso una trattazione che affronta elementi di logica Artificiale e proposizionale e di logica predicativa del primo ordine. logica Logica proposizionaleDestinatari Logica predicativa L'unità di lavoro è rivolta a studenti di un triennio di Liceo scientifico (classe del primo terza o quarta), dove si inserisce in modo naturale nel curriculo di filosofia e, ordine per l'indirizzo scientifico tecnologico, di informatica . Può tuttavia essere Logica predicativa utilizzata anche in un Istituto tecnico ad indirizzo informatico (dove il degli ordini programma di informatica prevede che si affrontino i diversi paradigmi di superiori programmazione), per integrare lo studio del linguaggio Prolog e fornire un Scheda Docente

supporto teorico al suo utilizzo: proprio per questo motivo viene compiuta una trattazione sintetica ma abbastanza completa, affrontando contenuti (come la logica proposizionale) che in un Liceo si possono invece assumere in toto o in parte come prerequisiti.

Prerequisiti In un Liceo si possono assumere come prerequisiti i concetti di base della logica proposizionale, inseriti nel programma di Matematica e Informatica del biennio.

Obiettivi In questa Unità di Lavoro convergono obiettivi di apprendimento di Matematica e Filosofia per i corsi Brocca scientifici e scientifici tecnologici, e di Informatica, in particolare: - cogliere interazioni tra pensiero filosofico e matematico - individuare analogie e differenze tra concetti, modelli e metodi dei diversi campi conoscitivi - saper individuare differenze ed analogie tra il paradigma procedurale ed il paradigma logico.

Strumenti

16/11/2012 11.11

Pagina base

2 di 3

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/index.html

- Lezioni frontali e discussione in classe - utilizzo del linguaggio Prolog in laboratorio di Informatica.

Metodi - Lezioni e discussione in classe - lavori individuali e di gruppo in laboratorio di Informatica - approfondimento individuale - svolgimento degli esercizi di verifica proposti.

Tempi - 10 ore di lezione e discussione in classe sulla programmazione logica, con svolgimento degli esercizi proposti ed esame degli spunti di approfondimento suggeriti - 10 ore di lezione e discussione in classe sulla logica.

Bibliografia Barker S.P. , Elements of Logic, McGraw Hill, New York 1965. a cura di Bonfiglioli A. e Valentini C., Matematica arte e tecnologia: da Escher alla Computer Graphics , Edizioni Aspasia Bologna, 2000 Casadei G, Teolis A.,Prolog, Zanichelli Bologna 1986. Console L., Lamma E., Mello P.,Programmazione logica e Prolog,Utet Torino 1991 Copi I.M. , Introduction to Logic, Macmillan, New York-London 1961; trad. it. Introduzione alla logica , Il Mulino, Bologna 1964. Eggert P.R., Chow K.P., Logic Programming graphics and infinite terms , Departement of Computer Science University of California, Santa Barbara June 1983 Galavotti M.C., Simili R. , Appunti di logica , CLUEB, Bologna 1973. Hofstadter D.R., Gödel, Escher, Bach: un’eterna ghirlanda brillante, Adelfi, Milano 1984. Lazotti L., Arte: percorsi, Bulgarini Firenze 1996, pagg. 436-447. Lloyd John W. , Fondamenti di programmazione logica, Franco Muzzio editore, Padova 1986. Russell S.J. , Norvig P. , Artificial Intelligence. A Modern Approach , Prentice-Hall, Englewood Cliff, N.J, 1995; trad. it. Intelligenza artificiale. Un approccio moderno, UTET, Torino 1998. Schagrin M.L., Rapaport W.J., Dipert R.R., Logic: a Computer Approach, McGraw-Hill 1985; trad. it. Logica e Computer, McGraw-Hill 1988. Watt D.A., Programming Language Concepts and Paradigms, Prentice Hall 1990.

16/11/2012 11.11

Pagina base

3 di 3

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/index.html

Riferimenti prof. Mario Alai, Liceo Scientifico "A. Righi" Cesena prof.ssa Milla Lacchini, Liceo Scientifico "G. Ricci Curbastro" Lugo(Ra) Il Progetto

UL 1 AI, Mente, Cervello

UL 2 Reti neurali

UL 3 Robot

UL 4 UL 5 Programmi Sistemi logici esperti

UL 6 Problem solving

UL 8 UL 7 Progetti Analisi del con le testo DCG

FAQ

download

16/11/2012 11.11

Pagina base

1 di 13

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/att1.html

Il Progetto

UL 1 AI, Mente, Cervello

UL 2 Reti neurali

UL 3 Robot

UL 4 UL 5 Programmi Sistemi logici esperti

UL 6 Problem solving

UL 8 UL 7 Progetti Analisi del con le testo DCG

FAQ

download

Programmazione logica

UL 4 Programmi 1. Struttura di un programma logico: termini e dichiarazioni (elementi di base, logici mutuati dalla logica). Introduzione Destinatari Prerequisiti Obiettivi Strumenti Metodi Tempi Bibliografia Attività:

2. Rappresentazione della base di conoscenza (fatti e regole) e degli obiettivi logici mediante clausole di Horn. 3. Principio di Risoluzione. Processo di Unificazione. 4. Il problema dell'occur check e le relative implicazioni. 5. Il Prolog come dimostratore automatico con utilizzo della risoluzione SLD e strategia di ricerca depth-first.

Programmazione 6. Interpretazione procedurale delle clausole alla base dell'utilizzo della logica logica Intelligenza del primo ordine come linguaggio di programmazione. Artificiale e L'attività consente interazioni online con un interprete Prolog semplificato logica (dovuto a Michael Winikoff e modificato da Milla Lacchini e Aldopaolo Logica proposizionalePalareti), con possibilità di modificare il programma proposto e di formulare Logica degli obiettivi logici. predicativa del primo Prerequisiti specifici connessi all'attività: conoscenza del linguaggio Prolog (ad ordine un livello base); elementi di logica degli enunciati: concetto di enunciato, Logica valore di verità di un enunciato, connettivi And, Or, Not; conoscenza dei limiti predicativa della logica degli enunciati; conoscenza degli elementi presi in considerazione degli ordini dalla logica dei predicati : individui e loro proprietà, quantificatori, relazioni superiori

Scheda Docente

tra individui; concetti di problema, esecutore, algoritmo (per opportuni confronti col paradigma procedurale); saper scomporre un problema in sottoproblemi; conoscenza delle strutture dati Albero e Pila.

La realizzazione dell'attività richiede complessivamente 10 ore: 6 ore per la trattazione dei contenuti; 2 ore per la risoluzione degli esercizi proposti e la relativa discussione in classe (parte integrante nello svolgimento dell'attività, perchè occasione per riflettere sui concetti trattati e puntualizzarli in modo adeguato); 2 ore per esaminare gli spunti che scaturiscono dal problema dell'occur check , in merito ai collegamenti con Storia dell'Arte e Matematica: le figure "impossibili" di M.C.Escher in cui troviamo trasformazioni geometriche, successioni, il concetto di infinito.

1. Struttura di un programma logico Vengono richiamati brevemente alcuni concetti della Logica del Primo ordine, descritti per esteso nella attività numero 4. La Sintassi riguarda le formule ben formate (fbf) ammesse dalla grammatica di un linguaggio formale. La Semantica riguarda il significato associato ai simboli contenuti nelle fbf. L’Alfabeto usato per costruire fbf comprende 7 classi di simboli: variabili, costanti, funzioni, predicati, connettivi, quantificatori, punteggiatura. Per ogni alfabeto le classi che comprendono costanti e funzioni possono anche essere vuote.

16/11/2012 11.14

Pagina base

2 di 13

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/att1.html

Per definire le fbf occorre definire il termine, che è l’elemento base: - una variabile è un termine - una costante è un termine - se f è una funzione n-aria cioè ad n argomenti e t1,..,tn sono termini allora f(t1,..,tn) è un termine. Esempio: f(a,b,g(h)) è un termine composto detto funtore, cioè una funzione i cui argomenti possono essere a loro volta ottenuti da un’altra funzione. Le funzioni e i predicati servono per descrivere delle relazioni. Le funzioni esprimono delle relazioni matematiche in cui ad ogni elemento del dominio viene associato uno e uno solo elemento del codominio; i predicati descrivino invece relazioni più generali. Una formula ben formata viene definita come segue: - se p è un predicato n-ario ( cioè con n- argomenti) e t1,..,tn sono termini allora p(t1,..,tn) è una formula atomica o atomo. - se t1 e t2 sono termini allora t1=t2 è un atomo - se F è un fbf allora ØF è una fbf - se F e G sono fbf allora F ÚG , F·G , FÉG , FºG sono fbf - se F è una formula e x è una variabile "xF e $xF sono fbf Seguendo la notazione comunemente usata nell'ambito della programmazione logica, scriveremo G Ì F invece di F É G , premettendo cioè il conseguente all'antecedente. Un linguaggio del primo ordine definito da un alfabeto è l’insieme di tutte le fbf costruite con i simboli dell’alfabeto. Una clausola è una formula del tipo "x1,.., "xr(L1Ú..ÚLm) essendo Lj atomi o negazioni di atomi e x1,..,xr le variabili che occorrono in (L1Ú..ÚLm) Indichiamo la clausola "x1,.., "xr(A1Ú..ÚAkÚØB1Ú..ÚØBn) con A1,..,Ak Ì B1,..,Bn cioè esprimiamo la clausola mediante una implicazione in cui Ai (conseguenti) e Bj (antecedenti) sono atomi e gli xhsono le variabili occorrenti in questi atomi, che si intendono quantificate universalmente. Si osservi che la virgola nel conseguente dell’implicazione significa disgiunzione, mentre nell’antecedente significa congiunzione. Una clausola di programma è una clausola del tipo A Ì B1,..,Bn

16/11/2012 11.14

Pagina base

3 di 13

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/att1.html

n>=0 , dove A è un atomo, detto testa della clausola, mentre B1,..,Bn è il corpo della clausola. Per n=0 si ha una clausola unaria AÌ con corpo vuoto. Una clausola di programma è quindi una particolare clausola di Horn, la cui semantica è definita come segue: - n > 0 : per ogni assegnazione di ogni variabile se B1,..,Bn sono veri allora A è vero - n = 0 : per ogni assegnazione di ogni variabile, A è vero La clausola vuota, con conseguente ed antecedente vuoti, viene interpretata come una contraddizione. La struttura di un programma logico è precisata dalla seguente definizione: un programma logico è un insieme finito di clausole di programma.

2. Base di conoscenza Dalla definizione di programma logico come insieme finito di clausole segue che il contesto di un problema logico, cioè la base di conoscenza, dovrà essere descritto formalmente utilizzando le clausole, come insieme di fatti e regole. Un fatto corrisponde ad una clausola unaria, e descrive una proprietà di un oggetto o una relazione tra oggetti. In merito alla formalizzazione dei predicati che descrivono i fatti della base di conoscenza, precisiamo le seguenti specifiche: - i nomi dei predicati e gli atomi che compaiono nei predicati, iniziano con una lettera minuscola; - ogni predicato termina con un punto; - l’ordine con cui sono elencati gli argomenti dei predicati viene autonomamente stabilito da chi progetta la base di conoscenza, ed espresso nella descrizione intensionale che definisce la struttura dei predicati: (,,..,) Nella descrizione estensionale dei predicati, che precisa invece il contenuto dei singoli fatti, occorrerà seguire tale ordine. Consideriamo il seguente albero genealogico:

16/11/2012 11.14

Pagina base

4 di 13

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/att1.html

Figura 1 Esaminiamo ora alcuni enunciati che descrivono il contenuto dell’albero, evidenziandone la struttura: 1) Luigi è padre di Marina e di Marco. Marco è padre di Priscilla.

Figura 2 Il predicato esprime una relazione tra i due argomenti; l’enunciato può quindi essere formalizzato mediante un predicato binario, che a livello intensionale può essere così descritto: padredi(,). La corrispondente descrizione estensionale sarà quindi: padredi(luigi,marina). L’ordine scelto per elencare gli argomenti deve essere il medesimo anche per gli altri predicati aventi lo stesso nome: padredi(luigi,marco). padredi(marco,priscilla). 2) Marina è una femmina.

Figura 3 Il predicato ha un solo argomento, di cui esprime una proprietà; l’enunciato può quindi essere formalizzato mediante un predicato unario: femmina(). con descrizione estensionale:

16/11/2012 11.14

Pagina base

5 di 13

http://www5.indire.it:8080/set/intelligenza_artificiale/ul4/att1.html

femmina(marina). 3) Le altre femmine della famiglia sono Maria, Angela, Priscilla. femmina(maria). femmina(angela). femmina(priscilla). Si può inoltre introdurre un predicato per descrivere i maschi della famiglia: maschio(luigi). maschio(marco). 4) Angela è madre di Marina e Marco. La madre di Priscilla è Maria. Questi due fatti possono essere espressi per mezzo di un predicato binario: madredi(,). madredi(angela,marina). madredi(angela,marco). madredi(maria,priscilla). Per la definizione data in precedenza, l’insieme di fatti descritto costituisce un semplice programma logico. Vogliamo ora aggiungere alla base di conoscenza nuove informazioni che consentano di individuare i genitori delle singole persone. Un primo approccio può consistere nel definire il predicato genitori(,,) e aggiungere poi i fatti genitori(lugi,marina,angela). genitori(luigi,angela,marco). genitori(marco,maria,priscilla). L’aggiunta di questi fatti alla base di conoscenza comporta un aumento di conoscenza estensionale all’interno del programma. Un secondo approccio consiste nel definire delle regole (corrispondenti a clausole con corpo non vuoto) che utilizzano conoscenza già presente nella base di conoscenza (fatti o regole). In forma dichiarativa la regola in esame può essere descritta come segue: X e Y sono genitori di Z se X è padre di Z e Y è madre di Z e formalizzata mediante la seguente clausola con corpo non vuoto: genitori(X,Y,Z)