Soluzionedellaprovadell26230393B11settembre2020

Page 1

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – Appello telematico 11 settembre 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. Sia f(A,B,C ) una f.b.f della teoria L che assume valore 1 solo nelle due interpretazioni v1,v 2 tali che v1(A) =v1(B) = 1 e v 1(C) = 0 v2(A) = 0 e v 2(B) =v2(C) = 1 (a) Scrivere una formula f(A,B,C ) che rispetti le condizioni assegnate. (b) Dire se la formula (¬A⇒B)⇒ (C⇒¬f(A,B,C )) ` e un teorema della teriaL. (c) Provare lo stesso risultato del punto precedente usando la risoluzione. Soluzione: a) Possiamo costruire una formula f(A,B,C ) in forma normale disgiuntiva:f(A,B,C )≡ (A∧B∧¬C)∨(¬A∧B∧C). b) Dal teorema di correttezza e completezza della teoria L, abbiamo che ⊢L (¬A⇒ B)⇒ (C⇒¬ f(A,B,C )) se e solo se ⊨ (¬A⇒ B)⇒ (C⇒¬ f(A,B,C )) e questo equivale a dire che la formula ` e una tautologia. Scrivendo la tavola di verit` a di (¬A⇒B)⇒ (C⇒¬f(A,B,C )) si verifica che tale formula non ` e una tautologia e quindi non ` e un teorema della teoriaL. Infatti dalla tavola di verit` a si pu` o facilmente verificare che l’unico modello della formula ` e l’interpretazionev tale che v1(A) = 0 e v 1(B) =v1(C) = 1 e pertanto la formula data ` e equivalente a A∨¬B∨¬C. c) Proviamo lo stesso risultato di prima mediante la risoluzione. Dal punto precedente sappiamo che dobbiamo verificare che la formula (¬A⇒¬B)⇒ (C⇒¬f(A,B,C )) non ` e una tautologia e…