Transcript
Prova scritta di Elementi di Logica Matematica Esempio Svolgete i primi due esercizi su un foglio, gli altri tre esercizi su un altro foglio. Rispondete alle domande di teoria direttamente sul testo mettendo una crocetta su vero o falso. Scrivete il vostro nome su ogni foglio che consegnate, compreso questo! A fianco di ogni domanda o esercizio `e indicato il punteggio massimo assegnato ad esso: per superare l’esame bisogna raggiungere 18 punti, di cui almeno 4 relativi alle domande di teoria. Domande di teoria Dite se l’affermazione `e vera o falsa. Le risposte errate influiranno negativamente sul punteggio. T1. Se I, σ |= ∀x F allora I, σ |= F {x/t} per ogni termine t. V F T2. Se I, σ |= F {x/t} per ogni termine t allora I, σ |= ∀x F . V F T3. Se F `e valida nella logica con uguaglianza allora F `e valida. V F T4. ∀x F ∨ ∀x G ⇔ ∀x(F ∨ G). V F T5. Se F `e una formula aperta di tipo α, allora (NB: le conclusioni corrette possono essere nessuna, una o pi` u d’una): F `e una congiunzione; V F F `e logicamente equivalente a una congiunzione; V F F non `e un’implicazione; V F F pu`o essere la negazione di un’implicazione. V F T6. Se F e G sono equisoddisfacibili, allora (NB: le conclusioni corrette possono essere nessuna, una o pi` u d’una): se F `e valida allora G `e valida; V F V F se F `e valida allora G `e soddisfacibile; se F non `e valida allora G non `e valida; V F F se F non `e soddisfacibile allora G non `e soddisfacibile. V T7. Se I e J sono interpretazioni per un linguaggio L e sappiamo che esiste un omomorfismo forte di I in J, allora (NB: le conclusioni corrette possono essere nessuna, una o pi` u d’una): V F I e J sono elementarmente equivalenti; V F I e J non sono elementarmente equivalenti; V F I e J sono isomorfe; F se F `e un enunciato atomico, I |= F se e solo se J |= F . V
1pt 1pt 1pt 1pt 2pt
2pt
2pt
Esercizi E1. Sia L = {a, d, p, q, =} un linguaggio con uguaglianza, dove a `e un simbolo di costante, d e p sono simboli di funzione unari, q `e un simbolo di relazione unario. Interpretando a come Andrea, d(x) come il dottore di x, p(x) come il padre di x e q(x) come x `e parente di Andrea, traducete le seguenti frasi: (i) Il padre di Andrea `e dottore di qualche parente di Andrea. (ii) Andrea ha un parente che `e dottore di qualcuno. (iii) Il dottore di Andrea `e dottore di tutti i parenti di Andrea, ad eccezione del padre di Andrea. E2. Sia L il linguaggio con un simbolo di costante c, un simbolo di funzione unario f e simboli di relazione p (unario) e r (binario). Sia I l’interpretazione per L definita da I
D = N,
I
c = 4,
I
f (n) = n + 1,
6pt
2pt
I
p = {0, 1, 4, 5, 11, 90},
rI = { (n, m) : n `e pari e m `e dispari } . Stabilite se I soddisfa l’enunciato p(c) ∧ ∀x ∃y(r(x, y) ∨ r(y, x)) → ∀x(p(x) ∧ ∃y r(y, x) → ¬p(f (x))). E3. Costruite un’interpretazione con dominio {A, B, C} e uno stato che soddisfano la formula
4pt
∀x ∃y(r(x, y) ∧ ¬r(y, x)) ∧ r(x, x) ∧ ¬r(f (x), x). E4. Se A, B, C, D e E sono formule atomiche, mettete in forma normale congiuntiva la formula
4pt
(A → ¬B) ∨ ¬(C ∧ D → ¬(¬C ∨ E)) E5. Sia F l’enunciato ∃z ∀x ∃y r(g(x, z), y) → ∀y ∃x r(x, g(y, z)) → ∃z ¬∀x ∃y r(g(x, y), z) ∧ ¬∃y ∀x r(g(z, x), g(z, y)) . (a) Indicate le occorrenze positive e negative dei quantificatori in F. (b) Skolemizzate localmente la F , ottenendo una formula F 0 . (c) Trasformate F 0 in forma prenessa, usando il minimo numero di quantificatori possibile.
6pt
