Simulazione Esame 5 - LogicaUniPR

Esercizio 1 (Punti: 8) - Relazioni

Sia $R$ la relazione sull'insieme dei numeri interi $\mathbb{Z}$ così definita: $xRy \iff x-y$ è un numero pari. Verifica se $R$ è una relazione di equivalenza. Se lo è, descrivi le classi di equivalenza.
Sia $A = \{(0,0), (0,1), (1,0), (1,1)\}$. Sia $S$ la relazione lessicografica su $A$: $(x_1, y_1) S (x_2, y_2) \iff (x_1 < x_2) \lor (x_1 = x_2 \land y_1 \le y_2)$. Verifica se $S$ è una relazione d'ordine. È totale o parziale? Disegna il diagramma di Hasse. Identifica elementi minimali/massimali e minimo/massimo, se esistono.

Risposte Brevi:

Sì, $R$ è una relazione di equivalenza. Le classi di equivalenza sono due: l'insieme dei numeri pari e l'insieme dei numeri dispari.
Sì, $S$ è una relazione d'ordine totale. Minimo: (0,0). Massimo: (1,1). Minimali: {(0,0)}. Massimali: {(1,1)}. Il diagramma di Hasse è una catena: $(0,0) \to (0,1) \to (1,0) \to (1,1)$.

Svolgimento Dettagliato:

a) Relazione $xRy \iff x-y$ è pari, su $\mathbb{Z}$.

Riflessiva: $xRx \iff x-x$ è pari $\iff 0$ è pari. Vero.
Simmetrica: Se $xRy$, allora $x-y = 2k$ per qualche $k \in \mathbb{Z}$. Allora $y-x = -(x-y) = -2k = 2(-k)$. Poiché $-k \in \mathbb{Z}$, $y-x$ è pari. Quindi $yRx$. Vero.
Transitiva: Se $xRy$ e $yRz$. Allora $x-y = 2k_1$ e $y-z = 2k_2$ per $k_1, k_2 \in \mathbb{Z}$.
Sommando le due equazioni: $(x-y) + (y-z) = 2k_1 + 2k_2 \implies x-z = 2(k_1+k_2)$.
Poiché $k_1+k_2 \in \mathbb{Z}$, $x-z$ è pari. Quindi $xRz$. Vero.

$R$ è una relazione di equivalenza.
Le classi di equivalenza sono determinate dalla parità. Se $x-y$ è pari, significa che $x$ e $y$ hanno la stessa parità.
Classe 1: $[0]_R = \{z \in \mathbb{Z} \mid z-0 \text{ è pari}\} = \{z \in \mathbb{Z} \mid z \text{ è pari}\}$. L'insieme dei numeri pari.
Classe 2: $[1]_R = \{z \in \mathbb{Z} \mid z-1 \text{ è pari}\}$. Se $z-1=2k$, allora $z=2k+1$, quindi $z$ è dispari. L'insieme dei numeri dispari.
Ci sono due classi di equivalenza: i numeri pari e i numeri dispari.

b) Relazione lessicografica $S$ su $A = \{(0,0), (0,1), (1,0), (1,1)\}$.

Riflessiva: $(x_1, y_1) S (x_1, y_1) \iff (x_1 < x_1) \lor (x_1 = x_1 \land y_1 \le y_1)$.
$(F) \lor (V \land V) \implies F \lor V \implies V$. Vero.
Antisimmetrica: Se $(x_1, y_1) S (x_2, y_2)$ e $(x_2, y_2) S (x_1, y_1)$, allora $(x_1, y_1) = (x_2, y_2)$?
Se $x_1 < x_2$, allora $(x_2, y_2) S (x_1, y_1)$ non può valere (perché $x_2 \not< x_1$).
Quindi deve essere $x_1 = x_2$. Allora la condizione diventa $(x_1=x_1 \land y_1 \le y_2)$ e $(x_2=x_2 \land y_2 \le y_1)$.
Cioè $y_1 \le y_2$ e $y_2 \le y_1$. Questo implica $y_1=y_2$.
Poiché $x_1=x_2$ e $y_1=y_2$, allora $(x_1,y_1)=(x_2,y_2)$. Vero.
Transitiva: Se $(x_1, y_1) S (x_2, y_2)$ e $(x_2, y_2) S (x_3, y_3)$, allora $(x_1, y_1) S (x_3, y_3)$?
Si analizzano i vari casi basati su $<_x$ o $(=_x \land \le_y)$. La transitività dell'ordine lessicografico è una proprietà nota. Vero.

$S$ è una relazione d'ordine.
È totale? Sì, date due coppie qualsiasi $(x_1,y_1)$ e $(x_2,y_2)$ in $A$, o $x_1 < x_2$, o $x_1 > x_2$, o $x_1=x_2$. Se $x_1 < x_2$, allora $(x_1,y_1)S(x_2,y_2)$. Se $x_1 > x_2$, allora $(x_2,y_2)S(x_1,y_1)$. Se $x_1=x_2$, allora o $y_1 \le y_2$ (quindi $(x_1,y_1)S(x_2,y_2)$) o $y_2 < y_1$ (quindi $(x_2,y_2)S(x_1,y_1)$). Tutti gli elementi sono confrontabili. È un ordine **totale**.

Diagramma di Hasse: Poiché è un ordine totale, il diagramma di Hasse è una catena lineare.
L'ordine è: $(0,0) < (0,1) < (1,0) < (1,1)$.

(1,1)
  |
(1,0)
  |
(0,1)
  |
(0,0)

Minimali: $\{(0,0)\}$.
Minimo: $(0,0)$.
Massimali: $\{(1,1)\}$.
Massimo: $(1,1)$.

Esercizio 2 (Punti: 9) - Induzione

Dimostrare per induzione che $\sum_{i=1}^{n} (3i^2 - 3i + 1) = n^3$ per ogni $n \ge 1$.

Esercizio 3 (Punti: 8) - Combinatoria

In un'urna ci sono 5 palline Rosse (R), 4 Blu (B) e 3 Verdi (V), tutte distinguibili tra loro all'interno dello stesso colore (es. R1, R2,...).

In quanti modi si possono estrarre 3 palline in modo che siano tutte dello stesso colore?
In quanti modi si possono estrarre 3 palline in modo che siano tutte di colori diversi?
Qual è il coefficiente di $a^4b^2$ nello sviluppo di $(a - 2b)^6$?

Risposte Brevi:

$\binom{5}{3} + \binom{4}{3} + \binom{3}{3} = 10 + 4 + 1 = 15$
$\binom{5}{1} \cdot \binom{4}{1} \cdot \binom{3}{1} = 5 \cdot 4 \cdot 3 = 60$
$\binom{6}{2} (a)^4 (-2b)^2 = 15 \cdot a^4 \cdot 4b^2 = 60 a^4 b^2$. Il coefficiente è 60.

Svolgimento Dettagliato:

Abbiamo 5R, 4B, 3V. L'ordine di estrazione non conta (si forma un gruppo di 3 palline).

a) 3 palline tutte dello stesso colore:

Usiamo il principio della somma, poiché i casi sono disgiunti.

Caso 1: 3 Rosse. Modi: $\binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \cdot 4}{2} = 10$.
Caso 2: 3 Blu. Modi: $\binom{4}{3} = \binom{4}{1} = 4$.
Caso 3: 3 Verdi. Modi: $\binom{3}{3} = 1$.

Totale modi = $10 + 4 + 1 = 15$.

b) 3 palline tutte di colori diversi:

Dobbiamo scegliere 1 Rossa E 1 Blu E 1 Verde. Usiamo il principio del prodotto.

Modi per scegliere 1 Rossa da 5: $\binom{5}{1} = 5$.
Modi per scegliere 1 Blu da 4: $\binom{4}{1} = 4$.
Modi per scegliere 1 Verde da 3: $\binom{3}{1} = 3$.

Totale modi = $5 \cdot 4 \cdot 3 = 60$.

c) Coefficiente di $a^4b^2$ nello sviluppo di $(a - 2b)^6$:

Usiamo il Teorema Binomiale: $(X+Y)^n = \sum_{k=0}^{n} \binom{n}{k} X^{n-k} Y^k$.
Nel nostro caso, $X = a$, $Y = -2b$, e $n=6$.
Vogliamo il termine in cui la potenza di $b$ è 2, quindi $Y^k = (-2b)^2 \implies k=2$.
La potenza di $X$ sarà $n-k = 6-2 = 4$.
Il termine generico è $\binom{6}{k} (a)^{6-k} (-2b)^k$.
Per $k=2$, il termine è $\binom{6}{2} (a)^{6-2} (-2b)^2 = \binom{6}{2} a^4 (-2b)^2$.
Calcoliamo $\binom{6}{2} = \frac{6!}{2!(6-2)!} = \frac{6!}{2!4!} = \frac{6 \cdot 5}{2 \cdot 1} = 15$.
Il termine è $15 \cdot a^4 \cdot ((-2)^2 b^2) = 15 \cdot a^4 \cdot (4 b^2)$
$= 15 \cdot 4 \cdot a^4 b^2 = 60 a^4 b^2$.
Il coefficiente di $a^4 b^2$ è **60**.

Esercizio 4 (Punti: 9) - Semantica Logica Proposizionale

Usando le definizioni semantiche (senza costruire l'intera tavola di verità, se possibile), stabilisci se la formula $F: (p \Rightarrow q) \Rightarrow (\neg p \Rightarrow q)$ è una tautologia, una contraddizione, o soddisfacibile ma non tautologia. Fornisci un modello se è soddisfacibile e un contromodello (interpretazione che la rende falsa) se non è una tautologia.

Svolgimento Dettagliato:

Sia $F: (p \Rightarrow q) \Rightarrow (\neg p \Rightarrow q)$.
Perché $F$ sia falsa, l'antecedente $(p \Rightarrow q)$ deve essere vero e il conseguente $(\neg p \Rightarrow q)$ deve essere falso.
1. Assumiamo $v(\neg p \Rightarrow q) = 0$. Questo accade se e solo se $v(\neg p) = 1$ e $v(q) = 0$.
Da $v(\neg p) = 1$, segue $v(p) = 0$.
Quindi, per rendere il conseguente falso, dobbiamo avere $v(p)=0$ e $v(q)=0$.
2. Ora verifichiamo se con questi valori l'antecedente $(p \Rightarrow q)$ è vero.
Se $v(p)=0$ e $v(q)=0$, allora $v(p \Rightarrow q) = v(0 \Rightarrow 0) = 1$.
L'antecedente è VERO.

Abbiamo trovato un'interpretazione $v$ (specificamente, $v(p)=0, v(q)=0$) per cui:
$v(p \Rightarrow q) = 1$
$v(\neg p \Rightarrow q) = 0$ (poiché $v(\neg p)=1, v(q)=0$)
Quindi, $v(F) = v(1 \Rightarrow 0) = 0$.

Poiché esiste un'interpretazione che rende $F$ falsa (ad esempio, $p=0, q=0$), $F$ **non è una tautologia**.
L'interpretazione $v(p)=0, v(q)=0$ è un **contromodello**.

La formula è **soddisfacibile**? Sì, se non è una contraddizione.
Proviamo un'altra interpretazione, ad esempio $v(p)=1, v(q)=1$:
$v(p \Rightarrow q) = v(1 \Rightarrow 1) = 1$.
$v(\neg p \Rightarrow q) = v(\neg 1 \Rightarrow 1) = v(0 \Rightarrow 1) = 1$.
Quindi $v(F) = v(1 \Rightarrow 1) = 1$.
L'interpretazione $v(p)=1, v(q)=1$ è un **modello**.
Poiché ha almeno un modello e almeno un contromodello, la formula è **soddisfacibile ma non una tautologia**.

Esercizio 5 (Punti: 9) - Deduzione Naturale

Usando il metodo di deduzione naturale, fornire una derivazione per:
$\vdash (p \Rightarrow q) \vee (q \Rightarrow p)$ (Legge di Dummett, o una forma del terzo escluso per l'implicazione)

Svolgimento Dettagliato (Albero di Derivazione):

Questa è una derivazione classica che utilizza la RAA o il principio del terzo escluso (che può essere derivato).

[¬((p ⇒ q) ∨ (q ⇒ p))]^1
--------------------------------- (RAA per $(p ⇒ q) ∨ (q ⇒ p)$)
       [p]^2      [¬q]^3
       ----- (I⇒ per q) (Assumiamo di poter derivare q da p, se non lo facciamo, l'imp è V)
        q
       --- (I⇒,2)
      p ⇒ q
      -------------------------- (I∨₁)
      (p ⇒ q) ∨ (q ⇒ p)         [¬((p ⇒ q) ∨ (q ⇒ p))]^1 (Ripetuta per E¬)
      -------------------------------------------------------------- (E¬ o I⊥)
                                     ⊥
----------------------------------------------------------------------- (RAA, 3, scaricando ¬q)
                                      q
                                     --- (I⇒, assumendo p non usato, o un'ipotesi [p] scaricata prima)
                                    q ⇒ p
                                    -------------------------- (I∨₂)
                                    (p ⇒ q) ∨ (q ⇒ p)         [¬((p ⇒ q) ∨ (q ⇒ p))]^1 (Ripetuta)
                                    -------------------------------------------------------------- (E¬ o I⊥)
                                                                 ⊥
-------------------------------------------------------------------------------------------------- (RAA, 1)
                                                 (p ⇒ q) ∨ (q ⇒ p)

Svolgimento più standard usando il Terzo Escluso (LEM) $A \lor \neg A$:
Assumiamo di aver già dimostrato $\vdash q \vee \neg q$ (LEM per $q$).

            [q]^1
            ----- (I⇒, scaricando un'ipotetica [p]^x non usata, o da $p \vdash q$ se $p$ fosse $q$)
            p ⇒ q                                           [¬q]^2   [p]^3
            ----------------------- (I∨₁)                   ----------- (E¬)
            (p ⇒ q) ∨ (q ⇒ p)                                  ⊥
q ∨ ¬q                                                      ---- (E⊥)
----------------------------------------------------------     q
                                                           ---- (I⇒,3)
                                                          p ⇒ q
                                                          ----------------------- (I∨₁)
                                                          (p ⇒ q) ∨ (q ⇒ p)
----------------------------------------------------------------------------------- (E∨, 1, 2)
                                      (p ⇒ q) ∨ (q ⇒ p)

Un modo più diretto e comune per dimostrare $\vdash (A \Rightarrow B) \lor (B \Rightarrow A)$ è spesso fatto con una derivazione che usa RAA a livello più alto e poi costruisce una delle due implicazioni.

Dimostrazione alternativa con RAA (più pulita):

[¬((p ⇒ q) ∨ (q ⇒ p))]^1
------------------------------------------------ (RAA per (p⇒q)∨(q⇒p) )
        [p]^2
        --- (I⇒, scaricando [¬q]^x non usata)
        ¬q ⇒ p (Non è quello che vogliamo)

Proviamo a derivare p ⇒ q o q ⇒ p.
Assumiamo ¬(p ⇒ q). Da questo, con passaggi, si può derivare q ⇒ p.
O assumiamo ¬(q ⇒ p). Da questo, con passaggi, si può derivare p ⇒ q.
Questa derivazione è un po' più avanzata.

Una derivazione standard per $\vdash A \lor \neg A$ (LEM) è:
[¬(A ∨ ¬A)]^1        [A]^2
------------        ------(I∨₁)
                    A ∨ ¬A      [¬(A ∨ ¬A)]^1 (ripetuta)
                    --------------------------------- (E¬)
                              ⊥
                         -------- (I¬, 2)
                           ¬A
                         ------ (I∨₂)
[¬(A ∨ ¬A)]^1 (ripetuta)   A ∨ ¬A
--------------------------------- (E¬)
             ⊥
--------------------------------- (RAA, 1)
           A ∨ ¬A

Una volta ottenuto LEM, $\vdash q \lor \neg q$.
Poi si procede per casi su $q \lor \neg q$:
Caso 1: $q$. Allora $p \Rightarrow q$ (se $p$ è F, o se $p$ è V e $q$ è V). Più direttamente, da $q$ si deriva $p \Rightarrow q$ (regola: da $B$ deriva $A \Rightarrow B$). Poi $(p \Rightarrow q) \lor (q \Rightarrow p)$.
Caso 2: $\neg q$. Allora $q \Rightarrow p$ (perché la premessa $q$ è falsa, quindi $q \Rightarrow p$ è vera). Poi $(p \Rightarrow q) \lor (q \Rightarrow p)$.
Entrambi i rami portano a $(p \Rightarrow q) \lor (q \Rightarrow p)$.

Esercizio 6 (Punti: 7) - Logica del Primo Ordine

Sia data la struttura $\mathcal{M} = (\mathbb{Z}, I)$ dove $\mathbb{Z}$ è l'insieme dei numeri interi e l'interpretazione $I$ è così definita:
- $I(a) = 0$ (per un simbolo di costante $a$)
- $I(f)(n) = n+1$ (per un simbolo di funzione unario $f$)
- $I(P) = \{n \in \mathbb{Z} \mid n > 0 \}$ (per un simbolo di predicato unario $P$)
- $I(Q) = \{(n,m) \in \mathbb{Z} \times \mathbb{Z} \mid n = m \}$ (per un simbolo di predicato binario $Q$)

Determina il valore di verità dei seguenti enunciati in $\mathcal{M}$:

$P(f(a))$
$\forall x (P(x) \Rightarrow P(f(x)))$
$\exists y \forall x Q(x,y)$

Soluzione:

a) Valutare $P(f(a))$ in $\mathcal{M}$:

Valore del termine $a$: $[[a]]^{\mathcal{M}} = I(a) = 0$.
Valore del termine $f(a)$: $[[f(a)]]^{\mathcal{M}} = I(f)([[a]]^{\mathcal{M}}) = I(f)(0) = 0+1 = 1$.
Valore della formula $P(f(a))$: $\mathcal{M} \models P(f(a)) \iff [[f(a)]]^{\mathcal{M}} \in I(P)$.
$\iff 1 \in \{n \in \mathbb{Z} \mid n > 0 \}$.
Poiché $1 > 0$ è vero, $1 \in I(P)$.
Quindi, $P(f(a))$ è VERA in $\mathcal{M}$.

b) Valutare $\forall x (P(x) \Rightarrow P(f(x)))$ in $\mathcal{M}$:

Dobbiamo verificare se per ogni intero $d \in \mathbb{Z}$, la formula $(P(x) \Rightarrow P(f(x)))$ è vera quando $x$ è interpretato come $d$.
Cioè, se $\mathcal{M}, [x \mapsto d] \models P(x) \Rightarrow P(f(x))$.
Questa implicazione è vera se ( ( $d \in I(P)$ ) implica ( $I(f)(d) \in I(P)$ ) ).
$(d > 0) \Rightarrow (d+1 > 0)$.
Consideriamo i casi per $d$:

Se $d > 0$: Allora $d+1$ è anche $>0$. Quindi $V \Rightarrow V$, che è VERO.
Se $d = 0$: $0 > 0$ è FALSO. L'implicazione $F \Rightarrow \dots$ è VERA.
Se $d < 0$: $d > 0$ è FALSO. L'implicazione $F \Rightarrow \dots$ è VERA.

Poiché l'implicazione interna $(d > 0) \Rightarrow (d+1 > 0)$ è vera per tutti gli interi $d$, l'enunciato $\forall x (P(x) \Rightarrow P(f(x)))$ è VERO in $\mathcal{M}$.

c) Valutare $\exists y \forall x Q(x,y)$ in $\mathcal{M}$:

Dobbiamo vedere se esiste un intero $d_y \in \mathbb{Z}$ tale che per tutti gli interi $d_x \in \mathbb{Z}$, la coppia $(d_x, d_y)$ appartiene a $I(Q)$.
$I(Q)$ è la relazione di uguaglianza, quindi $(d_x, d_y) \in I(Q) \iff d_x = d_y$.
L'enunciato diventa: "Esiste un intero $d_y$ tale che tutti gli interi $d_x$ sono uguali a $d_y$".
Questa affermazione è chiaramente falsa. Se scegliamo un $d_y$ (es. $d_y=5$), non è vero che tutti gli altri interi sono uguali a 5 (es. $d_x=6 \neq 5$).
Quindi, l'enunciato $\exists y \forall x Q(x,y)$ è FALSO in $\mathcal{M}$.

LogicaUniPR - Guida Interattiva

Simulazione Prova d'Esame N. 5

Esercizi