LOGICA E SISTEMI INFORMATICI http://cialdea.dia.uniroma3.it/teaching/lsi/
Logica (Wikipedia): La parola logica deriva dal greco “Logos”, ovvero “parola, pensiero, idea, argomento, ragione”. La logica `e lo studio dei procedimenti inferenziali, rivolto a chiarire quali procedimenti siano validi e quali non validi.
Logic is the art and science of reasoning. More specifically, it is defined by the Penguin Encyclopedia to be “The formal systematic study of the principles of valid inference and correct reasoning”. As a discipline, logic dates back to Aristotle ... and is now an integral part of disciplines such as mathematics, computer science, and linguistics.
Logic concerns the structure of statements and arguments ... The concept of logical form is central to logic; it being held that the validity of an argument is determined by its logical form, not by its content.
Logic is generally accepted to be formal, in that it aims to analyse and represent the form (or logical form) of any valid argument type. The form of an argument is displayed by representing its sentences in the formal grammar and symbolism of a logical language ...
Logica
Linguaggio formale
Sintassi (alfabeto e grammatica)
Semantica (interpretazione delle espressioni)
Sistemi di inferenza (deduzione)
Logica e Informatica
1. Ruolo esterno e teorico: logica come meta-informatica
• definizione della nozione di calcolabilit` a
• risultati di indecidibilit` a
• classificazione dei problemi secondo la loro complessit` a
2. Ruolo interno e pratico:
Esempi:
• Fondamento di paradigmi di program- mazione
– programmazione logica (basa- ta su metodi di dimostrazione auto- matica): il programmatore specifica CHE COSA si deve calcolare, senza occuparsi di COME
– programmazione funzionale (basata sul lambda-calcolo)
• Semantica di linguaggi di programma- zione
• Linguaggi di specifica formale
• Specifica algebrica di tipi astratti di dati
• Verifica di propriet` a di pro- grammi (correttezza, terminazione, ...), verifica dell’affidabilit`a di sistemi hardware e software
• Linguaggio di rappresentazione e ra- gionamento in IA. Applicazione, ad esempio, alla pianificazione auto- matica
2
Argomenti del corso 1. Logica classica (proposizionale e dei predicati)
(a) Sintassi e semantica, propriet`a della logica proposizionale e della logica dei predicati (b) Calcolo di deduzione naturale
2. Deduzione automatica in logica classica (a) Tableaux per la logica proposizionale
(b) Il metodo di risoluzione e la programmazione logica 3. Il linguaggio Prolog
4. Il Calcolo delle Situazioni e il linguaggio Golog
5. Metodi formali per la verifica di sistemi
Argomenti del corso: D.M.509/99 1. Logica classica (proposizionale e dei predicati)
(a) Sintassi e semantica, propriet`a della logica proposizionale e della logica dei predicati (b) Calcolo di deduzione naturale
2. Deduzione automatica in logica classica
(a) Tableaux per la logica proposizionale
(b) Il metodo di risoluzione e la programmazione logica 3. Il linguaggio Prolog
4. Il Calcolo delle Situazioni e il linguaggio Golog 5. Metodi formali per la verifica di sistemi
4
Argomenti del corso: esame integrativo 1. Logica classica (proposizionale e dei predicati)
(a) Sintassi e semantica, propriet`a della logica proposizionale e della logica dei predicati (b) Calcolo di deduzione naturale
2. Deduzione automatica in logica classica
(a) Tableaux per la logica proposizionale
(b) Il metodo di risoluzione e la programmazione logica 3. Il linguaggio Prolog
4. Il Calcolo delle Situazioni e il linguaggio Golog
5. Metodi formali per la verifica di sistemi
Argomenti del corso: IA1/a 1. Logica classica (proposizionale e dei predicati)
(a) Sintassi e semantica, propriet` a della logica proposizionale e della logica dei predicati
(b) Calcolo di deduzione naturale
2. Deduzione automatica in logica classica (a) Tableaux per la logica proposizionale
(b) Il metodo di risoluzione e la programmazione logica 3. Il linguaggio Prolog
4. Il Calcolo delle Situazioni e il linguaggio Golog 5. Metodi formali per la verifica di sistemi
6. Soluzione di problemi mediante ricerca nello spazio degli stati.
7. Pianificazione automatica
6
Argomenti del corso: IA1/b 1. Logica classica (proposizionale e dei predicati)
(a) Sintassi e semantica, propriet` a della logica proposizionale e della logica dei predicati
(b) Calcolo di deduzione naturale
2. Deduzione automatica in logica classica (a) Tableaux per la logica proposizionale
(b) Il metodo di risoluzione e la programmazione logica 3. Il linguaggio Prolog
4. Il Calcolo delle Situazioni e il linguaggio Golog 5. Metodi formali per la verifica di sistemi
6. Soluzione di problemi mediante ricerca nello spazio degli stati.
7. Pianificazione automatica
Materiale didattico
• Logica classica:
M. Cialdea Mayer. Logica. Linguaggio, ragionamento, calcolo. Esculapio 2002 + integrazioni disponibili in rete
• Prolog: qualunque testo di introduzione al Prolog + compilatore SWI-Prolog
• Calcolo delle Situazioni e Golog
Dispense + interprete Golog in SWI-Prolog Consultare:
R. Reiter. Knowledge in Action: Logical Foundations for Specifying and Implemen- ting Dynamical Systems. MIT Press, 2001.
H.J. Levesque et al. GOLOG: A Logic Programming Language for Dynamic Do- mains.
• Verifica di sistemi software Dispense.
D.A. Peled. Software Reliability Methods. Springer, 2001.
8
