Computer Engineering - Logica e Algebra

Full exam

LOGICA E ALGEBRA 5 febbraio 2016 Parte di Logica Esercizio 1 In logica proposizionale siano A,B,C le formule di un opportuno linguaggio proposizionale che traducono le frasi “ Se Carlo ha vinto la gara, allora Mario è arrivato secondo e Sergio è arrivato terzo ”, “Mario non è arrivato secondo ”, ” Carlo non ha vinto la gara ” rispettivamente. 1. Dire se { A,B}|-LC 2. Ritrovare il risultato precedente facendo uso della risoluzione. Esercizio 2 Si consideri la seguente formula F 1. Si dica se la formula è vera, falsa soddisfacibile ma non vera quando si prenda come dominio l’insiem e N dei naturali (0 incluso), si interpretino la lettera funzionale come l’operazione che restituisce il successivo, la lettera funzional e come l’operazione di somma, il predicato come x < y e il predicato come x ≤ y 2. Si porti F in forma prenessa, se ne scrivano le chiusure esistenziale ed universale e si discu ta la loro verità/falsità nell’ interpretazione data . 3. Si scriva una formula con lo stesso significato di F nell’interpretazione data, utilizzando un linguaggio del primo ordine in cui si hanno a disposizione la lettera funzionale , i predicati e e il predicato che indica che y è il successivo di x. Giustificare ogni risposta Traccia di s oluzione Esercizio 1 Usiamo le seguenti lettere enunciative: A: “Carlo ha vinto la gara ” B: “Mario è arrivato secondo ” C: “Sergio è arrivato terzo ” 1. La frase A diventa A  B  C, la frase B è B e infine C è A. Per il teorema di correttezza e completezza forte {A,B}|-LC se e solo se {A,B}|=C, pertanto se e solo se ogni modello di {A,B} è modello di C. Affinché v sia un modello di {A,B} deve essere v(B) = 1 e quindi v(B) = 0. Ciò implica che v(B C) = 0 e dunque anche v(A) = 0 dovendo risultare v(A) = 1. Segue che v(A) = 1 e pertanto v(C) = 1. 2. Come già detto { A,B}|-LC se e solo se { A,B}|= C e quindi se e solo se { A,B, C} è insoddisfacibile. Sappiamo che  è un insieme di formule insoddisfacibile se e solo se c|-R. Ora {A,B, C}c ={{ A, B},{ A, C},{ B},{A}} e allora da { A, B} e {A} si ricava la clausola {B} dalla quale con la clausola { B} si ha la clausola vuota. Esercizio 2 1. In linguaggio naturale co n l’interpretazione data la formula F si legge “per ogni x appartenente ad N il successore di x è strettamente minore del successore del successore di x e per ogni x appartenente ad N il suc cessore di x è minore o uguale di x + y”. Ovviamente è vero che “per ogni x appartenente ad N il successor e di x è strettamente minore del successore del successore di x” mentre la frase “per ogni x appartenente ad N il suc cessore di x è minore o uguale di x + y” non è soddisfa tta se y assume i l valore 0 ed è soddisfatta se y 1 e dunque è soddisfacibile ma no n vera. La formula F che è la congiunzione delle due formule è dunque soddisfacibile ma non vera. 2. Una forma normale prenessa di F è ottenuta ricordando che . O sserviamo che applicando nel modo usu ale le equivalenze si poteva anche ottenere . La chiusura esistenziale è che è una formula vera essendo la chiusura esistenziale di una formula (equivalente a d una formula) soddisfacibile . La chiusura universale è  che è una formula falsa essendo la chiusura universale di una formula (equivalente a una formula) non vera . 3. Utilizzando il nuovo linguaggio del I ordine una formula con lo stesso significato di F si scrive così : Per maggior e precisione , usando un linguaggio con identità, ovvero con tenente anche il predicato binario U(x,y) d a interpretare come uguaglianza, si poteva aggiungere che il successivo di un naturale esiste ed è unico scrivendo Questa formula poteva essere messa in congiunzione con la precedente. L OGICA E ALGEBRA 5 febbraio 2016 Parte di Algebra Esercizio 1 Sia X l’ins ieme di tutte le funzioni da N ad N e sia R la relazione binaria su X definita ponendo: (f, g)R se e solo se esiste un numero naturale k tale che per ogni x > k si abbia f(x) = g(x) a) Si provi che R è una relazione di equivalenza su X b) Si trovi la classe di equivalenza della funzione f definita da f(n) = n + 1. c) Determinare la classe di equivalenza della funzione i dentica su N . Esercizio 2 Sull’insieme Z × Z si consideri la legge di composi zione definita ponendo (a, b) × (c, d) = (a + c,(−1) c b + d) . a) Dimostrare che Z × Z è un gruppo rispetto all’operazione sopra definita . b) Dire se l’insieme H = {(0, b) | b Z} è un suo sottogruppo e in caso affermativo se è un sottogruppo normale. Giustificare ogni risposta Traccia di s oluzione Esercizio 1 1. La relazione R gode della proprietà riflessiva in quanto , preso comunque un numero naturale k, per ogni x > k si ha f(x) = f(x) e dunque (f,f) R. R gode anche della proprietà simmetrica in quanto (f,g) R implica che esiste un k naturale tale che , per ogni x > k, f(x) = g(x) e quindi , per ogni x>k , anche g(x) = f(x), pertanto (g,f) R. Infine R gode anche della proprietà transitiva in quanto (f,g) R implica che esiste un k1 natur ale tale che , per ogni x > k1, f(x) = g(x) , mentre (g,h) R implica che esiste un k2 naturale tale che , per ogni x > k2, g(x) = h(x). Pertanto, per ogni x > max{ k1,k2}, f(x) = h(x) quindi (f,h) R. 2. La classe di equivalenza della funzione f definita da f(n) = n + 1 è composta da tutte le funzioni da N ad N definitivamente uguali ad f, ovvero da tutte e sole le funzioni g tali che esista un intero k g per cui , per ogni x>k g, g(x) = x+1 . Si tratta di tutte e sole le funzioni così definite : dove h(x ) è una qualsiasi funzione da N ad N. 3. La classe di equivalenza della funzione identica è composta da tutte le funzioni da N ad N definitivamente uguali all’identità, ovvero da tutte e sole le funzioni g tali che esista un intero k g per cui , per ogni x>k g, g(x) = x. Si tratta di tutte e sole le funzioni così definite : dove h(x) è una qualsiasi funzione da N ad N. Esercizio 2 1. La legge di composizione definita da (a, b) × (c, d) = (a + c,(−1) c b + d) è un’operazione interna su Z×Z in quanto sia a + c sia (−1) c b + d appartengono a Z. La legge è associativa, infatti ((a, b) × (c, d)) × (e, f) = (a + c, (−1) c b + d) × (e, f) =((a + c) + e, ( -1) e((−1) c b + d) + f) (a, b) × ((c, d) × (e, f))= (a, b) × (c + e, ( -1) e d + f) = (a + (c + e), ( -1)c+e b + ((−1) e d + f)) . Ora per l’associatività della somma in Z si ha (a + c) + e = a + (e + c) e, per l’associatività di somma e prodotto, la distributività de l prodotto rispetto alla somma in Z , si ha anche (-1) e((−1) c b + d) + f = ((-1)e(−1) c b + (-1) e d) + f = (-1)c+e b + ((−1) e d + f) da cui segue che ((a, b) × (c, d)) × (e, f) = (a, b) × ((c, d) × (e, f)). L’elemento (0,0) funziona da elemento neutro a destra infatti (a,b) ×(0,0 ) = (a + 0, (-1) 0b + 0) = (a, b). Cerchiamo ora un candidato inverso destro : risulta (a, b) × (c, d) = (0,0) se e solo se a + c = 0 e (−1) c b + d = 0 da cui si ottiene c = -a, d= -(−1) c b = (−1) -a+1 b. Quindi ( -a, (−1) -a+1 b) è l’inverso destro di (a,b), infatti (a,b) × (-a, (−1) -a+1 b) = (a+( -a), ( -1)-ab+ (−1) -a+1 b) = (0,0) in quanto –a e –a+1 hanno parità diversa. Du nque , per la riduzione degli assiomi di gruppo , risulta che (Z×Z , ×) è gruppo. 2. Usiamo il secondo criterio per i sottogruppi e quindi calcoliamo il seguente prodotto : (0,a) × (0,b) -1=(0,a) × (0, -b) = (0,( -1)0a -b)) . Poiché (0,a) × (0,b) -1 ha la prima c omponente nulla appartiene ad H che quindi è un sottogruppo. E’ immediato verificare che è (un sott ogruppo ) normale perché (a,b) -1 × (0,c) × (a,b) = (-a, (−1) -a+1 b) × (0,c) × (a,b), ha sempre come prima componente –a + 0 + a = 0 e dunque sta in H.