Computer Engineering - Logica e Algebra

Full exam

Esame di Logica e Algebra - 9 luglio 2021 Durata della prova: 1h 30' 1.(9 punti)a) 4 punti; b) 5 punti Si consideri la formulaf(A; B; C) che assume il valore di verita 1 solo per le interpretazioniv 1ove v 1( A) =v 1( B) = 1 ev 1( C) = 0 ev 2ove v 2( A) = 0 ev 2( B) =v 2( C) = 1. (a)Dire se la formula:(B) :f(A; B; C)))(C) :A) e un teorema della teoria L; (b)Vericare utilizzando la risoluzione che l'insiemef:(C) :A); f(A; B; C)ge insoddisfacibile. Soluzione:(a)Per il teorema di correttezza e completezza dobbiamo vericare se:(B) :f(A; B; C)))(C) :A). Invece di costruire la tavola di verita, supponiamo per assurdo che:(B) :f(A; B; C)))(C) :A) non sia una tautologia. Cio vuole dire che:(B) :f(A; B; C) e vera e (C) :A) e falsa. Dal fatto cheB) :f(A; B; C) deve essere falsa ne deduciamo cheBe vera edf(A; B; C) e anch'essa vera, mentre dal fatto che (C) :A) e falsa ne deduciamo cheA; Csono vere. Ma perA; B; Cvere la formulaf(A; B; C) e falsa, che contraddice il fatto che f(A; B; C) doveva essere vera. Quindi la formula:(B) :f(A; B; C)))(C) :A) e una tautologia e pertanto e un teorema della teoriaL. (b)Sia =f:(C) :A); f(A; B; C)g. Usando la forma normale disgiuntiva otteniamo chef(A; B; C)(A^B^ :C)_(:A^B^C). Dal teorema di correttezza e completezza per refutazione per dimostrare che l'insieme e insoddisfacibile occorre vericare che c `R . Si ricava che c =ffAg;fBg;fCg;fA; Cg;f:A;:Cgg. DafAge f:A;:Cgotteniamof:Cgche confCgpermette di ricavare la clausola vuota. 2.(11 punti) a) 2 punti; b) 3 punti; c) 3 punti; d) 3 punti. SiaRXX, conX=fa; b; c; d; e; fgla relazione binaria rappresentata dal seguente grafo:a bc de f (a)Si provi che non esiste nessuna relazione d'ordine su XcontenenteR. Si dica, motivando la risposta, seRe transitiva. (b)Si trovi la relazione d'equivalenzagenerata daR. Si stabilisca secoincide con la chiusura ri essiva e simmetrica TdiR. (c)Si consideri la seguente formula della logica del primo ordine: 8x8y8z( (A(x; y)^A(y; z))A(x; z))^(A(x; y)) 9zA(y; z)) ) E si dica se e vera, falsa, soddisfacibile ma non vera, nel caso in cuiAsia interpretata dalla relazioneR. Cosa accade seAe la relazioneT? E se e? (d)Si consideri la seguente formula della logica del primo ordine: 8x(S(a; p(x; f(x))))S(a; p(f(x); x)) ) Si stabilisca se e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominio l'insiemeDdi tutte le relazioni binarie sull'insiemeXe in cui la lettera predicativape il prodotto di relazioni suX,fe l'inversa (f(b) e la relazione inversa dib),ae la relazione identica, edSe la lettera predicativa che indica la relazione di essere sottoinsieme. Soluzione: (a)Dato cheRcontiene le coppie (e; f);(f ; e), qualunque relazioneSche contengaRconterra queste coppie, quindi Snon potra mai essere antisimmetrica. Segue che non puo esistere una relazione d'ordine che contengaR.Rnon e transitiva poiche (e; f);(f ; e)2Rma (e; e)= 2R. (b)Ricordiamo che per chiudere transitivamente basta completare le clique del grafo d'adiacenza diR, quindi otteni- amo che il grafo d'adiacenza die:a bc de f La relazione Tche e la chiusura ri essiva e simmetrica diRha il seguente grafo d'adiacenza:a bc de f che e palesemente diverso da quello di . (c)La formula e chiusa quindi puo essere solo o vera o falsa, ma non solo soddiscibile (ma non vera). La formulaA(x; y)^A(y; z))A(x; z) esprime la transitivita quindi, nel caso in cuiAinterpretiRoppureT, l'intera formula e falsa dato che queste due relazioni non sono transitive. Nel caso in cuiAinterpretidobbiamo anche valutare la verita della sottoformulaA(x; y)) 9zA(y; z) che aerma: se (x; y)2allora esiste unoz2Xtale che (y; z)2. Dato chee ri essiva, scegliendoz=yabbiamo che (y; y)2per tutti gliy2Xe quindi il conseguente e sempre soddisfatto. Inoltree anche transitiva e pertanto l'intera formula e vera essendo chiusura universale della congiunzione di due formule vere. (d)La formula traduce la seguente proprieta: indicata con Ila relazione identica, seIR
R 1 alloraIR 1
R. La formula e falsa, basta considerare la relazioneR=f(1;2);(2;2)gsuY=f1;2g, alloraIR
R 1 = f(1;1);(2;2);(1;2);(2;1)g, maR 1
R=f(2;2)ge quindi la relazione identicaInon e contenuta in quest'ultimo prodotto. Pertanto l'antecedente e soddisfatto da questo assegnamento mentre il conseguente non lo e , dunque la formula e falsa. 3.(11 punti) a) 4 punti; b) 3 punti; c) 4 punti. Si consideri l'insiemeRR, doveRe l'insieme dei numeri reali, strutturato a gruppoGrispetto all'operazione (a; b) + (c; d) = (a+c; b+d) (a)Si mostri che l'insiemeH=f(x; y)2RR:x+ 2y= 0ge un sottogruppo normale diG. (b)Si consideri ora la seguente formula della logica del primo ordine: 8x8y(E(f(x; y); f(y; x)))E(g(f(x; y)); f(g(x); g(y)) ) ) e si dica se e vera, falsa soddisfacibile ma non vera nell'interpretazione in cui il dominio eG, la lettera predicativa Ee da interpretarsi come l'uguaglianza, le lettere funzionalifegrispettivamente come la somma inGe l'esistenza dell'inverso rispetto all'operazione inG. Si dica se la formula e logicamente valida o logicamente contraddittoria. (c)Si consideri ora la formula: 9x9y(8h(E(h; y))E(g(x); g(y)))) 8t(E(t; y))E(g(x); g(y))) ) e si mostri utilizzando la teoria della risoluzione della logica del primo ordine che e logicamente valida. Soluzione: (a)Notiamo che l'elemento neutro diGe (0;0), mentre l'inverso di (c; d) e (c;d). Siano (a; b);(c; d)2H, allora a+ 2b= 0,c+ 2d= 0. Consideriamo (a; b) + (c;d) = (ac; bd) allora, poichea+ 2b(c+ 2d) = 0, otteniamo (ac) + 2(bd) = 0, quindi, per il criterio di caratterizzazione dei sottogruppi, (ac; bd)2H. Segue cheH e un sottogruppo. Poiche (a; b) + (c; d) = (c; d) + (a; b), abbiamo cheGe un gruppo commutativo, quindiHe un sottogruppo normale. (b)La formula esprime il seguente fatto inG: seGe commutativo (cioex+y=y+x), allora l'inverso della somma dixeye la somma degli inversi dixedy:(x+y) = (x) + (y). Segue che in questa interpretazione la formula e vera e quindi non e logicamente contraddittoria. Essa pero non e nemmeno logicamente valida dato che se prendiamo un qualunque gruppo (G; ?) non commutativo allora non e vero in generale che (x ? y) 1 =x 1 ? y 1 . (c)Dobbiamo vericare che:9x9y(8h(E(h; y))E(g(x); g(y)))) 8t(E(t; y))E(g(x); g(y))) ) e insoddisfacibile. Questa formula e equivalente a: 8x8y(8h(:E(h; y)_E(g(x); g(y)))^ 9t(E(t; y)^ :E(g(x); g(y))) ) Quindi la sua forma normale prenessa e:8x8y(9t8h( (:E(h; y)_E(g(x); g(y)))^(E(t; y)^ :E(g(x); g(y))) ) ) da cui ricaviamo la sua forma di Skolem, dovewe una nuova lettera funzionale: 8x8y8h( (:E(h; y)_E(g(x); g(y)))^(E(w(x; y); y)^ :E(g(x); g(y))) ) Quindi l'insieme di clausole e dato daf:E(h; y); E(g(x); g(y))g;fE(w(x0 ; y0 ); y0 )g;f:E(g(x00 ); g(y00 ))g dove abbiamo dierenziato tutte le variabili tra le clausole. Una risolvente tra la prima e la seconda clausola con la sostituzionew(x0 ; y0 )=h; y0 =ypermette di ottenere la clausolafE(g(x); g(y0 ))gda cui con la terza clausola mediante la sostituzionex=x00 ; y0 =y00 permette di ottenere la clausola vuota.