Fondamenti di Informatica (parte Barbanera)
20 Febbraio 2020
Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o
smartphone (questi ultimi vanno riposti lontano dalla propria persona). Le risposte vanno scritte nel foglio di bella copia. Si
raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra'
considerata negativamente.
Per sostenere l'esame e' obbligatorio essersi prenotati sul portale studenti del nostro
ateneo. Elaborati di studenti non prenotati NON verranno valutati.
I risultati
verranno indicati nella pagina web del corso.
Date ed orari degli orali, sul Forum.
(a)
Sia {{},{c1, g1, p2, a2}} una segnatura dove c e g sono simboli
predicativi unari, mentre p e a
sono simboli predicativi binari.
Interpretando
c(x) come "x e' un cane", g(x) come "x e' un gatto",
p(x,y) come "x e' il padrone di y" e
a(x,y) come "x ama y"
traducete le seguenti frasi (scrivete cioe' le formule ben formate corrispondenti,
avendo a disposizione entrambi i quantificatori e tutti i connettivi logici):
(i) ogni cane non ama alcun gatto;
(ii) tutti i cani e i gatti hanno un padrone;
Scrivere inoltre la frase in italiano corrispondente alla seguente formula ben formata:
∀x.((c(x) ∧ ¬∃y.p(y,x)) → ∀z.¬a(z,x))
(b)
Dimostrare in deduzione naturale per la logica proposizionale la proposizione 3.10 del testo di Martini,
cioe' che α → β ⊢ ¬β → ¬α
(c)
Nel contesto del λ-calcolo,
enunciare il Teorema di Church-Rosser ed utilizzarlo per dimostrare il Corollario di Unicita'
della forma normale.
(d)
In un sistema formale ogni regola derivabile e' ammissibile? In caso di risposta affermativa, dimostrarlo.
In un sistema formale ogni regola ammissibile e' derivabile? In caso di risposta affermativa, dimostrarlo.