Computer Engineering - Logica e Algebra

Full exam

Logica e Algebra (30 Gennaio 2018) Esercizio 1 Sia f(A,B,C) una f.b.f. avente la seguente tavola di verità: A B C f (A,B,C) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 1. Scrivere una f.b.f. equivalente avente la tavola di verità di f(A,B,C) usando solo i connettivi { , }. 2. Mostrare che vale la deduzione (ABC) |-L f(A,B,C) . 3. Provare lo stesso risultato utilizzando la risoluzione . 4. Trovare una formula g (A,B,C) tale che f(A,B,C) )|-Lg(A,B,C) ma tale che g(A,B,C) non sia deducibile in L dalla formula A. Esercizio 2 Sia X = {a, b, c, d, e, f} e sia R  X  X la relazione con la seguente matrice di incidenza: 1. R è una funzione? Calcolare u na eventuale (se esiste) invers a destr a e/o sinistra . 2. Sia S  X  X la relazione S=R ∪{(a,e),(d,c)}. Dire se esiste la minima r elazione d’ordine T contenente S e in caso affermativo disegna rne il diagramma di Hasse . Trovare, se esistono , Sup{b,c,d}, Sup{b,c,e }, gli elementi massimali, minimali, massimi e minimi di X rispetto a T. 3. Sia U la chiusura transitiva di R. Verificare se la formula: ) è vera, o meno, nell’interpretazione che ha come dominio l’insieme X e la lettera predicativa è interpretata dalla relazione . In generale , quali proprietà (di quelle che conoscete) sono richieste da U affinché soddisfi la precedente formula? 4. La formula F è soddisfacibile? È logicamente valida? Esercizio 3 Sia un insieme dotato della seguente operazione interna definita da = 1. Provare che (G,*) è un gruppo . 2. Provare che la funzione definita da è un omomorfismo di gruppi. Descrivere la ker -f classe dell ’elemento neutro di G. GIUSTIFICARE OGNI RISPOSTA Soluzione Esercizio 1 1. Una f.b.f. avente la tavola di verità di f(A,B,C) e contenente solo i connettivi { ,  } è f(A,B,C) 2. Per il teorema di correttezza e completezza forte , dim ostrare che vale la deduzione sintattica (ABC)| -L f(A,B,C) equivale a mostrare che vale la deduzione semantica (ABC) f(A,B,C), cioè che tutti i modelli di ( ABC) sono modelli di f(A,B,C). Osservando che la f.b.f. (ABC) ha un solo modello che è v(A) = v(C) = 0 e v(B) = 1 che è anche modello di f(A,B,C), si ottiene il risultato. 3. Poichè mostrare che (ABC) f(A,B,C) equivale a mostrare che è insoddisfacibile, si può, utilizzando la risoluzione, mostrare che dall’insieme si deduce la clausola vuota. Osservando che scrivend o le formule in forma a clausole si ha C1= , C2= C3= C4= , C5= . Da C3 e C 4 si ha C 6= da C 6 e C 1 si ha C 7= , da C 7 e C2 si ottiene la clausola vuota. 4. Una possibile formula g(A,B,C) tale che f(A,B,C) )|-L g(A,B,C) ma tale che g(A,B,C) non sia deducibile in L dalla formula A è . Esercizio 2 1. Come si evince dalla matrice d’incidenza della relazione R, tale relazione è una funzione in quanto presenta uno ed un solo uno su ogni riga. Ricordando che u na funzione ammette inversa destra se e solo se è iniettiva ed inversa sin istra se e solo se è suriettiva e osservando che l a funzione R non è iniettiva in quanto l’ultima colonna della matrice d’incidenza presenta più di un 1 e che non è suriettiva perché la pr ima colonna non presenta alcun 1 , possiamo affermare che la funzione R non ammette né inverse destre né sinistre . 2. Considerata la relazione S  X  X con S = R∪{(a,e),(d,c)}, si può osservare che S è antisimmetrica quindi può esistere la minima relazione d’ordine T contenente S. Precisamente se la chiusura riflessiva e transitiva di S è antisimmetrica essa è la minima relazione d’ordine contenente S, diversamente tale chiusura non esiste. Essendo la chiusura riflessiva e transitiva di S uguale a S ∪ {(a,a),(b,b), (c,c),(d,d),(e,e), (a,c),(a,f),(b,f),(d,f)}, si osserva che è antisimmetrica e perciò coincide con la relazione T cercata. Il diagramma di Hasse di T è )) ~(~ ) ~ ( ~(~ A B B A C      f c b e a d Da esso si evince che Sup{b,c,d} = c, e che Sup{b,c,e} = f, l’unico elemento massimal e è f che è anche massimo mentre gli elementi minimali sono a , d ma non esiste minimo. 3. La chiusura transitiva U di R è data da R ∪{(a,c),(a,f),(b,f),(d,f)}. La formula ) è vera nell’interpretazione che ha come dominio l’insieme X e in cui la lettera predicativa è interpretata dalla relazione in quanto U è seriale ed è transitiva . Infatti, su ogni riga della matrice di incidenza di R vi è almeno un 1 e qui ndi ciò si verifica anche per ogni sua chiusura pertanto la sottoformula è sempre soddisfatta per ogni x. Inoltre vale la proprietà transitiva per U quindi anche la seconda sottoformula che segue l ’and è sempre soddisfatta dal momento che lo è . Pertanto le proprietà delle relazioni binarie ch e sono richieste da U affinché sia soddisf atta la precedente formula sono la serialità e la transitività. 4. Ovviamente la formula F è soddisfacibile essendo vera nella precedente interpretazione . La formula non è log icamente valida, basta infatti considerare l’interpretazione avente come dominio un insieme D costituito da due elementi, D ={a,b }, e in cui la lettera predicativa è interpretata dalla relazione x y. L’assegnamento x = a, y = b, z = b non soddisfa la formula. Esercizio 3 1. Per provare che (G,*) è un gruppo si deve mostrare che l’operazione * è interna, è associativa, ammette elemento neutro in G e che ogni elemento di G ammette inverso rispetto *. Osserviamo che l ’operazione * è interna in quanto e per ogni L’operazione * è associativa in quanto = = ed essendo l’operazione + associativa in Z si ha la tesi. Cerchiamo l’elemento neutro a sinistra di * in G, cioè cerchiamo un elemento tale che , per ogni , * . Cerchiamo quindi un elemento tale che , per ogni . L’elemento cercato è la coppia . Da ultimo cerchiamo l’inverso sinistro del generico elemento cioè un elem ento tale che . Ovviamente l’elemento cercato è la coppia . Essendo * associativa ed esistendo l ’elemento neutro a sinistra e l ’inverso a sinistra del g enerico elemento di G, per la riduzione dei postulati di un gruppo, abbiamo dimostrato che (G,*) è un gruppo . 2. Mostriamo ora che la funzione definita da è un omomorfismo di gruppi. Si ha infatti che e che ed essendo si ha la tesi. –classe della coppia                             )}. (mod | , { } 0 , { } 0 0, 0 , , { 0, 0 ker n b a G b a b a G b a f b a f G b a n n n n n n n n f n            