Computer Engineering - Logica e Algebra

Full exam

Esame di Logica e Algebra-Giugno 2021 Durata della prova: 1h 30' 1.(Punteggio: 9)Usando la risoluzione per la logica del primo ordine dedurre che se una relazione binariaRXXsoddisfa le seguenti proprieta: i)Sexe in relazioneRcon un elementoy, alloraye in relazione con se stesso (cioe (y; y)2R); ii)Esiste un elementoxtale che non e in relazioneRcon se stesso; allora: iii)Esiste un elementoytale che nessunxe in relazioneRcon questoy(cioe (x; y)= 2R). Soluzione:SiaR(x; y) la lettera predicativa che interpreta la relazione binariaR, allora: a)8x8y(R(x; y))R(y; y)); b)9x:R(x; x); c)9y8x:R(x; y) Verichiamo usando il teorema di correttezza e completezza per refutazione chea); b)c). Dalla prima formula ri- caviamo la clausolaf:R(x; y); R(y; y)g, mentre dalla seconda formula portata in forma di Skolem ricaviamo la clausola f:R(a; a)g, doveae la nuova costante che aggiungiamo quando Skolemizziamob). Inne neghiamoc) ottenendo : 9y8x:R(x; y) 8y9x R(x; y), la sua forma di Skolem e8yR(f(y); y), dovef(y) e una nuova lettera funzionale che aggiungiamo durante la Skolemizzazione. Da questa formula, la clausola che otteniamo efR(f(y); y)g. Mostriamo cheff:R(x; y); R(y; y)g;f:R(a; a)g;fR(f(y 1) ; y 1) gg ` R . Infatti daf:R(x; y); R(y; y)g;f:R(a; a)gusando la sosti- tuzionea=y, otteniamo la clausolaf:R(x; a)gda quest'ultima clausola insieme afR(f(y 1) ; y 1) gcon la sostituzione a=y1; f (a)=xotteniamo la clausola vuota. 2.(Punteggio: 12) a) 3 punti b) 2 punti c) 3 punti d) 4 punti SiaRXX, conX=fa; b; c; d; e; fgla relazione cos denita: R=f(a; d);(b; a);(c; a);(d; d);(e; f)g (a)Disegnare il grafo d'adiacenza della chiusura d'equivalenzaTdella relazioneR. Si determinino le classi d'equivalenza diT. (b)Quante funzioni contengonoR? Quante funzioni sono contenute inR? (c)Dire (motivando la risposta) se puo esistere la chiusura d'ordine diR, ed eventualmente disegnare il suo diagramma di Hasse, trovandone, se esistono, i punti di massimo, minimo, massimali e minimali. (d)Si consideri la seguente formula della logica del primo ordine: F1= 8x8y8z((A(x; y)^A(z; y))) 9zA(y; z)) Si stabilisca seF 1e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominio l'insieme X e in cui la lettera predicativaA(x; y) e interpretata dalla relazioneRsuX.F 1e logicamente valida o logicamente contradditoria? Soluzione:(a)Ricordiamo che per chiudere transitivamente basta completare le clique del grafo d'adiacenza diR, quindi otteni- amo che il grafo d'adiacenza diTe:a bc de f Le classi di equivalenza sono quindi [ b] T= fa; b; c; dg, e [e] T= fe; fg. (b)La matrice d'adiacenza diRe la seguente: 0 B B B B B B @0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 01 C C C C C C A nessuna relazione e contenuta inRpoiche l'elementofnon e in relazione con nessun elemento (l'ultima riga ha tutti valori nulli). Mentre, le funzioni che possono contenereRsono 6 dato che le prime 5 righe della matrice sono tutte occupate con un unico 1 e quindi non ho scelte possibili da fare, mentre l'ultima riga essendo vuota posso aggiungere un uno in una posizione arbitraria, e quindi ho 6 scelte. (c)Dato cheRe antisimmetrica, potrebbe esistere la sua chiusura d'ordine, chiudiamoRri essivamente e transiti- vamente ottenendo la relazioneHdescritta dal seguente grafo d'adiacenza:a bc de f che rimane antisimmetrica, e quindi He la chiusura d'ordine diR. Il suo diagramma di Hasse e il seguente:d a c bef Non ci sono ne massimi ne minimi, l'insieme dei massimali e fd; fg, l'insieme dei minimali efc; b; eg. (d)La formula e chiusa, quindi puo essere o vera o falsa, ma non soddiscibile ma non vera. Nell'interpretazionedata la formula e falsa, dato che se si considerax=z=eey=fabbiamo che l'antecedente della formula e vero, mentre il conseguente9zA(y; z) no, dato che non esiste nessun elementoz2Xche soddis (f ; z)2R. Quindi la formula non e logicamente valida, ma nemmeno logicamente contraddittoria. Infatti basta mostrare una interpretazione in cui sia vera. In questo caso, basta rendere il consequente della formula sempre vero, per esempio interpretandoA(x; y) come una qualunque relazione ri essiva (o anche seriale). 3.(Punteggio: 10) a) 4 punti b) 2 punti c) 4 punti Sia (A;+;
) un anello con unita (unitario). Si consideri suAuna nuova operazione?cos denita 8a; b2A:a ? b=a+b+a
b (a)Si provi che (A; ?) e un monoide. (b)Si consideri l'applicazionef: (A; ?)!(A;
) cos denita 8a2A:f(a) =a+e doveee l'unita dell'anelloA. Provare chefe un isomorsmo tra il monoide (A; ?) e il monoide (A;
). (c)Si consideri la seguente formula della logica del primo ordine: F2= 8x8y8z(E(f(x; s(y; z)); s(f(x; y); f(x; z))) ) Si stabilisca seF 2e vera, falsa o soddisfacibile ma non vera nell'interpretazione avente come dominio l'insieme A e in cui la lettera predicativaE(x; y) e interpretata dalla relazione di uguaglianza suA, mentref(x; y) interpreta l'operazione?descritta sopra, es(x; y) l'operazione di somma + dell'anello (A;+;
).F 2e logicamente valida o logicamente contradditoria? Soluzione: (a)Dato che non c'e scritto nel testo, dobbiamo prima vericare che?sia interna. Ma questo e ovvio perche essendo Aun anello abbiamo chea+b+ (a
b) e per denizione un elemento diAper ogni coppiaa; b2A. Per vericare che sia un semigruppo, verichiamo che sia associativa. Usando la denizione e le proprieta distributive dell'anello Aotteniamo le seguenti due uguaglianze: a ?(b ? c) =a ?(b+c+b
c) =a+ (b+c+b
c) +a
(b+c+b
c) =a+b+c+a
b+a
c+b
c+a
b
c (a ? b)? c= (a+b+a
b)? c=a+b+a
b+c+ (a+b+a
b)
c=a+b+c+a
b+a
c+b
c+a
b
c dove ovviamente si e usata la commutativita di + essendoAun anello. L'elemento neutro di?e lo 0 dell'anello, infattia ?0 =a+ 0 + (a
0) =a+ 0 + 0 =ae similmente 0? a=a(oppure si dimostra che?e commutativa, ma non e richiesto nell'esercizio). (b)Mostriamo prima chefe un omomorsmo. Abbiamo che f(a ? b) =f(a+b+a
b) =a+b+a
b+e che dobbiamo confrontare conf(a)
f(b) = (a+e)
(b+e) =a
b+a
e+e
b+e
e=a+b+a
b+e dove si e usata la distributivita della moltiplicazione rispetto all'addizione e il fatto cheee l'elemento neutro della moltiplicazione
. Da queste uguaglianze deduciamo chef(a ? b) =f(a)
f(b), quindife un omomorsmo di semigrouppi. Per mostrare che e un omomorsmo anche di monoidi dobbiamo mostrare chef(0) =e, ma questo e banale dato chef(0) = 0 +e=e. Per mostrare che sia un isomorsmo, mostriamo che e iniettiva, infatti f(a) =f(b) implica chea+e=b+eche implicaa=bdato che (A;+) e un gruppo. Inoltrefe suriettiva infatti, per ognia2A,fmandaa+ (e) ina, infattif(a+ (e)) = (a+ (e)) +e=a. (c)Anche in questo caso la formula e chiusa, quindi e vera o falsa. In questa interpretazione la formula aerma cheper ognix; y; zvale la distributivita di?rispetto all'addizione:x ?(y+z) =x ? y+x ? z. In questo caso la formula non e vera infattix ?(y+z) =x+ (y+z) +x
(y+z) =x+y+z+x
y+x
z mentre con un calcolo simile:x ? y+x ? z=x+y+x
y+x+z+x
z Queste ultime due uguaglianze forniscono lo stesso risultato se e solo sex= 0 e quindi non sempre. Segue che la formula e falsa nell'interpretazione assegnata e pertanto non e logicamente valida. Non e neppure contraddi- toria dato che esprime la legge di distributivita, quindi basta interpretare la lettera funzionalef(x; y) come la moltiplicazione
che sappiamo essere distributiva rispetto all'addizione.