Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 6 settembre 2022 Docente e ultimo voto laboratorio: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: a) 2; b) 2; c) 2; d) 3; e) 5)Si consideri la relazione binariaRsuA={a, b, c, d, e, f}definita nel seguente modo: R={(a, b),(a, c),(b, d),(c, f),(d, d),(e, e),(f , e)} (a)Disegnare il grafo d’adiacenza diRe determinarne la matrice d’adiacenza. (b)Stabilire quali propriet`a soddisfaRtra serialit`a, riflessivit`a, simmetria, antisimmetria e transitivit`a. (c)Determinare la chiusura di equivalenzaTdiRe descrivere il quozienteA/T. (d)Stabilire se esiste la chiusura d’ordineSdiRe, in caso affermativo, determinarla, disegnarne il diagramma di Hasse e individuare eventuali elementi minimali, massimali, minimi e massimi diArispetto adS. (e)Usando la risoluzione del primo ordine, dimostare che se una relazione `e riflessiva allora `e anche seriale. Soluzione (a)Il grafo di adiacenza diR`e il seguente:ab cd e f La matrice d’adiacenza di R`e la seguente: M=       0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0        (b)La relazioneR`e seriale dal momento che da ogni vertice del grafo di adiacenza parte almeno un arco ed `e antisimmetrica poich´e non ci sono archi con doppia freccia (esclusi gli autoanelli) e quindi, per lo stesso motivo,R non pu`o essere simmetrica.Rnon `e riflessiva poich´e non ci sono autoanelli su ogni arco e non `e transitiva perch´e, ad esempio, (a, b)∈R, (b, d)∈Rma (a, d)/ ∈R. (c)La chiusura d’equivalenzaTdiR`e la chiusura riflessiva, simmetrica e transitiva diRe pertanto coincide con la relazione universale suA, cio`eT=A×A. L’insieme quoziente `e costituito da un’unica classe di equivalenza che contiene tutti gli elementi di A:A/T={A}. (d)La relazioneR`e antisimmetrica e pertanto pu`o esistere la sua chiusura d’ordine. Chiudendo riflessivamente e transitivamente la relazioneRsi ottiene il seguente grafo di adiacenza:ab cd e f che `e il grafo di adicenza di una relazione antisimmetrica poich´e nessun arco ha la doppia freccia. Segue che la chiusura d’ordineSdiResiste ed ha come grafo d’adiacenza quello sopra riportato e a cui corrisponde il seguente diagramma di Hasse:abcde f Si evince che l’insieme dei massimali di Arispetto adS`e{d, e}e che quindi non esiste il massimo. L’elementoa `e minimale e minimo. (e)Una formula del primo ordine che traduce la frase ”se una relazione `e riflessiva allora `e anche seriale” `e la seguente: ∀xB(x, x) =⇒ ∀x∃yB(x, y), doveB`e una lettera predicativa binaria che interpreta una generica relazione. Occorre dimostrare che la formula `e logicamente valida quindi `e necessario negare la formula precedente, trasformarla in forma a clausole e vederese `e possibile ottenere la clausola vuota. Neghiamo la formula: ¬(∀xB(x, x) =⇒ ∀x∃yB(x, y)) e portiamola in forma normale prenessa: ¬(∀xB(x, x) =⇒ ∀x∃yB(x, y))≡ ¬∃x∀z∃y(B(x, x) =⇒B(z, y))≡ ∀x∃z∀y¬(B(x, x) =⇒B(z, y)). La forma di Skolem della precedente FNP `e la seguente: ∀x∀y¬(B(x, x) =⇒B(f(x), y)), dovef`e una lettera funzionale di arit`a 1. Scriviamo infine in forma a clausole la matrice¬(B(x, x) =⇒B(f(x), y)) della forma di Skolem: ¬(B(x, x) =⇒B(f(x), y))≡ ¬(¬B(x, x)∨B(f(x), y))≡B(x, x)∧ ¬B(f(x), y) da cui si ricavano le due clausoleC 1= {B(x, x)}eC 2= {¬B(f(x 1) , y)}(abbiamo effettuato la separazione delle variabili sostituendo conx 1la variabile xnella seconda clausola). Considerata la sostituzioneσ={f(x 1) /x, f(x 1) /y} si ha cheC 1σ ={B(f(x 1) , f(x 1)) }e cheC 2σ ={¬B(f(x 1) , f(x 1)) }e la risolvente di queste due clausole `e proprio la clausola vuota. Segue che∀xB(x, x) =⇒ ∀x∃yB(x, y) `e logicamente valida. 2.(Punteggio: a) 2; b) 4) Si consideri la seguente tavola di verit`a: A B CF 0 0 00 0 0 10 0 1 00 0 1 11 1 0 00 1 0 11 1 1 00 1 1 11 (a)Si scriva una formulaFavente come tavola di verit`a quella assegnata. (b)Dire se¬A⇒B|=Fe seA∧C|=¬F. Soluzione (a)Scriviamo la forma normale disgiuntiva diF: F ≡(¬A∧B∧C)∨(A∧ ¬B∧C)∨(A∧B∧C) (b)La deduzione¬A⇒B|=Fnon `e verificata in quanto l’interpretazionevtale chev(A) = 1 ev(B) =v(C) = 0 `e un modello per¬A⇒Bma non perF. Neppure la deduzioneA∧C|=¬F`e verificata poich´e l’interpretazione vtale chev(A) =v(B) =v(C) = 1 `e un modello perA∧Cma non per¬F. 3.(Punteggio: a) 3; b) 4; c) 4 ) Sia (A,+,·) un anello unitario. Si consideri suAl’operazione binaria∗definita nel seguente modo: ∀a, b∈A a∗b=a+b+a·b. (a)Si provi che (A,∗) `e un monoide. (b)Si consideri l’applicazionef: (A,∗)→(A,·) cos`ı definita: ∀a∈A f(a) =a+ 1 dove 1 `e l’unit`a di (A,+,·). Provare chef`e un isomorfismo tra il monoide (A,∗) e il monoide (A,·). (c)Si consideri la seguente formula della logica del primo ordine: ∀x∀y∀z E(p(x, s(y, z)), s(p(x, y), p(x, z)) ) Si stabilisca se `e vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominioAe in cuiE(x, y) interpreta la relazione di uguaglianza,s(x, y) l’operazione di addizione + dell’anello (A,+,·) ep(x, y) l’operazione ∗definita precedentemente suA. La formula `e logicamente valida oppure logicamente contraddittoria? Soluzione (a)Dimostriamo che∗soddisfa la propriet`a associativa. Sianoa, b, c∈A, risulta: (a∗b)∗c= (a+b+a·b)∗c=a+b+a·b+c+ (a+b+a·b)·c=a+b+a·b+c+a·c+b·c+a·b·c a∗(b∗c) =a∗(b+c+b·c) =a+b+c+b·c+a·(b+c+b·c) =a+b+c+b·c+a·b+a·c+a·b·c Segue che (a∗b)∗c=a∗(b∗c) e pertanto vale la propriet`a associativa. L’elemento neutro di (A,∗) `e lo zero dell’anello (A,+,·), infatti: a∗0 =a+ 0 +a·0 =a+ 0 + 0 =a e0∗a= 0 +a+ 0∗a= 0 +a+ 0 =a. Segue che (A,∗) `e un monoide. (b)Dimostriamo chef`e un omomorfismo. Sianoa, b∈A, risulta: f(a∗b) =f(a+b+a·b) =a+b+a·b+ 1 f(a)·f(b) = (a+ 1)·(b+ 1) =a·b+a·1 + 1·b+ 1·1 =a·b+a+b+ 1 Poich´ef(a∗b) =f(a)·f(b) segue chef`e un omomorfismo. f`e un’applicazione iniettiva, infatti sianoa, b∈Atali chef(a) =f(b). Segue chea+ 1 =b+ 1 e quindi che a+ 1 + (−1) =b+ 1 + (−1), cio`ea+ 0 =b+ 0 e quindia=b. Inoltref`e anche suriettiva: dato un generico elementoa∈A, si ha chea+ (−1)∈Ae chef(a+ (−1)) =a+ (−1) + 1 =a+ 0 =a. Pertanto f `e biunivoca e quindi risulta essere un isomorfismo. Infine, per dimostrare chef`e un isomorfismo di monoidi, occorre provare che l’elemento neutro 0 di (A,∗) viene portato nell’elemento neutro 1 di (A,·) e ci`o `e immedito da verificare:f(0) = 0 + 1 = 1. Possiamo pertanto concludere chef`e un isomorfismo tra il monoide (A,∗) e il monoide (A,·). (c)La formula data si traduce nel seguente modo: ∀x, y, z∈A x∗(y+z) = (x∗y) + (x∗z) e pertanto essa risulta falsa nell’interpretazione assegnata. Infatti, sviluppando i calcoli al primo e al secondo membro, si ottiene: x∗(y+z) =x+y+z+x·(y+z) =x+y+z+x·y+x·z (x∗y) + (x∗z) =x+y+x·y+x+z+x·z= 2x+y+z+x·y+x·z e quindi l’uguaglianza non `e verificata per ognix∈A. La formula non `e logicamente valida essendo falsa nella precedente interpretazione ma non `e neppure logicamente contraddittoria poich´e essa risulter`a vera in ogni interpretazione in cui la lettera predicativaEinterpreta la relazione universale.