Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30' Esame di Logica e Algebra Politecnico di Milano { Ingegneria Informatica { 25 Gennaio 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)Si costruisca una formulaF(A; B; C) nella logica proposizionale sulle lettere enunciativeA; B; Cche abbiasola- mentei tre modelli 1;  2;  3con  1( A) = 1( B) =(C) = 1, 2( A) = 1;  2( B) = 2( C) = 0, 3( A) = 0;  3( B) = 3( C) = 1. (b)Mostrare sia per via semantica che usando la risoluzione cheF(A; B; C)(B_ :C). Soluzioni: (a)Usando la forma normale disgiuntiva una formula che ha i modelli descritti nell'esercizio e (A^B^C)_(A^ :B^ :C)_(:A^B^C). (b)Per via semantica. Dire cheF(A; B; C)(B_ :C) equivale a dire che tutti i modelli diF(A; B; C) sono anche modelli di (B_ :C) ora i modelli diF(A; B; C) sono 1;  2;  3con  1( A) = 1( B) =(C) = 1, 2( A) = 1;  2( B) = 2( C) = 0, 3( A) = 0;  3( B) = 3( C) = 1, ed e facile vedere che sono anche modelli di (B_ :C). Mediante la risoluzione, dobbiamo mostrare che f(A^B^C)_(A^ :B^ :C)_(:A^B^C);:B^Cgc `R ora l'insieme di clausole contiene sicuramentef:Bg;fCg;fB;:Cg, ed e facile vedere chefBge una risolvente tra le ultime due clausole e quindi la clausola vuota si ottiene come risolvente dif:Bg;efBg. 2.Si consideri la relazione binaria Rsull'insiemeX=fa; b; c; d; egde nita dalla seguente matrice di incidenza 0 B B B B @0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 11 C C C C A (a)Re una funzione daXinX? In caso, disegnare il grafo d'adiacenza della relazioneK er(R) e calcolare l'insieme quozienteX=K er(R). (b)Esiste la chiusura d'ordine diR? In caso aermativo calcolarla e disegnare il suo diagramma di Hasse. Calcolare (se esistono):S upfa; cged eventuali minimali e massimali. (c)Si consideri la seguente formula della logica del primo ordine: 8x(9yA(y; x)) 8z(A(x; z))A(z; z))) Si stabilisca, motivando bene la risposta, se e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominio l'insiemeXe in cui la lettera predicativaAe interpretata dalla relazioneR2 suX. La formula e logicamente valida o logicamente contradditoria? (d)Usando la risoluzione del primo ordine veri care se la formula 8x(9y(A(y; x)) 8z(A(x; z))A(z; z)) )^ :9yA(x; y)) e logicamente contradditoria. Soluzioni:(a)Poiche la matrice d'adiacenza ha un solo 1 per ogni riga, la relazioneRe una funzione, dunque K er(R) =f(b; c);(c; b);(d; e);(e; d)g [I X Il suo grafo d'adiacenza e:bcea d quindi l'insieme quoziente X=K er(R) =ffb; cg;fag;fe; dgg. (b)Notiamo cheRe antisimmetrica, quindi potrebbe esistere la chiusura d'ordine. Per veri carlo, chiudiamo rif- lessivamente e transitivamenteRottenendoH=R[I X[ f (c; e);(a; d);(b; e);(a; e)gche e ancora antisimmetrica, quindi essendoHanche ri essiva e transitiva, otteniamo cheHe la chiusura d'ordine diR. Il suo diagramma di Hasse e il seguente:e d bc a L'insieme dei maggioranti di fa; cge costituito dall'insiemefd; egil cui minimo (rispetto adH) ed, quindi S upfa; cg=d. I minimali sonofa; cg, mentre l'isieme di massimali efegedee anche massimo. (c)La formula interpreta la seguente proprieta della relazioneR2 : per ognix2X, se esiste un elementoy2Xtale che (y; x), allora per ogni altroz2Xcon (x; z)2R2 si ha cheze in relazione con se stesso. La relazioneR2 ha il seguente grafo d'adiacenza:a deb c Indichiamo con Bla sottoformula9yA(y; x)) 8z(A(x; z))A(z; z)). Gli unici elementixche hanno una freccia entrante sonox=dex=equindi l'antecedente della formulaBe soddisfatto sex=doppurex=e. Inoltre se (d; z)2R2 , allora necessariamentez=ee, poiche (e; e)2R2 , abbiamo che (z; z)2R2 . Analogamente se (e; z)2R2 , allora necessariamentez=ee, poiche (e; e)2R2 , abbiamo che (z; z)2R2 . Quindi la formulaB e soddisfatta sex=doppurex=e. Sex6 =dex6 =eallora l'antecedente diBe non soddisfatto e pertanto l'intera formula Be soddisfatta. PertantoBe soddisfatta per ogni assegnamento di valori adxe quindi, essendo la formula assegnata la chiusura universale diBsegue che la formula assegnata e vera. Ovviamente tale formula non e soddisfacibile ma non vera dato che e chiusa e non e neppure logicamente contradditoria dato che nella precedente interpretazione la formuala e vera. Rimane da veri care se e logicamente valida. Per fare questo basta prendere l'interpretazione che ha per dominio l'insiemeY=fa; bge doveAe interpretata dalla relazione T=f(a; b);(b; a)g, allora l'antecedente della precedente formula e sempre vera, ma il conseguente no, infatti prendendox=a, abbiamo cheze necessariamente uguale ab, ma (b; b)= 2T, quindi il conseguente e falso, rendendo falsa la formula. (d)Per veri care se la precedente formula e logicamente contradditoria dobbiamo vedere se dalle clausole che siottengono dalla formula data si puo ottenere la clausola vuota. La forma normale prenessa della precedente formula e:8x9y8z8w((A(y; x))(A(x; z))A(z; z)) )^ :A(x; w)) da cui la sua forma di Skolem e 8x8z8w((A(f(x); x))(A(x; z))A(z; z)) )^ :A(x; w)) dovef(x) e una nuova lettera funzionale. Quindi portando la matrice della formula in forma normale congiuntiva otteniamo:8x8z8w( (:A(f(x); x)_ :A(x; z)_A(z; z) )^ :A(x; w)) e qundi otteniamo due sole clausolef:A(f(x); x);:A(x; z); A(z; z)g;f:A(x; w)g, ora una qualunque risolvente ottenuta usando queste due clausole e le eventuali ottenute conterranno sempre un letterale positivo della forma A(;) e uno negativo del tipo:A(;), oppure solamente un letterale negativo del tipo:A(;). Quindi non si potra mai ottenere una clausola contenente solo letterali della formaA(;). Quindi non si puo ottenere la clausola vuota, da cui deduciamo che la formula non e logicamente contradditoria. 3.Si consideri l'insieme Adelle matrici quadrate di ordine 2 ad elementi inZ 7strutturato ad anello rispetto alle usuali operazioni di somma e prodotto di matrici. Si consideri il sottoinsiemeBdiAcos de nito B= a[0] 7 b a :a; b2Z 7 (a)Si mostri cheBe un anello commutativo; (b)Si determinino i divisori dello zero diB. (c)Si consideri ora la seguente formula della logica del primo ordine 8x(9y(:E(x; a)^ :E(y; a)^E(p(x; y); a))) 8z:E(p(x; z); b) ) e si dica se e vera, falsa, soddisfacibile ma non vera nell'interpretazione che ha come dominioBe nella quale la lettera predicativaEsia da interpretare come l'uguaglianza, la lettera funzionalepcome il prodotto tra matrici, la costanteasia la matrice nulla ebla matrice identica. La formula e logicamente valida? Soluzioni: (a)Dato che il testo dice gia cheAe un anello eBe un suo sottoinsieme, ci basta applicare il criterio per i sottoanelli. SianoM 1; M 22 Bcon: M1= a[0] b a ; M2= c[0] d c allora abbiamoM1 M 2= a[0] b a  c[0] d c = ac[0] bd ac che e ancora una matrice diBdato che gli elementi sulla diagonale principale sono uguali fra loro e tutti gli elementi sono sempre classi di resto modulo 7. DunqueBe un anello e per veri care che e commutativo basta osservare quanto segue: a[0] b a  c[0] d c = ac[0] cb+da ac = c[0] d c  a[0] b a (b)Per cercare i divisori dello zero dobbiamo impostare l'equazione:a[0] b a  x[0] y x = [0] [0] [0] [0] dove almeno uno trabeadeve essere diverso da [0]. La precedente uguaglianza implica che deve valerexa= [0] ebx+ay= [0]. Ora, sea6 = [0], dato cheZ 7e un campo, dalla prima equazione otteniamo che necessariamente x= [0] e quindi la seconda equazione si riduce aay= [0]. Deduciamo allora chey= [0], quindi in questo caso non abbiamo divisori dello zero. Supponiamo chea= [0] eb6 = [0], in questo caso le precedenti equazioni si riducono abx= [0] che ha soluzioni perx= [0]. Si deduce che in questo caso i divisori dello zero sono della forma [0] [0] b[0] ; b6 = [0] (c)La formula si traduce nel seguente modo: se una matricex2Bnon e la matrice nulla ed esiste una matricey2B sempre non-nulla tale che il prodottoxye la matrice nulla, allora per tutti gliz,xznon e la matrice identita. In parole povere la formula mi dice che sexe un divisore dello zero allora non e invertibile, che e vero in ogni anello. Oppure, dato che l'anello in questione e nito, e noto che i divisori dello zero di un anello nito sono tutti e soli gli elementi non invertibili. Quindi la formula e vera ed essendo chiusa non puo essere soddisfacibile ma non vera. La formula non e logicamente valida, infatti basta prendere come interpretazione quella avente come dominio l'insieme dei numeri interi ed in cui la relazione che interpreta la lettera predicativaEe la relazione, l'operazione che interpreta la lettera funzionalepe la moltiplicazione e in cui la costanteae interpretata dal numero 0 e la costantebdal numero 1. Allora la traduzione della formula in questa interpretazione e la seguente: `per ogni interox, se esiste un interoytale chex