Esame 22 giugno

Pagina 1

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 22 Giugno 2022 Docente e ultimo voto laboratorio: Cognome: Nome: Codice persona: T utte le risposte devono essere motivate. Gli esercizi vanno svolti su questi fogli, nello spazio sotto il testo e sul retro. I fogli di brutta non devono essere consegnati. I compiti privi di indicazione leggibile di nome e cognome non verranno corretti. 1. (Punteggio: a) 3, b) 1+2, c) 4+1 ) Si consideri la relazione binaria ρ su X = Z × Z definita nel seguente modo: (a, b) ρ (c, d) se e solo se ab − cd = 0 (a) Si mostri che ρ ` e una relazione di equivalenza suX. (b) Si mostri che [(2 , 3)]ρ = [(1, 6)]ρ e si verifichi che ρ = ker(f), dove f : X → Z ` e definita daf(a, b) = ab. (c) Si consideri la seguente formula della logica del primo ordine: ∀x ( A(a, x) ∧ A(f(x), x) ⇒ A(g(x, x), x) ) Si stabilisca se ` e vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominio D l’insieme di tutte le relazioni binarie su X e nella quale la costante a ` e interpretata dalla relazione identica suX, A(x, y) ` e la relazione di inclusione di relazioni, f(x) ` e la relazione inversa dix, e g(x, y) ` e il prodotto tra le relazionix, y. La formula ` e logicamente valida o logicamente contradditoria? Soluzioni: (a) La relazione ρ ` e riflessiva dato che (a, b)ρ(a, b) dal momento che ab = ab; ` e anche simmetrica infatti se (a, b)ρ(c, d) allora ab = cd e quindi anche ( c, d)ρ(a, b). Infine ρ ` e anche transitiva: se (a, b)ρ(c, d) e ( c, d)ρ(e, f) allora ab = cd = ef da cui segue che ( a, b)ρ(e, f). (b) Dato che 2 · 3 = 1 · 6, abbiamo che (2 , 3)ρ(1, 6) e quindi [(2 , 3)]ρ = [(1, 6)]ρ. La relazione ker( f) mette in relazione due elementi ( a, b), ( c, d) se e solo se f(a, b) = f(c, d)…