What's the difference between the two logic phrases?

34 Views Asked by At

I understand how these two differ when transformed into CNF, but I can't understand how they differ when translated from/to Human language.

$$ 1. \exists x[p(x)\to \exists yq(y)] $$ $$ 2. \exists xp(x)\to \exists y q(y) $$

Can you give me a sentence in English that will relate to each?

1

There are 1 best solutions below

2
On BEST ANSWER

The two are not equivalent; the first one is equivalent to: 1') $∀xp(x) → ∃yq(y)$.

In order to find a counterexample, we have to find an interpretation where 1') is True and 2) is False.

Consider this arithmetical example for 2): $\exists x (x=0) \to \exists y (y < 0)$. It is clearly False in $\mathbb N$.

Regarding 1') instead, it is: $\forall x (x=0) \to \exists y (y < 0)$, which is $\text {F} \to \text {F}$ and thus is False in $\mathbb N$.

A natural language example (but, IMO, much less "natural") will be with the domain of Humans and with "Blonde" for $p$ and "Immortal" for $q$.

While 2) will be:

"if there is some Blonde (Human), then there is some Immortal (Human)",

which is a conditional with true antecedent and false consequent, and thus false, we have for 1):

"there is some Human such that (if she is Blonde, then there is some Immortal (Human))",

which is false, because there is some black-haired human.