Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { Appello telematico 11 settembre 2020 Tutte le risposte devono essere motivate. Gli esercizi vanno svolti in bella copia su fogli numerati e poi scannerizzati con lo stesso ordine di svolgimento dell'esame. Il primo foglio deve contenere nome cognome e matricola. Il numero massimo di fogli ammessi e di 6 pagine. Il le da caricare deve essere in formato pdf e quando lo salvate sul vostro OneDrive va nominato come "vostro-codice-persona". 1.Siaf(A; B; C) una f.b.f della teoria L che assume valore 1 solo nelle due interpretazioniv 1; v 2tali che v1( A) =v 1( B) = 1e v 1( C) = 0 v2( A) = 0e v 2( B) =v 2( C) = 1 (a)Scrivere una formulaf(A; B; C) che rispetti le condizioni assegnate. (b)Dire se la formula (:A)B))(C) :f(A; B; C)) e un teorema della teriaL. (c)Provare lo stesso risultato del punto precedente usando la risoluzione. Soluzione: a)Possiamo costruire una formulaf(A; B; C) in forma normale disgiuntiva:f(A; B; C)(A^B^ :C)_(:A^B^C). b)Dal teorema di correttezza e completezza della teoria L, abbiamo che` L( :A)B))(C) :f(A; B; C)) se e solo se(:A)B))(C) :f(A; B; C)) e questo equivale a dire che la formula e una tautologia. Scrivendo la tavola di verita di (:A)B))(C) :f(A; B; C)) si verica che tale formula non e una tautologia e quindi non e un teorema della teoriaL. Infatti dalla tavola di verita si puo facilmente vericare che l'unico modello della formula e l'interpretazionevtale chev 1( A) = 0e v 1( B) =v 1( C) = 1 e pertanto la formula data e equivalente aA_ :B_ :C. c)Proviamo lo stesso risultato di prima mediante la risoluzione. Dal punto precedente sappiamo che dobbiamovericare che la formula (:A) :B))(C) :f(A; B; C)) non e una tautologia e cio e equivalente a dimostrare chef:((:A) :B))(C) :f(A; B; C)))ge soddisfacibile. Applicando le equivalenze otteniamo: :((:A) :B))(C) :f(A; B; C)))  :(A_ :B_ :C) :A^B^C Pertanto si ottiene il seguente insieme di clausole di input: ff:Ag;fCg;fBgg dal quale e evidente che non e possibile ottenere la clausola vuota non essendoci nessun letterale che compare positivo in una clausola e negativo in un'altra. 2.Si consideri la relazione Rsull'insiemeX=fa; b; c; d; egdenita dalla seguente matrice d'incidenza 0 B B B B @1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 01 C C C C A (a)Si provi cheRe transitiva; (b)Si mostri che non esiste nessuna relazione d'ordine suXche contengaR; (c)Si disegni il grafo d'incidenza della chiusura d'equivalenzaTgenerata daR; (d)Si stabilisca seTcoincide con la chiusura ri essiva e simmetricaSdiR; (e)Si mostri che non esiste ne nessuna funzione daXinXcontenuta inR, ne nessuna funzione daXinXcontenente R; (f )Si consideri la seguente formula della logica del primo ordine: 8x9yA(x; y)) 8x8y8z((A(x; y)^A(y; z)))A(x; z)) Si stabilisca se e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominio l'insiemeXe in cui la lettera predicativaAe interpretata dalla relazioneRsuX. Cosa accade seAe interpretata dalla relazione SsuX? Soluzione:a)Per mostrare la transitivita diRbasta calcolareR2 e mostrare cheR2 R, per fare questo calcoliamo la matrice d'incidenza diR2 :0 B B B B @1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 C C C C A e osserviamo cheR2 Rdato che gli \1" della matrice d'incidenza diR2 sono contenuti nella matrice d'incidenza diR. b)Una qualunque relazioneconteneteRconterrebbe le coppie (a; b);(b; a) conb6 =ae quindinon sarebbe antisimmetrica. Pertanto non esiste nessuna relazione d'ordine contenenteR. c)La chiusura d'ordineTsi ottiene aggiungendo tutte gli archi nelle clique:c d ea b d)La chiusura ri essiva e simmetrica SdiRha il seguente grafo d'incidenza:c d ea b che chiaramente non coincide con T. e)Chiaramente non puo esistere una funzione contenuta inRdato che la penultima riga non ha \1" , mentre una qualunque relazionefcontenenteRavrebbe almeno due \1" sulla prima riga e quindi non potrebbe essere una funzione. f )La formula e chiusa quindi in qualunque interpretazione essa e vera o falsa mentre non puo essere soddisfacibilema non vera. La formula dice che una qualunque relazioneHinterpretata daA(x; y) ha la seguente proprieta: \Se He seriale, allora e transitiva". Nel caso si consideriH=R, la formula e vera dato cheRnon e seriale, quindi l'antecedente della formula non e vero. Mentre se interpretiamoA(x; y) conS, dato cheSe seriale, l'antecedente e vero mentre il conseguente e falso, dato cheSnon e transitiva, quindi in questa interpretazione la formula e falsa. 3.Si consideri l'insieme ZZstrutturato ad anello rispetto alle seguenti operazioni (a; b) + (c; d) = (a+c; b+d);(a; b)
(c; d) = (ac; bd) (a)Si verichi che la relazioneRcos denita: (a; b)R(c; d),ac(mod 3); bd(mod 5) e una relazione d'equivalenza suZZ.Re una congruenza dell'anello (ZZ;+;
)? (b)Si determini la classe di equivalenza [(0;0)] Ra cui appartiene lo zero dell'anello e si mostri che e un ideale. (c)Si consideri la seguente formula della logica del primo ordine: 8x8y8z8w( (A(x; y)^A(z; w)))(A(f(x; z); f(y; w))^A(g(x; z); g(y; w))) ) e si dica se e vera, falsa, soddisfacibile ma non vera nell'interpretazione nella quale il dominio eZZla lettera predicativeAe la relazioneR, le lettere funzioanalifegsono rispettivamente le operazioni di addizione e moltiplicazione inZZ. Soluzione:a)Re ri essiva, infatti, per ognia; b2Z,aa(mod 3); bb(mod 5) e quindi (a; b)R(a; b).Re simmetrica, infatti se (a; b);(c; d)2ZZsono tali che (a; b)R(c; d), alloraac(mod 3); bd(mod 5) e quindi, dalla simmetria della congruenza modulon, segue checa(mod 3); db(mod 5), cioe (c; d)R(a; b).Re transitiva, infatti se (a; b);(c; d);(e; f)2ZZsono tali che (a; b)R(c; d);(c; d)R(e; f), alloraac(mod 3); bd(mod 5) e ce(mod 3); df(mod 5). Pertanto, dalla transitivita della congruenza modulon, segue cheae(mod 3); b f(mod 5), cioe (a; b)R(e; f). Segue cheRe una relazione d'equivalenza. Per vericare seRe una congruenza dell'anello (ZZ;+;
), dobbiamo vericare seRe compatibile con le operazioni di addizione e moltiplicazione. Supponiamo che (a; b)R(; ), (c; d)R( ; ), questo e equivalente a dire (dalla denizione diR) che [a] 3= [ ] 3, [ b] 5= [ ] 5e [ c] 3= [ ] 3, [ d] 5= [ ] 5, quindi: {addizione (mostriamo che (a+c; b+d)R(+ ; +)): da [a] 3= [ ] 3, [ b] 5= [ ] 5e [ c] 3= [ ] 3, [ d] 5= [ ] 5 deduciamo che [a+c] 3= [ a] 3+ [ c] 3= [ ] 3+ [ ] 3= [ + ] 3, inoltre [ b+d] 5= [ b] 5+ [ d] 5= [ ] 5+ [ ] 5= [ +] 5, da cui abbiamo la tesi (a+c; b+d)R(+ ; +); {moltiplicazione (mostriamo che (ac; bd)R( ;  )): da [a] 3= [ ] 3, [ b] 5= [ ] 5e [ c] 3= [ ] 3, [ d] 5= [ ] 5 deduciamo che [ac] 3= [ a] 3
[c] 3= [ ] 3
[ ] 3= [ 
] 3, inoltre [ bd] 3= [ b] 5
[d] 5= [ ] 5
[] 5= [ 
] 5, da cui abbiamo la tesi (ac; bd)R( ;  ). PertantoRe una congruenza dell'anello (ZZ;+;
). b)Dalla teoria sappiamo gia che la classe d'equivalenza dello zero di un anello rispetto ad una congruenza e un ideale.Verichiamolo direttamente usando il criterio di caratterizzazione degli ideali. Risulta: I= [(0;0)] R= f(a; b) : (a; b)R(0;0)g=f(a; b) : [a] 3= [0] 3; [b] 5= [0] 5g Siano (a; b);(c; d)2I, allora: (a; b)(c; d) = (a; b) + (c;d) = (ac; bd)2I poiche [ac] 3= [ a] 3 [c] 3= [0] 3 [0] 3= [0] 3e [ bd] 5= [ b] 5 [d] 5= [0] 5 [0] 5= [0] 5. Siano ora ( c; d)2ZZ e (a; b)2I, allora: (c; d)
(a; b) = (a; b)
(c; d) = (ca; db)2I poiche [ca] 3= [ c] 3
[a] 3= [ c] 3
[0] 3= [0] 3; [db] 5= [ d] 5
[b] 5= [ d] 5
[0] 5= [0] 5. Pertanto Ie un ideale per il criterio di caratterizzazione degli ideali. d)La formula e chiusa, quindi e vera o falsa, ma non soddisfacibile ma non vera. La formula descrive la proprietacheRsia una congruenza, infatti per ognix= (a; b); y= (; ); z= (c; d); w= ( ; ) se (a; b)R(; ), (c; d)R( ; ), allora (a+c; b+d)R(+ ; +) e (ac; bd)R( ;  ), che e esattamente la denizione di congruenza. PoicheRe una congruenza segue che la formula data e vera nella interpretazione assegnata.