Логика предикатов, проблема разрешимости

[Йцуке]

Уважаемые посетители форума, не могли бы вы подсказать мне формулы логики предикатов, отличные от указанных мной (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))



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

[нг]

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

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

[Jnrty]

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

[Профессор Снэйп]

Йцуке писал(а):

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

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

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

$$ \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 $$

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

[Йцуке]

Цитата:

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

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

[luitzen]

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

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

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

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

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

[Профессор Снэйп]

Йцуке писал(а):

Цитата:

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

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

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

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

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

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

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

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

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

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

[Йцуке]

Цитата:

Молчаливо имея в виду...

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

Цитата:

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

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

Цитата:

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

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

Относительно третьей:я так понимаю как раз имеется ввиду это

Цитата:

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

Цитата:

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

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

Цитата:

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

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

[Профессор Снэйп]

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

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

Йцуке писал(а):

Цитата:

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

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

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

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