Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 22 Giugno 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) 3, b) 1+2, c) 4+1 )Si consideri la relazione binariaρsuX=Z×Zdefinita nel seguente modo: (a, b)ρ(c, d) se e solo seab−cd= 0 (a)Si mostri cheρ`e una relazione di equivalenza suX. (b)Si mostri che [(2,3)] ρ= [(1 ,6)] ρe si verifichi che ρ= ker(f), dovef:X→Z`e definita daf(a, b) =ab. (c)Si consideri la seguente formula della logica del primo ordine: ∀x(A(a, x)∧A(f(x), x)⇒A(g(x, x), x) ) Si stabilisca se `e vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominioDl’insieme di tutte le relazioni binarie suXe nella quale la costantea`e interpretata dalla relazione identica suX,A(x, y) `e la relazione di inclusione di relazioni,f(x) `e la relazione inversa dix, eg(x, y) `e il prodotto tra le relazionix, y. La formula `e logicamente valida o logicamente contradditoria? Soluzioni:(a)La relazioneρ`e riflessiva dato che (a, b)ρ(a, b) dal momento cheab=ab; `e anche simmetrica infatti se (a, b)ρ(c, d) alloraab=cde quindi anche (c, d)ρ(a, b). Infineρ`e anche transitiva: se (a, b)ρ(c, d) e (c, d)ρ(e, f) alloraab= cd=efda cui segue che (a, b)ρ(e, f). (b)Dato che 2·3 = 1·6, abbiamo che (2,3)ρ(1,6) e quindi [(2,3)] ρ= [(1 ,6)] ρ. La relazione ker( f) mette in relazione due elementi (a, b), (c, d) se e solo sef(a, b) =f(c, d) che `e equivalente aab=cd, cio`e (a, b)ρ(c, d). Pertanto ρ= ker(f). (c)La formula si interpreta nel seguente modo: per ogni relazione binariaRsuZ, seI⊆ReR− 1 ⊆R, allora R2 ⊆R. In altre parole dice che ogni relazione binaria suZche sia riflessiva e simmetrica `e necessariamente anche transitiva. Questa formula `e falsa, basta considerare ad esempio la relazione R=I∪ {(1,2),(2,1),(2,3),(3,2)} che `e chiaramente riflessiva e simmetrica, ma non transitiva. La formula non `e quindi logicamente valida, ma non `e nemmeno logicamente contraddittoria dato che risulta vera in una interpretazione avente un qualunque dominionon vuoto e in cuiA(x, y) sia interpretata dalla relazione vuota. 2.(Punteggio: a) 3, b) 3, c) 3 ) Si consideri la formulaf(A, B, C) della logica proposizionale che assume il valore di verit`a 1 se e solo sev(A) =v(B) = v(C) = 1 oppurev(A) =v(C) = 1 ev(B) = 0 oppurev(B) =v(C) = 1 ev(A) = 0. (a)Si scriva una formula equivalente adf(A, B, C) che contenga solo i connettivi¬,⇒. (b)Si stabilisca, giustificando l’affermazione, se da¬A⇒Bsi pu`o dedurre nel sistema formaleL, la formula f(A, B, C). (c)Si dica se l’insieme Γ ={¬A⇒B,¬f(A, B, C)}`e insoddisfacibile. Soluzioni: (a)Usando la forma normale disgiuntiva abbiamof(A, B, C)≡(A∧B∧C)∨(¬A∧B∧C)∨(A∧¬B∧C). Semplificando la precedente formula abbiamo: f(A, B, C)≡(B∧C)∨(A∧ ¬B∧C)≡(B∨(A∧ ¬B))∧C≡((B∨A)∧(B∨ ¬B))∧C≡(B∨A)∧C da cui, usando solo i connettivi¬,⇒, otteniamof(A, B, C)≡(B∨A)∧C≡ ¬(C⇒ ¬(¬A⇒B)). (b)Dal teorema di correttezza e completezza forte abbiamo¬A⇒B⊢ L¬ (C⇒ ¬(¬A⇒B)) se e solo se¬A⇒B⊨ ¬(C⇒ ¬(¬A⇒B)), quindi dobbiamo verificare che i modelli di¬A⇒Bsono anche modelli di¬(C⇒ ¬(¬A⇒ B)) (che conosciamo dal testo!). Ora, un modello di¬A⇒B`ev(A) = 0, v(B) = 1 ev(C) = 0 che per`o non `e modello dif(A, B, C). Pertanto da¬A⇒Bnon si pu`o dedurre inLla formulaf(A, B, C). (c)L’insieme{¬A⇒B,¬f(A, B, C)}`e insoddisfacibile se e solo se¬A⇒B⊨f(A, B, C) che, dal punto precedente, sappiamo essere una deduzione falsa. Infatti l’interpretazionev(A) = 0, v(B) = 1 ev(C) = 0 `e modello di¬A⇒B ma non dif(A, B, C), quindi `e anche modello di¬f(A, B, C) e pertanto Γ `e soddisfacibile. 3.(Punteggio: a) 3, b) 4, c) 4 ) Si consideri l’insieme delle matrici quadrate di ordine 2 ad elementi inZstrutturato ad anello rispetto alle usuali operazioni di somma e prodotto di matrici ed il suo sottoinsiemeAcos`ı definito: A= a0 b c :a, b, c∈Z . Sia inoltref:Z→Al’applicazione definita daf(z) = 0 0 z0 per ogniz∈Z. (a)Si mostri cheA`e un anello rispetto alle usuali operazioni di somma e prodotto di matrici. (b)Si mostri chef`e un monomorfismo del gruppo additivo (Z,+) nel gruppo additivo (A,+) e si dica se `e anche un monomorfismo di anelli. (c)Si considerino ora le seguenti formule della logica del primo ordine: E(p(x, y), p(y, x)) ∀x∀y(E(p(x, y), p(y, x))) e si dica se sono vere, false, soddisfacibili ma non vere nell’interpretazione che ha come dominioAe nella quale la lettera predicativaEsia da interpretare come l’uguaglianza e la lettera funzionalepcome il prodotto tra matrici. Le formule sono logicamente valide? Soluzioni: (a)Dato che l’insieme delle matrici 2×2 a coefficienti interi costituisce un anello rispetto alle usuali somma e prodotto di matrici, usiamo il criterio di caratterizzazione dei sottoanelli e verifichiamo che per ogni a0 b c , α0 β γ ∈A risulta che a0 b c − α0 β γ ∈Ae che a0 b c · α0 β γ ∈A. Abbiamo: a0 b c − α0 β γ = a−α0 b−β c−γ ∈A a0 b c · α0 β γ = aα0 bα+cβ cγ ∈A Poich`e `e verificato il criterio di caratterizzazione dei sottoanelli segue che (A,+,·) `e esso stesso un anello. (b)Per ogniz 1, z 2∈ Z, risulta che f(z 1+ z 2) = 0 0 z1+ z 20 = 0 0 z10 + 0 0 z20 =f(z 1) + f(z 2) e pertantof`e un omomorfismo. Inoltref`e iniettiva dato chef(z 1) = f(z 2) se e solo se 0 0 z10 = 0 0 z20 e quindi se e solo sez 1= z 2. Per verificare che fsia un omomorfismo di anelli dobbiamo avere anche che f(z 1z 2) = f(z 1) ·f(z 2), che per`o in generale non `e un’uguaglianza vera, infatti: f(z 1z 2) = 0 0 z1z 20 ̸ = 0 0 0 0 = 0 0 z10 · 0 0 z20 =f(z 1) ·f(z 2) Segue chef`e un monomorfismo di gruppi ma non di anelli. (c)La prima formula non `e chiusa ed `e soddisfacibile, ad esempio `e soddisfatta dall’assegnamento in cuix=y=  0 0 0 0 . Il suo valore di verit`a si pu`o dedurre dalla sua chiusura universale che `e la seconda formula. Quest’ultima `e falsa, infatti basta prenderex= 0 0 1 1 ey= 1 0 0 2 e si ha: 0 0 1 1 · 1 0 0 2 = 0 0 1 2 ̸ = 0 0 2 2 = 1 0 0 2  0 0 1 1 Deduciamo pertanto che la prima formula `e non vera ma solo soddisfacibile. Chiaramente dato che le due formule non sono vere, non sono nemmeno logicamente valide.