Computer Engineering - Logica e Algebra

Full exam

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 12 Luglio 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) 3 c) 2 d) 3 )SiaX={a, b, c, d, e, f}e siaRla relazione suXrappresentata dal seguente grafo di adiacenza:c a f edb (a)Determinare, se possibile, la minima relazione d’ordine ScontenenteRe, se esistono, gli elementi massimali e minimali, massimo e minimo diXrispetto aS. (b)Determinare la relazione d’equivalenzaρgenerata daRe l’insieme quozienteX/ρ. (c)Dire quante sono le funzioni daXadXcontenentiRe quante tra queste ammettono inversa sinistra. (d)Data la seguente formula della logica del primo ordine ∀x∀z(A(x, y)∧A(z, y) =⇒ ∃tA(y, t)∨A(x, z)) stabilire se essa `e vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominioXe in cuiA sia da interpretare come la relazioneR. Soluzioni:(a)La minima relazione d’ordineScontenenteR`e la chiusura riflessiva e transitiva diRe quindi ha il seguente grafo di adiacenza:c a f edb Il diagramma di Hasse di S`e il seguente:caf edb da cui si evince che l’insieme dei massimali `e {b, f}, l’insieme dei minimali `e{c, e, d}e quindi non esistono massimo e minimo diXrispetto adS. (b)La relazione d’equivalenza ρgenerata daR`e la chiusura riflessiva, simmetrica e transitiva diRe quindi ha il seguente grafo di adiacenza:c a f edb L’insieme quoziente `e X/ρ={[a] ρ, [b] ρ} , dove [a] ρ= {a, c, e, f}, [b] ρ= {b, d}. (c)Le funzionig:X→XcontenentiRdevono essere tali cheg(a) =f,g(c) =g(e) =a,g(d) =bmentre perg(f) eg(b) si hanno rispettivamente 6 possibili scelte. Segue che il numero totale di funzioni contenentiR`e 36. Di queste nessuna ammette inversa sinistra poich´e nessuna di esse `e suriettiva. Infatti, essendoXun insieme finito, una funzioneg:X→X`e suriettiva se e solo se `e iniettiva e nessuna funzionegcontenenteRpu`o essere iniettiva dal momento che deve verificare la condizioneg(c) =g(e) =a. (d)Osserviamo innanzitutto che la formula data non `e chiusa poich´e tutte le occorrenze della variabileysono libere. La formula data `e soddisfacibile ma non vera nell’interpretazione assegnata. Infatti, ad esempio, se consideri- amo un assegnamentos′ tale ches′ (y) =callora l’antecedente della formula sar`a sempre non soddisfatto das′ e pertantos′ soddisfer`a l’intera formula. Se invece consideriamo un assegnamentostale ches(y) =fallora l’antecedenteA(x, y)∧A(z, y) `e soddisfatto dasses(x) =s(z) =a. Non esiste per`o alcun elementot ∈Xtale che (f ,t )∈Rquindi la sottoformula∃tA(y, t) del conseguente non `e soddisfatta dase non lo `e neppure la sottoformula A(x, z) poich´e (a, a)/ ∈R. Pertantosnon soddisfer`a l’intera formula che quindi risulter`a soddisfacibile ma non vera nell’interpretazione assegnata. 2.(Punteggio: a) 3 b) 3 c) 3 ) Si consideri la seguente tavola di verit`a: A B Cf (A, B, C)0 0 01 0 0 11 0 1 00 0 1 11 1 0 00 1 0 11 1 1 01 1 1 11 (a)Si scriva una formulaf(A, B, C) che abbia come tavola di verit`a quella assegnata e che contenga solo i connettivi ¬e =⇒. (b)Verificare seB⇒A⊢ Lf (A, B, C) nella teoria L. (c)Ridimostrare il risultato trovato al punto precedente usando la risoluzione. Soluzioni:(a)Una formulaf(A, B, C) che abbia come tavola di verit`a quella assegnata ha la seguente forma normale congiuntiva: f(A, B, C)≡(C∨A∨ ¬B)∧(C∨ ¬A∨B) Semplifichiamola e scriviamola in modo tale che contenga solo i connettivi¬e =⇒: f(A, B, C)≡C∨((A∨ ¬B)∧(¬A∨B))≡C∨ ¬(¬(B=⇒A)∨ ¬(A=⇒B))≡ ≡(¬(B=⇒A)∨ ¬(A=⇒B)) =⇒C≡((B=⇒A) =⇒ ¬(A=⇒B)) =⇒C. (b)Per il teorema di correttezza e completezza forte, valeB⇒A⊢ Lf (A, B, C) se e solo seB⇒A⊨f(A, B, C), cio`e se e solo se tutti i modelli diB⇒Asono modelli dif(A, B, C). La deduzione pertanto non esiste in quanto l’interpreatazionevtale chev(A) = 1 ev(B) =v(C) = 0 `e modello diB⇒Ama non dif(A, B, C). Segue che B⇒A̸⊢ Lf (A, B, C). (c)Dobbiamo verificare che Γ ={B⇒A,¬f(A, B, C)}non `e insoddisfacibile e quindi che dalle clausole di Γ non possiamo ottenere la clausola vuota. Sappiamo che f(A, B, C)≡(C∨A∨ ¬B)∧(C∨ ¬A∨B)≡C∨((A∨ ¬B)∧(¬A∨B))≡C∨((A∧B)∨(¬A∧ ¬B)) da cui segue che¬f(A, B, C)≡ ¬C∧((¬A∨ ¬B)∧(A∨B)). Si ottengono pertanto le clausole{¬C},{¬A,¬B},{A, B}, mentre dalla formulaB⇒Aotteniamo la clausola {¬B, A}. Quindi abbiamo: Γc ={ {¬C},{¬A,¬B},{A, B},{¬B, A} } poich´e il letteraleCnon compare in nessuna altra clausola possiamo fare un pruning e considerare l’insieme di clausoleΛ ={ {¬A,¬B},{A, B},{¬B, A} } da cuiRis(Λ) = Λ∪ {{A},{¬B}}, eRis2 (Λ) = Λ∪ {{A},{¬B}}. Non potendo ottenere la clausola vuota, deduciamo che Γ non `e insoddisfacibile. Segue che non `e vero cheB⇒A⊨f(A, B, C) e quindi nemmeno che B⇒A⊢ Lf (A, B, C). 3.(Punteggio: a) 4 b) 2 c) 3 d) 2 ) Sia (Z 8, +,·) l’anello delle classi di resto modulo 8. (a)Si consideri il sottoinsiemeX={[0] 8, [2] 8, [4] 8, [6] 8} dell’anello (Z 8, +,·). Si stabilisca seX`e un sottoanello di (Z 8, +,·) e, in caso affermativo, si verifichi seX`e anche un ideale. (b)Si risolva la seguente equazione congruenziale inZ 8: [5]8· x+ [2] 8= [3] 8 (c)Si consideri la seguente formula della logica del primo ordine:¬∃yA(f(x, y), a) =⇒ ∃y(¬A(y, b)∧A(f(x, y), b)) e si stabilisca se `e vera, falsa o soddisfacibile ma non vera nell’interpretazione che ha dominioZ 8, in cui la costante asia da interpretare come l’unit`a dell’anello, la costantebcome lo zero dell’anello,fsia da interpretare come l’operazione di moltiplicazione tra classi di resto modulo 8 eAcome l’uguaglianza. (d)Si chiuda universalmente la formula data e si verifichi, usando la risoluzione del primo ordine, che tale chiusuranon `e logicamente valida. Soluzioni:(a)Usiamo il criterio di caratterizzazione dei sottoanelli e verifichiamo che, per ognix, y∈X, si ha chex−y∈Xe xy∈X. Questo punto pu`o essere affrontato o facendo le tavole delle differenzex−ye dei prodottixy, oppure notando cheX`e composto da divisori dello zero e dallo zero stesso. In particolare, i rappresentanti degli elementi diXsono tutti e soli i multipli di 2, cio`eX={[2k] 8: k∈Z}. Quindi sea, b∈Zsono i rappresentanti di x= [a] 8, y = [b] 8, allora a−beabsono anch’essi multipli di due e quindi abbiamo che [a−b] 8, [ab] 8∈ Xda cui segue che (X,+,·) `e sottoanello di (Z 8, +,·). Inoltre (X,+,·) `e anche un ideale dato che sex= [a] 8allora moltiplicandoxa destra o a sinistra (per commutativit`a!) per un elementoz= [c] 8∈ Z 8abbiamo che xz= [ac] 8 che appartiene ancora adXdato chea`e multiplo di 2 e quindi ancheaclo `e. (b)L’equazione `e equivalente a [5]8· x= [3] 8− [2] 8e quindi a [5] 8· x= [1] 8. Dato che 5 `e primo con 8 allora [5] 8ha inverso moltiplicativo che ovviamente non sar`a da ricercare fra gli elementi dell’insiemeX. Chiaramente [1] 8non `e l’inverso di [5]8e quindi restano da verificare gli elementi [3] 8, [5] 8, [7] 8. Poich´e [5] 8· [5] 8= [25] 8= [1] 8segue che la soluzione dell’equazione `ex= [5] 8. (c)La formula si traduce nel seguente modo: dato unx∈Z 8, se non esiste nessun y∈Z 8tale che xy= [1] 8, allora esiste unoz∈Z 8(possiamo cambiare nome alla variabile!) diverso da [0] 8tale che xz= [0] 8. In pratica la formula dice che sexnon ha inverso moltiplicativo, allorax`e divisore dello zero. Si pu`o verificare direttamente la formula facendo una casistica su tutti glix∈Z 8oppure si pu`o fare riferimento alla teoria in quanto sappiamo che x∈Z n ha inverso moltiplicativo se e solo non `e divisore dello zero. Pertanto la formula risulta vera nell’interpretazione assegnata. (d)La chiusura universale della formula data `e la seguente: ψ=∀x(¬∃yA(f(x, y), a) =⇒ ∃y(¬A(y, b)∧A(f(x, y), b))) Sappiamo cheψ`e logicamente valida se e solo se¬ψ`e insoddisfacibile e quindi dal teorema di correttezza e completezza per refutazione{¬ψ}c ⊢R□ . Per calcolare le clausole di¬ψ, portiamo prima la formula in FNP: ¬ψ≡∃x¬(∃yA(f(x, y), a)∨ ∃y(¬A(y, b)∧A(f(x, y), b)))≡ ∃x(¬∃yA(f(x, y), a)∧ ¬∃y(¬A(y, b)∧A(f(x, y), b)))≡ ∃x∀y(¬A(f(x, y), a)∧ ∀y¬(¬A(y, b)∧A(f(x, y), b)))≡ ∃x∀y∀z(¬A(f(x, y), a)∧ ¬(¬A(z, b)∧A(f(x, z), b)))≡ ∃x∀y∀z(¬A(f(x, y), a)∧(A(z, b)∨ ¬A(f(x, z), b))) e quindi la sua forma di Skolem `e ∀y∀z(¬A(f(d, y), a)∧(A(z, b)∨ ¬A(f(d, z), b))) doved`e la nuova costante introdotta nella skolemizzazione al posto della variabilex. Pertanto le clausole che otteniamo sono:{¬ψ}c ={ {¬A(f(d, y), a)},{A(z, b),¬A(f(d, z), b)} } nessun letterale tra la prima e la seconda clausola `e unificabile dato che nella prima clausola la seconda componente `e la constantea, mentre nelle altre clausole la seconda componente `eb. Pertanto l’insieme delle risolventi di{¬ψ}c `e{¬ψ}c stesso e quindi non possiamo ottenere la clausola vuota. Ne deduciamo che¬ψnon `e insoddisfacibile da cui segue cheψnon `e logicamente valida.