Soluzionedellaprovadel30gennaio2018

Pagina 1

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 una eventuale (se esiste) inversa destra e/o sinistra. 2. Sia S  X  X la relazione S=R∪{(a,e),(d,c)}. Dire se esiste la minima relazione d’ordine T contenente S e in caso affermativo disegnarne 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) ))~(~)~(~(~ ABBAC  2. Per il…