Предварённая нормальная форма

[nbyte]

Здравствуйте.
Готовлюсь к экзамену и
хочу разобраться как нужно решать следующие задачи

Цитата:

Найдите предварённая нормальную форму
$\forall x(\exists y(P(y)) \to Q(x))\& \forall x\exists y(R(x,y))$

пробую решить, получаю
$\forall x\exists y(((P(y)) \to Q(x))\& (R(x,y))$
только сильно совневаюсь в решении, скорей всего неправильно понимаю.

[maxmatem]

Ну берёте в зубы таблицу основных равносильностей на эту тему, и начинаете медленно жевать....

[nbyte]

А можете посоветовать где имеено её найти? (ну чтоб понятная была для новичка)

[mkot]

nbyte в сообщении #332026 писал(а):

А можете посоветовать где имеено её найти? (ну чтоб понятная была для новичка)

М. б. в конспекте?

А вообще используя правило:
Чёрный или белый единорог существует тогда и только тогда, когда существует белый единорог или чёрный единорог.
выводится если не всё, то добрая половина основных эквивалентностей.

-- Чт июн 17, 2010 20:15:20 --

nbyte в сообщении #332015 писал(а):

Цитата:

Найдите предварённая нормальную форму
$\forall x(\exists y(P(y)) \to Q(x))\& \forall x\exists y(R(x,y))$

пробую решить, получаю
$\forall x\exists y(((P(y)) \to Q(x))\& (R(x,y))$
только сильно совневаюсь в решении, скорей всего неправильно понимаю.

Да, неправильно, распишите по шагам, чтоб было о чём говорить, хотя конечно понятно, что здесь не так.

[nbyte]

Вроде-бы теперь уловил как надо делать
Попробую заново
Есть
$\forall x(\exists y(P(y)) \to Q(x))\& \forall x\exists y(R(x,y))$
пробую решить

1. шаг
преобразовываю
$\exists y(P(y)) \to Q(x) \equiv \exists yP(y) \to Q(x)$
получаю
$\forall x(\exists yP(y) \to Q(x))\& \forall x\exists y(R(x,y))$

2. шаг
использую
$p \to q \equiv \neg p \vee q$
получаю
$\forall x(\neg P(y) \& Q(x))\& \forall x\exists y(R(x,y))$

3. шаг
а дальше незнаю.......

Правильно я хоте-бы начал?

[nbyte]

[mkot]

nbyte в сообщении #332559 писал(а):

$\exists y(P(y)) \to Q(x) \equiv \exists yP(y) \to Q(x)$

Ну, почему?! Ведь
$(\forall x \, P(x)) \to Q \sim \exists x \, (P(x) \to Q)$.

На шаге 2 квантор вообще потерялся.

-- Вс июн 20, 2010 11:27:59 --

Эх, ну вот смотрите:

(1) $(\forall x \, P(x)) \vee Q \sim \forall y \, (P(y) \vee Q)$, если $y$ не входит свободно ни в $P(x)$, ни в $Q$,
(2) $(\exists x \, P(x)) \vee Q \sim \exists y \, (P(y) \vee Q)$, если $y$ не входит свободно ни в $P(x)$, ни в $Q$,
(3) $(\forall x \, P(x)) \wedge Q \sim \forall y \, (P(y) \wedge Q)$, если $y$ не входит свободно ни в $P(x)$, ни в $Q$,
(4) $(\exists x \, P(x)) \wedge Q \sim \exists y \, (P(y) \wedge Q)$, если $y$ не входит свободно ни в $P(x)$, ни в $Q$,
(5) $(\forall x \, P(x)) \to Q \sim \exists y \, (P(y) \to Q)$, если $y$ не входит свободно ни в $P(x)$, ни в $Q$,
(6) $(\exists x \, P(x)) \to Q \sim \forall y \, (P(y) \to Q)$, если $y$ не входит свободно ни в $P(x)$, ни в $Q$,
(7) $P \to (\forall x \, Q(x)) \sim \forall y \, (P \to Q(y))$, если $y$ не входит свободно ни в $P$, ни в $Q(x)$,
(8) $P \to (\exists x \, Q(x)) \sim \exists y \, (P \to Q(y))$, если $y$ не входит свободно ни в $P$, ни в $Q(x)$,
(9) $\neg \forall x \, P(x) \sim \exists x \,\neg P(x)$,
(10) $\neg \exists x \, P(x) \sim \forall x \,\neg P(x)$.

[mkot]

Давайте пошагово рассмотрим на примере вашей формулы:

(1) Имеем
$\Big(\forall x \big((\exists y \, P(y)) \to Q(x)\big) \Big)\wedge (\forall x \exists y \, R(x,y))$
(2) Формула приводится к н. ф. "снизу-вверх", то есть начиная с самых глубоких подформул, вы так и сделали. Имеем $(\exists y \, P(y)) \to Q(x) \sim \forall y (P(y) \to Q(x))$, переменную можно не переименовывать, так как $y$ всё одно не входит свободно в $Q(x)$:
$\Big(\forall x \forall y (P(y) \to Q(x)) \Big)\wedge (\forall x \exists y \, R(x,y))$.
(3) Теперь из левого конъюнкта выносим $\forall x$, во второй конъюнкт $x$ вободно не входит, поэтому можно не переименовывать:
$\forall x \Big(\big(\forall y (P(y) \to Q(x)) \big)\wedge (\forall x \exists y \, R(x,y))\Big)$.
(4) Выносим из первого конъюнкта $\forall y$:
$\forall x \forall y \Big((P(y) \to Q(x))\wedge (\forall x \exists y \, R(x,y))\Big)$.
(5) Теперь из второго конъюнкта выносим $\forall x$, так как $x$ теперь входит свободно в первый конъюнкт, то $x$ переименуем в $z$:
$\forall x \forall y \forall z\Big((P(y) \to Q(x))\wedge (\exists y \, R(z,y))\Big)$.
(6) Далее выносим $\exists y$, по аналогичным причинам переименовываем:
$\forall x \forall y \forall z \exists w \Big((P(y) \to Q(x)) \wedge R(z,w)\Big)$.

Кто-то быть может скажет, что один квантор можно было сэкономить, но это не принципиально.

[nbyte]

Извините что задержался.
Мне почти всё понятно, только вот это преобразование я не знаю как запомнить (а лучше понять)

mkot в сообщении #333011 писал(а):

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

Вы не могли-бы поподробней объяснить откуда оно берётся

[mkot]

nbyte в сообщении #333832 писал(а):

Извините что задержался.
Мне почти всё понятно, только вот это преобразование я не знаю как запомнить (а лучше понять)

mkot в сообщении #333011 писал(а):

$(\exists y \, P(y)) \to Q(x)$\sim(\forall y \, \neg P(y)) \vee Q(x) \sim \forall y (\neg P(y) \vee Q(x)) \sim \forall y (P(y) \to Q(x))$ \sim \forall y (P(y) \to Q(x))$

Вы не могли-бы поподробней объяснить откуда оно берётся

Формальный вывод можно найти например у Мендельсона. А чтоб запомнить,
ну например, можно держать в голове следующую цепочку:
$(\exists y \, P(y)) \to Q(x) \sim \neg(\exists y \, P(y)) \vee Q(x) \sim$
$\sim(\forall y \, \neg P(y)) \vee Q(x) \sim \forall y (\neg P(y) \vee Q(x)) \sim \forall y (P(y) \to Q(x))$.

[nbyte]

А, вот как
Ну теперь всё вроде-бы всё прояснилось как это делается, буду пробовать дальше решать другие по аналогии.
mkot, Спасибо Вам.