06 07 2011 1

Pagina 1

Logica e Algebra II prova in itinere 6/7/2011 ESERCIZIO 1 Si consideri la seguente formula di logica del I ordine ∼∀ y ∃ z ( A1 2(x, z) ∧ A 2 2 ( x, f 1 2(y, z)) ⇒ A1 1(x) dove x, y, z sono delle variabili. Si porti la formula in forma normale prenessa e si scriva la forma di Skolem della chiusura universale della formula stessa. Si dica se questa formula è vera, falsa o soddisfacibile (ma non vera) nell’interpretazione avente come dominio l’insieme dei numeri interi Z, in cui A1 1 ( x) significa “ x è primo”, A1 2 (x, y) significa “x > y ”, A2 2 ( x, y) significa “ x divide y”, f1 2(x, y) significa “x ⋅ y”. Si scrivano le chiusure universale ed esistenziale della formul a data e si dica se sono vere, false o soddisfacibili (ma non vere) nell’interpretazione data. ESERCIZIO 2 Si considerino l’insieme A delle matrici quadrate di ordine 2 i cui elementi appartengono a Z 6, strutturato ad anello rispetto alle usuali operazioni di somma e prodot to di matrici, e l’insieme: B =   ∈      6Zc , b , a |cb 0a a) B è a sua volta anello rispetto alle operazioni di somma e prodotto di matrici? B è un ideale di A? b) B ammette divisori dello 0? Esistono elementi invertibili in B? c) Si consideri l’applicazione f:B → Z6 definita da             cb af 0 = c e si provi che è un epimorfismo di B su Z 6. d) Si dica se l’insieme C = { }       ∈∈      6666 ] 4 [ ,] 2 [ ,] 0 [,,,|0 cZcbacb a è un ideale di B. Motivare le risposte date . Traccia di soluzione ESERCIZIO 1 Data la formula ( )())) ,(,(),( 1 1 2 1 2 2 2 1 xAzyfxAzxAzy ⇒∧∃¬∀ e considerate le equivalenze ∃¬ ≡¬∀ e ∀¬ ≡¬∃ si ha innanzitutto che la formula iniziale è equi valente alla seguente: ( )())) ,(,(),( 1 1 2 1 2 2 2 1 xAzyfxAzxAzy ⇒∧¬∀∃ . Da questa, utilizzando i noti lemmi che permettono…