Soluzione Esame 12 luglio

Pagina 1

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 12 Luglio 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) 3 c) 2 d) 3 ) Sia X = {a, b, c, d, e, f} e sia R la relazione su X rappresentata dal seguente grafo di adiacenza: c a f e d b (a) Determinare, se possibile, la minima relazione d’ordine S contenente R e, se esistono, gli elementi massimali e minimali, massimo e minimo di X rispetto a S. (b) Determinare la relazione d’equivalenza ρ generata da R e l’insieme quoziente X/ρ. (c) Dire quante sono le funzioni da X ad X contenenti R e quante tra queste ammettono inversa sinistra. (d) Data la seguente formula della logica del primo ordine ∀x∀z(A(x, y) ∧ A(z, y) =⇒ ∃tA(y, t) ∨ A(x, z)) stabilire se essa ` e vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominio X e in cui A sia da interpretare come la relazione R. Soluzioni: (a) La minima relazione d’ordine S contenente R ` e la chiusura riflessiva e transitiva diR e quindi ha il seguente grafo di adiacenza: c a f e d b Il diagramma di Hasse di S ` e il seguente: c a f e d b da cui si evince che l’insieme dei massimali ` e{b, f}, l’insieme dei minimali ` e{c, e, d} e quindi non esistono massimo e minimo di X rispetto ad S. (b) La relazione d’equivalenza ρ generata da R ` e la chiusura riflessiva, simmetrica e transitiva di R e quindi ha il seguente grafo di adiacenza: c a f e d b L’insieme quoziente ` eX/ρ = {[a]ρ, [b]ρ}, dove [a]ρ = {a, c, e, f},…