Parte 2 + Esempi domande teoriche

1. Persi occorrenza

Cosa intende libera ed occorrenza vincolata variabile?

Una variabile è libera se compare nel campo d'azione dei quantificatori.
Una variabile è vincolata se compare nel campo d'azione di quantificatori.

2. Termine

Definizione di induttiva [fbf]

Base:

• Per ogni dichiarazione di costante tipo t, c: T, un termine di tipo T.
• Per ogni dichiarazione di variabile tipo t, x: T, un termine x: T.

• Per ogni dichiarazione di funzione f, se t1,...,tn sono termini di tipo T1,...,Tn, allora f(t1,...,tn) è un termine di tipo T.

3. Interpretazione di segnatura

Dare un esempio di interpretazione della seguente segnatura:

Simboli di costante: a, b
Simboli di funzione: f(_)
Predicato: p(_, _)
Interpretazione:

• u0 ↦ {u0}
• f(u0) ↦ a
• b ↦ u0
• p ↦ vera se e solo se p(u0, u0) è vera

4. Conseguenza tautologica

Dare la definizione di conseguenza tautologica

Una conseguenza è tautologica se per ogni interpretazione, ogni premessa è vera implica la conclusione è vera. In termini formali, se per ogni interpretazione della segnatura (p1,..., pn → Q) è vera, allora (p1,..., pn → Q) è una conseguenza logica.

5. Teoria con assiomi

Consideri una teoria con assiomi Ax

Assiomatica: Si dice che un insieme assiomatico T_Ax ha validità se ogni teorema P_n è dimostrabile a partire dalle premesse P₁, ..., P_n.

6. Teorema di completezza

Fitch: Usa le regole proposizionali e le regole dei quantificatori partendo dalle premesse.
Teoria Assiomatica: Se è dimostrabile dagli assiomi, è una conseguenza logica.
Sistema Formale: Se c'è una conseguenza logica SF con premesse P₁, ..., P_n, allora Q è una conseguenza logica nel SF di P₁, ..., P_n.

7. Definizione induttiva

(Spiegare la definizione induttiva in modo dettagliato seguendo la struttura sopra).