09 05 2014

Page 1

LOGICA E ALGEBRA Prima prova in itinere 9 maggio 2014 Esercizio 1 1. Si mostri se valgono in L le seguenti deduzioni a. A, B¬├L (BCA ⇒⇒) b. A, C¬├L (BCA ⇒⇒) 2. Si provino i risultati ottenuti mediante la risoluzione. 3. Nel caso in cui una deduzione valga, si dica se per la stessa esiste una risoluzione lineare per input. Esercizio 2 Sia A = {1, 2, 3, 4, 5, 6} e si denoti con ρ la relazione di divisibilità su A, ovvero dati a1, a2,A∈ a1 ρ a2 ⇔ a1divide a2. 1. Si scriva la matrice di incidenza di ρ e si stabilisca se ρ è una funzione. In caso negativo si dica quante sono le funzioni contenute in essa e quante di esse non sono biunivoche. 2. Si disegni il diagramma di Hasse di ρ e si determinino, se esistono, elementi massimali, minimali, massimo e minimo di A rispetto a ρ. 3. (A, ρ) è un reticolo? In caso negativo si esibisca un esempio di relazione d’ordine σ su A che non sia totale, che contenga ρ e tale che (A, σ) sia un reticolo. 4. Si determini la chiusura simmetrica di ρ e si dica se è una relazione d’equivalenza. 5. Dimostrare che se A è un generico insieme, date due qualsiasi relazioni d’equivalenza21,RR su A, la relazione binaria τ su AA× definita nel seguente modo: )),(),((),(),,( 21 dRbcRadcbaAAdcba ∧⇔×∈∀ τ è una relazione d’equivalenza. TRACCIA DI SOLUZIONE Esercizio 1 1. Per il teorema di correttezza (versione forte) se in L vale la deduzione A,¬B |-L (A⇒C)⇒B, deve essere anche A,¬B |= (A⇒C)⇒B. L’unico modello di { A,¬B} assegna ad A il valore 1 e a B il valore 0, ma non soddisfa (A⇒C)⇒B, in quanto se diamo a C il valore 1 la formula vale 0. Pertanto non c’è la deduzione semantica e neppure la deduzione in L. Analogamente sempre per il teorema di correttezza (versione forte) se in L vale la deduzione A,¬C |-L (A⇒C)⇒B, deve essere anche A,¬C |= (A⇒C)⇒B.…