11 07 2014

Page 1

LOGICA E ALGEBRA 11 luglio 2014 Parte prima Esercizio 1 Sia data la seguente tavola di verità A B C f (A, B, C ) _______________________________________ 1 1 1 x 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 y 0 1 0 1 0 0 1 1 0 0 0 1 1. Si completi la tavola di verità attribuendo ad x ed y il valore 0 oppure 1 in modo che valgano le seguenti deduzioni: a. ABA ¬⇒, ├L f(A,B,C) b. CBAB ∧⇒, ├L¬f(A,B,C) 2. Si mostrino le deduzioni del punto precedente mediante la risoluzione. 3. Si dica se, date tre generiche formule ben formate A, B, C che operano sulle stesse lettere enunciative, è sempre vero che valgono le seguenti deduzioni: a. A ⇒ B,¬A ├L ¬ A b. B ⇒ A ,B ∧ C ├L A Esercizio 2 Sia f: Z→ N × N la funzione definita ponendo ⎩ ⎨ ⎧ ≤+ >=∈∀ 0 se)1||4,( 0 se)2,()( 2 2 xxx xxxxfZx 1) Si dica se f ammette inversa (destra, sinistra o bilatera) ed in caso affermativo si fornisca almeno un esempio di tale inversa. 2) Si provi che se una funzione f: A→B è iniettiva allora per ogni coppia di funzioni g: B→A, h: B→A si ha che da g · f = h · f segue g = h. (FACOLTATIVO: si mostri il viceversa) 3) Sia R la relazione binaria definita su N × N nel seguente modo: dbcadcRbaNNdcba | | ),(),(),(),,( ∧⇔×∈∀ Si stabilisca se la relazione R ristretta all’insieme f (A) con A= {1,2,3,4,5,6} è una relazione d’ordine. In caso affermativo si determinino gli elementi massimali, minimali, massimo e minimo (se esistono) di f (A) rispetto ad R e si dica se ( f (A), R ) è un reticolo. Motivare ogni risposta Traccia di soluzione della parte prima Esercizio 1 1) Per il teorema di correttezza e completezza forte risulta che ABA ¬⇒, ├L f(A,B,C) se e solo se ABA ¬⇒, |= f(A,B,C), cioè se e solo se ogni modello dell’insieme {ABA ¬⇒, } è modello per f(A,B,C). I modelli dell’insieme {ABA ¬⇒, } sono le ultime quattro interpretazioni…