Simulazione Prova d'Esame N. 4
Questa è la quarta simulazione di una possibile prova d'esame. Prova a risolvere gli esercizi autonomamente prima di consultare le soluzioni. Tempo consigliato: 2 ore.
Istruzioni: Per ogni esercizio, leggi attentamente il testo. Giustifica tutte le tue risposte e mostra i passaggi chiave.
Esercizi
Esercizio 1 (Punti: 8) - Relazioni d'Ordine e Diagrammi di Hasse
Sia $A = \{1, 2, 3, 4, 5, 6\}$. Si consideri la relazione $R$ su $A$ definita da $xRy \iff (x=y \text{ oppure } x \text{ è dispari e } y \text{ è pari})$.
- Verifica se $R$ è una relazione d'ordine. Se non lo è, indica quali proprietà falliscono e fornisci un controesempio.
- Sia ora $B = \{1, 2, 3, 6, 9, 18\}$ e sia $S$ la relazione di divisibilità "$|$" su $B$. Disegna il diagramma di Hasse per $(B, S)$. Identifica minimo, massimo, elementi minimali e massimali.
Risposte Brevi:
- $R$ non è una relazione d'ordine. Fallisce l'antisimmetria e la transitività.
- Minimo: 1. Massimo: 18. Minimali: {1}. Massimali: {18}. (Il diagramma di Hasse mostrerà le relazioni di divisibilità).
Svolgimento Dettagliato:
a) Analisi della relazione $R$ su $A = \{1, 2, 3, 4, 5, 6\}$: $xRy \iff (x=y \text{ oppure } (x \text{ è dispari e } y \text{ è pari}))$.
- Riflessiva: $\forall x \in A, xRx$?
Se $xRx$, allora $x=x$ oppure ($x$ è dispari e $x$ è pari). Poiché $x=x$ è sempre vero, la prima parte della disgiunzione è vera, quindi $xRx$ è vera. $R$ è riflessiva. - Antisimmetrica: $\forall x,y \in A, (xRy \wedge yRx) \Rightarrow x=y$?
Consideriamo $x=1$ (dispari) e $y=2$ (pari).
$1R2$ è vera perché $1$ è dispari e $2$ è pari.
$2R1$? $2=1$ (Falso) E ($2$ è dispari (Falso) e $1$ è pari (Falso)). Quindi $2R1$ è Falsa.
Proviamo un altro caso. Siano $x=1, y=2$. $1R2$ è vera.
C'è un problema nella definizione per verificare l'antisimmetria. Se $xRy$ perché $x$ è dispari e $y$ è pari, allora $yRx$ sarebbe vera solo se $y=x$ (impossibile se $x \neq y$) oppure se $y$ è dispari e $x$ è pari (il contrario della nostra assunzione $xRy$).
Prendiamo $x=1, y=2$. $1R2$ è vera. Ma $yRx$ (cioè $2R1$) è falsa, perché $2 \neq 1$ e $2$ non è dispari.
L'antisimmetria richiede che se $xRy$ e $yRx$, allora $x=y$.
Controesempio per l'antisimmetria: non si può formare $xRy \wedge yRx$ con $x \neq y$ se uno è dispari e l'altro pari.
Se $x=y$, $xRx$ è vera. Se $xRy \wedge yRx \implies x=y$.
Consideriamo $x=1, y=2$. $1R2$ (1 dispari, 2 pari). Ma $2R1$ è falsa.
La proprietà antisimmetrica sembra reggere perché è difficile avere $xRy$ e $yRx$ se $x \neq y$.
Se $xRy$ perché $x$ è dispari e $y$ è pari, allora $yRx$ implicherebbe $y$ dispari e $x$ pari (impossibile) oppure $y=x$ (impossibile se $x \neq y$).
Quindi, se $x \neq y$, non possiamo avere $xRy \wedge yRx$ basandoci sulla seconda clausola. L'unico modo per avere $xRy \wedge yRx$ è se $x=y$. Quindi è antisimmetrica. - Transitiva: $\forall x,y,z \in A, (xRy \wedge yRz) \Rightarrow xRz$?
Controesempio: Sia $x=1, y=2, z=3$.
$1R2$ è vera (1 dispari, 2 pari).
$2R3$? $2=3$ (Falso). $2$ è dispari e $3$ è pari? (Falso, $2$ è pari, $3$ è dispari). Quindi $2R3$ è falsa. Questo controesempio non funziona.
Controesempio corretto: Sia $x=1$ (dispari), $y=2$ (pari), $z=4$ (pari).
$xRy \implies 1R2$: vero (1 dispari, 2 pari).
$yRz \implies 2R4$: vero (2 dispari e 4 pari? Falso. $2=4$? Falso. Ah, la definizione è $x=y$ OPPURE $x$ dispari e $y$ pari. Quindi $2R4$ è vera perché $2=2$ (se $y=2, z=2$) o $2R2$ è vera perché $2=2$.
Sia $x=1$ (dispari), $y=2$ (pari), $z=3$ (dispari).
$1R2$ è Vera (1 dispari, 2 pari).
$2R3$ è Falsa ($2 \ne 3$ e $2$ non è dispari).
Cerchiamo $xRy$ e $yRz$ veri, ma $xRz$ falso.
Sia $x=1$ (dispari), $y=2$ (pari). $1R2$ è VERA.
Sia $y=2$ (pari), $z=2$ (pari). $2R2$ è VERA (per $y=z$).
Dobbiamo verificare $xRz$, cioè $1R2$. È VERA. Questo non è un controesempio.
Sia $x=1$ (dispari), $y=4$ (pari). $1R4$ è VERA.
Sia $y=4$ (pari), $z=3$ (dispari). $4R3$ è FALSA.
La transitività fallisce se: $x$ dispari, $y$ pari, $z$ dispari.
$xRy$: VERA (es. $1R2$).
$yRz$: $y=z$ (impossibile se $y$ pari, $z$ dispari) oppure ($y$ dispari e $z$ pari) (Falso). Quindi $yRz$ è FALSA.
La transitività è la proprietà più difficile da rompere qui.
Se $xRy$ (x disp, y pari) e $yRz$ (y disp, z pari) -> impossibile.
Se $xRy$ (x disp, y pari) e $yRz$ (y=z) -> $xRz$ (x disp, z=y pari) -> VERA.
Se $xRy$ (x=y) e $yRz$ (y disp, z pari) -> $xRz$ (x=y disp, z pari) -> VERA.
Se $xRy$ (x=y) e $yRz$ (y=z) -> $xRz$ (x=z) -> VERA.
La relazione $R$ è transitiva.
Quindi $R$ è una relazione d'ordine.
Rettifica: L'analisi dell'antisimmetria era affrettata.
Se $xRy$ e $yRx$.
Caso 1: $x=y$. Allora $x=y$ è vero.
Caso 2: $x$ dispari, $y$ pari. E $y$ dispari, $x$ pari. Questo è impossibile.
Caso 3: $x$ dispari, $y$ pari. E $y=x$. Questo è impossibile.
Caso 4: $x=y$. E $y$ dispari, $x$ pari. Questo è impossibile.
Quindi l'antisimmetria vale.
È un ordine. Parziale o totale?
$2R4$ è vera (2=2 se $y=2, z=2$ no, $2R4$ è vera perché $2=2$ se $y=4$. No, $2R4$ è vera perché $2=2$ e $4=4$.
$2R4 \iff (2=4 \text{ F) or (2 disp F e 4 pari V) F}$. Quindi $2R4$ è Falsa (a meno che $2=4$).
$R$ è riflessiva. $xRx \iff (x=x) \lor (x \text{ disp} \land x \text{ pari})$. La prima è vera.
Antisimmetria: se $xRy \land yRx \implies x=y$.
Se $x \text{ disp}, y \text{ pari}$: $xRy$ è vera. $yRx$ è vera se $y=x$ (impossibile) o ($y$ dispari e $x$ pari) (impossibile). Quindi se $x \neq y$, non si può avere $xRy \land yRx$. Dunque è antisimmetrica.
Transitiva: $xRy \land yRz \implies xRz$.
1. $x=y, y=z \implies x=z \implies xRz$.
2. $x=y, (y \text{ disp} \land z \text{ pari}) \implies (x \text{ disp} \land z \text{ pari}) \implies xRz$.
3. $(x \text{ disp} \land y \text{ pari}), y=z \implies (x \text{ disp} \land z \text{ pari}) \implies xRz$.
4. $(x \text{ disp} \land y \text{ pari}), (y \text{ disp} \land z \text{ pari})$. La premessa $(y \text{ disp} \land z \text{ pari})$ è falsa perché $y$ è pari. Quindi l'implicazione $F \implies \dots$ è vera. Questo caso non rompe la transitività.
Consideriamo $x=1, y=2, z=4$.
$1R2$ (1 disp, 2 pari) è VERA.
$2R4$ (2=4 FALSO; 2 disp FALSO). Quindi $2R4$ è FALSA.
La relazione $R$ come definita è d'ordine.
È totale? $2R3$: Falso. $3R2$: Vero. Quindi sono confrontabili.
$2R4$: Falso. $4R2$: Falso. Non sono confrontabili. Quindi è **parziale**.
Correzione all'interpretazione della definizione di R: $xRy \iff (x=y) \lor (x \text{ è dispari } \land y \text{ è pari})$.
Riflessiva: $xRx \iff (x=x) \lor (\dots)$. Vero.
Antisimmetrica: Se $xRy$ e $yRx$, dobbiamo avere $x=y$.
Se $x=y$, ok.
Se $x \neq y$: $xRy \implies x$ dispari e $y$ pari. $yRx \implies y$ dispari e $x$ pari. Questo è impossibile.
Quindi l'unico modo per $xRy \land yRx$ è che $x=y$. È antisimmetrica.
Transitiva: $xRy \land yRz \implies xRz$.
Controesempio: $x=1, y=2, z=2$.
$1R2$ (1 disp, 2 pari): VERA.
$2R2$ (2=2): VERA.
Dobbiamo avere $1R2$: VERA. Ok.
Controesempio: $x=2, y=2, z=1$.
$2R2$ (2=2): VERA.
$2R1$ (2=1 F; 2 disp F): FALSA.
Controesempio: $x=1, y=2, z=1$.
$1R2$ (1 disp, 2 pari): VERA.
$2R1$ (2=1 F; 2 disp F): FALSA.
La transitività fallisce. Sia $x=1, y=2, z=4$.
$xRy$: $1R2 \implies (1=2) \lor (1 \text{ disp} \land 2 \text{ pari}) \implies F \lor (V \land V) \implies V$.
$yRz$: $2R4 \implies (2=4) \lor (2 \text{ disp} \land 4 \text{ pari}) \implies F \lor (F \land V) \implies F$.
Questo non è un controesempio.
Per rompere la transitività: $xRy$ V, $yRz$ V, ma $xRz$ F.
Sia $x=1$ (dispari), $y=2$ (pari), $z=3$ (dispari).
$xRy \implies 1R2$: VERA (1 disp, 2 pari).
$yRz \implies 2R3$: FALSA ($2 \ne 3$ e $2$ non è dispari).
La transitività sembra valere.
Riconsideriamo $x=1, y=2, z=1$. $1R2$ (V), $2R1$ (F).
Fallisce l'antisimmetria se interpretiamo male.
$R$ è riflessiva.
$R$ è antisimmetrica: se $xRy$ e $yRx$ allora $x=y$.
Se $x \ne y$: $xRy \implies x$ dispari, $y$ pari. $yRx \implies y$ dispari, $x$ pari. Impossibile.
Quindi se $xRy$ e $yRx$ deve essere $x=y$. Antisimmetrica è VERA.
$R$ è transitiva: se $xRy$ e $yRz$ allora $xRz$.
Caso 1: $x=y$ e $y=z$. Allora $x=z$, quindi $xRz$. VERO.
Caso 2: $x=y$ e ($y$ dispari, $z$ pari). Allora $x$ è dispari, $z$ è pari. Quindi $xRz$. VERO.
Caso 3: ($x$ dispari, $y$ pari) e $y=z$. Allora $x$ è dispari, $z$ è pari. Quindi $xRz$. VERO.
Caso 4: ($x$ dispari, $y$ pari) e ($y$ dispari, $z$ pari). La seconda parte ($y$ dispari) contraddice $y$ pari. Quindi la premessa $(xRy \land yRz)$ è Falsa. Quindi l'implicazione è Vera.
Quindi $R$ è una relazione d'ordine.
È parziale: $2R4$ è Falsa, $4R2$ è Falsa. $2,4$ sono inconfrontabili.
Rettifica finale sulla transitività: Sia $x=1, y=2, z=2$. $1R2$ (V), $2R2$ (V). $1R2$ (V). OK.
Sia $x=1, y=1, z=2$. $1R1$ (V), $1R2$ (V). $1R2$ (V). OK.
La relazione $R$ è effettivamente d'ordine. È parziale (es. 2 e 4 sono inconfrontabili).b) $(B, |)$ con $B = \{1, 2, 3, 6, 9, 18\}$
La relazione di divisibilità è una relazione d'ordine (riflessiva, antisimmetrica, transitiva).
Diagramma di Hasse:
18 / \ / \ 6 9 / \ / / \ / 2 3 \ / \ / 1- Minimali: $\{1\}$ (non c'è nessun altro elemento che divide 1).
- Minimo: $1$ (divide tutti gli altri elementi in $B$).
- Massimali: $\{18\}$ (non divide nessun altro elemento in $B$).
- Massimo: $18$ (è diviso da tutti gli altri elementi in $B$).
Esercizio 2 (Punti: 9) - Induzione
Dimostrare per induzione che per ogni $n \ge 1$, $4^n - 1$ è divisibile per 3.
Svolgimento Dettagliato:
Sia $P(n): "4^n - 1 \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$, $4^1 - 1 = 4 - 1 = 3$.
$3$ è divisibile per $3$ (poiché $3 = 3 \cdot 1$).
Quindi $P(1)$ è vera.
2. Passo Induttivo:
Ipotesi Induttiva (I.I.): Assumiamo $P(k)$ vera per un $k \ge 1$.
Cioè, assumiamo che $4^k - 1$ sia divisibile per 3. Questo significa che $4^k - 1 = 3m$ per qualche intero $m$. Da cui, $4^k = 3m + 1$.
Tesi Induttiva: Dobbiamo dimostrare $P(k+1)$, cioè che $4^{k+1} - 1$ è divisibile per 3.
Dimostrazione:
Consideriamo l'espressione per $P(k+1)$:
$4^{k+1} - 1 = 4 \cdot 4^k - 1$.
Sostituiamo $4^k$ usando l'Ipotesi Induttiva ($4^k = 3m + 1$):
$= 4(3m + 1) - 1$
$= 12m + 4 - 1$
$= 12m + 3$
Mettiamo in evidenza il 3:
$= 3(4m + 1)$.
Poiché $m$ è un intero, anche $(4m + 1)$ è un intero. Sia $k' = 4m + 1$.
Quindi, $4^{k+1} - 1 = 3k'$, il che significa che $4^{k+1} - 1$ è divisibile per 3.
Il passo induttivo è verificato.
Conclusione: Per il principio di induzione, $4^n - 1$ è divisibile per 3 per ogni $n \ge 1$.
Esercizio 3 (Punti: 8) - Combinatoria
Una commissione di 6 persone deve essere scelta da un gruppo di 6 uomini e 8 donne.
- In quanti modi si può formare la commissione se deve essere composta esattamente da 3 uomini e 3 donne?
- In quanti modi si può formare la commissione se deve contenere più uomini che donne?
Risposte Brevi:
- $\binom{6}{3} \cdot \binom{8}{3} = 20 \cdot 56 = 1120$
- Casi: (6U, 0D) + (5U, 1D) + (4U, 2D) = $\binom{6}{6}\binom{8}{0} + \binom{6}{5}\binom{8}{1} + \binom{6}{4}\binom{8}{2} = 1 \cdot 1 + 6 \cdot 8 + 15 \cdot 28 = 1 + 48 + 420 = 469$.
Svolgimento Dettagliato:
Abbiamo 6 uomini (U) e 8 donne (D). Dobbiamo formare una commissione di 6 persone.
a) Comitato con esattamente 3 uomini e 3 donne:
Dobbiamo scegliere 3 uomini da 6 E scegliere 3 donne da 8. L'ordine non conta.
- Modi per scegliere 3 uomini da 6: $\binom{6}{3} = \frac{6!}{3!3!} = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$.
- Modi per scegliere 3 donne da 8: $\binom{8}{3} = \frac{8!}{3!5!} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56$.
Per il principio del prodotto, il numero totale di modi è $20 \cdot 56 = 1120$.
b) Comitato con più uomini che donne (commissione di 6 persone):
I casi possibili sono (Uomini, Donne):
- Caso 1: 6 Uomini, 0 Donne
Modi: $\binom{6}{6} \cdot \binom{8}{0} = 1 \cdot 1 = 1$. - Caso 2: 5 Uomini, 1 Donna
Modi: $\binom{6}{5} \cdot \binom{8}{1} = \binom{6}{1} \cdot 8 = 6 \cdot 8 = 48$. - Caso 3: 4 Uomini, 2 Donne
Modi: $\binom{6}{4} \cdot \binom{8}{2} = \binom{6}{2} \cdot \binom{8}{2} = \left(\frac{6 \cdot 5}{2}\right) \cdot \left(\frac{8 \cdot 7}{2}\right) = 15 \cdot 28 = 420$.
Questi casi sono mutuamente esclusivi. Per il principio della somma, il numero totale di modi è:
$1 + 48 + 420 = 469$.
Esercizio 4 (Punti: 9) - Semantica Logica Proposizionale
Considera la formula $F: (p \Leftrightarrow q) \Leftrightarrow ((p \wedge q) \vee (\neg p \wedge \neg q))$.
- Costruisci la tavola di verità per $F$.
- La formula $F$ è una tautologia, una contraddizione o una formula soddisfacibile (ma non tautologia)?
- Se $p \Leftrightarrow q$ è vera, cosa puoi dire di $(p \wedge q) \vee (\neg p \wedge \neg q)$?
Svolgimento Dettagliato:
a) Tavola di Verità di $F: (p \Leftrightarrow q) \Leftrightarrow ((p \wedge q) \vee (\neg p \wedge \neg q))$:
Sia $A = (p \Leftrightarrow q)$ e $B = ((p \wedge q) \vee (\neg p \wedge \neg q))$. La formula è $A \Leftrightarrow B$.
| $p$ | $q$ | $\neg p$ | $\neg q$ | $p \Leftrightarrow q$ (A) | $p \wedge q$ (B1) | $\neg p \wedge \neg q$ (B2) | $(B1) \vee (B2)$ (B) | $F = A \Leftrightarrow B$ |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
b) Tautologia, contraddizione o soddisfacibile?
Dalla colonna finale della tavola di verità, vediamo che la formula $F$ è sempre VERA (valore 1) per ogni interpretazione di $p$ e $q$.
Quindi, $F$ è una **tautologia** (e di conseguenza è anche soddisfacibile).
c) Se $p \Leftrightarrow q$ è vera, cosa puoi dire di $(p \wedge q) \vee (\neg p \wedge \neg q)$?
Poiché $F$ è una tautologia, significa che $p \Leftrightarrow q$ è logicamente equivalente a $(p \wedge q) \vee (\neg p \wedge \neg q)$.
Quindi, se $p \Leftrightarrow q$ è vera, allora anche $(p \wedge q) \vee (\neg p \wedge \neg q)$ deve essere vera.
Questo perché due formule logicamente equivalenti hanno sempre lo stesso valore di verità.
Esercizio 5 (Punti: 9) - Deduzione Naturale
Usando il metodo di deduzione naturale, fornire una derivazione per:
$\vdash (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \wedge q) \Rightarrow r)$
Svolgimento Dettagliato (Albero di Derivazione):
[p ⇒ (q ⇒ r)]^3 [p ∧ q]^2
----------------- --------- (E∧₁)
p
--------------------------- (E⇒, MP)
q ⇒ r [p ∧ q]^2
----------- --------- (E∧₂)
r q
------------------------ (E⇒, MP)
r
-------------------- (I⇒, 2)
(p ∧ q) ⇒ r
------------------------------------------------ (I⇒, 3)
(p ⇒ (q ⇒ r)) ⇒ ((p ∧ q) ⇒ r)
Spiegazione dei passaggi:
- L'obiettivo è $(p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \wedge q) \Rightarrow r)$. Assumiamo $[p \Rightarrow (q \Rightarrow r)]^3$ (ipotesi esterna).
- Dobbiamo derivare $((p \wedge q) \Rightarrow r)$. Assumiamo $[p \wedge q]^2$ (ipotesi interna).
- Da $[p \wedge q]^2$, con $(E\wedge_1)$ deriviamo $p$.
- Da $[p \wedge q]^2$, con $(E\wedge_2)$ deriviamo $q$.
- Da $p$ (derivato al passo 3) e $[p \Rightarrow (q \Rightarrow r)]^3$, con $(E\Rightarrow)$ deriviamo $(q \Rightarrow r)$.
- Da $q$ (derivato al passo 4) e $(q \Rightarrow r)$ (derivato al passo 5), con $(E\Rightarrow)$ deriviamo $r$.
- Avendo derivato $r$ sotto l'ipotesi $[p \wedge q]^2$ (e l'ipotesi 3 ancora attiva), concludiamo $((p \wedge q) \Rightarrow r)$ per $(I\Rightarrow)$, scaricando l'ipotesi 2.
- Avendo derivato $((p \wedge q) \Rightarrow r)$ sotto l'ipotesi $[p \Rightarrow (q \Rightarrow r)]^3$, concludiamo la formula finale per $(I\Rightarrow)$, scaricando l'ipotesi 3.
Tutte le ipotesi temporanee sono state scaricate, quindi la formula è un teorema.
Esercizio 6 (Punti: 7) - Logica del Primo Ordine
Considera un linguaggio del primo ordine con un simbolo di predicato binario $Ama(x,y)$ ("x ama y") e un simbolo di predicato unario $Gatto(x)$ ("x è un gatto").
- Traduci in LPO: "Tutti i gatti amano se stessi".
- Traduci in LPO: "Esiste un gatto che è amato da tutti i gatti".
- Traduci in LPO: "Non tutti i gatti amano qualche gatto". (Interpreta "qualche" come "almeno un").
Soluzione:
a) "Tutti i gatti amano se stessi"
$\forall x (Gatto(x) \Rightarrow Ama(x,x))$
b) "Esiste un gatto che è amato da tutti i gatti"
$\exists x (Gatto(x) \wedge \forall y (Gatto(y) \Rightarrow Ama(y,x)))$
(Esiste un x tale che x è un gatto E per ogni y, se y è un gatto, allora y ama x)
c) "Non tutti i gatti amano qualche gatto"
Questa frase può essere interpretata come la negazione di "Tutti i gatti amano qualche gatto".
"Tutti i gatti amano qualche gatto": $\forall x (Gatto(x) \Rightarrow \exists y (Gatto(y) \wedge Ama(x,y)))$
Quindi, "Non tutti i gatti amano qualche gatto" diventa:
$\neg (\forall x (Gatto(x) \Rightarrow \exists y (Gatto(y) \wedge Ama(x,y))))$
Che è semanticamente equivalente a (spingendo la negazione all'interno):
$\exists x \neg (Gatto(x) \Rightarrow \exists y (Gatto(y) \wedge Ama(x,y)))$
$\equiv \exists x (Gatto(x) \wedge \neg (\exists y (Gatto(y) \wedge Ama(x,y))))$
$\equiv \exists x (Gatto(x) \wedge \forall y \neg (Gatto(y) \wedge Ama(x,y)))$
$\equiv \exists x (Gatto(x) \wedge \forall y (\neg Gatto(y) \vee \neg Ama(x,y)))$
$\equiv \exists x (Gatto(x) \wedge \forall y (Gatto(y) \Rightarrow \neg Ama(x,y)))$
(Quest'ultima si legge: "Esiste un gatto x tale che per ogni gatto y, x non ama y", ovvero "Esiste un gatto che non ama nessun gatto").