Soluzionedellaprovadel15giugno2019

Pagina 1

1 Durata della prova: 1 h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 15 giugno 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 Si consideri la seguente tavola di verità: A B C f (A,B,C) 0 0 0 1 0 0 1 x 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 y 1 1 1 z con x, y, z {0; 1}. 1. Si attribuiscano ad x, y, z dei valori in modo tale che valgano contemporaneamente le due seguenti condizioni: A  B |-L f(A,B,C) f (A,B,C) | C(BA). 2. Si scriva una formula in cui compaiano solo i connettivi  e  e che abbia come tavola di verità quella che si ottiene sostituendo nella tavola data i valori di x, y, z trovati al punto precedente. 3. Si verifichi che f (A,B,C) | C(BA) usando la risoluzione. Svolgimento 1. Poiché i modelli della formula A  B sono gli ultimi due che compaiono nella tavola di verità assegnata, allora, affinchè valga la deduzione A  B |-L f(A,B,C) è necessario che y = z = 1. Per soddisfare la condizione f (A,B,C) | C(BA) è necessario che f (A,B,C) abbia un modello in corrispondenza del quale la f.b.f. C(BA) sia falsa e ciò può accadere solo se x = 1. 2. Risulta: f (A,B,C) ≡ (~A  ~B  ~C)  (~A  ~B  C)  (A  B  ~C)  (A  B  C) ≡ ((~A  ~B)  (~C C))  ((A  B)  (~C  C)) ≡ (~A  ~B )  (A  B ) ≡ ~(~A  ~B )  (A  B ) ≡ A  B  ~(A  ~B ) ≡ (~A  B)  ~(A  ~B ) 3. Trasformiamo le formule f (A,B,C) e ~(C(BA)) in forma a clausole: f (A,B,C) ≡ (~A  ~B )  (A  B ) ≡ (~A  (A  B ))  (~B  (A  B )) ≡ (~A  B)  (~B  A) ~(C(BA)) ≡ ~(~C  B  A) ≡ C  ~B  ~A Si…