Soluzionedellaprovadel31agosto2018

Page 1

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 31 Agosto 2018 Cognome: Nome: Matricola: 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. Sia X ={a, b, c, d, e} Y ={x, y, z} e sia R⊆ X× Y la relazione definita da: R ={(a, x), (b, y), (b, z), (c, x), (d, z), (e, x), (e, y), (e, z)} (a) Quante funzioni sono contenute in R? Quante di queste sono iniettive? (b) Indicare una funzione f : X→ Y che sia contenuta in R. Determinare ker f, e costruire X/kerf . (c) Dire se esiste una funzione g : X→ Y che sia suriettiva e contenuta in R. In caso affermativo costruire una sua inversa sinistra e dire quante sono le possibili inverse sinistre di g. Soluzione: (a) Dato che l’unico elemento in relazione con a e c ` ex e con d ` ez, allora se f⊆ R necessariamente f(a) = f(c) = x, mentre f(d) = z, f(b) pu` o essere o z o y, mentre f(e) pu` o esserex, y, z. Quindi 2 · 3 = 6 scelte. Non ci sono funzioni iniettive dato che se esistesse una funzione iniettiva g avremmo 5 =|g(X)|≤| Y| = 3, assurdo. (b) Una possibile funzione ` e f(a) = f(c) = x, f(d) = f(b) = f(e) = z. Le ker f-classi di f sono [ a]ker f ={a, c}, [b]ker f ={d, b, e} da cui X/ker f ={[a]ker f , [b]ker f}. (c) Una possibile funzione suriettiva ` eg(a) = g(c) = x, g(d) = g(b) = z, g(e) = y. Un’inversa sinistra ` e data scegliendo h(x)∈{ a, c}, h(z)∈{ b, d}, h(e) = y, quindi 4 possibili inverse sinistre, una possibile ` e data dah(x) = a, h(z) = b, h(e) = y. `E facile verificare che h· f ` e l’identit` a suY . 2. (a) Dire se nella teoria L la formula (A∧ B)⇒ (A⇒¬ B) pu` o…