Soluzionedellaprovadel5luglio2018

Page 1

LOGICA E ALGEBRA 5 luglio 2018 Esercizio 1 Sia R la relazione binaria sull’insieme {a; b; c; d; e; f} definita nel seguente modo: R = {(b, a); (b, d); (c, d); (c, e); (c, f); (d, a); (d, e); (f, a)} a) Stabilire se R è antisimmetrica e se è una relazione d'ordine. b) Verificare se esiste una relazione d'ordine che contiene R. c) Sia S la più piccola relazione d'ordine contenente R. Costruire il diagramma di Hasse di S e determinare se S ammette massimo e/o minimo, elementi massimali e/o elementi minimali. d) Determinare il diagramma di Hasse di una relazione d'ordine totale contenente S. e) Dimostrare che non esistono funzioni contenute in R né funzioni contenenti R. Esercizio 2 Sia f(A,B,C) una f.b.f che assume i seguenti valori di verità: A B C f (A, B, C ) ___________________________________ 1 1 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 a) Si completi la tavola di verità di f(A,B,C) in modo tale che dall’insieme di f.b.f. {  AB, BC} non si deduca f(A,B,C) ma da f(A,B,C) si deduca A  C. b) Si scriva la formula ottenuta f(A,B,C) utilizzando solo i connettivi  e . c) Si verifichi usando la risoluzione che da {  AB, BC} non si deduce f(A,B,C). Esercizio 3 Sia f : N → N la funzione così definita: xxfNx 2)(  dove N è l’insieme dei numeri naturali. a) Dimostrare che f è un monomorfismo di (N, +) in (N, ·). E’ anche un isomorfismo? b) Tradurre in un opportuno linguaggio del primo ordine la seguente frase: “Se g è un omomorfismo da (N, +) ad (N, +), allora la funzione composta g · f è un omomorfismo da (N, +) ad (N, ·)” Il dominio da considerare dev’essere l’insieme dei numeri naturali N e le due funzioni f e g devono essere interpretate da due lettere funzionali di arità 1. c) Si porti la formula trovata in forma normale prenessa e poi in forma di Skolem. d)…