Fondamenti Logici dell’Informatica

Fondamenti Logici dell’Informatica

Corso di Laurea Magistrale in Informatica Introduzione al Corso

Ugo Dal Lago

Anno Accademico 2018-2019

Sezione 1

Introduzione al Corso

Questo Corso

I Questo è un corso pensato per gli studenti del primo anno della Laurea Magistrale in Informatica.

I Può anche essere seguito da studenti di altri corsi di laurea che abbiano i prerequisiti descritti di seguito.

I Il carico di lavoro complessivo è di 6 ECTS, che corrispondono a circa 40 ore di lezioni frontali.

Contenuti del Corso

I In questo corso si analizza in che senso la logica fornisce all’informatica una serie di strumenti di analisi che

risultano estremamente utili, in diverse aree.

Logica Matematica Complessit`a

Computazionale

Basi di Dati

Linguaggi di Programmazione

Intelligenza Artificiale Verifica di Sistemi

Contenuti del Corso

I In questo corso si analizza in che senso la logica fornisce all’informatica una serie di strumenti di analisi che

risultano estremamente utili, in diverse aree.

Logica Matematica Complessit`a

Computazionale

Basi di Dati

Linguaggi di Programmazione

Intelligenza Artificiale Verifica di Sistemi

Prerequisiti

I Fondamentale per affrontare questo corso è una conoscenza delle nozioni di base della logica matematica.

I Occorre, in particolare, conoscere bene:

I La logica proposizionale.

I La logica al prim’ordine.

I La loro semantica.

I Uno o più sistemi deduttivi.

I Sistemi alla Hilbert.

I Deduzione Naturale.

I Alberi Semantici.

I Risoluzione.

I Teoremi di Correttezza e Completezza.

Formule

I Logica Proposizionale

F, G::= >

|

|

|

|

|

|

I A è una variabile proposizionale;

I I connettivi logici ¬, ∧ e F hanno il loro significato intuitivo.

I Logica Predicativa

t, s ::= x

|

F, G ::= >

|

|

|

|

|

|

|

|

dove:

I x è una variabile al prim’ordine;

I Ogni simbolo funzionale f ha un’arietà n(f );

I t, s, ti sono detti termini;

I Ogni simbolo predicativo P ha un’arietà n(P ).

Formule

I Logica Proposizionale

F, G::= >

|

|

|

|

|

|

I A è una variabile proposizionale;

I I connettivi logici ¬, ∧ e F hanno il loro significato intuitivo.

I Logica Predicativa

t, s ::= x

|

F, G ::= >

|

|

|

|

|

|

|

|

dove:

I x è una variabile al prim’ordine;

I Ogni simbolo funzionale f ha un’arietà n(f );

I t, s, ti sono detti termini;

I Ogni simbolo predicativo P ha un’arietà n(P ).

Semantica in Logica Proposizionale

I La semantica di una formula è parametrizzata su

un’interpretazione v, ossia su una mappa che assegna ad ogni variabile proposizionale A un valore di verità A_v∈ {0, 1}.

I Con v |= F indichiamo che la formula F è vera nell’interpretazione v.

I E’ definita per induzione sulla struttura della formula:

v |= >;

v 6|= ⊥;

v |= A sse Av = 1;

v |= ¬F sse v 6|= F ; ...

Semantica in Logica Predicativa

I In logica predicativa, il significato di una formula è più complesso da definire.

I Prima di tutto, abbiamo bisogno di un universo A, i cui elementi sono gli oggetti di cui la formula parla.

I Abbiamo poi bisogno di un’intepretazione I, che però riguardi i simboli funzionali e predicativi.

I Ad ogni simbolo funzionale f l’interpretazione I fa corrispondere una funzione

fI : A^{n(f )}→ A.

I Ad ogni simbolo predicativo P l’interpretazione I fa corrispondere un sottoinsieme P_I di A^{n(P )}

I Infine, c’è bisogno di un ambiente ξ che faccia corrispondere ad ogni variabile x un elemento x_ξ di ξ.

Semantica in Logica Predicativa

I Semantica dei Termini

JxK

(A,I) ξ = x_ξ; Jf (t1, . . . , t_{n(f )})K

(A,I)

ξ = f_I(Jt1K

(A,I)

ξ , . . . ,Jtn(f )K

(A,I)

ξ )

I Semantica delle Formule

(A, I), ξ |= P (t1, . . . , t_{n(P )}) sse (Jt¹K

(A,I)

ξ , . . . ,Jtn(f )K

(A,I) ξ ) ∈ PI

(A, I), ξ |= ∃x.F sse (A, I), ξ[x := a] |= F per qualche a ∈ A (A, I), ξ |= ∀x.F sse (A, I), ξ[x := a] |= F

per tutti gli a ∈ A ..

.

Conseguenza Logica

I Indichiamo con Γ o ∆ delle sequenze finite di formule.

I In logica proposizionale, diciamo che F è conseguenza logica di Γ = G1, . . . , G_n sse per ogni v, se è vero che v |= G1, . . . , v |= Gn, allora vale anche che v |= F . In tal caso, scriviamo

Γ |= F.

I In logica predicativa, si può dare una definizione analoga.

I Il modo in cui abbiamo definito la relazione di conseguenza logica è tale per cui non esiste un modo semplice, di natura algoritmica, per determinare se una formula è conseguenza logica di una sequenza di formule.

Sistemi Deduttivi

I Un sistema deduttivo può essere pensato come un modo per dimotrare che F è una conseguenza logica di Γ senza far riferimento alla semantica delle formule coinvolte.

I Esempi:

I La Deduzione Naturale, dovuto a Gentzen.

I I Sistemi alla Hilbert, basati su assiomi e regole.

I Il metodo di Risoluzione, che si basano sulla ricerca di refutazioni.

I In ciascuno di tali sistemi deduttivi viene definita una nozione di giudizio derivabile nella formaΓ ` F .

I In che relazione stanno ` e |=?

Sistemi Deduttivi

Γ ` A Γ |= A

Correttezza

Completezza

Organizzazione del Corso

I Primo Modulo

I Docente: Prof. Claudio SACERDOTI COEN.

I È un modulo monografico sulla logica nei linguaggi di programmazione.

I Si va un po’ in profondità nell’argomento.

I Occuperà (suppergiù) tutte le lezioni fino all’inizio di Novembre.

I Secondo Modulo

I Docente: Prof. Ugo DAL LAGO.

I Le applicazioni della logica a molte aree dell’informatica verranno introdotte.

I Per ragioni di tempo, non è possibile andare troppo in dettaglio.

I Inizierà a Novembre e terminerà poco prima della fine del Primo Semestre.

Organizzazione del Corso

Logica Matematica Complessit`a

Computazionale

Basi di Dati

Linguaggi di Programmazione

Intelligenza Artificiale Verifica di Sistemi

Organizzazione del Corso

Logica Matematica Complessit`a

Computazionale

Basi di Dati

Linguaggi di Programmazione

Intelligenza Artificiale Verifica di Sistemi Primo Modulo

Organizzazione del Corso

Logica Matematica Complessit`a

Computazionale

Basi di Dati

Linguaggi di Programmazione

Intelligenza Artificiale Verifica di Sistemi Primo Modulo Secondo Modulo

Modalità d’Esame

I L’esame consiste in una prova orale, che riguarderà entrambi moduli.

I Le domande riguarderanno l’intero corso.

I Data la natura del corso, le domande saranno teoriche, ma potrebbero anche declinarsi in semplici esercizi.

I Come per tutti gli altri corsi, ci saranno a disposizione ben sei appelli in ogni anno accademico, di cui:

I Due in Sessione Invernale;

I Tre in Sessione Estiva;

I Uno in Sessione Autunnale.

Sezione 2

Il Secondo Modulo

Logistica

I Quattro ore di lezione a settimana.

I Il martedì, dalle 11.30 alle 13.30.

I Il mercoledì, dalle 15.30 alle 17.30.

I Non c’è un orario di ricevimento studenti prefissato.

I Basta però prendere appuntamento via email (ugo.dallago@unibo.it).

I Se avete dubbi sui contenuti del corso, potete ovviamente inviarmi una mail.

I Vi invito a fare tutte le domande che volete durante la lezione, ma anche offline.

Libri di Testo e Materiale Didattico

I La pagina web del modulo è

http://www.cs.unibo.it/~dallago/FLI1819/

A partire da essa trovate:

I Il syllabus del corso;

I Alcuni riferimenti bibliografici;

I Sono disponibili delle trasparenze, non necessariamente per tutte le parti del corso.

I Alcune dimostrazioni verranno svolte alla lavagna.