Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { 31 Agosto 2018 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. SiaX=fa; b; c; d; egY=fx; y; zge siaRXYla relazione denita da: R=f(a; x);(b; y);(b; z);(c; x);(d; z);(e; x);(e; y);(e; z)g (a) Quante funzioni sono contenute inR? Quante di queste sono iniettive? (b) Indicare una funzionef:X!Yche sia contenuta inR. Determinare kerf, e costruireX= kerf. (c) Dire se esiste una funzioneg:X!Yche sia suriettiva e contenuta inR. In caso aermativo costruire una sua inversa sinistra e dire quante sono le possibili inverse sinistre dig. Soluzione: (a) Dato che l'unico elemento in relazione conaecexe condez, allora sefRnecessariamentef(a) =f(c) =x, mentref(d) =z,f(b) puo essere ozoy, mentref(e) puo esserex; y; z. Quindi 2
3 = 6 scelte. Non ci sono funzioni iniettive dato che se esistesse una funzione iniettivagavremmo 5 =jg(X)j  jYj= 3, assurdo. (b) Una possibile funzione ef(a) =f(c) =x,f(d) =f(b) =f(e) =z. Le kerf-classi difsono [a] kerf= fa; cg, [b] kerf= fd; b; egda cuiX= kerf= f[a] kerf; [b] kerfg . (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)2 fa; cg,h(z)2 fb; dg,h(e) =y, quindi 4 possibili inverse sinistre, una possibile e data dah(x) =a,h(z) =b, h(e) =y. E facile vericare cheh
fe l'identita suY. 2. (a) Dire se nella teoria Lla formula (A^B))(A) :B) puo essere dedotta daA_ :B. (b) Provare lo stesso risultato utilizzando la teoria della risoluzione. Soluzione: (a) Per il teorema di correttezza e completezza nella teoriaLabbiamoA_ :B` L( A^B))(A) :B) se e solo se A_ :B(A^B))(A) :B) dato che (A^B))(A) :B) e falso solo quandoAeBsono entrambe vere, abbiamo che (A^B))(A) :B) e equivalente a:(A^B) =:A_ :B. Quindi il modelloA= 1; B= 1 di A_ :Bnon e modello di (A^B))(A) :B), da cui possiamo dedurreA_ :B0 L( A^B))(A) :B). (b) Dal teorema di correttezza e completezza per refutazione dobbiamo mostrare chef:((A^B))(A) :B));(A_ :B)gc `R . Dato che:((A^B))(A) :B)) e equivalente a (A^B), abbiamof:((A^B))(A) :B));(A_ :B)gc =ffAg;fBg;fA;:Bgg. Si nota subito che l'unica risolvente signicativa che si puo ottenere e quella trafA;:BgefBgche da ancorafAg, quindi non si puo ottenere la clausola vuota e quindiA_ :B0 L (A^B))(A) :B). 3. Si consideri la seguente formula del primo ordine: ((8x)(8y)A(f(x; y); z)))(9x) (A(x; y))(8y)A(x; y)) (a) Si indichino le occorrenze libere e vincolate di ogni variabile e si porti la formula data in forma normale prenessa. (b) Si consideri l'interpretazione avente come dominio i naturaliN, in cui la lettera predicativaA(x; y) viene in- terpretata comex > ye la lettera funzionalef(x; y) viene interpretata come il prodottox
y. Dire se in tale interpretazione la formula e vera, falsa o soddisfacibile ma non vera. Soluzione: (a)ze una variabile libera ed inoltre e libera la prima occorrenza diynel conseguente. Tutte le altre occorrenze di xedysono vincolate. Per portare la formula a forma prenessa cominciamo a portare in forma prenessa il suo conseguente: ((8x)(8y)A(f(x; y); z)))(9x)(8u) (A(x; y))A(x; u)) poi portiamo davanti a tutto i quanticatori dell'antecedente: (9x)(9v) ((A(f(x; v); z))(9x)(8u) (A(x; y))A(x; u))) e da ultimo portiamo davanti a tutto i quanticatori del conseguente:(9x)(9v)(9w)(8u) (A(f(x; v); z))(A(w; y))A(w; u))) (b) Nell'interpretazione suggerita dal testo la formula data si legge come: \se per ognixe per ogniy xy > zallora esiste unxtale che sex > yallora per ogniy; x > y, dove x,y,z stanno inN. Comunque assegniamo un valore a z, la formula per ognixe per ogniy xy > ze falsa (basta prenderex=y= 1 ez= 1), dunque la nostra formula e vera. 4. Sia consideri sull'insieme dei numeri reali Rl'operazione binaria interna # denita nel seguente modo: a#b=a+b(a
b) dove + e
sono le usuali operazioni di addizione e moltiplicazione inRe l'elemento(a
b) e l'opposto rispetto all'operazione + dell'elementoa
b. (a) Mostrare che (R;#) e un monoide commutativo. (b) (R;#) e anche un gruppo? In caso contrario, descrivere l'insieme degli elementi chenonsono invertibili. Soluzione: 1. Dobbiamo vericare che l'operazione sia associativa. Si ha a#(b#c) =a+ (b+cbc)a(b+cbc) =a+b+cbcabac+abc inoltre si ha:(a#b)#c= (a+bab) +c(a+bab)c=a+b+cabacbc+abc che sono chiaramente uguali, quindi l'operazione e associativa. E chiaramente commutativa: a#b=a+bab=b+aba=b#a Cerchiamo l'unita. Questa e un elementoxche deve soddisfare: a#x=a per ognia. Quindia+xax=ada cui otteniamo che necessariamentex(1a) = 0 per ognia, quindix= 0. Si verica facilmente chea#0 =aper ognia, quindi 0 e l'unita e dunque (R;#) e un monoide. 2. Per vericare se e un gruppo, dato che # e commutativa, basta vericare se, dato un qualunque elementoa, esiste un elementoxtale che: a#x= 0 cioea+xax= 0 da cui otteniamo che necessariamentex=a1 a. Quindi non e un gruppo, dato che l'elemento 1 non e invertibile. Nel caso in cuia6 = 1 si verica subito chea#a1 a= 0, da cui deduciamo che l'insieme degli elementi che non sono invertibili e l'insiemef1g.