Logica quantificabile. Differenza tra $\forall y, \forall z(F(y,z) \implies Q(y)) $ e $\forall y, \exists z (F(y,z)\implies Q(y))$.

Aug 25 2020

Sto leggendo "come dimostrarlo" e sto lottando sulla seguente domanda:

"Analizza la forma logica: se qualcuno nel dormitorio ha il morbillo, allora tutti quelli che hanno un amico nel dormitorio dovranno essere messi in quarantena".

Mi è venuto in mente quanto segue:

$\exists x(D(x) \land M(x))\implies \forall y ,\forall z ((F(y,z) \land D(z)) \implies Q(y))$

Dove $D(x) = $ x è nel dormitorio, $M(x)=$ x ha il morbillo, $F(y,z)=$ y è un amico di z, $Q(x)=$ x deve essere messo in quarantena.

Ho cercato la risposta online e la mia risposta è corretta, tranne invece di $\forall z$ è $\exists z$. Non riesco a risolverlo. Sicuramente per tutte le combinazioni di persone y e z, se sono amici (es:$F(y,z)$) allora la mia affermazione / soluzione è corretta.

Qualcuno può spiegarmi perché dovremmo usare $\exists z$ invece di $\forall z$ in questo caso?

Risposte

3 TannerSwett Aug 25 2020 at 02:56

Immagino che tu abbia trascurato una differenza tra parentesi.

La tua risposta è

$$\forall y \forall z ((F(y,z) \land D(z)) \implies Q(y)),$$

e immagino che la risposta nel libro sia

$$\forall y (\exists z (F(y,z) \land D(z)) \implies Q(y)).$$

Entrambe queste frasi sono equivalenti, quindi entrambe sono corrette. Mi piace di più la seconda frase, poiché la frase "chi ha un amico" suona come una quantificazione esistenziale all'interno dell'antecedente di un'implicazione. Ma anche il primo è corretto.

D'altra parte, la frase

$$\forall y \exists z ((F(y,z) \land D(z)) \implies Q(y))$$

è completamente diverso. Questa frase lo dice per ogni persona$y$, c'è un'altra persona ($z$) chi

  • non è un amico di $y$, o
  • non vive nel dormitorio, o
  • dovrà essere messo in quarantena.

Se la chiave di risposta ha davvero la terza frase qui, allora è probabilmente un errore di stampa.


A proposito, ecco come dimostrare che le prime due frasi sono equivalenti. Cominciamo con la frase

$$\forall y \forall z ((F(y,z) \land D(z)) \implies Q(y)).$$

Innanzitutto, riscriviamo l'implicazione come disgiunzione:

$$\forall y \forall z (\neg (F(y,z) \land D(z)) \lor Q(y)).$$

Fattori di disgiunzione fuori dalla quantificazione universale:

$$\forall y (\forall z \ \neg (F(y,z) \land D(z)) \lor Q(y)).$$

Legge di De Morgan per i quantificatori:

$$\forall y (\neg \exists z (F(y,z) \land D(z)) \lor Q(y)).$$

Infine, riscrivi di nuovo la disgiunzione come implicazione:

$$\forall y (\exists z (F(y,z) \land D(z)) \implies Q(y)).$$