Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { 03 Febbraio 2022 Docente:Cognome:Nome:Codice persona: 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.(Punteggio:2.5+3.5, 3) (a)Vericare sia per via semantica sia usando la risoluzione che il seguente insieme di f.b.f.: =f:A; B^C)(A()B); B)A; C_(B) :C)g e soddisfacibile. (b)Vericare se [ f:(:A^(B)A)^ :C)ge un insieme insoddisfacibile. Soluzione:(a)E' immediato vericare cheC_(B) :C) e una tautologia, quindi i modelli di e quelli di 0 =f:A; B^C)(A()B); B)Ag coincidono. Dalle tavole di verita delle formule di 0 otteniamo i modelli di 0 che sono solo due: 1( A) = 1( B) = 1( C) = 0 e 2( A) = 1( B) = 0, 2( C) = 1. Pertanto e chiaramente un insieme soddisfacibile poiche ammette almeno un modello. Con la risoluzione dobbiamo mostrare che dalle clausole di 0 non ricaviamo quella vuota. Le clausole di 0 sono le seguenti: ˆdalla prima formula si ricavaf:Ag; ˆdalla seconda si ricavaf:B; A;:Cg(dato che la formula e semanticamente equivalente a:B_A_ :C); ˆdalla terza formula si ricavaf:B; Ag: Ora dalle tre clausolef:Ag,f:B; A;:Cg,f:B; Agvediamo subito che possiamo eliminare (pruning) le ultime due clausole che contengono:B(dato che non compare unBe quindi non potro mai \eliminarlo") e quindi rimaniamo con la sola clausolaf:Agda cui non potro mai ottenre la clausola vuota, quindi 0 e soddisfacibile, e quindi anche . Alternativamente bastava vericare cheRis(0 ) = 0 [ ff:B;:Cg;f:Bgg=Ris2 (0 ) e, poiche la clausola vuota non appartiene aRis(0 ), segue che l'insieme 0 e soddisfacibile e quindi lo e anche . (b)Il problema e equivalente a vericare(:A^(B)A)^ :C) dato che l'interpretazione 2tale che  2( A) = 1( B) = 0, 2( C) = 1 e modello di ma non di (:A^(B)A)^ :C), ne deduciamo che l'insieme [ f:(:A^(B)A)^ :C)ge soddisfacibile. 2.(Punteggio:2+1+1,1,2, 2+2) SiaRla relazione binaria sull'insiemeX=fa; b; c; d; e; fgdenita nel seguente modo: R=f(a; b);(a; d);(c; d);(c; e);(c; f);(d; b);(d; e);(f ; b)g (a)Vericare che puo esistere una relazione d'ordine contenenteRe indicare conSla piu piccola relazione d'ordine contenenteR. Costruire il diagramma di Hasse diSe determinare seXammette massimo e/o minimo, elementi massimali e/o elementi minimali rispetto adS. (b)Determinare il diagramma di Hasse di una relazione d'ordine totale contenenteS. (c)Dimostrare che non esistono funzioni contenute inRne funzioni contenentiR. (d)Si consideri la seguente formula della logica del primo ordine: 8x(A(x; y)^ :E(x; y)) 9zA(y; z)) stabilire se essa e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominioXe in cui, A(x; y) sia da interpretare come la relazioneReE(x; y) come l'uguaglianza. Rispondere alla medesima richiesta nel caso in cui nell'interpretazione precedenteA(x; y) sia da interpretare come la relazioneS. Soluzione:(a)La matrice d'adiacenza diRe data da: M=0 B B B B B B @0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 01 C C C C C C A Si nota subito cheRe antisimmetrica, per vericare se esiste la relazione d'ordine contenteRchiudiamo transiti- vamente e ri essivamente. Abbiamo M2 =0 B B B B B B @0 1 0 0 1 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 C C C C C C A mentreM3 e la matrice nulla, quindi la matrice della chiusura transitiva e ri essiva diRe N=0 B B B B B B @1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 11 C C C C C C A che e chiaramente la matrice di adiacenza di una relazione antisimmetrica e quindi rappresenta la matrice d'adiacenza della chiusura d'ordineSdiR. Il diagramma di Hasse diSe il seguente:b f d cae da cui deduciamo che non ci sono ne massimi ne minimi e che l'insieme dei massimali e fb; egmentre l'insieme dei minimali efc; ag. (b)Dobbiamo trovare una relazione d'ordine totaleTche contengaS. Per farlo, basta costruire un diagramma di Hasse che sia compatibile conS, cioe sexsta sotto un verticeynel diagramma di Hasse diS, allora anche nel diagramma di Hasse diTdobbiamo avere chexsta sottoy. Una possibilita e la seguente: b e d f a c (c)Non esistono funzioni che contengono Rpoiche per qualunque relazioneFconRFsi avrebbe (a; d);(a; b)2F e cio contraddirebbe la denizione di funzione. Inoltre per ogni relazioneFtale cheFRsi avrebbe chebnon e in relazione con nessun elemento e pertantoFnon potrebbe essere una funzione. (d)Osserviamo innanzitutto che la formula non e chiusa. Dato che il conseguente9zA(y; z) e soddisfatto pery=d segue che la formula assegnata e soddisfacibile. La formula pero e non vera, infatti pery=bex=dl'antecedente A(x; y)^ :E(x; y) e soddisfatto poiched6 =be (d; b)2Rma il conseguente non lo e poiche non esiste alcunoztale che (b; z)2R. Pertanto la formula assegnata risulta essere soddisfacibile ma non vera nella prima interpretazione. Invece interpretandoA(x; y) come la relazioneSabbiamo che la formula e vera: infatti, per ogniy2X, abbiamo (y; y)2SessendoSri essiva e pertanto il conseguente9zA(y; z) e vero rendendo l'intera formula vera in questa seconda interpretazione. 3.(Punteggio: 3,2+1, 2+2) Si consideri il seguente sottoinsiemeSdelle matrici quadrate di ordine 2 ad elementi inZ 5 S= a b b a :a; b2Z 5 (a)Si mostri che (S;
) con l'usuale prodotto
righe per colonne e un monoide commutativo. (b)Mostrare che la funzione':S!Z 5denita da ' a b b a =a2 b2 e un omomorsmo tra il monoide (S;
) e il monoide (Z 5;
),'e anche un monomorsmo? (c)Si consideri la seguente formula della logica del primo ordine: 8x8y(E(f(x); f(y))) 8zK(p(z; x); p(z; y)) ) Si stabilisca se e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominio l'insiemeS, in cuifinterpreta un omomorsmoF: (S;
)!(S;
) di monoidi,p(x; y) interpreta il prodottox
ynel monoide (S;
),E(x; y) interpreta l'uguaglianza, mentreK(x; y) interpreta la relazione ker(F). La formula e logicamente valida o insoddisfacibile? Soluzione: (a)Verichiamo che l'operazione
sia interna, infatti: a b b a
     = a+b a+b b+ a  b+a 2S dato chea+b= b+aeb+ a=a+b. L'associativita e conseguenza dell'associativita del prodotto righe per colonne di matrici su di un campo (in questo casoZ 5), mentre l'identita del monoide e data dalla matrice I= [1]5[0] 5 [0]5[1] 5 che appartiene chiaramente adS. Dimostriamo la commutativita dell'operazione: a b b a
     = a+b a+b b+ a  b+a =    
 a b b a Pertanto (S;
) e un monoide commutativo. (b)Dato che, per ogniA2S,'(A) =det(A), il risultato segue immediatamente dal teorema di Binet, infatti: '(A
B) =det(AB) =det(A)det(B) ='(A)'(B) In alternativa si puo eettuare una verica diretta: ' a b b a
     = (a+b)2 (a+b)2 = (a2 b2 )(2 2 ) =' a b b a '     Per essere un omomorsmo di monoidi si verica anche che'(I) = [1] 5che e l'unita del monoide ( Z 5;
): L'applicazione assegnata non e un monomorsmo dato che non e iniettiva, infatti: ' [4]5[0] 5 [0]5[4] 5 = [1]5= ' [1]5[0] 5 [0]5[1] 5 nonostante le due matrici siano diverse. (c)Nell'interpretazione data, la formula si traduce nel seguente modo: seF(x) =F(y) allora, per ogniz, (zx; zy)2 ker(F). Questa e vera dato cheFe un omomorsmo e quindi ker(F) e una congruenza, in particolare ker(F) e compatibile con la moltiplicazione. Segue che se (x; y)2ker(F) (cioe seF(x) =F(y)), allora per ognizabbiamo che anche (zx; zy)2ker(F) (ovviamente (z; z)2ker(F)). Segue che la formula non e insoddisfacibile ma non e nemmeno logicamente valida. Infatti considerando l'interpretazione in cuiE(x; y) e interpretata dalla relazione universale su di un insiemeX,K(x; y) dalla relazione vuota efda una funzione qualunque suX, otteniamo che l'antecedente della formula e sempre vero mentre il conseguente e sempre falso, pertanto la formula e non vera in questa interpretazione.