Soluzione Esame 6 settembre 2022

Pagina 1

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 6 settembre 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) 2; b) 2; c) 2; d) 3; e) 5) Si consideri la relazione binaria R su A = {a, b, c, d, e, f} definita nel seguente modo: R = {(a, b), (a, c), (b, d), (c, f), (d, d), (e, e), (f, e)} (a) Disegnare il grafo d’adiacenza di R e determinarne la matrice d’adiacenza. (b) Stabilire quali propriet` a soddisfaR tra serialit` a, riflessivit` a, simmetria, antisimmetria e transitivit` a. (c) Determinare la chiusura di equivalenza T di R e descrivere il quoziente A/T . (d) Stabilire se esiste la chiusura d’ordine S di R e, in caso affermativo, determinarla, disegnarne il diagramma di Hasse e individuare eventuali elementi minimali, massimali, minimi e massimi di A rispetto ad S. (e) Usando la risoluzione del primo ordine, dimostare che se una relazione ` e riflessiva allora ` e anche seriale. Soluzione (a) Il grafo di adiacenza di R ` e il seguente: a b c d ef La matrice d’adiacenza di R ` e la seguente: M =   0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0   (b) La relazione R ` e seriale dal momento che da ogni vertice del grafo di adiacenza parte almeno un arco ed ` e antisimmetrica poich´ e non ci sono archi con doppia freccia (esclusi gli autoanelli) e quindi, per lo stesso motivo,R non pu` o essere simmetrica.R non ` e riflessiva poich´ e non ci sono autoanelli su ogni arco e non ` e…