Задача на предикаты

[vityanya]

Доброе время суток.
Помогите решить задание пожалуйста... я предикаты вообще не понимаю((( но надо как то разобарться...
$A(x,y)\to($\forall y)b(y)$

а)Переименовать связанные переменные(если это необходимо), затем в полученной ормуле указать свободные и связанные переменные, определить длину формулы, привести данную формулу(равносильным образом) к приведенной, нормальной форме, указать длину получнной формулы.
б)Определить, выполнимы или нет эти формулы, если считать что А(х,у) - предикат 2х=у, а В(х) - предикат: х-четное число(причем оба предиката имеют интерпретацию всех целых неотрицательных чсел).


Отделено от чужой темы. АКМ

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

Ваши попытки решения?

[vityanya]

Простите, но я даже не наю как начать, а именно: Переименовать связанные переменные(если это необходимо)
надо ли их переименовывать в данном случае? и в каких случаях они переименовываются?
вот хотяб для начала это, а потом мона и решение предоставить попробовать по вашим прошлым обсуждениям немного понял алгоритм решения...

[vityanya]

Вот как то так у меня:
Свободные переменные - 1 (у)
Связанные переменные - 2 (х,у)

$A(x,y) \to ($\forall y)B(y)$
$!A(x,y)V($\forall y)B(y)$
$A(x,y) !(\forall y)B(y)$
$!B(y)A(x,y)(\forall y)$

где ! - отрицание.
Длина формулы - 4
А далее не знаю что и как...

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

vityanya в сообщении #342992 писал(а):

Отделено от чужой темы. АКМ

По-моему, зря.

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

[vityanya]

Перечитав предыдущий я опять же не все понял норм...
Сначала избавляемс от импликации:
$\neg A(x,y)\vee ($\forall y)B(y)$

Цитата:

2) Проносите отрицания под кванторы.

То есть надо, чтоб перед $A(x,y)$ не было $\neg$,
а было тут $ \neg ($\forall y)$, а далее было так $(\exists \ z )\neg B(y)$
я правильно понял?

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

vityanya в сообщении #343198 писал(а):

я правильно понял?

Нет. Перед $A$ отрицание стоять может и, даже, более того, обязано там стоять. Отрицаний не должно быть перед кванторами. То есть, например, формулу типа $\neg \forall x H(x,y)$ следует преобразовать в $\exists x \neg H(x,y)$ и т. п. А совсем избавиться от отрицаний никак и не получится; если отрицание есть в условии, то от него часто никуда не деться.

Начали Вы правильно: $A(x,y) \rightarrow \forall y B(y)$ преобразовали в $\neg A(x,y) \vee \forall y B(y)$. Теперь проносить отрицания никуда не надо, они и так уже стоят на нужных местах. Следующий шаг --- замена связанной переменной: поскольку переменная $y$ входит свободно в первый дизьюнктивный член, то Вы не можете взять и сразу вынести вперёд квантор по $y$. Нужно менять $y$ на что-то другое. Сделайте и покажите, что у Вас получилось.

-- Вс авг 08, 2010 15:51:15 --

P. S. Неограниченные кванторы не принято брать в скобки, а ограниченные принято. Сравните: $\forall x \Phi(x)$, $(\forall x \in X) \Phi(x)$, $(\forall x \leqslant x_0) \Phi(x)$. В последних двух случаях скобки вокруг квантора нужны, а в первом --- не нужны.

[vityanya]

ммм...
$\neg A(x,y)\vee \forall u B(u)$
так?

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

vityanya в сообщении #343245 писал(а):

ммм...
$\neg A(x,y)\vee \forall u B(u)$
так?

Да, годится.

Ну а теперь последнее действие: выносите квантор вперёд.

[vityanya]

$\forall u (\neg A(x,y) \vee B(u))$

так?

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

vityanya в сообщении #343248 писал(а):

$\forall u (\neg A(x,y) \vee B(u))$

так?

Да. Как видите, всё очень просто

Предлагаю решить более замысловатый пример:

$$ \big(\forall x \exists y P(x,y,z) \rightarrow \forall y \exists z Q(x,y,z)\big) \rightarrow \forall z \exists x R(x,y,z) $$

Если с ним справитесь, то больше в этой теме для Вас никаких сложностей не будет

[vityanya]

ммм.. а длина формулы чему буде равна и от чего она зависит?

Цитата:

б)Определить, выполнимы или нет эти формулы, если считать что А(х,у) - предикат 2х=у, а В(х) - предикат: х-четное число(причем оба предиката имеют интерпретацию всех целых неотрицательных чсел).

и это как понять?

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

vityanya в сообщении #343258 писал(а):

ммм.. а длина формулы чему буде равна и от чего она зависит?

Длина формулы --- это просто количество входящих в неё символов. Формула $\forall u \big(\neg A(x,y) \vee B(u)\big)$ имеет длину $16$ (квантор, переменная, скобка, знак отрицания, скобка и т. д., короче, считаем всё). Хотя допускаю, что в Вашем конкретном учебном заведении на том конкретном курсе, который Вы слушали, длину формулы могли определять чуть-чуть по другому: например, считать $\forall u$ за один символ, а не за два и т. п. Эти вещи совершенно не принципиальны.

vityanya в сообщении #343258 писал(а):

Определить, выполнимы или нет эти формулы, если считать что А(х,у) - предикат 2х=у, а В(х) - предикат: х-четное число(причем оба предиката имеют интерпретацию всех целых неотрицательных чисел).

это как понять?

Хм... Наверное, так и понять, как написано: выяснить, верна ли формула на натуральных числах. Точнее, выяснить, для каких натуральных $x$ и $y$ формула верна.

А теперь то же самое, но чуть подробнее.

1) Ваше формула содержит свободные переменные, а про такие формулы бессмысленно говорить, истинны они или ложны. Простейший пример: формула $2 + 2 = 4$ истинна, формула $2 + 3 = 4$ ложна, а про формулу $2 + x = 4$ как-то даже бессмысленно говорить, будет она истинной или ложной. Сначала надо задать означивание свободной переменной, то есть, проще говоря, указать, чему равен $x$

2) Иногда (хотя это отнюдь не общепринято) про формулу со свободными переменными говорят, что она истинна, если она выполняется при всех допустимых означиваниях свободных переменных. И также говорят, что она ложна, если она не выполняется при всех означиваниях. Так, например, формула $0 + x = x$ истинна, а формула $1 + x = x$ ложна. А формула $x + x = x$ не истинна (при некоторых $x$ равенство не выполняется), но и ложной её тоже назвать нельзя (поскольку равенство выполняется при $x = 0$). Честно говоря, мне всё это представляется мутным и неблагодарным делом, и у себя на курсе в НГУ я предпочитаю вообще не рассматривать понятия истинности или ложности для подобных формул. Какие определения на этот счёт были конкретно у Вас я, увы, не знаю.

3) Когда говорят про истинность или ложность предложения (предложением называется формула без свободных переменных), то важно указывать не только саму формулу, но и модель, на которой формула рассматривается. К примеру, формула $\exists x (x \cdot x = 2)$ истинна на действительных числах, но ложна на рациональных. Но с этим у Вас в задании вроде всё в порядке: указана конкретная модель --- натуральные числа $\mathbb{N} = \{ 0,1,2,\ldots \}$.

4) Какая-то у Вас странная формулировка задачи в пункте (б): написано "выполнимы или нет эти формулы", а формула всего одна. Ладно, будем считать, что множественное число в данном случае --- просто опечатка.

5) Ну и что, в конце концов, утверждает Ваша формула? А утверждает она следующее: "Если $y = 2x$, то все числа чётные". Поскольку не все натуральные числа являются чётными, то заключение импликации ложно и сама ипликация будет истинной в том и только в том случае, когда она имеет ложную посылку. То есть Ваша формула истинна при всех натуральных $x$ и $y$, для которых $y \neq 2x$, и ложна для всех натуральных $x$ и $y$, для которых $y = 2x$. Проще говоря, Ваша формула эквивалентна утверждению о том, что $y \neq 2x$.

6) Ещё какие-то вопросы остались?

[vityanya]

Нифига себе... Да, с Вашей помощью начал понимать поболее, чем объясняли в универе...
Вот решение Вашего задания:

$(\forall x\exists yP(x,y,z) \to \forall y\exists zQ(x,y,z))\to \forall z\exists xR(x,y,z)$
$(\neg \forall x\exists yP(x,y,z) \vee \forall y\exists zQ(x,y,z))\to \forall z\exists xR(x,y,z)$
$\neg (\neg \forall x\exists yP(x,y,z) \vee \forall y\exists zQ(x,y,z))\vee \forall z\exists xR(x,y,z)$
$\forall x\exists yP(x,y,z)\neg \forall y\exists zQ(x,y,z)\vee \forall z\exists xR(x,y,z)$
$\forall x\exists yP(x,y,z)\forall z\exists y\neg Q(x,y,z)\vee \forall z\exists xR(x,y,z)$
$\forall x\forall z \exists yP(x,y,z)\neg Q(x,y,z)\vee \forall z\exists xR(x,y,z)$

Заменяем переменную x:

$\exists x \equiv \exists u$

Получаем:

$\forall x\forall z \exists yP(x,y,z)\neg Q(x,y,z)\vee \forall z\exists uR(u,y,z)$
$\forall z(\forall x\exists y\exists uP(x,y,z)\neg Q(x,y,z)\vee R(u,y,z))$

Где ошибки?

[vityanya]

Нашел сам где точно не правильно:

$\forall x\exists yP(x,y,z)\forall z\exists y\neg Q(x,y,z)\vee \forall z\exists xR(x,y,z)$
после этого не правильно идет...

а так?

$\forall x\forall z(\exists yP(x,y,z)\exists y\negQ(x,y,z))\vee \forall z\exists xR(x,y,z)$

$\forall x\forall z\exists x((\exists yP(x,y,z)\exists y\negQ(x,y,z))\vee \forall zR(x,y,z))$

что то намудрил я

ммм.... еще мысль есть с заменой переменной в предикате $R$ и вынести квантор вперед...