Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { Appello telematico Luglio 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.(a)Scrivere una formulaf(A; B; C) che ammetta la tavola di verita qui a anco. (b)Argomentando bene la risposta, dire se:A^C` Lf (A; B; C) usando la risoluzione. (c)Scrivere una formulag(A; B; C) non equivalente af(A; B; C) che non sia una tautologia tale cheff(A; B; C);:g(A; B; C)gsia un insieme di formule insoddis- facibile.ABCf (A; B; C)0000 0011 0100 0111 1000 1011 1100 1110 Soluzione: a)Dato che il numero di \1" presenti nella tabella e minore del numero di \0", possiamo costruire una formulaf(A,B,C) in forma normale disgiuntiva:f(A; B; C)(:A^ :B^C)_(:A^B^C)_(A^ :B^C). b)Dal teorema di correttezza e completezza della teoria L, abbiamo che:A^C` Lf (A; B; C) se e solo se:A^ Cf(A; B; C) e questo e equivalente a dire che l'insieme di formulef:A^C;:f(A; B; C)ge insoddisfacibile. Dal teorema di correttezza e completezza per refutazione abbiamo chef:A^C;:f(A; B; C)ge insoddisfacibile se e solo se dall'insieme di clausolef:A^C;:f(A; B; C)gc che si ottengono da questo insieme di formule si ottiene la clausola vuota per risoluzione. Calcoliamof:A^C;:f(A; B; C)gc , da:f(A; B; C) ricaviamo le clausole fA; B;:Cg;fA;:B;:Cg;f:A; B;:Cg, e dalla prima formula ricaviamo le clausolef:Ag;fCg. Un possibile modo per ottenere la clausola vuota e dato dalla seguente derivazione per risoluzione:f A; B;:Cgf: Agf Cgf A;:B;:Cgf A;:Bgf: Bgf B;:Cgf Bg c)Dobbiamo cercare una formula g(A; B; C) tale che per ogni modellovdif(A; B; C) non sia modello di:g(A; B; C), cioe sia un modello dig(A; B; C). Quindig(A; B; C) deve avere gli stessi modelli dif(A; B; C), corrispondenti alle righe in cuif(A; B; C) e vera. Dato cheg(A; B; C) non deve essere equivalente af(A; B; C) basta che la tavola di verita digdierisca da quella difper esempio sulla prima riga, cioe facciamo in modo che nell'interpretazione w(A) =w(B) =w(C) = 0 la f.b.f.g(A; B; C) valga \1". Quindi abbiamog(A; B; C)f(A; B; C)_(:A^ :B^ :C). Notiamo cheg(A; B; C) non e una tautologia. 2.In Z 6sia Dl'insieme dei divisori dello zero. Si consideri la relazioneRZ 6 Z 6cosi denita: aRbse e solo se a; b2D[ f[0] 6g . (a)Disegnare il grafo d'adiacenza diR. Di quali proprieta godeR? (b)Esiste la chiusura d'ordine diR? (c)Si disegni il grafo d'adiacenza della chiusura d'equivalenzaTdiRe si costruisca l'insieme quozienteZ 6=T . (d)Si consideri la funzionef:Z 6! Z 6co denita: f([a] 6) =( [0]6se M :C:D(a;6)6 = 1 [a] 6altrimenti e si dica se e un morsmo del monoide (Z 6;
) (rispetto al prodotto di classi). (e)Si dica seK er f=T. (f )Si consideri la seguente f.b.f della logica del primo ordine: F=8x9y(A(x; y)) 9z((A(x; z)^ :E(x; z)))A(z; x)) ) e si dica se e vera, falsa, soddisfacibile ma non vera nelle seguenti interpretazioni:ˆdominioZ 6, A(x; y) siaReE(x; z) l'uguaglianza; ˆdominioZ 6, A(x; y) siaTeE(x; z) l'uguaglianza; La precedente formula e logicamente valida? Soluzione:a)I divisori dello zero diZ 6sono D=f[2] 6; [3] 6; [4] 6g , quindi il grafo di adiacenza diRe il seguente:[2] 6[4] 6[3] 6[0] 6[1] 6[5] 6Le proprieta di cui gode Rsono la simmetria (tutti gli archi hanno la doppia freccia) e la transitivita (tutti gli elementi da cui parte almeno un arco sono collegati fra di loro con archi bidirezionali). b)Non puo esistere la chiusura d'ordine diRperche qualunque relazione che contieneRcontiene anche le coppie ([2]6; [4] 6) e ([4] 6; [2] 6) quindi non puo essere antisimmetrica. c)La chiusura d'equivalenzaTdiRsi ottiene chiudendo ri essivamente, quindiT=R[ f([1] 6; [1] 6) ;([5] 6; [5] 6) g. Il suo grafo d'adiacenza e il seguente:[2] 6[4] 6[3] 6[0] 6[1] 6[5] 6L'insieme quoziente Z 6=T =ff[0] 2; [2] 6; [3] 6; [4] 6g ;f[1] 6g ;f[5] 6gg d)Ricordiamo la seguente tavola moltiplicativa di (Z 6;
):
[0] 6[1] 6[2] 6[3] 6[4] 6[5] 6[0] 6[0] 6[0] 6[0] 6[0] 6[0] 6[0] 6[1] 6[0] 6[1] 6[2] 6[3] 6[4] 6[5] 6[2] 6[0] 6[2] 6[4] 6[0] 6[2] 6[4] 6[3] 6[0] 6[3] 6[0] 6[3] 6[0] 6[3] 6[4] 6[0] 6[4] 6[2] 6[0] 6[4] 6[2] 6[5] 6[0] 6[5] 6[4] 6[3] 6[2] 6[1] 6Dalla tavola di composizione della moltiplicazione fra classi in Z 6si puo notare che: {sex; y2 f[1] 6; [5] 6g alloraf(x) =x; f(y) =yex
y2 f[1] 6; [5] 6g ; quindif(x
y) =x
ye cosf(x
y) =f(x)
f(y); { sex; y2 f[0] 6; [2] 6; [3] 6; [4] 6g , abbiamo chex
y2 f[0] 6; [2] 6; [3] 6; [4] 6g quindif(x
y) = [0] 6= f(x) =f(y), quindi anche in questo casof(x
y) =f(x)
f(y); {sex2 f[1] 6; [5] 6g ey2 f[0] 6; [2] 6; [3] 6; [4] 6g alloraf(x) =x; f(y) = [0] 6e quindi f(x)
f(y) = [0] 6; inoltre x
y2 f[0] 6; [2] 6; [3] 6; [4] 6g e quindif(x
y) = [0] 2da cui segue che f(x
y) =f(x)
f(y). Pertantofe un morsmo ed in particolare si puo osservare che e un morsmo di monoidi poichef([1] 6) = [1] 6. e)Notiamo che (a; b)2K er(f) se e solo sea; b2 f[0] 6; [2] 6; [3] 6; [4] 6g , oppurea=bcona2 f[1] 6; [5] 6g , quindi K er(f) e esattamente la chiusura ri essiva diR, cioeT. f )La formula e chiusa quindi in qualunque interpretazione essa e vera o falsa mentre non puo essere soddisfacibilema non vera. {Nella prima interpretazione la formula e interpretata nel seguente modo: per ognixesiste unytale che se (x; y)2R, allora esiste unoztale che se (x; z)2Rconx6 =z, allora (z; x)2R. La formula e vera. Infatti sex2 f[1] 6; [5] 6g allora l'antecedente non e mai soddisfatto dato che non esiste nessunycon (x; y)2R. Se invecex2 f[0] 6; [2] 6; [3] 6; [4] 6g , basta prendere un qualunquez6 =xconz2 f[0] 6; [2] 6; [3] 6; [4] 6g per soddisfare il conseguente della formulaFe quindi soddisfare la formula stessa. {Nella seconda interpretazione la formula e ancora vera: le motivazioni sono le stesse del caso precedente se x2 f[0] 6; [2] 6; [3] 6; [4] 6g mentre nel caso in cuix2 f[1] 6; [5] 6g si ha che l'antecedenteA(x; y) e ora soddisfatto (basta prenderey=x) e pero non esiste nessunoz6 =xtale che (x; z)2T, pertanto la sottoformula A(x; z)^ :E(x; z) non e soddisfatta e quindi il conseguente dell'intera formulaFrisulta soddisfatto. La formulaFe logicamente valida, infatti per ogni relazioneRsuXche interpretaA(x; y), per ognix2X, se (x; x)= 2R, allora prendendoy=x, l'antecedente diFe non soddisfatto, quindiFe soddisfatta, invece se (x; x)2Rprendendoy=x, l'antecedente diFe soddisfatto, e prendendoz=x, la formulaA(x; z)^ :E(x; z) e non soddisfatta, rendendo il consequente diFsoddisfatto. Quindi in entrambi i casi l'intera formulaFe soddisfatta e pertanto essa risulta essere vera. E' possibile dimostrare che la formula e logicamente valida anche usando la risoluzione per la logica del primo ordine. Innanzitutto neghiamo la formula data e portiamola in forma normale prenessa: :F  :8x9y(A(x; y)) 9z((A(x; z)^ :E(x; z)))A(z; x)) )  :8x9y9z(A(x; y))((A(x; z)^ :E(x; z)))A(z; x)) )  9x8y8z:(A(x; y))((A(x; z)^ :E(x; z)))A(z; x)) ) Scriviamo, ora, la forma di Skolem della formula ottenuta eliminando il primo quanticatore esistenziale dal presso e sostituendo con la costantecogni occorrenza della variabilexda esso quanticata: 8y8z:(A(c; y))((A(c; z)^ :E(c; z)))A(z; c)) ) Trasformiamo in forma a clausole la matrice della precedente formula::(:A(c; y)_(:(A(c; z)^ :E(c; z))_A(z; c)) ) A(c; y)^A(c; z)^ :E(c; z)^ :A(z; c) Dopo la separazione delle variabili, si ottengono cos le clausole di inputfA(c; y)g;fA(c; z)g;f:E(c; z 1) g;f:A(z 2; c )g. Applicando la sostituzione=fc=z 2; c=y galla prima e all'ultima clausola si ottengono le clausolefA(c; c)g;f:A(c; c)g, la cui risolvente e proprio la clausola vuota. 3.Sia A=f(a; b) :a; b2R; b6 = 0ge sia?l'operazione interna suAdenita da: (a; b)?(c; d) = (a+bc; bd) (a)Si mostri che (A; ?) e un gruppo; (b) E commutativo? (c)Si consideri la seguente formula della logica del primo ordine: 8x8y8z(E(p(x; y); p(x; z)))E(y; z) ) e un'interpretazione avente come dominio l'insiemeAe in cui la lettera funzionaleEe interpretata dalla relazione di uguaglianza e la lettera funzionalepdall'operazione interna?vista nei punti precedenti. Dire se la formula e vera, falsa, soddisfacibile ma non vera in questa interpretazione Soluzione:a)L'esercizio gia aerma che l'operazione?e interna, quindi verichiamo cheAsia un semigruppo mostrando l'associativita:((a; b)?(c; d))?(e; f) = (a+bc; bd)?(e; f) = (a+bc+bde; bdf) (a; b)?((c; d)?(e; f)) = (a; b)?(c+de; df) = (a+bc+bde; bdf) che sono uguali. Per mostrare che e un gruppo basta provare che ha identita e inverso destro (teorema sui gruppi presente sulle dispense). Per l'identita imponiamo l'equazione (a; b)?(c; d) = (a; b) cioe (a+bc; bd) = (a; b), quindi d= 1; c= 0. Quindi si verica poi facilmente che (a; b)?(0;1) = (a; b) per ognia; b2R. Per l'inverso imponiamo l'equazione (a; b)?(x; y) = (0;1) cioe (a+bx; by) = (0;1) da cuiy= 1=b,x=a=b(ricordarsi cheb6 = 0). Quindi si verica che (a; b)?(a=b;1=b) = (0;1). b)Non e commutativo infatti (1;2)?(3;1) = (7;2), mentre (3;1)?(1;2) = (4;2) che sono diversi. c)La formula e chiusa, quindi e vera o falsa. Nell'interpretazione data si traduce in: per ognix; y; z2Asex?y=x?z, alloray=zche e vera in tutti i gruppi. Infatti basta moltiplicare l'equazionex ? y=x ? zperx 1 a sinistra per ottenere chey=z(legge di cancellazione a sinistra per i gruppi).