2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Логика предикатов, проблема разрешимости
Сообщение11.05.2008, 17:30 


21/05/07
13
Уважаемые посетители форума, не могли бы вы подсказать мне формулы логики предикатов, отличные от указанных мной (V - квантор всеобщности) Увы использовать эти я не могу. По одной на каждый пример:

Пример формулы, выполнимой на бесконечном множестве и не выполнимой ни на каком конечном:
($\forall x$)($\exists y$)( P(x,y))$\wedge$ ($\forall x$)($\overline P$ (x,x)) $\wedge$ ($\forall x$)($\forall y$)($\forall z$)((P(x,y) $\wedge$ P(y,z)) $\to $ P(x,z))


Пример формулы, выполнимой на множестве из трёх элементов и не выполнимой на множестве из двух элементов:
($\exists x$)($\exists y$)($\exists z$)(P(x,y) $\wedge$ P(x,z) $\wedge$ P(y,z) $\wedge$ ($\forall t$)($\overline P$ (t,t)) )


Пример формулы, тождественно истинной на любом конечном множестве и опровержимой на бесконечном:
($\forall x$)($\forall y$)($\forall z$)[ P(x,x) $\wedge$ (P(x,z) $\to $ (P(x,y) $\vee$ P(y,z))) ] $\to $ ($\exists x$)($\forall y$)(P(x,y))



Заранее, большое спасибо за любые ответы.

 Профиль  
                  
 
 
Сообщение11.05.2008, 21:48 
Экс-модератор
Аватара пользователя


30/11/06
1265
 !  Йцуке
На форуме принято записывать формулы, используя нотацию ($\TeX$; введение, справка).

Пожалуйста, исправьте и сообщите модератору (ЛС).

 Профиль  
                  
 
 
Сообщение13.05.2008, 00:26 
Модератор


16/01/07
1567
Северодвинск
 !  Jnrty:
Вернул.


P.S. Достаточно окружить всю формулу одной парой знаков доллара, нет необходимости окружать отдельные части формулы.

$(\forall x)(\exists y)(P(x,y))\wedge(\forall x)(\overline P(x,x))\wedge(\forall x)(\forall y)(\forall z)((P(x,y)\wedge P(y,z))\to P(x,z))$

 Профиль  
                  
 
 Re: Логика предикатов, проблема разрешимости
Сообщение13.05.2008, 06:21 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Йцуке писал(а):
Уважаемые посетители форума, не могли бы вы подсказать мне формулы логики предикатов, отличные от указанных мной...


Долго смеялся :P

Вопрос напоминает следующий: не могли бы Вы подсказать натуральные числа, отличные от

$$
\sqrt{2 + \sqrt{196}}
$$

$$
\frac{1}{\pi^2} \sum_{n=0}^\infty \frac{24}{n^2}
$$

и

$$
5 +\int_{1}^{1^{100}} \sqrt{4x^2-2x} \, dx
$$

Кстати, почему бы в качестве третьей формулы не взять отрицание первой? Тоже вариант.

 Профиль  
                  
 
 
Сообщение13.05.2008, 17:27 


21/05/07
13
Цитата:
Вопрос напоминает следующий: не могли бы Вы подсказать натуральные числа, отличные от

Такой вопрос несравнимо проще чем мой. :P Мне нужны формулы, которые будут удовлетворять указанным (и заметьте достаточно узким) критериям.
По поводу отрицания первой и третьей формулы я думал еще вчера, но боюсь такой вариант мне не подходит...

 Профиль  
                  
 
 
Сообщение13.05.2008, 18:00 
Заслуженный участник


18/03/07
1068
1. Молчаливо имея в виду, что $P(x,y)$ интерпретируется как $x < y$, запишите какое-нибудь утверждение о порядке на натуральных числах. Например, «не существует наибольшего натурального числа». Для конечных подмножеств $\mathbb{N}$ такое утверждение будет неверно. Если повезёт, оно не будет выполнимым и при других «интерпретациях» $P$. Для того, чтобы повезло, нужно, вероятно, этим Вашим утверждением «довольно полно» охарактеризовать отношение $<$.

2. Молчаливо имея в виду, что $P(x,y)$ интерпретируется как $=$

3. Тут примерно как в 1.

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

И это… Порыскайте в книжках, что ли…

 Профиль  
                  
 
 
Сообщение13.05.2008, 18:58 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Йцуке писал(а):
Цитата:
Вопрос напоминает следующий: не могли бы Вы подсказать натуральные числа, отличные от

Такой вопрос несравнимо проще чем мой. :P


Это Вам так кажется. Ваш вопрос не менее тривиален, чем мой.

Добавлено спустя 3 минуты 27 секунд:

Кстати, в Ваших вариантах какая-то чушь написана. Они вовсе не являются примерами того, на что претендуют.

Добавлено спустя 23 минуты 58 секунд:

Так... Немного повнимательнее вгляделся. Снимаю своё последнее замечание относительно первой и второй формул. Относительно третьей оно остаётся в силе.

Первая формула корректна. Во второй допущена опечатка: неправильно расставлены скобки.

А вот по поводу третьей... Что, по вашему, означает, что формула "истинна на любом конечном множестве"? Если это означает, что она истинна на любой конечной модели с произвольной интерпретацией бинарного предиката $P$, то это, конечно же, ерунда. А если это означает, что для любого конечного (непустого) множества можно придумать интерпретацию $P$, при которой формула истинна, то тогда да, это верно. Но ведь и на произвольном бесконечном множестве можно придумать интерпретацию $P$, при которой формула верна! Так что насчёт третьей подумайте хорошенько!

Что касается формул, отличных от... А какие у нас ограничения на условия? Исчисление предикатов с равенством или без равенства? Допускаются ли в сигнатуре функциональные и/или константные символы? Считаются ли формулы $\Phi$ и $\neg\neg\Phi$ различными или нет? И опять же: каков точный смысл фразы "формула выполнима на множестве"? Означает ли это, что она должна быть выполнена при произвольной интерпретации сигнатурных символов или это означает, что она должна быть выполнена лишь при некоторой интерпретации?

 Профиль  
                  
 
 
Сообщение13.05.2008, 19:47 


21/05/07
13
Цитата:
Молчаливо имея в виду...

Большое спасибо, идея мне нравится, подумаю.

Цитата:
Порыскайте в книжках, что ли…

Был бы очень рад, если бы вы ещё подсказали в каких :D

Цитата:
Во второй допущена опечатка

Поправил, сказывается моя хроническая нелюбовь к ТЕХ'у. :D

Относительно третьей:я так понимаю как раз имеется ввиду это
Цитата:
для любого конечного (непустого) множества можно придумать интерпретацию , при которой формула истинна, то тогда да, это верно.


Цитата:
Что касается формул, отличных от...

Естественно, формулы полученные из этих через двойные отрицания или простые преобразования не приветствуются..

Цитата:
Означает ли это, что она должна быть выполнена при произвольной интерпретации сигнатурных символов или это означает, что она должна быть выполнена лишь при некоторой интерпретации?

Скорее всего второе :D

 Профиль  
                  
 
 
Сообщение13.05.2008, 19:56 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Вы не ответили на главный вопрос: исчисление у нас с равенством или без равенства? И сигнатура какая: произвольная или обязательно состоящая из одного-единственного символа двухместного предиката?

И понимаете ли Вы, что Ваш собственный пример третьей формулы вообще не в кассу?

Йцуке писал(а):
Цитата:
Означает ли это, что она должна быть выполнена при произвольной интерпретации сигнатурных символов или это означает, что она должна быть выполнена лишь при некоторой интерпретации?

Скорее всего второе :D


Знакома ли Вам теорема компактности и следствие из неё: если формула выполнима на моделях сколь угодно большой конечной мощности, то она выполнима и на некоторой бесконечной модели?

Если что, то имейте в виду, что теорема такая имеет место. Так что, вероятно, всё же первое, а не второе. Так как иначе, по теореме компактности, третья задача не имеет решения :)

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

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



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

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


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

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