07 07 2016

Pagina 1

LOGICA E ALGEBRA Recupero prima prova in itinere 7/7/2016 Esercizio 1 Scrivere la tavola di verità di una f.b.f f(A,B.C) da cui si deduca logicamente la formula  BA  e che sia deducibile da .CBA  Scrivere la formula f(A,B,C) facendo uso solo dei connettivi  e  . Dire se  CBA f(A,B,C) è un teorema di L. Provare che da f(A,B,C) si deduce  BA  usando la risoluzione. Esercizio 2 Sia P l’insieme dei numeri naturali primi e S = {pn| p P , n N } . In S si consideri la relazione così definita: x R y se e solo se esiste un primo p in P che divida sia x che y, con x e y elementi di S. 1. Si verifichi che R è una relazione d’equivalenza su S e se ne determinino le classi. 2. Si consideri l’applicazione f da S a P definita da f (s) = p se s = p n e s i verifichi che R S è in corrispondenza biunivoca con P. 3. Si definisca in R S la relazione T ponendo [ p ] T [ _ p ] se e solo se p ≤ _ p con p , _ p P, e si mostri che T è una relazione d’ordine in R S . 4. Si dica se R S rispetto a T ammette massimo e minimo e se R S rispetto a T è un reticolo. Motivare ogni risposta data Soluzione Esercizio 1 La formula f(A,B,C) deve avere tutti i modelli di CBA  e tutti i suoi modelli devono essere modelli di  BA  . Pertanto quando v( A) = v(B) = 0 e v( C) = 1 si deve avere v(f( A,B,C)) = 1, inoltre deve essere v(f(A,B,C)) = 0 ogniqualvolta  BA  vale 0, ovvero se v( A) = v(B) = 1. Poiché  BA  è conseguenza semantica di CBA  , una qualsiasi di queste due formule può essere scelta come f(A,B,C). Una possibile scelta non banale per la tavola di verità di f(A,B,C) è A B C f(A,B,C) 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 da cui f(A,B,C)  (ABC)(ABC)  AB  (AB). La formula  CBA f(A,B,C) è un teorema di L in quanto…