Soluzioneprovadel25gennaio2021

Pagina 1

Durata della prova: 1h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 25 Gennaio 2021 Docente: Cognome: Nome: Matricola: T utte 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. 1. (a) Si costruisca una formula F(A,B,C ) nella logica proposizionale sulle lettere enunciative A,B,C che abbia sola- mente i tre modelli ν1,ν 2,ν 3 con ν1(A) =ν1(B) =ν(C) = 1, ν2(A) = 1,ν 2(B) =ν2(C) = 0, ν3(A) = 0,ν 3(B) = ν3(C) = 1. (b) Mostrare sia per via semantica che usando la risoluzione che F(A,B,C ) ⊨ (B∨¬C). Soluzioni: (a) Usando la forma normale disgiuntiva una formula che ha i modelli descritti nell’esercizio ` e ( A∧B∧C)∨ (A∧ ¬B∧¬C)∨ (¬A∧B∧C). (b) Per via semantica. Dire che F(A,B,C ) ⊨ (B∨¬C) equivale a dire che tutti i modelli di F(A,B,C ) sono anche modelli di (B∨¬C) ora i modelli diF(A,B,C ) sonoν1,ν 2,ν 3 conν1(A) =ν1(B) =ν(C) = 1,ν2(A) = 1,ν 2(B) = ν2(C) = 0, ν3(A) = 0,ν 3(B) = ν3(C) = 1, ed ` e facile vedere che sono anche modelli di ( B∨¬C). Mediante la risoluzione, dobbiamo mostrare che {(A∧B∧C)∨ (A∧¬B∧¬C)∨ (¬A∧B∧C),¬B∧C}c⊢R □ ora l’insieme di clausole contiene sicuramente {¬B},{C},{B,¬C}, ed ` e facile vedere che{B} ` e una risolvente tra le ultime due clausole e quindi la clausola vuota si ottiene come risolvente di {¬B}, e{B}. 2. Si consideri la relazione binaria R sull’insieme X ={a,b,c,d,e } definita dalla seguente matrice di incidenza   0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1   (a) R ` e una funzione daX in X? In caso, disegnare il grafo d’adiacenza della relazione Ker(R) e calcolare l’insieme quozienteX/Ker(R). (b)…