Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { Appello telematico 6 Luglio 2020 Tutte le risposte devono essere motivate. Gli esercizi vanno svolti in bella copia su fogli e poi scannerizzati con lo stesso ordine di svolgimento dell'esame. Il primo foglio deve contenere nome cognome e matricola, mentre tutti i fogli devono essere numerati. Il numero massimo di fogli ammessi e di 7 pagine. Il le da caricare deve essere in formato pdf e quando lo salvate sul vostro OneDrive va rinominato come "vostro- codice-persona.pdf". 1.Si considerino le seguenti proposizioni:(a)se Anna e una pittrice, allora Giorgio e uno scrittore oppure Silvia e una insegnante; (b)se Giorgio e uno scrittore, allora Lucia non fa la commessa oppure Silvia e una insegnante; (c)se Lucia fa la commessa, allora Anna e una pittrice; (d)Lucia fa la commessa;(e)Silvia e una insegnante. Si mostri sia per via semantica che utilizzando la teoria della risoluzione, che e) e deducibile da a), b), c), d). Soluzione:Consideriamo le seguenti lettere predicative: ˆAinterpreta \Anna e una pittrice"; ˆSinterpreta \Silvia e un' insegnante"; ˆGinterpreta \Giorgio e uno scrittore"; ˆLinterpreta \Lucia fa la commessa". A questo punto le precedente frasi possono essere riscritte in logica proposizionale nel seguente modo:a)A)(G_S); b)G)(:L_S); c)L)A d)L; e)S; Dobbiamo veri care sia usando la risoluzione che per via semantica chea); b); c); d)e). Mediante la risoluzione, per il teorema di correttezza e completezza per refutazione dobbiamo veri care che fa); b); c); d);:e)gc `R Per ricavare le clausole, trasformiamo trasformiamo in forma a clausole le precedenti formule, ricordandoci di negare la e), ottenendo da a) la clausolaf:A; G; Sg, da b)f:G;:L; Sg, da c),f:L; Ag, da d)fLge da:e) la clausolaf:Sg. Un possibile modo per ottenere la clausola vuota e dato dalla seguente derivazione per risoluzione:f: A; G; Sgf: G;:L; Sgf: Sgf Lgf: L; Agf Agf: A; Ggf: G;:Lgf: Ggf: Ag Usando invece la semantica, dobbiamo mostrare che ogni modello di a); b); c); d) e anche modello die), si puo fare la solita tabella, oppure si ragiona per assurdo. Infatti, supponiamo che questo non sia vero e che esista un modello vdia); b); c); d) che non lo sia pere), cioev(S) = 0. Dato che e modello did); c) abbiamo anche chev(L) = 1 e v(:L_A) = 1, da cui deduciamo che necessariamentev(A) = 1. Dato che e modello dia) abbiamov(A)(G_S)) = 1 e quindi necessariamentev(G) = 1, e quindi poichev(G)(:L_S)) = 1, deduciamo chev(:L) = 1, da cui l'assurdo v(L) = 0. 2.Sia RXX, conX=fa; b; c; d; egla relazione descritta dal seguente grafo d'incidenza:a b c de Notare la doppia freccia tra aeb (a)Costruire la chiusuraT d'equivalenza diT=Rn f(d; b)ge calcolarne il quozienteX=T . (b)Disegnare il grafo d'incidenza diR2 . Quali proprieta soddisfa? (c)Dire se puo esistere la chiusura d'ordine diR2 , ed eventualmente disegnare il suo diagramma di Hasse e trovare i il massimo. minimo, massimali e minimali. (d)Si consideri la seguente formula della logica del primo ordine: F=9x8y(A(x; y)) 9z(A(y; z)^A(z; y))) Si stabilisca seFe vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominio l'insiemeX e in cui la lettera predicativaA(x; y) e interpretata dalla relazioneRsuX.Fe logicamente valida? Soluzione:a)Il grafo di adiacenza diTe il seguente:a b c de La chiusura d'equivalenzaT si ottiene aggiungendo tutte le possibili frecce nelle componenti connesse, quindi:a b c de Quindi il quoziente X=T =ffa; b; cg;fd; egg. b)Il grafo di incidenza diR2 e il seguente:a b c de La relazione R2 e sia ri essiva che antisimmetrica e seriale. c)Dato cheR2 e sia ri essiva che antisimetrica, potrebbe esistere la chiusura d'ordine. Per veri carlo chiudiamola transitivamente (e gia ri essiva), il grafo d'incidenza della sua chiusura transitiva e il seguente:a b c de che e ancora antissimetrica, dunque esiste la chiusura d'ordine e il suo diagramma di Hasse e il seguente: a bc d e Chiaramente ce sia massimo che massimale, mentreee sia minimo che minimale. d)La formula e chiusa, quindi nell'interpretazione data puo essere solo o vera o falsa. In questo caso e vera, infattiprendendox=b, allora l'unico elementoytale che (b; y)2Rey=a, ed in questo caso il coseguente e vero prendendoz=b, infatti in questo caso e vero che (a; b)2Re (b; a)2R. La formula non e logicamente valida, infatti basta interpretareA(x; y) mediante la relazione su due elementifa; bgde nita daH=f(a; b)g. 3.Sia Gil gruppo delle matrici invertibili di ordine 2 a coecienti inZ 5(gruppo rispetto al prodotto righe per colonne), e si consideri il suo sottoinsieme H= a b 0c :a; b; c2Z 5; ac = [1] 5 a)Si mostri cheHe un sottogruppo diG; b)Si calcoli la cardinalita diHe si stabilisca seHpuo contenere sottogruppi di cardinalita 3; c)Si considerino la seguente formula della logica del primo ordine: 8x8y(E(y; h(x)),(E(f(x; y); b)^E(f(y; x); b)^E(h(f(x; y)); f(h(y); h(x)) ) ) ) e un'interpretazione avente come dominio l'insiemeHe in cui la lettera predicativaEe interpretata dalla relazione di uguaglianza e la lettera funzionalefdall'operazione interna dell sottogruppoHvista nei punti precedenti. Si stabilisca come si possono interpretare la lettera funzionalehe la costantebanche la formula assegnata risulti vera nell'interpretazione considerata. Soluzione:a)Usiamo il criterio per i sottogruppi: mostriamo che per ognig; h2H,gh 1 2H. Per trovare l'inverso del generico elementoh= a b 0c 2Ho impostiamo l'equazione a b 0c  x y z t = 1 0 0 1 oppure ci ricordiamo cheZ 5e un campo e l'inversa di una matrice 2 2 si calcola come det(h) 1 cb 0a = [ac] 1 5 cb 0a = cb 0a dato che [ac] 5= [1] 5. Quindi: gh 1 = d f 0e  cb 0a = cd afbd 0ae dato cheg2Habbiamo [de] 5= 1, quindi [ cd] 5
[ae] 5= [ ca] 5
[de] e= [1] 5
[1] 5= [1] 5, da cui cd afbd 0ae 2H. b)Dobbiamo calcolare i possibili valori dia; ctale che [a] 5
[c] 5= [1] 5cioe: {a=c= [1] 5; {a= [2] 5; c = [3] 5; {a= [3] 5; c = [2] 5; {a= [4] 5; c = [4] 5. cioe 4 possibili valori, il parametrobinvece puo assumere tutti i valori diZ 5, cioe 5, quindi la cardinalita di jHj= 5
4 = 20. Ora per il Teorema di Lagrange sappiamo che la cardinalita di ogni sottogruppoSdiHdeve dividere la cardinalita diG. Quindi, poiche la cardinalita diHe 20, e 3 non divide 20, possiamo concludere che non possono esistere sottogruppiSdiHdi cardinalita 3. d)La formula precedente si traduce nell'interpretazione data come: 8x8y y=h(x),(xy=b^yx=b^h(xy) =h(y)h(x)) se prendiamob=Icome l'unita del gruppoH, eh(x) =x 1 cioe la funzione che considera l'inverso allora la formula precedente e vera perche dice chey=x 1 se solo seyx=I,yx=Ie (xy) 1 =y 1 x 1 .