Simulazione Esame 2 - LogicaUniPR

Esercizio 1 (Punti: 8) - Relazioni d'Ordine

Sia $A = \{a, b, c\}$ un insieme e si consideri l'insieme delle sue parti $\mathcal{P}(A)$. Sia $R$ la relazione di inclusione $\subseteq$ definita su $\mathcal{P}(A)$, cioè $X R Y \iff X \subseteq Y$ per $X, Y \in \mathcal{P}(A)$.

Elenca tutti gli elementi di $\mathcal{P}(A)$.
Dimostra che $(\mathcal{P}(A), \subseteq)$ è una relazione d'ordine.
L'ordinamento è totale o parziale? Giustifica.
Identifica elementi minimali, massimali, minimo e massimo di $(\mathcal{P}(A), \subseteq)$.

Risposte Brevi:

$\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$.
Sì, è una relazione d'ordine (riflessiva, antisimmetrica, transitiva).
Parziale (es. $\{a\}$ e $\{b\}$ sono inconfrontabili).
Minimale: $\{\emptyset\}$ (è anche Minimo). Massimale: $\{\{a,b,c\}\}$ (è anche Massimo).

Svolgimento Dettagliato:

a) Elementi di $\mathcal{P}(A)$ per $A = \{a, b, c\}$:

L'insieme delle parti $\mathcal{P}(A)$ contiene tutti i sottoinsiemi di $A$. Poiché $|A|=3$, $|\mathcal{P}(A)|=2^3=8$.
$\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$.

b) Dimostrare che $(\mathcal{P}(A), \subseteq)$ è una relazione d'ordine:

Riflessiva: $\forall X \in \mathcal{P}(A), X \subseteq X$?
Sì, ogni insieme è sottoinsieme di se stesso. Vera.
Antisimmetrica: $\forall X,Y \in \mathcal{P}(A), (X \subseteq Y \wedge Y \subseteq X) \Rightarrow X=Y$?
Sì, questa è la definizione di uguaglianza tra insiemi (doppia inclusione). Vera.
Transitiva: $\forall X,Y,Z \in \mathcal{P}(A), (X \subseteq Y \wedge Y \subseteq Z) \Rightarrow X \subseteq Z$?
Sì. Se ogni elemento di $X$ è in $Y$, e ogni elemento di $Y$ è in $Z$, allora ogni elemento di $X$ deve essere in $Z$. Vera.

Poiché $\subseteq$ su $\mathcal{P}(A)$ è riflessiva, antisimmetrica e transitiva, è una relazione d'ordine.

c) L'ordinamento è totale o parziale?

L'ordinamento è **parziale**. Per essere totale, ogni coppia di elementi di $\mathcal{P}(A)$ dovrebbe essere confrontabile.
Consideriamo $X=\{a\}$ e $Y=\{b\}$. Entrambi sono in $\mathcal{P}(A)$.
$\{a\} \not\subseteq \{b\}$ (perché $a \in \{a\}$ ma $a \notin \{b\}$).
$\{b\} \not\subseteq \{a\}$ (perché $b \in \{b\}$ ma $b \notin \{a\}$).
Poiché esistono elementi inconfrontabili, l'ordine è parziale.

d) Elementi minimali, massimali, minimo e massimo:

Elemento Minimale: Un insieme $X \in \mathcal{P}(A)$ è minimale se non esiste $Y \in \mathcal{P}(A)$, $Y \neq X$, tale che $Y \subseteq X$. L'unico insieme che soddisfa questa condizione è $\emptyset$, poiché nessun altro sottoinsieme è contenuto propriamente in $\emptyset$. Quindi, l'unico minimale è $\emptyset$.
Minimo: Poiché $\emptyset$ è l'unico minimale e $\emptyset \subseteq X$ per ogni $X \in \mathcal{P}(A)$, allora $\emptyset$ è il **minimo**.
Elemento Massimale: Un insieme $X \in \mathcal{P}(A)$ è massimale se non esiste $Y \in \mathcal{P}(A)$, $Y \neq X$, tale che $X \subseteq Y$. L'unico insieme che soddisfa questa condizione è $A = \{a,b,c\}$ stesso, poiché nessun altro sottoinsieme di $A$ lo contiene propriamente. Quindi, l'unico massimale è $\{a,b,c\}$.
Massimo: Poiché $\{a,b,c\}$ è l'unico massimale e $X \subseteq \{a,b,c\}$ per ogni $X \in \mathcal{P}(A)$, allora $\{a,b,c\}$ è il **massimo**.

Esercizio 2 (Punti: 9) - Induzione

Dimostrare per induzione che per ogni $n \ge 0$, la somma dei primi $n+1$ termini di una progressione geometrica di ragione $q \neq 1$ e primo termine $a$ è data da:
$\sum_{i=0}^{n} a \cdot q^i = a \frac{q^{n+1}-1}{q-1}$.

Esercizio 3 (Punti: 8) - Combinatoria

Un club è composto da 7 uomini e 5 donne.

In quanti modi si può formare un comitato di 5 persone?
In quanti modi si può formare un comitato di 3 uomini e 2 donne?
In quanti modi si può formare un comitato di 5 persone che includa almeno una donna?

Risposte Brevi:

$\binom{12}{5} = 792$
$\binom{7}{3} \cdot \binom{5}{2} = 35 \cdot 10 = 350$
$\binom{12}{5} - \binom{7}{5} = 792 - 21 = 771$

Esercizio 4 (Punti: 8) - Semantica Logica Proposizionale

Determina se la formula $F: ((p \vee q) \wedge \neg p) \Rightarrow q$ è una tautologia, una contraddizione o una formula soddisfacibile (ma non tautologia). Giustifica la risposta usando le definizioni semantiche o una tavola di verità.

Svolgimento Dettagliato:

Sia $A = (p \vee q) \wedge \neg p$. La formula è $A \Rightarrow q$.
Costruiamo la tavola di verità:

Tavola di Verità per $((p \vee q) \wedge \neg p) \Rightarrow q$
$p$	$q$	$p \vee q$	$\neg p$	$(p \vee q) \wedge \neg p$ (Antecedente A)	$A \Rightarrow q$ (Formula F)
0	0	0	1	0	1
0	1	1	1	1	1
1	0	1	0	0	1
1	1	1	0	0	1

Dalla colonna finale, vediamo che la formula $F$ è sempre VERA per ogni interpretazione di $p$ e $q$.
Quindi, $F$ è una **tautologia** (e di conseguenza è anche soddisfacibile).

Dimostrazione semantica alternativa (per assurdo):
Supponiamo che $F$ non sia una tautologia. Allora esiste un'interpretazione $v$ tale che $v(F)=0$.
Se $v(A \Rightarrow q)=0$, allora deve essere $v(A)=1$ e $v(q)=0$.
Se $v(A)=1$, cioè $v((p \vee q) \wedge \neg p)=1$, allora deve essere $v(p \vee q)=1$ e $v(\neg p)=1$.
Da $v(\neg p)=1$, segue $v(p)=0$.
Sostituendo $v(p)=0$ in $v(p \vee q)=1$, otteniamo $v(0 \vee q)=1$, che implica $v(q)=1$.
Ma avevamo assunto $v(q)=0$ per rendere l'implicazione principale falsa.
Siamo giunti a una contraddizione ($v(q)=1$ e $v(q)=0$).
Quindi, l'ipotesi che $F$ non sia una tautologia è falsa. $F$ è una tautologia.

Esercizio 5 (Punti: 10) - Deduzione Naturale

Usando il metodo di deduzione naturale, fornire una derivazione per:
$\vdash (p \wedge q) \Rightarrow (q \wedge p)$ (Commutatività della Congiunzione)

Svolgimento Dettagliato (Albero di Derivazione):

[p ∧ q]^1            [p ∧ q]^1
--------- (E∧₂)      --------- (E∧₁)
    q                    p
    ---------------------- (I∧)
          q ∧ p
-------------------------- (I⇒, 1)
  (p ∧ q) ⇒ (q ∧ p)

Spiegazione dei passaggi:

L'obiettivo è derivare $(p \wedge q) \Rightarrow (q \wedge p)$. Essendo un'implicazione, assumiamo la sua premessa $[p \wedge q]^1$ e cerchiamo di derivare $(q \wedge p)$.
Dall'ipotesi $[p \wedge q]^1$, usando la regola di eliminazione dell'AND $(E\wedge_2)$, possiamo derivare $q$.
Dall'ipotesi $[p \wedge q]^1$, usando la regola di eliminazione dell'AND $(E\wedge_1)$, possiamo derivare $p$.
Avendo derivato $q$ (dal passo 2) e $p$ (dal passo 3), possiamo usare la regola di introduzione dell'AND $(I\wedge)$ per concludere $(q \wedge p)$.
Infine, avendo derivato $(q \wedge p)$ sotto l'assunzione $[p \wedge q]^1$, possiamo concludere $(p \wedge q) \Rightarrow (q \wedge p)$ usando la regola di introduzione dell'implicazione $(I\Rightarrow)$ e scaricando l'ipotesi $[p \wedge q]^1$.

Poiché tutte le ipotesi temporanee sono state scaricate, la formula è un teorema.

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

Traduci la seguente frase in una formula della logica del primo ordine, specificando la segnatura utilizzata: "C'è almeno un professore che piace a tutti gli studenti."
Data la formula $F = \exists y \forall x (P(x,y) \vee \neg Q(y,f(a)))$. Identificare le variabili libere e vincolate. Il termine $f(a)$ è chiuso?

Soluzione:

a) Traduzione in LPO: "C'è almeno un professore che piace a tutti gli studenti."

Segnatura Proposta:

$Prof(x)$: "$x$ è un professore"
$Stud(y)$: "$y$ è uno studente"
$PiaceA(x,y)$: "al professore $x$ piace lo studente $y$" o, più probabilmente inteso come "$x$ piace a $y$" (cioè lo studente $y$ apprezza il prof $x$). Assumiamo la seconda interpretazione: $PiaceA(y,x)$ significa "allo studente $y$ piace il professore $x$".

Formula: $\exists x (Prof(x) \wedge \forall y (Stud(y) \Rightarrow PiaceA(y,x)))$
(Esiste un $x$ tale che $x$ è un professore E per ogni $y$, se $y$ è uno studente, allora a $y$ piace $x$)

b) Variabili Libere/Vincolate e Termine Chiuso in $F = \exists y \forall x (P(x,y) \vee \neg Q(y,f(a)))$

Occorrenze di $y$:
- In $\exists y$: quantificatore.
- In $P(x,y)$: vincolata da $\exists y$.
- In $Q(y,f(a))$: vincolata da $\exists y$.
Occorrenze di $x$:
- In $\forall x$: quantificatore.
- In $P(x,y)$: vincolata da $\forall x$.
La costante $a$ non è una variabile.

Quindi:
Variabili Libere: Nessuna. $FV(F) = \emptyset$. La formula $F$ è un enunciato.
Variabili Vincolate: $\{x, y\}$.

Il termine $f(a)$ è chiuso?
Un termine è chiuso se non contiene variabili.
$f$ è un simbolo di funzione, $a$ è un simbolo di costante.
Il termine $f(a)$ non contiene alcuna variabile.
Sì, $f(a)$ è un **termine chiuso** (ground term).

LogicaUniPR - Guida Interattiva

Simulazione Prova d'Esame N. 2

Esercizi