Задача на предикаты (привести к предваренной нормальн форме)

[Виктория123]

Цитата:

А первая --- это замена связанных переменных.

$$ (\neg \ Pxy \vee Qyz) \vee \exists u(\neg Puz \mathbin{\&} Qyu)\vee \exists u\ (Puy \mathbin{\&} \neg Qux) $$

А в первой скобке я так понимаю ничего не надо заменять?
Или надо,ведь потом когда буду выносить квантор \exists u вперед,то в первой скобке его нет?

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

Да, в первой скобке ничего не надо заменять. Там ведь нет связанных переменных!

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

Дело здесь вот в чём. Следующие эквивалентности действительно имеют место:

$$ \exists u \Phi(u) \vee \exists u \Psi(u) \equiv \exists u \big(\Phi(u) \vee \Psi(u)\big) $$

$$ \forall u \Phi(u) \mathbin{\&} \forall u \Psi(u) \equiv \forall u \big(\Phi(u) \mathbin{\&} \Psi(u)\big) $$

НО!!! При этом

$$ \forall u \Phi(u) \vee \forall u \Psi(u) \not\equiv \forall u \big(\Phi(u) \vee \Psi(u)\big) $$

$$ \exists u \Phi(u) \mathbin{\&} \exists u \Psi(u) \not\equiv \exists u \big(\Phi(u) \mathbin{\&} \Psi(u)\big) $$

Предположим на секунду, что в Вашем задании вместо квантора $\exists$ везде стоит квантор $\forall$. Тогда если мы заменим обе связанные переменные на одну и ту же переменную $u$, то будем иметь формулу

$$ (\neg Pxy \vee Qyz) \vee \forall u(\neg Puz \mathbin{\&} Qyu)\vee \forall u (Puy \mathbin{\&} \neg Qux) $$

Далее, поскольку первая скобка не содержит переменной $u$, от этой формулы можно перейти к формуле

$$ \forall u \big(\neg Pxy \vee Qyz \vee (\neg Puz \mathbin{\&} Qyu)\big) \vee \forall u (Puy \mathbin{\&} \neg Qux) $$

А вот что делать дальше? Вынести вперёд квантор по $u$ ведь мы не можем!!!

Зато если бы мы изначально сделали так:

$$ (\neg \ Pxy \vee Qyz) \vee \forall u(\neg Puz \mathbin{\&} Qyu)\vee \forall v (Pvy \mathbin{\&} \neg Qvx) $$

то после

$$ \forall u \big(\neg \ Pxy \vee Qyz \vee (\neg Puz \mathbin{\&} Qyu)\big) \vee \forall v (Pvy \mathbin{\&} \neg Qvx) $$

мы могли бы перейти к тому, что требуется:

$$ \forall u \big(\neg \ Pxy \vee Qyz \vee (\neg Puz \mathbin{\&} Qyu) \vee \forall v (Pvy \mathbin{\&} \neg Qvx)\big) $$

$$ \forall u \forall v \big(\neg \ Pxy \vee Qyz \vee (\neg Puz \mathbin{\&} Qyu) \vee (Pvy \mathbin{\&} \neg Qvx)\big) $$

А если бы кванторы были вообще различны (такое ведь тоже может случится)? Тогда введения двух разных переменных уже никак не избежать.

Ещё раз повторюсь: в Вашем конкретном случае можно оставить $u$ в обоих местах. Но поелику тут кроется большая опасность, Вы должны очень прочно запомнить, когда это делать можно, а когда нельзя. У меня студенты часто предпочитают, чтобы лишний раз не перепутать, сразу менять все связанные переменные так, чтобы каждая поменялась на свою, особенную. И в этом я их понимаю.

В общем, доведите пример до ответа и покажите, что у Вас получилось.

[Виктория123]

Ну да,я поняла,лучше чтобы были разные замены
Вот,что получилось.Все так?

$$ (\neg \ Pxy \vee Qyz) \vee \exists u(\neg Puz \mathbin{\&} Qyu)\vee \exists v (Pvy \mathbin{\&} \neg Qvx) $$

$$ \exists u (\neg \ Pxy \vee Qyz ) \vee (\neg Puz \mathbin{\&} Qyu) \vee \exists v (Pvy \mathbin{\&} \neg Qvx)\) $$

$$ \exists u \exists v ((\neg \ Pxy \vee Qyz ) \vee (\neg Puz \mathbin{\&} Qyu) \vee (Pvy \mathbin{\&} \neg Qvx)) $$

Значит это и есть предваренная нормальная форма?
А что надо было еще сделать,чтобы получилась пренексная нормальная форма?(Вы там писали что,надо что-то сделать с бескванторной частью)

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

Ответ правильный!!!

Только выкладки не очень. Во второй формуле глупость написана. Но я подозреваю, что это просто опечатка: Вы упустили пару скобок. Должно быть так:

$$ \exists u \big( (\neg \ Pxy \vee Qyz ) \vee (\neg Puz \mathbin{\&} Qyu)\big) \vee \exists v (Pvy \mathbin{\&} \neg Qvx) $$

или так

$$ \exists u \big( \neg \ Pxy \vee Qyz \vee (\neg Puz \mathbin{\&} Qyu)\big) \vee \exists v (Pvy \mathbin{\&} \neg Qvx) $$

Но ни в коем случае не так, как у Вас.

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

Если хотите разобраться в теме, то лучше решите ещё пару примеров:

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

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

Они чуть сложнее, чем Ваш. Но если их решите, то значит и любой пример потом решить сможете

[Виктория123]

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

А можно вот еще спросить про одну задачку.

Надо доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.
(A \to (B \to C)) выводима из (B \to (A \to C))

Вот как я начала решать

$1.$(A \to (B \to C)) (Гипотеза)
$2.$(A \to (B \to C)) \to ((A \to B) \to(A \to C)) (Аксиома)
$3.$((A \to B) \to (A \to C)) (Применение правила modus ponens (2,3))

А дальше как? Можно ли просто сделать замену $(A \to B)$ на $\math{B}$ и получить ответ или нет?

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

Простите, а вот под номером 2... Что там у Вас? Скобка закрывается, скобка открывается, и никаких логических связок между скобками. Так не бывает!!!

[Виктория123]

Исправила,там была импликация

[luitzen]

Виктория123 писал(а):

Можно ли просто сделать замену $(A \to B)$ на $\math{B}$ и получить ответ или нет?

Не было такого уговору…

Вам, Виктория123, нужно в каком-то смысле просто поменять местами $A$ и $B$. Нельзя ли это сделать при помощи всего лишь неоднократно примененной теоремы дедукции?

Ведь слева от штопора может быть больше одной посылки? И мы ведь можем менять их там местами?

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

Виктория123 писал(а):

Надо доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.
(A \to (B \to C)) выводима из (B \to (A \to C))

Я только сейчас увидел фразу "можно пользоваться теоремой о дедукции".

В свете этого задача оказывается весьма и весьма тривиальной. luitzen Вам уже на это указал.

$$ \{ A \rightarrow (B \rightarrow C), A, B \} \rhd C $$

$$ \{ A \rightarrow (B \rightarrow C), B \} \rhd A \rightarrow C $$

$$ \{ A \rightarrow (B \rightarrow C) \} \rhd B \rightarrow (A \rightarrow C) $$

Оба перехода сделаны по теореме о дедукции. Так что всё, что нужно --- это обосновать первое утверждение. С этим-то, надеюсь, справитесь

[Виктория123]

Да,понятно,что 2 раза применяется теорема дедукции.

А не подскажите немного,как объяснить первую строку,нам же не дано ,что $A$,$B$ $-$гипотезы

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

Виктория123 писал(а):

А не подскажите немного,как объяснить первую строку,нам же не дано ,что $A$,$B$ $-$гипотезы

В смысле??? В первой-то строке как раз и дано, что $A$ и $B$ --- гипотезы.

Я не понимаю Ваш вопрос.

[Виктория123]

Я имею ввиду,как доказать,что $A$ и $B$ гипотезы, то есть почему можно написать Вашу первую строчку?

Добавлено спустя 6 минут 37 секунд:

Ведь нам дана только гипотеза
(A \to (B \to C))

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

Тогда у меня к Вам вопрос: а что именно записано в первой строчке? Какое утверждение в ней содержится?

[Виктория123]

ну то,что из этих трех гипотез вы водится формула.

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

Виктория123 писал(а):

ну то,что из этих трех гипотез вы водится формула.

Вы не согласны с этим утверждением?