05 02 2016

Page 1

LOGICA E ALGEBRA 5 febbraio 2016 Parte di Logica Esercizio 1 In logica proposizionale siano A,B,C le formule di un opportuno linguaggio proposizionale che traducono le frasi “Se Carlo ha vinto la gara, allora Mario è arrivato secondo e Sergio è arrivato terzo”, “Mario non è arrivato secondo”, ”Carlo non ha vinto la gara” rispettivamente. 1. Dire se {A,B}|-LC 2. Ritrovare il risultato precedente facendo uso della risoluzione. Esercizio 2 Si consideri la seguente formula F 1. Si dica se la formula è vera, falsa soddisfacibile ma non vera quando si prenda come dominio l’insieme N dei naturali (0 incluso), si interpretino la lettera funzionale come l’operazione che restituisce il successivo, la lettera funzionale come l’operazione di somma, il predicato come x < y e il predicato come x ≤ y 2. Si porti F in forma prenessa, se ne scrivano le chiusure esistenziale ed universale e si discuta la loro verità/falsità nell’interpretazione data. 3. Si scriva una formula con lo stesso significato di F nell’interpretazione data, utilizzando un linguaggio del primo ordine in cui si hanno a disposizione la lettera funzionale , i predicati e e il predicato che indica che y è il successivo di x. Giustificare ogni risposta Traccia di soluzione Esercizio 1 Usiamo le seguenti lettere enunciative: A: “Carlo ha vinto la gara” B: “Mario è arrivato secondo” C: “Sergio è arrivato terzo” 1. La frase A diventa A  B  C, la frase B è B e infine C è A. Per il teorema di correttezza e completezza forte {A,B}|-LC se e solo se {A,B}|=C, pertanto se e solo se ogni modello di{A,B} è modello di C. Affinché v sia un modello di {A,B} deve essere v(B) = 1 e quindi v(B) = 0. Ciò implica che v(BC) = 0 e dunque anche v(A) = 0 dovendo risultare v(A) = 1. Segue che v(A) = 1 e pertanto v(C) = 1. 2. Come già…