Durata della prova: 1h 30’

Esame di Logica e Algebra – 16/06/2025

Docente e Lab. pregresso Cognome: Nome: Codice persona:

Tutte le risposte devono essere motivate e parte della valutazione è dedicata a come si espone la soluzione.
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.

1. (Punteggio: (a)2, (b)2, (c)2, (d)2, (e)1)

Data la seguente tavola di verità
A B C f(A,B,C)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

(a) Scrivere una formula f(A,B,C) che abbia tale tavola di verità.
(b) Dire, giustificando la risposta, se ∼ A ∧ B ⊢L f (A, B, C).
(c) Dimostrare il risultato ottenuto utilizzando la risoluzione.
(d) Scrivere una formula g(A, B, C) non equivalente a f (A, B, C) che non sia una tautologia e che sia costituita da
una sola lettera enunciativa tale che {f (A, B, C), ∼ g(A, B, C)} sia un insieme di formule insoddisfacibile.
(e) Nella formula f (A, B, C) ⇒ g(A, B, C) sostituire ogni occorrenza di A, di B e di C rispettivamente con le formule
del primo ordine ∀xA(x), ∃yB(x, y), C(x, y) e dire se la formula cosı̀ ottenuta è una formula logicamente valida.

Soluzioni:
(a) Identifichiamo le righe in cui f (A, B, C) vale 1: (0,1,0), (0,1,1), (1,1,0). La DNF è la seguente:
(∼ A ∧ B∧ ∼ C) ∨ (∼ A ∧ B ∧ C) ∨ (A ∧ B∧ ∼ C).
Semplificando, si ottiene: f (A, B, C) = B ∧ (∼ A∨ ∼ C).
(b) Usando il teorema di deduzione sintattica e il teorema di correttezza e completezza, dobbiamo verificare se
l’implicazione (∼ A ∧ B) ⇒ f (A, B, C) è una tautologia. Quando la premessa ∼ A ∧ B è vera (cioè A=0 e
B=1), f (A, B, C) vale 1 sia per C=0 che per C=1. Quindi, l’implicazione è sempre vera, e ∼ A ∧ B ⊢L f (A, B, C)
è vero.
(c) Per dimostrare che ∼ A ∧ B ⊢L f (A, B, C), usando il teorema di correttezza e completezza per refutazione,
mostriamo che {∼ A ∧ B, ∼ f (A, B, C)} è insoddisfacibile. Le clausole ottenute da ∼ A ∧ B sono C1 = {∼ A}
e C2 = {B}. Risulta inoltre che ∼ f (A, B, C) ≡∼ (B ∧ (∼ A∨ ∼ C)) ≡∼ B ∨ (A ∧ C) e quindi si ottengono le
clausole: C3 = {∼ B, A} e C4 = {∼ B, C}. La risolvente di C2 e C3 su B è C5 = {A}, la risolvente di C1 e C5 su
A è □ (clausola vuota). La derivazione della clausola vuota dimostra l’insoddisfacibilità.
(d) Dobbiamo trovare una lettera enunciativa g tale che f (A, B, C) ⇒ g(A, B, C) sia una tautologia. Le righe in cui
f (A, B, C) = 1 sono (0,1,0), (0,1,1), (1,1,0). Se scegliamo g(A, B, C) = B, allora quando f (A, B, C) = 1, B è
sempre 1 quindi f (A, B, C) ⇒ g(A, B, C) è sempre vera. B non è una tautologia (è falsa quando B=0) e non è
equivalente a f (A, B, C) (es. per (1,1,1), B = 1 ma f (A, B, C) = 0).
(e) La formula della logica proposizionale f (A, B, C) ⇒ g(A, B, C) corrisponde a B ∧ (∼ A∨ ∼ C) ⇒ B ed è quindi
una tautologia. Sostituendo A, B, C rispettivamente con le formule del primo ordine ∀xA(x), ∃yB(x, y) e C(x, y),
si ottiene la formula seguente:
[∃yB(x, y) ∧ (∼ (∀xA(x))∨ ∼ (C(x, y)))] ⇒ ∃yB(x, y).
Questa formula è logicamente valida perché è un esempio di tautologia.
2. (Punteggio: (a)3, (b) 3, (c)3)
Sia M l’insieme delle matrici di adiacenza delle relazioni binarie su X = {a, b, c, d, e} che contengono la relazione
R = {(a, b), (c, a), (d, e)}.

(a) Si determini una matrice appartenente ad M che sia la matrice di adiacenza di una relazione d’equivalenza ρ su X
tale che nessuna altra matrice di M possa essere la matrice di adiacenza di una relazione d’equivalenza contenuta
in ρ e dire se tale matrice è unica. Scrivere le classi di equivalenza della relazione ρ.
(b) Dire se è possibile trovare in M la matrice di adiacenza di una funzione da X ad X ed in caso affermativo dire
quante sono tali matrici. Tra di esse c’è la matrice di adiacenza di una funzione invertibile?
(c) Tra le matrici di M sceglierne una in modo che sia matrice di adiacenza di una relazione d’ordine ≤ su X. Precisare
elementi massimali e minimali di X rispetto a tale relazione e dire se X è un reticolo rispetto alla relazione ≤.

Soluzione:
(a) La relazione ρ deve essere la chiusura di equivalenza di R. Per riflessività, simmetria e transitività, si ottengono
le classi di equivalenza {a, b, c} e {d, e}. La relazione ρ è:

ρ = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c), (d, d), (d, e), (e, d), (e, e)}

La matrice associata a ρ è unica in quanto è la chiusura di equivalenza di R.

 
1 1 1 0 0
1 1 1 0 0
 
Mρ =  1 1 1 0 0

0 0 0 1 1
0 0 0 1 1

(b) Una relazione è una funzione se ogni riga ha esattamente un 1. Data R, abbiamo f (a) = b, f (c) = a, f (d) = e.
Per f (b) ci sono 5 scelte e per f (e) ci sono 5 scelte (qualsiasi elemento di X), pertanto ci sono 5 × 5 = 25 matrici di
adiacenza di funzioni in M. Per una funzione invertibile (biiettiva), ogni riga e ogni colonna deve avere esattamente
un 1. Le assegnazioni obbligatorie sono f (a) = b, f (c) = a, f (d) = e. Gli elementi del dominio a cui assegnare
un’immagine sono {b, e} e gli elementi del codominio senza controimmagine sono {c, d}. Pertanto, per completare
una biiezione, si può scegliere uno dei seguenti due modi:
ˆ f (b) = c, f (e) = d.
ˆ f (b) = d, f (e) = c.
Segue che ci sono due matrici di adiacenza di funzioni invertibili in M.
(c) Chiudiamo riflessivamente e transitivamente aggiungendo ad R le seguenti coppie:
- Riflessività: {(a, a), (b, b), (c, c), (d, d), (e, e)}
- Transitività: {(c, b)} (da (c, a) e (a, b)).
Poiché la relazione ≤ ottenuta è ancora antisimmetrica risulta essere una relazione d’ordine avente la seguente
matrice:  
1 1 0 0 0
0 1 0 0 0
 
1 1 1 0 0
M≤ =  
0 0 0 1 1
0 0 0 0 1
Gli elementi minimali sono c e d mentre gli elementi massimali sono b ed e.
Il diagramma di Hasse è il seguente:
b

a e

c d

X non è un reticolo. Ad esempio, la coppia (a, d) non ha un estremo superiore (join) né un estremo inferiore
(meet), poiché gli elementi a e d appartengono a componenti disconnesse della relazione d’ordine parziale.
3. (Punteggio: (a)3, (b) 2+1, (c)2, (d)1, (e)3, (f) 1)
  
 1 a b 
Sia G = 0 1 c  a, b, c ∈ R , dove R è l’insieme dei numeri reali.
0 0 1
 

(a) Si verifichi che G è un gruppo rispetto al prodotto di matrici.

  
 1 a b 
(b) Si consideri il sottoinsieme H = 0 1 a a, b ∈ R di G e si dica se è un suo sottogruppo. In caso affermativo,
0 0 1
 
si dica se H è normale in G.
 
1 a b
(c) Si consideri ora l’applicazione f da (G, ·) a (R, +) cosı̀ definita: f : 0 1 c  → a − c. e si verifichi che f è un
0 0 1
omomorfismo di gruppi.
(d) Si mostri che la ker f -classe della matrice identica è H.
(e) Si consideri la seguente formula della logica del primo ordine ∀x∀y E(g(g(h(y), x), y), x) e si stabilisca se è vera,
falsa o soddisfacibile ma non vera nell’interpretazione che ha dominio il gruppo G, in cui la lettera predicativa
E si interpreti come l’uguaglianza, la lettera funzionale di arità due g come il prodotto tra matrici e la lettera
funzionale h di arità uno come l’inverso della matrice.
(f) Si dica se si tratta di una formula logicamente valida.

Soluzioni
   
1 a1 b1 1 a2 b2
(a) Siano M1 = 0 1 c1  e M2 = 0 1 c2  in G.
0 0 1 0 0 1
 
1 a1 + a2 b1 + a1 c2 + b2
ˆ Chiusura: M1 M2 = 0 1 c1 + c2 . Poiché a1 + a2 , b1 + a1 c2 + b2 , c1 + c2 ∈ R, M1 M2 ∈ G.
0 0 1
ˆ Associatività: il prodotto di matrici è associativo.
 
1 0 0
ˆ Elemento neutro: la matrice identità I = 0 1 0 è in G e M I = IM = M , per ogni M ∈ G.
0 0 1
   
1 a b 1 −a ac − b
ˆ Elemento inverso: L’inverso di M = 0 1 c  è M −1 = 0 1 −c . Poiché −a, ac − b, −c ∈ R,
0 0 1 0 0 1
M −1 ∈ G.
Dunque, G è un gruppo. Si poteva anche usare il criterio dei sottogruppi pensando (H, ·) come sottogruppo di
(GL3 (R), ·).
   
1 a1 b1 1 a2 b2
(b) H non è vuoto (contiene I). Siano M1 = 0 1 a1  e M2 = 0 1 a2  in H.
0 0 1 0 0 1
 
1 a1 + a2 b1 + a1 a2 + b2
ˆ Chiusura: M1 M2 = 0 1 a1 + a2 . La matrice risultante ha la forma richiesta (c = a), quindi
0 0 1
M1 M2 ∈ H.
1 −a a2 − b
   
1 a b
ˆ Inverso: per M = 0 1 a ∈ H, l’inverso è M −1 = 0 1 −a . Questa è della forma richiesta,
0 0 1 0 0 1
−1
quindi M ∈ H.
Dunque, H è un sottogruppo di G per il criterio di caratterizzazione dei sottogruppi. Per  verificare
 che H
1 x y
sia un sottogruppo normale, dobbiamo vedere se gHg −1 ⊆ H per ogni g ∈ G. Sia g = 0 1 z  ∈ G e
0 0 1
     
1 a b 1 −x xz − y 1 a y+b
h = 0 1 a ∈ H, inoltre g −1 = 0 1 −z . Effettuando i calcoli risulta che ghg −1 = 0 1 a .
0 0 1 0 0 1 0 0 1
Questa matrice è in H in quanto l’elemento (3, 2) è uguale all’elemento (1, 2) (entrambi a). Segue che H è un
sottogruppo normale di G.
  
1 a b
(c) L’applicazione f : G → R è definita da f 0 1 c  = a − c. Dobbiamo verificare che f (M1 M2 ) = f (M1 ) +
0 0 1
 
1 a1 + a2 b1 + a1 c2 + b2
f (M2 ). Essendo M1 M2 = 0 1 c1 + c2  segue che f (M1 M2 ) = (a1 +a2 )−(c1 +c2 ) = a1 +a2 −c1 −c2
0 0 1
= f (M1 ) + f (M2 ). Poiché f (M1 M2 ) = f (M1 ) + f (M2 ), f è un omomorfismo di gruppi.
(d) Il 
nucleo
 di f ,ovvero
 la ker(f )-classe della materice identica, è 
l’insieme
  matriciM ∈ G tali che f (M ) = 0R .
delle
1 a b  1 a b 
f 0 1 c  = a − c = 0 =⇒ a = c. Quindi [I]ker(f ) = 0 1 a a, b ∈ R . Questa è esattamente la
0 0 1 0 0 1
 
definizione del sottogruppo H.
(e) La formula ∀x∀y E(g(g(h(y), x), y), x) tradotta nell’interpretazione in cui E(u, v) è u = v, g(u, v) è u · v, h(u)
è u−1 diventa ∀x∀y ((y −1 · x) · y = x). Questa afferma che per ogni x, y ∈ G,y −1 xy = x, il chesignifica che
1 1 1 1 2 3
G è un gruppo abeliano. Il gruppo G non è abeliano, ad esempio presi x = 0 1 1 e y = 0 1 4 si
0 0 1 0 0 1
       
1 −2 5 1 1 3 1 1 3 1 1 1
ha che y −1 = 0 1 −4 e che (y −1 x)y = 0 1 1. Poiché 0 1 1 ̸= 0 1 1, la formula è falsa
0 0 1 0 0 1 0 0 1 0 0 1
nell’interpretazione data.
(f) Una formula è logicamente valida se è vera in ogni interpretazione. Poiché abbiamo dimostrato che la formula è
falsa in almeno un’interpretazione specifica (quella data nel punto e), la formula non è logicamente valida.
PAGINE EXTRA (Riferirsi all’esercizio e al punto che si intende svolgere in queste pagine)