2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Помогите закончить приведение к ПНФ. Логика предикатов
Сообщение23.09.2012, 12:52 


23/09/12
5
Здравствуйте. Необходимо привести к предваренной нормальной форме (то есть как я понял чтобы все кванторы были слева) следующую формулу:
$\forall x ( \neg A(x) \to \exists x(B(y))) \to (\neg B(y) \to A(x)) $
Следуя алгоритму найденному на этом форму сначала избавляюсь от импликации:
В правой скобке:
$\forall x ( \neg A(x) \to \exists x(B(y))) \to (B(y) \vee  A(x) ) $
В первой скобке
$\forall x ( A(x) \vee \exists x(B(y))) \to (B(y) \vee  A(x) ) $
Последняя импликация
$\neg \forall x ( A(x) \vee \exists x(B(y))) \vee (B(y) \vee  A(x) ) $
Избавляюсь от отрицания
$\exists x (\neg( A(x) \vee \exists x(B(y)))) \vee (B(y) \vee  A(x) ) $
$\exists x (\neg A(x) \wedge \neg\exists x(B(y))) \vee (B(y) \vee  A(x) ) $
$\exists x (\neg A(x) \wedge \forall x(\neg B(y))) \vee (B(y) \vee  A(x) ) $
В вот дальше затык, не понимаю как вынести квантор общности, и возможно ли это. Заранее спасибо.

 Профиль  
                  
 
 Re: Помогите закончить приведение к ПНФ. Логика предикатов
Сообщение23.09.2012, 19:26 
Аватара пользователя


01/12/06
697
рм
Почему в данной формуле первый $y$ несвязанный? На каком-то этапе, если я хорошо помню, надо переименовать переменные.

 Профиль  
                  
 
 Re: Помогите закончить приведение к ПНФ. Логика предикатов
Сообщение23.09.2012, 19:50 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
gefest_md в сообщении #622683 писал(а):
Почему в данной формуле первый $y$ несвязанный?

Формально это ничему не противоречит. Хотя я, думаю, что тут скорее всего ТС переписывая условие ошибку допустил.

 Профиль  
                  
 
 Re: Помогите закончить приведение к ПНФ. Логика предикатов
Сообщение24.09.2012, 07:00 


23/09/12
5
Нет при переписывании ошибка допущена не была. Раз 20 сравнил с методичкой. А может быть в принципе нельзя привести к ПНФ?

 Профиль  
                  
 
 Re: Помогите закончить приведение к ПНФ. Логика предикатов
Сообщение24.09.2012, 08:19 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
kirflaer в сообщении #622843 писал(а):
А может быть в принципе нельзя привести к ПНФ?

Так не бывает :shock: К ПНФ можно привести всегда, как любое натуральное число можно записать в десятичной системе счисления.

Тут просто квантор по $x$ внутри квантора по $x$, и навешан на формулу, в которой $x$ вроде бы как нет. Возможно, в методичке опечатка, а, возможно, так и задумывалось...

-- Пн сен 24, 2012 11:20:20 --

P. S. Скобок много лишних. Некрасиво!

 Профиль  
                  
 
 Re: Помогите закончить приведение к ПНФ. Логика предикатов
Сообщение25.09.2012, 03:27 


06/09/12
5
Если действительно не опечатка, а так задумано, то...
квантор всеобщности можно выбросить вообще, потому что верно следующее:
Если (произвольная) формула $Z$ не содержит свободно переменную $x$, то $Z \equiv \forall x Z \equiv \exists x Z$.
Кстати, чтобы формула стала приведённой, нужно не только чтобы все кванторы оказались слева, но и чтобы в области их действия оказалась вся остальная формула. А вот чтобы добиться этого, одну переменную действительно придётся переименовать.

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

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



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

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


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

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