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

[vityanya]

Профессор Вы где???

[vityanya]

Помогите еще решить такое задание пожалуйста

$\exists xA(x,y) ~ B(y)$

Моё решение:

$(\exists xA(x,y) \to B(y))(B(y) \to \exists xA(x,y))$

$(\neg \exists xA(x,y) \vee B(y))(\neg B(y) \vee \exists xA(x,y))$

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

А что дальше сделать не знаю

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

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

Помогите еще решить такое задание пожалуйста

$\exists xA(x,y) ~ B(y)$

Э-э-э... Ну я же не могу всю жизнь на форуме сидеть. В жизни много других интересных вещей

Я не понял условие. Какая логическая связка между $A(x,y)$ и $B(y)$?

-- Вс авг 15, 2010 20:44:53 --

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

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

Ага Опять же в формулах явно не хватает логических связок. Мне трудно оценить, верен Ваш ответ или нет, он просто синтаксически некорректен.

[vityanya]

там эквиваленция должна быть между А и В простите, вроде писал тильду...

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

В смысле $\exists x A(x,y) \sim B(y)$? То есть сокращение для $(\exists x A(x,y) \rightarrow B(y)) \mathop{\&} (B(y) \rightarrow \exists x A(x,y))$?

Вы там в своём решении конъюнкции расставьте. А то скобка закрывается, потом сразу скобка открывается, логической связки нету, непорядок...

И как это Вы не понимаете, что делать дальше? Выносить кванторы вперёд, меняя, при необходимости, связанные переменные. Начните с того, что вынесите кванторы вперёд в двух дизьюнкциях.

[vityanya]

$(\forall x (\neg A(x,y)\vee B(y))) \mathop{\&}(\exists x(\neg B(y)\vee A(x,y)))$

Правильно? А далее тогда:

$\forall x\exists x ((\neg A(x,y)\vee B(y)) \mathop{\&}(\neg B(y)\vee A(x,y)))$

так?

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

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

Правильно?

До этого момента правильно.

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

А далее тогда...

А вот далее уже неправильно

Сами посмотрите, что получилось! У Вас идут подряд два квантора по одной переменной. Формально это не запрещено, но выглядит довольно бессмысленно: внешний квантор по $x$ действует на формулу, не содержащую $x$ в качестве свободной переменной!!!

Распишите подробнее переход от верхней строчки к нижней и увидите, где ошибка.

[vityanya]

замена переменной?

Вместо $\exists x$ надо $\exists u$ к примеру? А остальное оставить как есть?

Или вместо $\forall x\neg A(x,y)$ (в первом случае) написать $\forall u\neg A(u,y)$ ???

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

Да, совершенно верно.

Если по порядку:

$$ \begin{array}{c} \forall x(\neg A(x,y) \vee B(y)) \mathop{\&} \exists x(\neg B(y) \vee A(x,y)) \equiv \\ \forall x \Big((\neg A(x,y) \vee B(y)) \mathop{\&} \exists x (\neg B(y) \vee A(x,y))\Big) \not\equiv \\ \forall x \exists x \Big((\neg A(x,y) \vee B(y)) \mathop{\&} (\neg B(y) \vee A(x,y))\Big) \end{array} $$

Первый переход абсолютно законен, поскольку выносим вперёд $\forall x$ из первого конъюнктивного члена, в то время как во второй конъюнктивный член $x$ свободно не входит. Но второй переход уже незаконен. Мы хотим вынести вперёд $\exists x$ из второго конъюнктивного члена, но этого делать нельзя, ибо в первом конъюнктивном члене $x$ теперь является свободной переменной. Прежде чем выносить, надо менять связанную переменную. Например, так:

$$ \begin{array}{c} \forall x(\neg A(x,y) \vee B(y)) \mathop{\&} \exists x(\neg B(y) \vee A(x,y)) \equiv \\ \forall x \Big((\neg A(x,y) \vee B(y)) \mathop{\&} \exists x (\neg B(y) \vee A(x,y))\Big) \equiv \\ \forall x \Big((\neg A(x,y) \vee B(y)) \mathop{\&} \exists u (\neg B(y) \vee A(u,y))\Big) \equiv \\ \forall x \exists u \Big((\neg A(x,y) \vee B(y)) \mathop{\&} (\neg B(y) \vee A(u,y))\Big) \end{array} $$