Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { 13 Febbraio 2020 Voto Lab. precedente & docente:Cognome:Nome:Matricola: Tutte 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.Si vuole vedere se la diagnostica di un server sia avviata o meno sapendo che sussistono le seguenti regole:(a)La diagnostica e avviata se accade che non riceva un segnale e sia occupato, oppure nel caso in cui non sia occupato. (b)Se la diagnostica non e avviata allora vuol dire che il segnale non e arrivato e che il server non e occupato. Dopo aver formalizzato il problema nella logica proposizionale, mostrare sia per viasemanticache con larisoluzione che la diagnostica e sempre avviata. Soluzioni: (a)Indichiamo conSla lettera enunciativa che indica che il segnale e stato ricevuto,Oche il server e occupato, eD che la diagnostica e stata avviata. Allora la prima frase si traduce in ((:S^O)_ :O))Dche e equivalente a (:S_ :O))D. Mentre la seconda formula e:D)(:S^ :O). Dobbiamo mostrare sia per via semantica che con la risoluzione chef(:S_ :O))D;:D)(:S^ :O)gD. Mediante la tabella di verita e semplice calcolare i modelli dif(:S_ :O))D;:D)(:S^ :O)ge si veri ca che tutti questi modelliv isoddisfano vi( D) = 1, e quindi l'implicazione semantica vale. Mediante la risoluzione dobbiamo mostrare che l'insieme f(:S_ :O))D;:D)(:S^ :O);:Dge insoddisfacibile. Per il teorema di correttezza e completezza per refutazione questo equivale a mostraref(:S_ :O))D;:D)(:S^ :O);:Dgc `. Le clausole sono quindi f:Dg;fD; Og;fS; Dg;fD;:Sg;fD;:Og. La risolvente trafS; Dg;fD;:SgefDgche conf:Dgotteniamo la clausola vuota. 2.Sia RXX, conX=fa; b; c; d; egla relazione descritta dal seguente grafo d'incidenza:a b dc e (a) Re una funzione? In caso costruire la relazioneK er Re l'insieme quozienteX= K er R; (b)Dire se puo esistere la chiusura d'ordine diR, ed eventualmente disegnare il suo diagramma di Hasse. Calcolare (se esistono)S upfa; egeI nffa; eg. (c)Veri care se la seguente formulaH=9x8y(B(y; x)) 9zB(z; y)) e vera, falsa, o soddisfacibile ma non vera quandoB(x; y) e interpretata dalla relazioneR; (d)Si consideri la seguente formula della logica del primo ordine: F=8x8y(A(x; y), 9z(B(y; z)^B(z; x))) doveB(y; z) e interpretata dalla relazione precedenteR, mentreA(x; y) da una nuova relazione binariaTsuX. Disegnare il grafo d'incidenza diTin modo che la precedente formula risulti vera.Fe logicamente valida? Soluzione:(a)S, infattiRe una funzione perche per ognia2Xvi e un unicox2Xt.c. (a; x)2R. La relazioneK erR=I[ f(a; d);(d; a);(b; e);(e; b);(e; c);(c; e);(b; c);(c; b)g(doveIe la relazione identica). Quindi il quoziente eX=K erR= f[a];[c]g, dove [a] =fa; dg, [c] =fb; e; cg. (b)La relazioneRe antisimmetrica, quindi potrebbe esistere la sua chiususra d'ordine. Chiudiamo transitivamente e ri essivamente:a b dc e che rimane antisimmetrica, quindi e la piu piccola relazione d'ordine che contiene R. Il suo diagramma di Hasse edb ac e da cui S upfa; eg=c, mentreI nffa; egnon esiste dato che l'insieme dei minoranti difa; ege vuoto. (c)La formula dice che esiste unxtale che, per ogniy, seyRx, allora deve esistere anche unoztale chezRy. La formula e chiusa, quindi e vera o falsa. In questo caso e vera dato che per esempio prendendox=anon esiste nessunytale cheyRaquindi essendo l'antecedenteB(y; x) sempre falso, la formula risulta vera. (d)La formulaFdescrive la relazioneTnel seguente modoxT yse e solo se esiste unoz2Xtale cheyRzezRx. Per esempio (a; b);(b; c)2Rquindi (c; a)2T, similmente (b; c);(c; c)2Rda cui (c; b)2T, quindiTe descritta dal seguente grafo d'incidenza:a b dc e La formula non e logicamente valida, basta prendere la stessa intepretazione con Ainterpretata daR,Binterpre- tata dalla relazioneTn f(c; a)g(doveTe descritta dal grafo d'incidenza illustrato qua sopra). 3.Si consideri il sottoinsieme A=f(a; b)2RR; a6 = 0gdotato dell'operazione: (a; b)?(c; d) = (ac; ad+bc) (a)Mostrare che (A; ?) e un gruppo. E un gruppo commutativo? (b)Il sottoinsiemeH=f(a; b)2A; a+b= 0; a6 = 0ge un sottogruppo di (A; ?)? (c)Si consideri il gruppo B= a0 b a :a6 = 0 rispetto all'usuale prodotto righe per colonne. Dimostrare che la funzioneh:A!Bde nita da: h(a; b) = a0 b a e un isomor smo di gruppi. Soluzioni:(a)L'operazione e interna infatti (a; b)?(c; d) = (ac; ad+bc) cona; c6 = 0 implicaac6 = 0. E associativa: ((a; b)?(c; d))? (e; f) = (ac; ad+bc)?(e; f) = (ace; acf+(ad+bc)e) = (ace; acf+ade+bce) = (ace; a(cf+de)+bce) = (a; b)?(ce; cf+ de) = (a; b)?((c; d)?(e; f)). L'elemento neutro e (1;0) infatti (a; b)?(1;0) = (1;0)?(a; b) = (a; b). Per l'inverso cerchiamo (x; y) t.c. (a; b)?(x; y) = (1;0) cioeax= 1,ay+bx= 0 da cuix= 1=a,y=b=a2 (ricordarsia6 = 0). Si veri ca anche che (1=a;b=a2 )?(a; b) = (1;0) da cui otteniamo che l'inverso di (a; b) e (1=a;b=a2 ). Quindi (G; ?) e un gruppo. Notate che e commutativo dato che (a; b)?(c; d) = (ac; ad+bc) = (ca; cb+da) = (c; d)?(a; b). (b)L'insiemeHe fatto dalle coppie (a;a) cona6 = 0 ora e evidente che questo insieme non e chiuso per?, infatti (a;a)?(b;b) = (ab;2ab) che non appartiene adH. (c)Poiche: h((a; b)?(c; d)) =h(ac; ad+bc) = ac0 ad+bc ac = a0 b a  c0 d c =h(a; b)h(c; d) quindihe un omomor smo di gruppi. Per dimostrare che e un isomor smo mostriamo che e suriettiva, infatti per ogni matriceC= a0 b a e chiaro cheh(a; b) =C. L'inieittivita e anche evidente, infatti:h(a; b) =h(c; d) implica che: a0 b a = c0 d c da cui si deducea=c; b=d.