2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Предварённая нормальная форма
Сообщение16.06.2010, 20:54 


21/03/09
406
Здравствуйте.
Готовлюсь к экзамену и
хочу разобраться как нужно решать следующие задачи
Цитата:
Найдите предварённая нормальную форму
$\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))$
только сильно совневаюсь в решении, скорей всего неправильно понимаю.

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение16.06.2010, 21:21 
Аватара пользователя


15/08/09
1458
МГУ
Ну берёте в зубы таблицу основных равносильностей на эту тему, и начинаете медленно жевать....

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение16.06.2010, 21:35 


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

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение17.06.2010, 16:09 
Аватара пользователя


18/10/08
454
Омск
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))$
только сильно совневаюсь в решении, скорей всего неправильно понимаю.

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

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение18.06.2010, 18:57 


21/03/09
406
Вроде-бы теперь уловил как надо делать
Попробую заново
Есть
$\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. шаг
а дальше незнаю.......

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

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение19.06.2010, 16:09 


21/03/09
406
:?:

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение20.06.2010, 07:14 
Аватара пользователя


18/10/08
454
Омск
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)$.

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение20.06.2010, 08:33 
Аватара пользователя


18/10/08
454
Омск
Давайте пошагово рассмотрим на примере вашей формулы:

(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)$.

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

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение22.06.2010, 17:01 


21/03/09
406
Извините что задержался.
Мне почти всё понятно, только вот это преобразование я не знаю как запомнить (а лучше понять)
mkot в сообщении #333011 писал(а):
$(\exists y \, P(y)) \to Q(x) \sim \forall y (P(y) \to Q(x))$

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

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение22.06.2010, 18:57 
Аватара пользователя


18/10/08
454
Омск
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))$.

 Профиль  
                  
 
 Re: Предварённая нормальная форма
Сообщение22.06.2010, 19:01 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group