Soluzionedellaprovadel15luglio2019

Pagina 1

1 Durata della prova: 1 h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 15 luglio 2019 Cognome: Nome: Matricola: Tutte le risposte devono essere motivate. Gli esercizi vanno svolti su questi fogli, nello spazio sotto il testo e sul retro. I fogli di brutta non devono essere consegnati. I compiti privi di indicazione leggibile di nome e cognome non verranno corretti. Esercizio 1 Data la formula (A  C) ( C B), 1) semplificarla e trasformarla in una che contenga solo i connettivi {, } ; 2) provare che è un teorema di L sia per via semantica, sia utilizzando la teoria della risoluzione; 3) utilizzando il risultato precedente verificare che la formula ben formata del primo ordine   (  è logicamente valida. Svolgimento 1) (A  C) ( C B) ≡  (A  C)  (C  B) ≡  A   C  C  B ≡  C  C ≡  (C  C) 2) Poichè la formula data è equivalente a  C  C che è una tautologia, per il teorema di corretteza e completezza segue che la formula assegnata è un teorema di L. La forma a clausole della negazione della formula assegnata è C  C quindi si ottengono le clausole { C } e { C } la cui risolvente è proprio la clausola vuota. Ciò conferma che la formula assegnata è un teorema di L. 3) La f.b.f.   (  è logicamente valida in quanto è un esempio di tautologia. Infatti si ottiene a partire dalla tautologia (A  C) ( C B) effettuando le seguenti sostituzioni:  A  C   B 2 Esercizio 2 Si consideri l’insieme X = a,b,c,d,e e la relazione binaria R su X rappresentata dal grafo 1) Si provi che R è transitiva e che non esiste nessuna relazione d’ordine su X contenente R. 2) Si costruisca la relazione di equivalenza S generata da R e si determini l’insieme quoziente X / S. 3) Si stabilisca se S coincide con la chiusura simmetrica…