Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { 10 Febbraio 2021 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.(a)La formula (A)B))(C)A) e un teorema della teoriaL? (b)Mostrare usando il metodo della risoluzione del primo ordine che la formula: F=8x8y( (A(x; y)) 9y:B(y)))(8zB(z)) :A(x; y)) ) e logicamente valida. Soluzioni:Punteggio 9: a) 4; b) 5 (a)Dal teorema di correttezza e completezza della teoriaLabbiamo che la assegnata formula e un teorema diLse e solo se risulta che(A)B))(C)A), cioe se e solo se la formula assegnata e una tautologia. Ora, invece di scrivere la tavola di verita, ragioniamo per assurdo e cerchiamo (se esiste) un eventuale assegnamento che renda falsa la formula. Questo assegnamentodovrebbe rendere vero l'antecedenteA)Be falso il conseguenteC)A, quindi(C) = 1 e(A) = 0 da cui si ottiene(A)B) = 1. Quindi, per esempio, l'assegnamento(C) = 1, (A) = 0 e(B) = 1 rende la formula (A)B))(C)A) falsa e pertanto tale formula non e una tautologia e quindi non e un teorema diL. (b)Dobbiamo veri care se la formula:Fe insoddisfacibile e quindi, per il teorema di correttezza e completezza per refutazione della risoluzione, se (:F)c `R . Portiamo in fnp la formula dell'esercizio: 8x8y( (A(x; y)) 9y:B(y)))(8zB(z)) :A(x; y)) ) 8x8y(9t(A(x; y)) :B(t))) 9z(B(z)) :A(x; y)) ) 8x8y8t9z( (A(x; y)) :B(t)))(B(z)) :A(x; y)) ) Neghiamo la formula:F  9x9y9t8z:( (A(x; y)) :B(t)))(B(z)) :A(x; y)) ) e portiamo in forma di Skolem: :Fsk 8 z:( (A(a; b)) :B(c)))(B(z)) :A(a; b)) ) Quindi dalla matrice della formula ricaviamo le clausolef:A(a; b);:B(c)g;fB(z)g;fA(a; b)g. Una risolvente tra la prima e l'ultima clausola ef:B(c)ge quindi la clausola vuota si ottiene come risolvente tra quest'ultima clausola e la seconda con la sostituzionec=z. Segue che la formuala assegnata e logicamente valida. 2.Sia RXX, conX=fa; b; c; d; egla relazione descritta dal seguente grafo d'incidenza:a b c d e (a)Disegnare il grafo d'adiacenza della chiusura d'equivalenza Tdella relazioneRn f(b; a)ge costruireX=T; (b)Quante funzioni daXinXsono contenute inRe quante funzioni contengonoR? (c)Dire se puo esistere la chiusura d'ordine diRed eventualmente disegnare il suo grafo d'adiacenza e disegnare il suo diagramma di Hasse, trovandone, se esistono, i punti di massimo, minimo, massimali e minimali. (d)Si consideri la seguente formula della logica del primo ordine: F=8x8y(9z(A(x; z)^A(y; z))) 9wA(z; w)) 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? Soluzioni:Punteggio 12: a) 2, b) 2, c) 4, d) 4 (a)Il grafo d'adiacenza e il seguentea b c d e da cui ricaviamo che X=T=f[c];[a]g, dove [a] =fag, [c] =fc; d; b; eg. (b)Per ogni vertice diverso daeabbiamo una sola freccia uscente, mentre abbiamo due frecce uscenti dae, quindi le uniche due funzioni contenute inRsono:f 1( e) =c; f 1( c) =b; f 1( d) =b; f 1( b) =a; f 1( a) =aef 2( e) =d; f 2( c) = b; f2( d) =b; f 2( b) =a; f 2( a) =a. Non esistono invece funzioni che contengonoRdato che, per una qualunque relazioneFcontenenteR, si avrebbe che (e; c);(e; d)2RFe quindiFnon sarebbe una funzione. (c)Dato cheRe antisimmetrica, potrebbe esistere la sua chiusura d'ordine, chiudiamoRri essivamente e transiti- vamente ottenendo la relazioneTdescritta dal seguente gra d'adiacenza:a b c d e Il suo diagramma di Hasse e il seguente: a b c d e Dunque ee minimo, quindi anche minimale, mentreae massimo e quindi anche massimale. (d)Notate che la formula non e chiusa. Pero dato cheRe seriale abbiamo che per ognizesiste sempre unwtale che (z; w)2Re quindi il conseguente della precedente formula e sempre vero, da cui otteniamo che la formula e vera in questa interpretazione. La formula non e logicamente valida basta considera l'interpretazione sul dominio Y=fa; bgdoveAe interpretata dalla relazioneS=f(a; b)g: prendendo l'assegnamentox=y=a, l'antecedente 9z(A(x; z)^A(y; z)) e soddisfatto ma non lo e il conseguente dato che non esistewtale che (b; w)2S. Notare che non e vero che in ogni relazione non seriale la formula e falsa, basta considerare la relazione vuota su di un qualunque dominio che non e una relazione seriale ma rende falso l'antecedente, rendendo vera la formula. 3.Si consideri il seguente sottoinsieme di Q X=n z3 k: z2Z; k2N=f0;1; : : :go (a)Si provi che (X;+) e un sottogruppo normale di (Q;+). (b)(Xn f0g;
), con l'usuale moltiplicazione di razionali, e sottogruppo di (Q;
)? Si motivi la risposta. (c)Veri care che (X;+;
) e un sottoanello di (Q;+;
);Xe un ideale di (Q;+;
)? (d)Si consideri la seguente formula della logica del primo ordine: 8x8y8z(E(f(f(x; y); z); f(x; f(y; z)))^(A(x))A(f(x; z))) ) Si stabilisca se essa e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominioQed in cuiEinterpreta la relazione di uguaglianza,finterpreta la moltiplicazione eA(x) si interpreta come \x2X". E logicamente valida o contradditoria. Soluzioni:Punteggio 10: a) 3, b) 2, c) 2, d) 3 (a)Per il criterio di caratterizzazione dei sottogruppi veri chiamo se presix 1; x 22 Xabbiamo chex 1 x 22 X. Sex 1= z 1= 3k 1 ,x 2= z 2= 3k 2 , e supponiamok 1 k 2, allora abbiamo x 1 x 2=z 1 3k 1 k 2 z23 k 12 Xin quanto z1 3k 1 k 2 z2e un intero. Segue che ( X;+) e un sottogruppo di (Q;+) ed inoltre, essendo (Q;+) commutativo, allora ogni suo sottogruppo e normale e quindi deduciamo che anche (X;+) e normale. (b)Nel testo si intendeva ovviamente il gruppo (Qn f0g;
) e non (Q;
). (Xn f0g;
) non e un sottogruppo di (Qn f0g;
), infatti per esempio 2=32Xma l'inverso moltiplicativo e 3=2 che non appartiene aX, infatti non esistono nessun interoze nessun naturalektali chez=3k = 3=2. Infatti l'equazionez=3k = 3=2 implica chez= 3k +1 =2 e dato che 2 non divide 3 abbiamo cheznon puo essere un intero. (c)Veri chiamo che (X;+;
) e un sottoanello di (Q;+;
). Abbiamo gia veri cato nel primo punto che presix 1; x 22 X abbiamo chex 1 x 22 X, dunque dobbiamo solo veri care chex 1
x 22 X. Questo e molto semplice dato che sex 1= z 1= 3k 1 ,x 2= z 2= 3k 2 , allorax 1x 2= ( z 1z 2) =3k 1+ k 2 2Xdato chez 1z 2e ancora intero. Per il criterio di caratterizzazione dei sottoanelli, (X;+;
) e un sottoanello di (Q;+;
) ma non e un ideale, infatti prendendo z= 3=22Qex= 12Xabbiamo chexz= 3=2= 2X(lo abbiamo visto nel punto precedente). (d)La formula dice che, per ognix; y; z2Q, il prodotto di numeri razionali e un'operazione associativa (che e vero) e che sex2Xallora anchexz2X. Quest'ultima parte non e vera, come abbiamo visto prima prendendo per esempiox= 1; z= 2=3. Quindi la formula e falsa nell'interpretazione data (essendo congiunzione di due formule di cui una falsa) e quindi non e logicamente valida. Non e nemmeno logicamente contradditoria, basta considerare l'interpretazione avente come dominio un qualunque insiemeYe in cuiEinterpreta la relazione binaria universale edAla relazione unaria (sottoinsieme) coincidente conY, cioeA(y) signi ca \y2Y". In questo caso entrambe le sottoformuleE(f(f(x; y); z); f(x; f(y; z))) eA(x))A(f(x; z)) risultano vere e la loro congiunzione e pertanto vera, cos come la sua chiusura univerale.