Soluzioneprovadel19giugno2021

Pagina 1

Esame di Logica e Algebra-Giugno 2021 Durata della prova: 1h 30’ 1. (Punteggio: 9) Usando la risoluzione per la logica del primo ordine dedurre che se una relazione binaria R⊆ X× X soddisfa le seguenti propriet` a: i) Se x ` e in relazioneR con un elemento y, allora y ` e in relazione con se stesso (cio` e (y, y)∈ R); ii) Esiste un elemento x tale che non ` e in relazioneR con se stesso; allora: iii) Esiste un elemento y tale che nessun x ` e in relazioneR con questo y (cio` e (x, y) /∈ R). Soluzione: Sia R(x, y) la lettera predicativa che interpreta la relazione binaria R, allora: a) ∀x∀y (R(x, y)⇒ R(y, y)); b) ∃x¬R(x, x); c) ∃y∀x¬R(x, y) Verifichiamo usando il teorema di correttezza e completezza per refutazione che a), b) ⊨ c). Dalla prima formula ri- caviamo la clausola{¬R(x, y), R(y, y)}, mentre dalla seconda formula portata in forma di Skolem ricaviamo la clausola {¬R(a, a)}, dove a ` e la nuova costante che aggiungiamo quando Skolemizziamo b). Infine neghiamo c) ottenendo ¬∃ y∀x¬R(x, y)≡∀ y∃x R(x, y), la sua forma di Skolem ` e∀yR(f(y), y), dove f(y) ` e una nuova lettera funzionale che aggiungiamo durante la Skolemizzazione. Da questa formula, la clausola che otteniamo ` e {R(f(y), y)}. Mostriamo che{{¬R(x, y), R(y, y)},{¬R(a, a)},{R(f(y1), y1)}}⊢ R □. Infatti da {¬R(x, y), R(y, y)},{¬R(a, a)} usando la sosti- tuzione a/y, otteniamo la clausola {¬R(x, a)} da quest’ultima clausola insieme a {R(f(y1), y1)} con la sostituzione a/y1, f(a)/x otteniamo la clausola vuota □. 2. (Punteggio: 12) a) 3 punti b) 2 punti c) 3 punti d) 4 punti Sia R⊆ X× X, con X ={a, b, c, d, e, f} la relazione cos` ı definita: R ={(a, d), (b, a), (c, a), (d, d), (e, f)} (a) Disegnare il grafo d’adiacenza della chiusura d’equivalenzaT della relazione R. Si determinino le classi d’equivalenza di…