Computer Engineering - Logica e Algebra

Full exam

1 Durata della prova: 1 h 30’ Esame di Logica e Algebra Politecnico di Milano – In gegneria 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 d i 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 ass egnata è 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 della chi usura riflessiva e transitiva T di R . 4) Si consideri no le seguente formule della logica del primo ordine : (x,y) ˄ (y, z))  (x,z)) ˄ ( x)( y) ( (x,y) ˄ (y, z))  (x, y)) b) ( x) (y) (x, y) ˄ (x, y)  (y, x)) Si stabilisca se a) è vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominio l’insieme X e in cui la lettera predicativa è interpretata dalla relazione R su X e la lettera predicativa è interpretata dalla relazione di uguaglianza. Si stabilisca altresì se b) è vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominio l’insi eme X e in cui la lettera predicativa è interpretata dalla relazione S su X . Svolgimento 1) Scriviamo la matrice di incidenza di R e di R 2: Poiché si ha che R è transitiva. Inoltre non può esistere nessuna relazione d’ordine su X contenente R in quanto R non è antisimmetrica poiché, ad esempio, (a, b) ∊ R e (b, a) ∊ R. 2) Costruiamo la chiusura riflessiva a simmetrica V di R: e calcoliamo le potenze di V: 21A 22A                  0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 R M                  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 2R M R R 2                  1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 V M 3 Segue che e quindi l’insieme quoziente è X / S = {[a] S, [c] S}, con [a] S = {a, b} e [c] S = {c, d, e}. 3) Poiché R è già transitiva, la sua chiusura riflessiva e transitiva corrisponde alla chiusura riflessiva W di R: e quindi la chiusura simmetrica W’ di W è la seguente: che, come si può vedere, non coincide con S che invece è la chiusura transitiv a della chiusura riflessiva e simmetrica di R. 4) La formula a) è vera nell’interpretazione assegnata in quanto è data dalla congiunzione di due formule vere. Infatti la formula (x,y) ˄ (y, z))  (x,z)) è vera in quanto R soddisfa la proprietà transitiva . La f.b.f. ( x)( y)( (x,y) ˄ (y, z)) (x, y)) è anch’essa vera in quanto qualunque sia l ’assegnamento di valori a lla vari abile z, basta assegnare ad x ed y lo stesso valore per rend ere soddisfatto il conseguente e pertanto l ’intera implicazione è vera. La formula b) è falsa in quanto è data dalla congiunzione di due formule di cui la seconda è vera (esprime la proprietà simmetrica di S) mentre la prima è falsa. Infatti la sottoformula ( x)( y) (x, y) è falsa poiché non c’è nessun elemento che è in relazione con tutti gli altri. 3 2 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 V V M M                                    1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 S M                  1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 W M                  1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 W M 4 Esercizio 3 Si consideri il seguente sottoinsieme del gruppo GL(2, Q) delle matrici non singolari 2 × 2 a coefficienti razionali, (a) Si provi che G è un gruppo rispetto all’usuale prodotto di matrici. (b) Si stabilisca se G è gruppo abeliano. (c) Si scriva in un opportuno linguaggio del primo ordine, che contenga tra i suoi simboli u na lettera funzionale binaria f (x, y) e una lettera unaria g(x), una formula chiusa che dica che in un gruppo l’inverso del prodotto di due elementi è il prodotto degli inversi di ogni singolo elemento. (d) Si dica se si tratta di una formula logicamente valida e se può essere soddisfacibile ma non vera . Svolgimento (a) Poiché GL(2, Q) è un gruppo rispetto all’usuale prodotto di matrici e G è un suo sottoinsieme, per provare che G è un gruppo possiamo applicare il criterio di caratterizzazione dei sottogr uppi. Siano , allora l’inversa della matrice A è la matrice e quindi risulta: e quindi poiché la matrice ha gli elementi di posto (1,2) e (2,1) uguali e che, sommati tra di loro, danno come risultato l’elemento di posto (2,2). Per il criterio di caratterizzazione dei sottogruppi segue che G è sottogruppo di GL(2, Q) . (b) Siano , allora risulta: ed essendo segue che vale la proprietà commutativa e quindi G è un gruppo abeliano. (c) Introduciamo una lettera predicativa binaria E che interpreti la relazione di uguaglianza, una lettera funzionale binaria f che interpreti l’operazione di moltiplicazione fra gli elementi del gruppo e una lettera funzionale unaria g che interpreti la funzione che ad ogni elemento del gruppo associa il suo inverso. Allora la formula richiesta è la seguente: . (d) La formula trovata non è logicamente valida in quanto non è vera in un’interpretazione in cui il dominio è un gruppo non abeliano, infatti è noto dalla teoria che l’inverso del prodotto di due elementi di un gruppo è uguale al prodotto degli inversi dei due elementi scambiati di posto. Inoltre la formula trovata non può essere soddisfacibile ma non vera poiché si tratta di una formula chiusa. N.B .: per un errore materiale , nel testo dell ’esame non compariva il simbolo  nella definizione dell ’insieme G. Ovviamente nella correzione degli elaborati non si è tenuto conto di eventuali errori derivanti da tale fatto.                   0 0 , , : b a Q b a b a b b a G G b a b b a B b a b b a A                 ' ' ' ' ' ,               a b b b a b ab a A 2 2 1 1                                       ' ' ' ' ' ' ' ' ' ' 1 ' ' ' ' ' 1 2 2 2 2 1 ab aa bb ab ba ba ab bb ba aa b ab a b a b b a a b b b a b ab a B A G B A  1                  ' ' ' ' ' ' ' ' ' ' 1 2 2 ab aa bb ab ba ba ab bb ba aa b ab a G b a b b a B b a b b a A                 ' ' ' ' ' , A B b a b b a b a b b a bb ba ab aa bb bb ab ba bb ba ab bb aa b a b b a b a b b a B A                                               ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' A B B A    ))) ( ), ( ( )), , ( ( ( y g x g f y x f g Ey x 