01 07 2013

Page 1

LOGICA E ALGEBRA II PROV A IN ITINERE 1 LUGLIO 2013 ESERCIZIO 1 Si considerino le seguenti formule • F1 ≡ ¬∀xA1 1(x) • F2 ≡ ∀xA1 1(x) ⇒ A1 2(f 2 1 (x; y)) • F3 ≡ ∀xA1 1(x) ⇒ A1 2(f 2 1 (x; y)) ∨ ¬∀xA1 1(x) ∨ ∃xA2 2(x; y) a) Si traducano le formule date nell’interpretazione avente come dominio N − {0} e in cui A1 1(x) significa ‘ x ´ e un numero positivo’, A1 2 interpre- ta la relazione di primalit´ a,A2 2 interpreta la relazione di uguaglianza e f 2 1 interpreta l’operazione di moltiplicazione. Si dica poi se in tale interpre- tazione le formule date risultano false, vere oppure soddisfacibili ma non vere motivando la risposta. b) Si scrivano la chiusura universale e la chiusura esistenziale di F2 e si sta- bilisca se sono false, vere oppure soddisfacibili ma non vere nell’interpre- tazione assegnata al punto precedente. c) Si verifichi se la formula ¬F1 ∨ (F2 ∧ F3) ´ e logicamente valida. d) Si porti la formula ¬F1 ∨ (F2 ∧ F3) in forma normale prenessa. ESERCIZIO 2 a) Sia ⟨G; ·⟩ un gruppo e sia a ∈ G tale che per ogni g ∈ G sia a · g = g · a. Verificare se la relazione R ⊆ G × G definita da: g1Rg2 se e solo se esistono due interi positivi m; n tali che amg1 = ang2 ´ e una relazione di congruenza su ⟨G; ·⟩ e, in caso affermativo, si determini la R-classe dell’elemento neutro e di ⟨G; ·⟩. b) Si consideri il gruppo moltiplicativo Z 7 = Z7 − {[0]7} delle classi di resti modulo 7 diverse dalla classe [0] 7. Si provi che la relazione R ⊆ Z 7 × Z 7 definita da: [ a]7R[b]7 se e solo se esistono due interi positivi m; n tali che ([2]7)m · [a]7 = ([2] 7)n · [b]7 ´ e una relazione di congruenza su ⟨Z 7; ·⟩ e si provi che H = {[1]7; [2]7; [4]7} ´ e laR-classe di [1] 7. c) Dato il gruppo ⟨{−1; +1}; ·⟩, si dimostri che la funzione f : Z  7 → {−1; +1} definita da f ([a]7) = 1 se [ a]7…