квантор

[gefest_md]

Формулы

$$\forall x(P(x)\to\exists yQ(y))$$

и

$$\exists y\forall x(P(x)\to Q(y))$$

не эквивалентны?

[zhoraster]

Кванторы, формулы...
Давайте попробуем с яблоками и грушами, как в начальной школе.
Первое высказывание: "Для любого яблока, если оно вкусное, то найдется вкусная груша".
Второе: "Найдется такая груша, что для любого яблока, если оно вкусное, то и груша тоже".

Эквивалентны ли эти высказывания?

[Iby]

да

[gefest_md]

Показать справедливость выводимости в одну сторону

$$\exists y\forall x(P(x)\to Q(y))\vdash\forall x(P(x)\to\exists yQ(y))$$

очень просто. Доказать обратное

$$\forall x(P(x)\to\exists yQ(y))\vdash\exists y\forall x(P(x)\to Q(y))$$

не получается.

[Munin]

А если через промежуточный шаг $(\forall xP(x))\to\exists yQ(y)$?

[Padawan]

Доказывая, что из первой формулы следует вторая, рассмотрите два случая 1) $\exists y Q(y)$ истинно 2) $\exists y Q(y)$ ложно.