Soluzionedellaprovadel26luglio2018

Page 1

LOGICA E ALGEBRA 26 luglio 2018 Esercizio 1 Sia X = {1, 2, 3, 4, 5} e sia R  X  X la relazione avente la matrice di incidenza M quadrata di ordine 5 con tutti gli elementi nulli tranne m11 = m12 = m22 = m34 = m54 = 1 e m21= k ∊ {0,1}. a) Si mostri che R è una relazione transitiva su X. b) Al variare di k ∊ {0,1} si determini, se esiste, una relazione d’ordine T su X che contenga R. In caso affermativo la si costruisca e si determinino gli elementi massimali e minimali di X rispetto a T. c) Nel caso k = 1 si determini la relazione d’equivalenza S generata da R e si descriva X / S. Si stabilisca se S coincide con la chiusura riflessiva e simmetrica di R. Esercizio 2 Sia f (A,B,C) la f.b.f. avente la seguente tavola di verità: A B C f (A,B,C ) _________________________________________ 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 a) Dire se esiste nella teoria L una deduzione di C  f (A,B,C) dall’insieme {A, B}. b) Provare il risultato ottenuto al punto precedente utilizzando la risoluzione. Esercizio 3 a) Si scriva in un opportuno linguaggio del primo ordine la seguente proposizione: « Due numeri interi sono congrui a zero modulo n se e solo se lo è la loro somma » Attenzione: oltre ai connettivi, le variabili, i quantificatori e le parentesi, s i usi solo una lettera predicativa U per la relazione di uguaglianza, una costante per denotare l’intero n, due lettere funzionali S e P per le operazioni di addizione e moltiplicazione tra interi. b) Si stabilisca se la formula ottenuta è vera nell’interpretazione assegnata e se è logicamente valida. c) Sia, ora, A = Zn l’anello degli interi modulo n ed a un suo elemento. Si verifichi che l’insieme H a = {x ∊ A | x · a = [0]n} è un sottoanello di A. E’ anche un suo ideale? TRACCIA DI SOLUZIONE Esercizio 1 a)…