Soluzionedellaprovadel27luglio2020

Page 1

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – Appello telematico Luglio 2020 Tutte le risposte devono essere motivate. Gli esercizi vanno svolti in bella copia su fogli numerati e poi scannerizzati con lo stesso ordine di svolgimento dell’esame. Il primo foglio deve contenere nome cognome e matricola. Il numero massimo di fogli ammessi ` e di 6 pagine. Il file da caricare deve essere in formato pdf e quando lo salvate sul vostro OneDrive va nominato come ”vostro-codice-persona”. 1. (a) Scrivere una formula f(A,B,C ) che ammetta la tavola di verit` a qui a fianco. (b) Argomentando bene la risposta, dire se ¬A∧ C ⊢L f(A,B,C ) usando la risoluzione. (c) Scrivere una formula g(A,B,C ) non equivalente a f(A,B,C ) che non sia una tautologia tale che {f(A,B,C ),¬g(A,B,C )} sia un insieme di formule insoddis- facibile. A B C f(A,B,C ) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 Soluzione: a) Dato che il numero di “1” presenti nella tabella ` e minore del numero di “0”, possiamo costruire una formula f(A,B,C) in forma normale disgiuntiva: f(A,B,C )≡ (¬A∧¬B∧C)∨ (¬A∧B∧C)∨ (A∧¬B∧C). b) Dal teorema di correttezza e completezza della teoria L, abbiamo che ¬A∧C⊢L f(A,B,C ) se e solo se ¬A∧ C ⊨ f(A,B,C ) e questo ` e equivalente a dire che l’insieme di formule {¬A∧C,¬f(A,B,C )} ` e insoddisfacibile. Dal teorema di correttezza e completezza per refutazione abbiamo che {¬A∧C,¬f(A,B,C )} ` e insoddisfacibile se e solo se dall’insieme di clausole {¬A∧C,¬f(A,B,C )}c che si ottengono da questo insieme di formule si ottiene la clausola vuota per risoluzione. Calcoliamo{¬A∧C,¬f(A,B,C )}c, da¬f(A,B,C ) ricaviamo le clausole {A,B,¬C},{A,¬B,¬C},{¬A,B,¬C}, e dalla prima formula ricaviamo le clausole{¬A},{C}. Un possibile…