Simulazione Esame 3 - LogicaUniPR

Esercizio 1 (Punti: 8) - Relazioni di Equivalenza

Sia $A = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, l'insieme delle coppie di numeri interi dove il secondo elemento non è zero. Si definisca la relazione $R$ su $A$ come segue:
$(a,b) R (c,d) \iff ad = bc$.

Dimostrare che $R$ è una relazione di equivalenza su $A$.
Qual è il significato intuitivo delle classi di equivalenza generate da $R$? Fornisci un esempio di una classe di equivalenza.

Risposte Brevi:

Sì, R è una relazione di equivalenza (si verificano riflessività, simmetria, transitività, simile all'Esercizio 1 della Simulazione 1 ma su $\mathbb{Z}$).
Le classi di equivalenza rappresentano i numeri razionali $\mathbb{Q}$. Esempio: $[(1,2)]_R = \{(1,2), (2,4), (-1,-2), (3,6), \dots \}$, che rappresenta il numero razionale $1/2$.

Svolgimento Dettagliato:

a) Dimostrare che $R$ è una relazione di equivalenza:

$A = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$. $(a,b) R (c,d) \iff ad = bc$. Ricordiamo $b \neq 0, d \neq 0$.

Riflessiva: $\forall (a,b) \in A, (a,b)R(a,b)$?
$(a,b)R(a,b) \iff ab = ba$. Poiché la moltiplicazione in $\mathbb{Z}$ è commutativa, $ab=ba$ è vero. Quindi $R$ è riflessiva.
Simmetrica: $\forall (a,b),(c,d) \in A, ((a,b)R(c,d) \Rightarrow (c,d)R(a,b))$?
Assumiamo $(a,b)R(c,d)$, cioè $ad=bc$.
Dobbiamo dimostrare $(c,d)R(a,b)$, cioè $cb=da$.
Poiché $ad=bc$ e la moltiplicazione è commutativa, possiamo scrivere $da=cb$. Questa è la tesi. Quindi $R$ è simmetrica.
Transitiva: $\forall (a,b),(c,d),(e,f) \in A, [((a,b)R(c,d) \wedge (c,d)R(e,f)) \Rightarrow (a,b)R(e,f)]$?
Assumiamo $(a,b)R(c,d)$ e $(c,d)R(e,f)$.
Questo significa: (i) $ad=bc$ e (ii) $cf=de$.
Dobbiamo dimostrare $(a,b)R(e,f)$, cioè $af=be$.
Da (i), $ad=bc$. Moltiplichiamo entrambi i membri per $f$: $adf=bcf$. (Lecito perché $f \in \mathbb{Z}$)
Da (ii), $cf=de$. Sostituiamo $cf$ nell'equazione precedente: $adf=b(de)$.
$adf=bde$.
Poiché $d \in \mathbb{Z} \setminus \{0\}$, possiamo dividere per $d$: $af=be$.
Quindi $R$ è transitiva.

Poiché $R$ è riflessiva, simmetrica e transitiva, è una relazione di equivalenza.

b) Significato intuitivo delle classi di equivalenza:

La condizione $ad=bc$ è la definizione di uguaglianza tra frazioni $\frac{a}{b} = \frac{c}{d}$ (assumendo $b,d \neq 0$).
Quindi, due coppie $(a,b)$ e $(c,d)$ sono in relazione se rappresentano lo stesso numero razionale.
Ogni classe di equivalenza $[(a,b)]_R$ è l'insieme di tutte le coppie $(x,y)$ tali che la frazione $\frac{x}{y}$ è uguale alla frazione $\frac{a}{b}$.
Quindi, le classi di equivalenza rappresentano i **numeri razionali** $\mathbb{Q}$.

Esempio di una classe di equivalenza:
Sia $(a,b) = (2,3)$.
$[(2,3)]_R = \{(x,y) \in A \mid (2,3)R(x,y)\} = \{(x,y) \in A \mid 2y = 3x\}$.
Questa classe include coppie come $(2,3), (4,6), (6,9), (-2,-3), (-4,-6), \dots$
Tutte queste coppie rappresentano il numero razionale $\frac{2}{3}$.

Esercizio 2 (Punti: 9) - Induzione

Dimostrare per induzione che per ogni $n \ge 1$, $n^3 + 2n$ è divisibile per 3.

Svolgimento Dettagliato:

Sia $P(n): "n^3 + 2n \text{ è divisibile per } 3"$. Vogliamo dimostrarlo per $n \ge 1$.
Dire che "$X$ è divisibile per 3" significa che $X = 3k$ per qualche intero $k$.

1. Passo Base ($n=1$):
Per $n=1$, $1^3 + 2(1) = 1 + 2 = 3$.
$3$ è divisibile per $3$ (poiché $3 = 3 \cdot 1$).
Quindi $P(1)$ è vera.

2. Passo Induttivo:
Ipotesi Induttiva (I.I.): Assumiamo $P(j)$ vera per un $j \ge 1$.
Cioè, assumiamo che $j^3 + 2j$ sia divisibile per 3. Questo significa che $j^3 + 2j = 3m$ per qualche intero $m$.
Tesi Induttiva: Dobbiamo dimostrare $P(j+1)$, cioè che $(j+1)^3 + 2(j+1)$ è divisibile per 3.

Dimostrazione:
Consideriamo l'espressione per $P(j+1)$:
$(j+1)^3 + 2(j+1)$
$= (j^3 + 3j^2 + 3j + 1) + (2j + 2)$ (sviluppando il cubo e il prodotto)
$= j^3 + 3j^2 + 3j + 1 + 2j + 2$
$= (j^3 + 2j) + 3j^2 + 3j + 3$ (raggruppando i termini per usare l'I.I.)
Per l'Ipotesi Induttiva, $j^3 + 2j = 3m$. Sostituiamo:
$= 3m + 3j^2 + 3j + 3$
Mettiamo in evidenza il 3:
$= 3(m + j^2 + j + 1)$.
Poiché $m, j$ sono interi, anche $(m + j^2 + j + 1)$ è un intero. Sia $k' = m + j^2 + j + 1$.
Quindi, $(j+1)^3 + 2(j+1) = 3k'$, il che significa che $(j+1)^3 + 2(j+1)$ è divisibile per 3.
Il passo induttivo è verificato.

Conclusione: Per il principio di induzione, $n^3 + 2n$ è divisibile per 3 per ogni $n \ge 1$.

Esercizio 3 (Punti: 8) - Combinatoria e Binomio di Newton

Quante stringhe binarie (sequenze di 0 e 1) di lunghezza 8 contengono esattamente tre 0?
Quante stringhe binarie di lunghezza 8 contengono almeno sei 1?
Trova il coefficiente di $x^5 y^3$ nello sviluppo di $(2x - y)^8$.

Risposte Brevi:

$\binom{8}{3} = 56$
$\binom{8}{6} + \binom{8}{7} + \binom{8}{8} = 28 + 8 + 1 = 37$
$\binom{8}{3} (2x)^5 (-y)^3 = 56 \cdot 32 \cdot (-1) x^5 y^3 = -1792 x^5 y^3$. Il coefficiente è -1792.

Svolgimento Dettagliato:

a) Stringhe binarie di lunghezza 8 con esattamente tre 0:

Una stringa binaria di lunghezza 8 ha 8 posizioni. Dobbiamo scegliere 3 di queste 8 posizioni per inserire gli 0. Le restanti $8-3=5$ posizioni saranno automaticamente riempite da 1. L'ordine in cui scegliamo le posizioni per gli 0 non conta (scegliere la posizione 1, poi 3, poi 5 è come scegliere 5, poi 1, poi 3).
Numero di modi = $\binom{8}{3} = \frac{8!}{3!(8-3)!} = \frac{8!}{3!5!} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 8 \cdot 7 = 56$.

b) Stringhe binarie di lunghezza 8 con almeno sei 1:

"Almeno sei 1" significa che la stringa può avere esattamente sei 1, o esattamente sette 1, o esattamente otto 1. Questi tre casi sono mutuamente esclusivi, quindi possiamo usare il principio della somma.

Esattamente sei 1 (e quindi due 0): $\binom{8}{6} = \binom{8}{2} = \frac{8 \cdot 7}{2 \cdot 1} = 28$.
Esattamente sette 1 (e quindi un 0): $\binom{8}{7} = \binom{8}{1} = 8$.
Esattamente otto 1 (e quindi zero 0): $\binom{8}{8} = 1$.

Numero totale di modi = $28 + 8 + 1 = 37$.

c) Coefficiente di $x^5 y^3$ nello sviluppo di $(2x - y)^8$:

Usiamo il Teorema Binomiale: $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$.
Nel nostro caso, $a = 2x$, $b = -y$, e $n=8$.
Vogliamo il termine in cui la potenza di $y$ è 3, quindi $k=3$.
La potenza di $a$ sarà $n-k = 8-3 = 5$.
Il termine generico è $\binom{8}{k} (2x)^{8-k} (-y)^k$.
Per $k=3$, il termine è $\binom{8}{3} (2x)^{8-3} (-y)^3 = \binom{8}{3} (2x)^5 (-y)^3$.
Calcoliamo $\binom{8}{3} = \frac{8!}{3!5!} = 56$.
Il termine è $56 \cdot (2^5 x^5) \cdot ((-1)^3 y^3) = 56 \cdot (32 x^5) \cdot (-1 y^3)$
$= 56 \cdot 32 \cdot (-1) \cdot x^5 y^3$
$= 1792 \cdot (-1) \cdot x^5 y^3 = -1792 x^5 y^3$.
Il coefficiente di $x^5 y^3$ è **-1792**.

Esercizio 4 (Punti: 9) - Semantica Logica Proposizionale e FNC/FND

Data la formula $F: \neg (p \Rightarrow (\neg q \wedge r))$.

Scrivi la tavola di verità di $F$.
Trova una Forma Normale Disgiuntiva (FND) per $F$.
Trova una Forma Normale Congiuntiva (FNC) per $F$.

Svolgimento Dettagliato:

Sia $F: \neg (p \Rightarrow (\neg q \wedge r))$.

a) Tavola di Verità di $F$:

Tavola di Verità per $\neg (p \Rightarrow (\neg q \wedge r))$
$p$	$q$	$r$	$\neg q$	$\neg q \wedge r$ (A)	$p \Rightarrow A$ (B)	$F = \neg B$
0	0	0	1	0	1	0
0	0	1	1	1	1	0
0	1	0	0	0	1	0
0	1	1	0	0	1	0
1	0	0	1	0	0	1
1	0	1	1	1	1	0
1	1	0	0	0	0	1
1	1	1	0	0	0	1

b) Trova una Forma Normale Disgiuntiva (FND) per $F$:

Una FND è una disgiunzione di congiunzioni di letterali. La otteniamo dalle righe della tavola di verità in cui $F=1$.
$F=1$ nelle seguenti righe (interpretazioni):

$p=1, q=0, r=0$: corrisponde al termine $p \wedge \neg q \wedge \neg r$
$p=1, q=1, r=0$: corrisponde al termine $p \wedge q \wedge \neg r$
$p=1, q=1, r=1$: corrisponde al termine $p \wedge q \wedge r$

Quindi, una FND per $F$ è:
$(p \wedge \neg q \wedge \neg r) \vee (p \wedge q \wedge \neg r) \vee (p \wedge q \wedge r)$.

Alternativa con manipolazione algebrica:
$F \equiv \neg (p \Rightarrow (\neg q \wedge r))$
$\equiv \neg (\neg p \vee (\neg q \wedge r))$ (Eliminazione $\Rightarrow$)
$\equiv \neg \neg p \wedge \neg (\neg q \wedge r)$ (De Morgan)
$\equiv p \wedge (\neg \neg q \vee \neg r)$ (Doppia negazione, De Morgan)
$\equiv p \wedge (q \vee \neg r)$ (Doppia negazione)
$\equiv (p \wedge q) \vee (p \wedge \neg r)$ (Distributività). Questa è già una FND.

(Le due FND trovate sono equivalenti. Quella da manipolazione algebrica è più semplice).

c) Trova una Forma Normale Congiuntiva (FNC) per $F$:

Una FNC è una congiunzione di disgiunzioni di letterali. La otteniamo dalle righe della tavola di verità in cui $F=0$.
$F=0$ nelle seguenti righe:

$p=0, q=0, r=0$: $\neg(\neg p \wedge \neg q \wedge \neg r) \equiv p \vee q \vee r$
$p=0, q=0, r=1$: $\neg(\neg p \wedge \neg q \wedge r) \equiv p \vee q \vee \neg r$
$p=0, q=1, r=0$: $\neg(\neg p \wedge q \wedge \neg r) \equiv p \vee \neg q \vee r$
$p=0, q=1, r=1$: $\neg(\neg p \wedge q \wedge r) \equiv p \vee \neg q \vee \neg r$
$p=1, q=0, r=1$: $\neg(p \wedge \neg q \wedge r) \equiv \neg p \vee q \vee \neg r$

Quindi, una FNC per $F$ è:
$(p \vee q \vee r) \wedge (p \vee q \vee \neg r) \wedge (p \vee \neg q \vee r) \wedge (p \vee \neg q \vee \neg r) \wedge (\neg p \vee q \vee \neg r)$.

Alternativa con manipolazione algebrica (partendo da $p \wedge (q \vee \neg r)$):
$p \wedge (q \vee \neg r)$ è già in FNC, poiché $p$ è una clausola disgiuntiva (con un solo letterale) e $(q \vee \neg r)$ è una clausola disgiuntiva.
Quindi $F \equiv p \wedge (q \vee \neg r)$ è una FNC.

Esercizio 5 (Punti: 8) - Deduzione Naturale

Usando il metodo di deduzione naturale, fornire una derivazione per:
$p \Rightarrow q, q \Rightarrow r \vdash p \Rightarrow r$ (Questa è la regola del Sillogismo Ipotetico, già vista come esempio, qui da dimostrare formalmente come derivazione da premesse).

Svolgimento Dettagliato (Albero di Derivazione):

Premessa: p ⇒ q     [p]^1
------------------------- (E⇒, MP)
            q            Premessa: q ⇒ r
            ----------------------------- (E⇒, MP)
                         r
            ----------------------------- (I⇒, 1)
                       p ⇒ r

Spiegazione dei passaggi:

Abbiamo due premesse date: $p \Rightarrow q$ e $q \Rightarrow r$.
L'obiettivo è derivare $p \Rightarrow r$. Essendo un'implicazione, assumiamo la sua premessa $[p]^1$ e cerchiamo di derivare $r$.
Dall'ipotesi $[p]^1$ e dalla premessa $p \Rightarrow q$, usando la regola di Eliminazione dell'Implicazione (Modus Ponens), deriviamo $q$.
Da $q$ (appena derivato) e dalla premessa $q \Rightarrow r$, usando nuovamente $(E\Rightarrow)$, deriviamo $r$.
Avendo derivato $r$ sotto l'assunzione $[p]^1$ (e usando le premesse date), possiamo concludere $p \Rightarrow r$ usando la regola di Introduzione dell'Implicazione $(I\Rightarrow)$, scaricando l'ipotesi $[p]^1$.

Le foglie non scaricate sono le premesse date ($p \Rightarrow q$ e $q \Rightarrow r$), e la radice è la conclusione $p \Rightarrow r$. La derivazione è corretta.

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

Sia data la seguente formula della logica del primo ordine:
$F: \forall x (Studente(x) \Rightarrow \exists y (Corso(y) \wedge Frequenta(x,y)))$

Spiega il significato della formula $F$ in linguaggio naturale.
Fornisci una struttura $\mathcal{M}=(D,I)$ e un'interpretazione dei simboli predicativi $Studente^{(1)}$, $Corso^{(1)}$, $Frequenta^{(2)}$ in cui la formula $F$ sia VERA.
Fornisci una struttura $\mathcal{M'}=(D',I')$ e un'interpretazione dei simboli predicativi in cui la formula $F$ sia FALSA.

Soluzione:

a) Significato di $F = \forall x (Studente(x) \Rightarrow \exists y (Corso(y) \wedge Frequenta(x,y)))$:

"Per ogni $x$, se $x$ è uno studente, allora esiste un $y$ tale che $y$ è un corso e $x$ frequenta $y$."
In linguaggio più naturale: "Ogni studente frequenta almeno un corso."

b) Struttura $\mathcal{M}$ in cui $F$ è VERA:

Dominio $D = \{\text{Anna, Bruno, Logica, Analisi}\}$
Interpretazione $I$:
- $I(Studente) = \{\text{Anna, Bruno}\}$
- $I(Corso) = \{\text{Logica, Analisi}\}$
- $I(Frequenta) = \{(\text{Anna, Logica}), (\text{Bruno, Analisi})\}$

Verifica:
- Per $x=\text{Anna}$: $Studente(\text{Anna})$ è VERO. Dobbiamo verificare $\exists y (Corso(y) \wedge Frequenta(\text{Anna},y))$.
Scegliamo $y=\text{Logica}$. $Corso(\text{Logica})$ è VERO. $Frequenta(\text{Anna, Logica})$ è VERO. Quindi $\exists y (\dots)$ è VERO.
L'implicazione $V \Rightarrow V$ è VERA.
- Per $x=\text{Bruno}$: $Studente(\text{Bruno})$ è VERO. Dobbiamo verificare $\exists y (Corso(y) \wedge Frequenta(\text{Bruno},y))$.
Scegliamo $y=\text{Analisi}$. $Corso(\text{Analisi})$ è VERO. $Frequenta(\text{Bruno, Analisi})$ è VERO. Quindi $\exists y (\dots)$ è VERO.
L'implicazione $V \Rightarrow V$ è VERA.
- Per $x=\text{Logica}$ (o $x=\text{Analisi}$): $Studente(x)$ è FALSO. L'implicazione $F \Rightarrow \dots$ è VERA.
Poiché l'implicazione interna è vera per tutti gli $x \in D$, la formula $F$ è VERA in $\mathcal{M}$.

c) Struttura $\mathcal{M'}$ in cui $F$ è FALSA:

Per rendere $F$ falsa, dobbiamo trovare almeno un $x$ per cui $Studente(x)$ è vero, ma $\exists y (Corso(y) \wedge Frequenta(x,y))$ è falso. Cioè, uno studente che non frequenta nessun corso.

Dominio $D' = \{\text{Carla, Logica101}\}$
Interpretazione $I'$:
- $I'(Studente) = \{\text{Carla}\}$
- $I'(Corso) = \{\text{Logica101}\}$
- $I'(Frequenta) = \emptyset$ (Nessuno frequenta nessun corso)

Verifica:
- Consideriamo $x=\text{Carla}$. $Studente(\text{Carla})$ è VERO.
Dobbiamo valutare $\exists y (Corso(y) \wedge Frequenta(\text{Carla},y))$.
Se $y=\text{Logica101}$: $Corso(\text{Logica101})$ è VERO, ma $Frequenta(\text{Carla, Logica101})$ è FALSO (perché $I'(Frequenta)$ è vuoto). Quindi $V \wedge F = F$.
Non ci sono altri $y$ che sono corsi.
Quindi $\exists y (Corso(y) \wedge Frequenta(\text{Carla},y))$ è FALSO.
L'implicazione $Studente(\text{Carla}) \Rightarrow \exists y (\dots)$ diventa $V \Rightarrow F$, che è FALSA.
Poiché abbiamo trovato un $x$ (Carla) per cui l'implicazione interna è falsa, la formula universale $F$ è FALSA in $\mathcal{M'}$.

LogicaUniPR - Guida Interattiva

Simulazione Prova d'Esame N. 3

Esercizi