spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
  • spacer
  • spacer
  • spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer
spacer

Menu Sezioni

  • Indice generale
  • Redazione e rivista
  • Letteratura e editoria
  • Cinema e TV
  • Anime e cartoni
  • Fumetti e disegno
  • Scienza e tecnologia
    • Articoli
    • Recensioni documentari
  • Storia e cultura
  • Mitologia e mistero
  • Cosplay, musica e fun
  • Racconti e scrittura
  • English translations
  • Forum

sponsor

spacer
spacer Se vuoi supportare l'Associazione Culturale e mantenere attivo il progetto TdC, aiutaci effettuando una modica donazione
spacer

Introduzione all'Intelligenza Artificiale

Scritto da Fabrizio Riguzzi | 15 Gennaio 2006 | Commenti (0)
sezione Scienza | categoria Articoli

PDF - Introduzione...

spacer


Per scaricare l'articolo in PDF o visualizzarne l'anteprima, clicca qui

Introduzione all'I.A.

spacer
Garri Kímovich Kaspárov

Il termine Intelligenza Artificiale (d'ora in avanti IA) è stato inventato da John McCarthy nel 1956, in occasione di un seminario di due mesi (da lui organizzato al Dartmouth College di Hanover, New Hampshire, USA) che ebbe il merito di far conoscere tra loro 10 studiosi (su teoria degli automi, reti neurali e intelligenza) statunitensi, e di dare l'imprimatur al termine "Intelligenza Artificiale" come nome ufficiale del nuovo campo di ricerca.

Da allora l'IA si è affermata ed evoluta; oggi è riconosciuta come branca autonoma, sebbene connessa a informatica, matematica, scienze cognitive, neurobiologia e filosofia.

Molte definizioni sono state date di questa materia: esse differiscono per i compiti svolti dalle macchine che l'IA cerca di costruire. Tali compiti possono essere classificati secondo due dimensioni ortogonali (RusNor2005): macchine che pensano o agiscono, e macchine che simulano gli umani (o che si comportano razionalmente). In tutto quattro classi, a seconda che le macchine: pensino come umani, agiscano come umani, pensino razionalmente, agiscano razionalmente. Quattro approcci distinti alla ricerca nel campo dell'IA, dunque, tutti attivamente perseguiti.

L'obiettivo dell'approccio "macchine che pensano come umani" è quello di riprodurre il ragionamento umano nelle macchine. Può essere fatto a due livelli: imitando i metodi di ragionamento o replicando il funzionamento del cervello. Nel primo caso, la scienza cognitiva ci fornisce un importante punto di partenza, ottenuto mediante introspezione ed esperimenti psicologici. Nel secondo caso, è la neurobiologia a fornirci un modello adeguato. Questo primo criterio si occupa quindi di produrre macchine automi che, oltre a comportarsi come umani, "funzionino" come umani tali.

L'obiettivo dell'approccio "macchine che si comportano come umani" è quello di realizzare macchine indistinguibili dagli uomini. Questa proprietà è stata meglio definita da Alan Turing che, in un suo articolo del 1950 (Tur1950), ha proposto il test che prende il suo nome: un "giudice" ha la facoltà di porre a un "soggetto" domande per iscritto e, in base alle risposte, deve decidere se si tratta di un uomo o di una macchina. Al fine di superare il test di Turing, una macchina deve esibire le seguenti capacità:

elaborazione del linguaggio naturale, al fine di comunicare efficacemente nella lingua del giudice;

rappresentazione della conoscenza, per memorizzare quello che sa o impara;

ragionamento automatico, per inferire (produrre), a partire dalla propria conoscenza, le risposte al giudice;

apprendimento automatico, per aumentare la propria base di conoscenza.



Il test di Turing non prevede interazione fisica tra il giudice e la macchina, non essendo necessaria. Volendo, si può pensare a un test di Turing totale in cui, invece delle risposte scritte, il giudice riceve un segnale audio-video, ed ha la possibilità di passare degli oggetti alla macchina attraverso una feritoia. In questo caso la macchina deve esibire anche le seguenti capacità:



visione artificiale, per riconoscere gli oggetti ricevuti;

robotica, per manipolarli;

elaborazione del linguaggio parlato, per comprendere le domande del giudice e per rispondere.



Il test di Turing totale ricorda il test Voight-Kampf nel film Blade Runner con il quale i poliziotti distinguono gli androidi dagli esseri umani.

L'approccio "macchine che pensano razionalmente" non si preoccupa che le macchine realizzate funzionino come umani, ma solo che seguano ragionamenti razionali, dove "razionale" è definito in maniera precisa dalla matematica, anche tramite tecniche che gli esseri umani naturalmente non usano. Ad esempio la logica, cioè lo studio di come effettuare ragionamenti inattaccabili. La logica svolge un importante ruolo nell'IA, anche se le aspettative iniziali sono state ridimensionate dai limiti pratici del suo uso, soprattutto in situazioni di conoscenza incompleta e/o incerta.

L'approccio "macchine che agiscono razionalmente" usa la definizione di "azione razionale" fornita dall'economia, ossia: selezione delle azioni che portano al migliore risultato, o al migliore risultato atteso nel caso ci siano elementi di impredicibilità. L'obiettivo di questo approccio è quello di realizzare un agente, un'entità in grado di agire in un ambiente al fine di raggiungere uno o più obbiettivi. L'agente utilizzerà il ragionamento razionale per scegliere quali azioni compiere, ma in alcuni casi dovrà reagire agli stimoli ambientali in maniera tanto veloce da "scavalcare" la scelta (ad esempio quando una inazione mettesse a rischio la sua esistenza). Se si tocca qualcosa che scotta, si reagisce ritirando immediatamente la mano, senza un ragionamento cosciente; allo stesso modo l'agente, in certe situazioni, deve poter agire senza svolgere un ragionamento. Gli agenti possono essere di due tipi: solo software, e in questo caso si chiamano softbot, o sia hardware che software, chiamati allora robot. Nel caso dei softbot, l'ambiente esterno in cui operano è rappresentato da Internet, dove interagiscono con esseri umani e altri softbot. Questo, al momento, è l'approccio maggiormente perseguito, in quanto quello che promette i risultati di maggior utilità pratica.

Al fine di presentare le varie tecniche proposte dall'IA, le suddivideremo in due grandi classi: simboliche e subsimboliche. Le prime si propongono di automatizzare il ragionamento e l'azione, rappresentando le situazioni oggetto di analisi tramite simboli comprensibili agli esseri umani, ed elaborandole mediante algoritmi. Le seconde, invece, non rappresentano esplicitamente la conoscenza in maniera direttamente comprensibile, e sono basate sulla riproduzione di fenomeni naturali.



Tecniche Simboliche

Tra le tecniche simboliche descriveremo la ricerca nello spazio degli stati, il ragionamento automatico e l'apprendimento automatico.

Ricerca nello spazio degli stati


Questa tecnica viene utilizzata quando si vuole scegliere una serie di azioni che portino da uno stato iniziale a uno o più stati finali desiderati. Condizioni, affinché possa essere utilizzata, sono: che lo stato del mondo esterno possa essere rappresentato in maniera concisa (in forma simbolica), che le azioni disponibili possano essere espresse come regole per il passaggio da uno stato al successivo e che esista un test per stabilire se uno stato è finale.

Vediamo un esempio di problema che può essere trattato in questo modo. Nel gioco dell'otto (o puzzle dell'otto) si ha una scacchiera tre per tre, in cui otto caselle sono occupate da otto tessere numerate dall'1 all'8 e una casella è vuota. Si parte da una configurazione iniziale casuale delle tessere, come ad esempio quella rappresentata in figura 1 a), e si vuole arrivare alla configurazione rappresentata in figura 1 b).

Le mosse possibili consistono nello spostare sulla casella vuota una tessera numerata ad essa adiacente. Per questo problema, lo "stato" consiste nella posizione delle otto tessere numerate: lo stato iniziale è quello rappresentato in figura 1 a), e il test per stabilire se si è raggiunto uno stato finale verifica semplicemente che lo stato sia identico a quello di figura 1 b).

Si tratta di un problema che sembra richiedere intelligenza: un essere umano lo risolverebbe provando diverse mosse e cercando di prevederne il risultato. Il metodo di soluzione proposto dall'IA consiste nel compiere una ricerca nello spazio dei possibili stati. A tal fine, si può rappresentare lo "spazio" come un albero in cui ogni nodo corrisponde a uno "stato". La radice dell'albero è lo stato iniziale, i figli di un nodo sono quegli stati che si possono raggiungere dallo stato associato al nodo applicando una sola mossa. Ad esempio, nel caso del gioco dell'otto, lo spazio degli stati si può rappresentare come l'albero di figura 2.

Il problema è risolto quando si è trovato un percorso dallo stato iniziale a uno stato finale. Solitamente non basta trovare una soluzione ma si cerca quella che ha costo minimo. Occorre quindi definire un "costo": di norma si assegna un costo alle varie mosse, e il costo di un cammino si misura come somma dei costi delle mosse che lo compongono. Nel caso del gioco dell'otto, ogni mossa costa 1, e si cerca la soluzione che richiede il numero minimo di mosse.

Citiamo altri problemi che si possono risolvere con una ricerca nello spazio degli stati. Iniziamo da quelli "giocattolo", ovvero problemi che non hanno immediato interesse pratico.

Il problema "dei missionari e dei cannibali" consiste nel far attraversare un fiume a 3 missionari e 3 cannibali, utilizzando una barca ed evitando che i primi mangino i secondi (quando li superano in numero su una delle due sponde). La barca può contenere al massimo due persone alla volta e, per muoversi da una sponda all'altra del fiume, dev'essere guidata da almeno una persona. Lo stato di questo problema può essere rappresentato utilizzando una terna di numeri, nella quale i primi due quantifichino i missionari e i cannibali sulla sponda iniziale, e il terzo equivalga a: 1 se la barca è sulla sponda iniziale, e 0 se è sull'altra. Lo stato iniziale è (3,3,1), lo stato finale è (0,0,0) e un possibile stato (2,2,1) indica che sulla sponda iniziale ci sono due missionari e due cannibali e che la barca è sulla sponda iniziale. Le operazioni possibili sono cinque: attraversa il fiume con 2 missionari, con 2 cannibali, con un missionario e un cannibale, con un solo cannibale o con un solo missionario. Non tutte le operazioni sono consentite in ogni stato: ad esempio, a partire dallo stato (2,2,1) non è possibile applicare l'operazione "attraversa il fiume con un missionario" perchè sulla sponda iniziale rimarrebbero un missionario e due cannibali, e quindi i cannibali mangerebbero il missionario. Il costo, in questo caso, è unitario per tutte le operazioni, si cercano quindi soluzioni con il minimo numero di attraversamenti del fiume.


Il problema "delle n-regine" consiste nel disporre, su una scacchiera n per n, n regine in modo che non si attacchino. Una regina attacca tutti i pezzi che si trovano sulla stessa colonna, riga o diagonale. Lo stato in questo caso è rappresentato dalla posizione di i regine sulla scacchiera, con i che va da 0 a n. Lo stato iniziale è rappresentato dalla scacchiera senza regine, lo stato finale da una scacchiera con n regine che non si attaccano a vicenda. Le mosse sono l'aggiunta di una regina su una casella della scacchiera. In questo caso tutte le soluzioni hanno uguale costo perchè richiedono tutte 8 mosse.

Passiamo ai problemi reali, come quello di "trovare un percorso", che consiste nell'andare da un luogo ad un altro con il minimo costo, transitando per luoghi intermedi, al collegamento tra ognuno dei quali è associato un costo. Un esempio è il tragitto in macchina da una città ad un'altra: i collegamenti sono le strade e il costo può essere la distanza o il tempo necessario a percorrere quel collegamento. Se lo spostamento avviene in aereo, i collegamenti sono i voli disponibili, e il costo può essere il tempo o il prezzo del volo. Gli "stati" sono i luoghi, e le mosse disponibili consistono nell'utilizzare uno dei collegamenti che partono dal luogo corrente per spostarsi in un altro luogo.

Altro problema reale risolvibile mediante ricerca nello spazio degli stati è quello del "tour", cioè un percorso che parta da un luogo e vi ritorni dopo aver "visitato" almeno una volta tutti i luoghi di un insieme. Questo problema ha le stesse mosse del precedente ma stati diversi: qui lo stato è costituito dal luogo corrente più l'insieme dei luoghi già visitati. Lo stato finale è quindi quello in cui il luogo corrente è il luogo iniziale e l'insieme di luoghi visitati corrisponde a quello specificato. Il costo può essere, anche in questo caso, rappresentato dalla distanza, dal tempo o dal costo monetario delle mosse.

Come si risolvono problemi di ricerca? Occorre generare e percorrere lo spazio di ricerca dal nodo iniziale fino a trovare uno stato che superi mediante verifica il test di stato finale; quando la verifica non viene superata, occorre "espandere" il nodo, generare i suoi successori utilizzando le possibili mosse od operatori, ed esaminare quelli, fino a trovarne uno che superi il test, o fino a che non si sia esplorato tutto lo spazio degli stati. Si genera così progressivamente l'albero di ricerca.

Gli algoritmi per la ricerca nello spazio degli stati differiscono nella scelta del nodo da espandere (strategia di ricerca). Le due strategie più comuni sono la ricerca in profondità e la ricerca in ampiezza.

Nella ricerca in profondità si espande sempre il nodo a profondità maggiore che sia stato generato ma non ancora espanso. Questo significa che si procede prima in profondità fino ad arrivare ad un nodo che non può essere ulteriormente espanso o a trovare una soluzione. Nel primo caso si riparte dai nodi al livello precedente di profondità e così via. Nella ricerca in ampiezza invece si espandono sempre i nodi a profondità minore che siano stati generati ma non ancora espansi. In questo caso si espande prima la radice dell'albero, poi tutti i suoi figli, poi tutti i figli dei figli e così via. In figura 3 è rappresentato l'ordine di espansione dei nodi di un albero secondo la strategia in profondità, e in figura 4 secondo la strategia in ampiezza.

Lo spazio di ricerca in realtà può strutturarsi anche in un "grafo", un albero nel quale un nodo può essere raggiunto seguendo percorsi multipli. In questo caso l'esplorazione può capitare in un nodo già espanso in precendenza. È importante accorgersene per non ripetere operazioni già svolte, e non complicare un problema altrimenti risolvibile. Perciò esistono algoritmi specifici che svolgono la ricerca in grafi anziché in alberi.

Le strategie viste precedentemente sono dette non informate, in quanto non utilizzano criteri per scegliere quale nodo espandere quando ve ne siano più di uno alla stessa profondità. Strategie più efficienti sono invece quelle informate, che, per scegliere, si basano su una conoscenza specifica del problema. Per esempio, la strategia best-first usa una funzione di valutazione f(n) che, dato un nodo n, restituisce un valore numerico; per primi sceglie i nodi con il valore f(n) più basso.

Nella strategia best-first "golosa", f(n) viene scelta uguale ad una funzione h(n) che, dato un nodo n, restituisce una stima del costo del cammino più economico da n ad un nodo finale. h(n) viene chiamata una funzione euristica, in quanto fornisce esclusivamente una stima, per difetto o per eccesso, non un valore certo.

Nella strategia A* (si legge "A star") la funzione f(n) è data dalla somma di due funzioni, g(n) e h(n). h(n) è una funzione euristica come nel caso precedente, mentre g(n) indica il costo del percorso dallo stato iniziale al nodo n. Quindi f(n) in questo caso indica il costo stimato della soluzione più economica che passa attraverso n. È possibile dimostrare che, se h(n) rispetta una certa condizione, la strategia A* è completa e ottimale; cioè, se esiste una soluzione, A* la trova, e al costo minimo. La condizione da rispettare è che h(n) sia "ottimistica", ovvero che non valga mai più del costo reale del cammino più economico da n ad un nodo finale.

Tutti gli algoritmi visti finora presentano un'architettura comune (Mel2002): essi hanno una memoria di lavoro per archiviare i risultati parziali, una serie di operatori associabili alle varie situazioni, e una strategia (o controllo), per stabilire quali di questi operatori siano applicabili, sceglierli (se più di uno) e applicarli. Questa architettura, condivisa da molti sistemi di IA, è descritta in figura 5.


Il tipo di ricerca considerata finora è una ricerca "in avanti" (forward o data-driven), che parte dallo stato iniziale e termina in uno stato finale. È possibile anche una ricerca che proceda in direzione opposta, "all'indietro" (backward o goal-driven), cioè partendo dallo stato finale (o goal) e, applicando gli operatori in senso inverso, arrivando ad uno stato iniziale. In genere, conviene utilizzare la ricerca in avanti quando lo stato iniziale sia uno solo, o pochi, e gli stati finali possano essere molti e il fattore di ramificazione sia basso vicino allo stato iniziale; mentre è preferibile la ricerca all'indietro quando lo stato finale sia uno solo o pochi, gli stati iniziali possano essere molti, e il fattore di ramificazione sia basso vicino allo stato finale. Esiste infine un terzo tipo di ricerca, che si chiama "bidirezionale" o "mista", in cui si procede contemporaneamente in avanti a partire dallo stato iniziale e all'indietro a partire dal goal, terminando quando si incontra lo stesso stato nelle due direzioni. Questo tipo di ricerca ha il vantaggio di restituire due alberi finali, costruiti a partire dallo stato iniziale e da quello finale, che possono avere profondità pari alla metà della profondità di un singolo albero finale costruito invece a partire dallo stato inziale o dallo stato finale. Dato che la dimensione dell'albero cresce in maniera esponenziale con la profondità, la somma delle dimensioni dei due alberi può essere molto più piccola della dimensione dell'albero singolo.

L'approccio alla soluzione dei problemi trattato finora contempla che l'agente intelligente possa prevedere gli effetti delle sue azioni. Il presupposto decade nel caso ci sia più di un agente, umano o artificiale, nel sistema. In particolare, gli altri agenti potrebbero avere obiettivi in conflitto con quelli dell'agente considerato. Si parla allora di "giochi".


Nei giochi di cui ci occuperemo esistono due giocatori che effettuano mosse a turno, l'effetto delle azioni è deterministico, e la somma delle utilità dei due giocatori al termine del gioco è sempre 0, quindi se uno vince (utilità +1) necessariamente l'altro perde (utilità -1). Inoltre sono giochi in cui si ha informazione perfetta: l'effetto delle mosse è direttamente visibile.

Esempi sono gli scacchi, la dama, l'othello e il go. Giochi a informazione imperfetta sono invece quelli con le carte, nei quali il giocatore non conosce ciò che ha in mano l'avversario. Programmare un computer per giocare a scacchi è stato uno dei primi obiettivi dell'IA, e già nel 1950 esistevano software del genere. I progressi raggiunti sono stati tali che l'11 maggio del 1997, per la prima volta nella storia, un computer ha battuto in un torneo il campione del mondo di scacchi Garry Kasparov, per 3,5 a 2,5. Il computer era Deep Blue della IBM. Per quanto riguarda la dama e l'othello, le macchine hanno ormai distanziato gli esseri umani, mentre nel backgammon, come negli scacchi, lasciano loro qualche chanche in più. Ma l'unico gioco che ancora resiste davvero è il go, nel quale i computer hanno prestazioni da dilettante.

Giocare può essere visto come un problema di ricerca in cui gli stati sono rappresentati dalle configurazioni dei pezzi sul tavolo da gioco, lo stato iniziale è rappresentato dalla configurazione di partenza dei pezzi, e le mosse possibili per ciascun giocatore sono quelle concesse dalle regole del gioco stesso. A partire da questi dati, si può costruire dalla configurazione iniziale un albero, in questo modo: i figli della radice sono le configurazioni che risultano da una mossa del giocatore che muove per primo, i figli dei figli sono le configurazioni che risultano da una mossa dell'altro giocatore, e così via. Quindi i nodi ai livelli dispari riguardano il primo giocatore, quelli ai livelli pari il secondo. L'albero di ricerca può essere ramificato fino a che non si raggiunga una configurazione finale, nella quale non sia più possibile muovere.

Nel caso dei giochi, è poi necessaria una funzione di utilità che assegna agli stati finali un valore numerico rispecchiante il risultato del gioco stesso: negli scacchi, ad esempio, i valori possono essere +1, -1 o 0, rispettivamente nel caso in cui abbia vinto il primo giocatore, il secondo oppure che la partita sia terminata con un pareggio. In altri giochi i punteggi potrebbero essere diversi; ad esempio, nel backgammon possono andare da +192 a -192. Valori alti dell'utilità sono buoni per il primo giocatore, che chiameremo quindi "max", mentre valori bassi dell'utilità sono buoni per il secondo giocatore, che chiameremo quindi "min".


Supponiamo di essere il giocatore max: come selezioniamo la mossa da eseguire in una data configurazione? La soluzione consiste nel costruire l'albero che ha quella configurazione come radice, fino ad arrivare alle configurazioni finali, assegnando poi a ognuna di esse il valore di utilità tramite la funzione di utilità. Dopodichè si assegna un ulteriore valore, che prende il nome di minimax, a tutti i nodi non finali partendo dal basso e procedendo verso l'alto: se al livello del nodo tocca muovere a min, il minimax del nodo è il minimo tra i valori di utilità dei figli; se al livello del nodo tocca muovere a max, il minimax del nodo è il massimo tra i valori di utilità dei figli. Il giocatore max eseguirà la mossa che porta alla configurazione con il minimax più alto.

Purtroppo lo spazio di ricerca dei giochi, esclusi i più semplici come il gioco del tris, è enorme e non è quindi possibile costruire l'albero fino agli stati finali. Negli scacchi, è stato stimato che il numero di configurazioni possibili sia dell'ordine di 10120. In questi casi si costruisce l'albero fino ad una profondità fissata m: le foglie dell'albero allora non saranno necessariamente configurazioni finali, e quindi, in luogo dell'utilità, si assegna loro una stima dell'utilità, del tutto simila alla funzione euristica vista in precedenza, ottenuta sulla base della configurazione stessa tramite una funzione di valutazione. Questa funzione deve essere fortemente correlata con le possibilità del giocatore di vincere partendo da quella configurazione. Inoltre dev'essere veloce da calcolare, perché la computazione va eseguita molte volte. Nel caso degli scacchi, un esempio di funzione di valutazione è dato dalla somma dei valori materiali di ciascun pezzo di max meno la somma dei valori materali di ciascun pezzo di min, dove il valore materiale di un pezzo è definito dai testi di scacchi e vale ad esempio 1 per un pedone, 3 per un alfiere o un cavallo, 5 per la torre e così via. Ovviamente le funzioni reali sono più complicate.

Per dare un'idea dell'importanza delle funzioni di valutazione: Deep Blue era in grado di esplorare circa 200 milioni (2•108) di posizioni al secondo (But2002). L'esplorazione dell'intero spazio di ricerca avrebbe dunque richiesto a Deep Blue 5•10111 secondi, ovvero 1095 miliardi di anni! Quindi la porzione dello spazio di ricerca effettivamente esplorata è stata piccola, e sono state usate complesse e articolate funzioni di valutazione. Al confronto con Kasparov, però, le funzioni di valutazione di Deep Blue sono semplici, se si pensa che lo scacchista russo, pur elaborando, secondo una stima, solo 3 posizioni al secondo, è riuscito a dare del filo da torcere al computer! Per questo si dice che Deep Blue abbia usato per vincere la forze bruta, piuttosto che una intelligenza raffinata.


Ragionamento automatico


Per ragionamento automatico s'intende l'utilizzo di conoscenza al fine di inferire nuova conoscenza. A questo scopo è necessario rappresentare la conoscenza in un formato memorizzabile da un calcolatore, e utilizzabile per effettuare inferenze. Questi requisiti restringono il formato di rappresentazione a linguaggi formali, ovvero linguaggi con una sintassi e una semantica definiti in maniera precisa.

Uno dei linguaggi formali maggiormente studiati è quello della logica. Essa ha le sue origini nella filosofia e nella matematica greca antica. Il padre fondatore della logica come disciplina autonoma può essere considerato Aristotele (384-321 a.C. circa), mentre Crisippo di Soli (280-205 a.C. circa), della scuola stoica, definì i connettivi logici, gli assiomi e le regole fondamentali della logica proposizionale.

La nascita della moderna logica matematica può essere fatta risalire a George Boole (1815-1864), che nel 1847 pubblicò un metodo per descrivere la teoria dei sillogismi aristotelici e la logica proposizionale sotto forma di equazioni algebriche, e propose un procedimento meccanico per la loro soluzione. Gottlob Frege (1848-1925) fu il primo a sviluppare un sistema di assiomi e regole per la logica del primo ordine, superando così i limiti imposti dai sillogismi e dalla logica proposizionale.

Nel 1965 John Robinson pubblicò il metodo di risoluzione che consente di automatizzare in maniera efficiente l'inferenza deduttiva nella logica del primo ordine. Su questo metodo è basata la programmazione logica, e il linguaggio Prolog (PROgramming in LOGic) in particolare, le cui basi furono gettate da alcuni ricercatori delle Università di Edimburgo e Marsiglia nei primi anni '70. Soprattutto Robert Kowalski, a Edimburgo, si occupò di definire i fondamenti teorici della programmazione logica, e propose una interpretazione procedurale delle formule logiche che consente di ridurre il processo di dimostrazione di un teorema ad un processo di computazione su un tradizionale elaboratore. Alain Colmerauer a Marsiglia fu il primo a realizzare, nel 1972, un interprete per il linguaggio Prolog.

Vediamo alcuni rudimenti della programmazione logica, cominciando dalla logica proposizionale. In essa, le unità elementari sono le proposizioni atomiche, cioè affermazioni non ulteriormente scomponibili che possono essere vere o false. Le proposizioni arbitrarie o formule proposizionali sono ottenute dalle formule atomiche, combinandole mediante i connettivi logici: negazione, congiunzione, disgiunzione e implicazione.


Esempi di proposizioni atomiche sono le affermazioni "l'erba è

gipoco.com is neither affiliated with the authors of this page nor responsible for its contents. This is a safe-cache copy of the original web site.