Soluzioneprova9luglio2021

Page 1

Esame di Logica e Algebra - 9 luglio 2021 Durata della prova: 1h 30’ 1. (9 punti) a) 4 punti; b) 5 punti Si consideri la formula f(A,B,C ) che assume il valore di verit` a 1 solo per le interpretazioni v1 ovev1(A) =v1(B) = 1 e v1(C) = 0 e v2 ovev2(A) = 0 e v2(B) =v2(C) = 1. (a) Dire se la formula ¬(B⇒¬f(A,B,C ))⇒ (C⇒¬A) ` e un teorema della teoria L; (b) Verificare utilizzando la risoluzione che l’insieme {¬(C⇒¬A),f (A,B,C )} ` e insoddisfacibile. Soluzione: (a) Per il teorema di correttezza e completezza dobbiamo verificare se ⊨¬(B⇒¬f(A,B,C ))⇒ (C⇒¬A). Invece di costruire la tavola di verit` a, supponiamo per assurdo che ¬(B ⇒¬ f(A,B,C ))⇒ (C ⇒¬ A) non sia una tautologia. Ci` o vuole dire che¬(B⇒¬ f(A,B,C ) ` e vera e (C⇒¬ A) ` e falsa. Dal fatto che B⇒¬ f(A,B,C ) deve essere falsa ne deduciamo cheB ` e vera edf(A,B,C ) ` e anch’essa vera, mentre dal fatto che (C⇒¬A) ` e falsa ne deduciamo che A,C sono vere. Ma per A,B,C vere la formula f(A,B,C ) ` e falsa, che contraddice il fatto che f(A,B,C ) doveva essere vera. Quindi la formula ¬(B⇒¬f(A,B,C ))⇒ (C⇒¬A) ` e una tautologia e pertanto ` e un teorema della teoriaL. (b) Sia Γ = {¬(C⇒¬ A),f (A,B,C )}. Usando la forma normale disgiuntiva otteniamo che f(A,B,C )≡ (A∧B∧ ¬C)∨ (¬A∧B∧C). Dal teorema di correttezza e completezza per refutazione per dimostrare che l’insieme Γ ` e insoddisfacibile occorre verificare che Γ c⊢R □. Si ricava che Γ c ={{A},{B},{C},{A,C},{¬A,¬C}}. Da {A} e {¬A,¬C} otteniamo{¬C} che con{C} permette di ricavare la clausola vuota. 2. (11 punti) a) 2 punti; b) 3 punti; c) 3 punti; d) 3 punti. Sia R⊆X×X, con X ={a,b,c,d,e,f } la relazione binaria rappresentata dal seguente grafo: a b c d e f (a) Si provi che non esiste nessuna relazione d’ordine su X contenente R. Si dica, motivando la risposta, se R ` e…