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

[Виктория123]

Помогите решить пожалуйста!

надо формулу исчисления предикатов привести к предварённой нормальной форме:

$(P(x, y) \to Q(y, z)) \vee (!(($\forall x)(P(x, z) \vee (!Q(y, x))))) \vee (( \exists \ z)( P(z, y) \wedge (!Q(z, x))))$
где ! значит отрицание

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

А в чём проблема? Алгоритм стандартный:

1) Избавляетесь от импликаций.
2) Проносите отрицания под кванторы.
3) Заменяете связанные переменные и выносите кванторы вперёд.
4) Проделываете всё, что надо, с бескванторной частью.

Получится пренексная нормальная форма. Что такое предварённая, точно не помню, но, по моему, примерно то же самое.

Какой именно шаг вызывает затруднения?

[Виктория123]

Спасибо за план решения.
Но я просто совсем не понимаю,как это решать (

[luitzen]

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

$$ (Pxy \to Qyz) \vee \neg \forall x\, (Pxz \vee \neg Qyx) \vee \exists z\, (Pzy \wedge \neg Qzx) $$

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

Ну и чем это "читабельней" по сравнению с вариантом автора? Меня, к примеру, отсутствие скобок после предикатов сильно раздражает. У Виктории они хоть стоят.

to Виктория123: Что, совсем-совсем ничего не знаете? Как же Вам, бедненькой помочь?.. Давайте начнём со следующего:

1) Дайте определение предварённой нормальной формы (заодно хоть узнаем, к чему стремимся )

2) Пользуясь эквивалентностью $\Phi \rightarrow \Psi \equiv \neg \Phi \vee \Psi$, избавьтесь от импликаций в исходной формуле.

[bot]

Профессор Снэйп писал(а):

Ну и чем это "читабельней" по сравнению с вариантом автора?

Хотя бы тем, что не требуется сверять число открывающих скобок с числом закрывающих, не говоря уж о том, правильно ли они вложены.

Профессор Снэйп писал(а):

Меня, к примеру, отсутствие скобок после предикатов сильно раздражает

А меня нет - обычно пишу x<y, а не <(x,y) и $x\cdot yz$ вместо $x(yz)$
Возможно, убрав нагромождение скобок и запятых, luitzen просто поленился ещё буковки переставить - лучше бы писать xQy, а не Qxy, впрочем этот эксклюзив только для бинарных отношений.

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

Вот именно, что эксклюзив. Мы пишем $x + y$ вместо $+(x,y)$, но для произвольной бинарной операции $f$ запись $f(x,y)$ всё же предпочтительнее, чем $x \mathbin{f} y$. И также для произвольного $k$-арного предиката $P$ запись $P(x_1, \ldots, x_k)$ предпочтительнее всех остальных.

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

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

Если приводить утверждение к привычному в НГУ виду (тому виду, который прописан в учебнике Ершова-Палютина), то выглядеть оно будет так:

$$ \big(P(x, y) \rightarrow Q(y, z)\big) \vee \neg\forall x\big(P(x, z) \vee \neg Q(y, x)\big) \vee \exists z\big(P(z, y) \mathbin{\&} \neg Q(z, x)\big) $$

(Оффтоп)

bot, Вы же сами из НГУ! Что же Вы так непатриотично себя ведёте?!

[bot]

Всё равно не вижу причин, почему бы не писать $Pxyz $ вместо $P(x,y,z)$

Существует запись для термов любой арности вообще без скобок и запятых (кажется её польской называют), в некоторых случаях она удобна:

$xyz+\cdot$ это $x(y+z)$, а $xyz\cdot+$ это $x+(yz)$

Распутывать строение терма надо с конца.

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

(Оффтоп)

Ну мы же не в Польше!!!

[bot]

(Оффтоп)

Профессор Снэйп писал(а):

bot, Вы же сами из НГУ! Что же Вы так непатриотично себя ведёте?!

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

Ладно, больше не буду отвлекать от помощи девушке.

[Виктория123]

Цитата:

1) Дайте определение предварённой нормальной формы (заодно хоть узнаем, к чему стремимся )

Ну предваренная нормальная форма,как я понимаю,это когда все кванторы стоят слева.

Цитата:

2) Пользуясь эквивалентностью , избавьтесь от импликаций в исходной формуле.

Вот,избавилась:

$$ (\neg \ Pxy \vee Qyz) \vee \neg \forall x\, (Pxz \vee \neg Qyx) \vee \exists z\, (Pzy \wedge \neg Qzx) $$

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

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

А теперь надо пронести отрицания под кванторы,как писал
Профессор Снэйп. А поясните,как.

То есть если было

$$( \neg \forall\ x)$$

, то станет

$$(\exists (\neg x))$$

?

[Someone]

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

А теперь надо пронести отрицания под кванторы,как писал
Профессор Снэйп. А поясните,как.

То есть если было

$$( \neg \forall\ x)$$

, то станет

$$(\exists (\neg x))$$

?

Нет. $x$ - это переменная, к ней нельзя отрицание применить. Отрицание применяется к формуле, которая идёт после квантора:
$\neg\forall xP(x)$ превращается в $\exists x\neg P(x)$.

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

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

Ну предваренная нормальная форма,как я понимаю,это когда все кванторы стоят слева.

Значит, алгоритм оказывается ещё проще (пренексная нормальная форма отличается от предварённой тем, что помимо всех кванторов спереди бескванторная часть должна иметь определённый вид). Четвёртый пункт указанного мною выше алгоритма отменяется, остаются только первых три.

Первый пункт Вы сделали. Как сделать второй, Вам уже указал Someone. Следует воспользоваться эквивалентностями

$$ \neg \forall x \Phi \equiv \exists x \neg \Phi $$

$$ \neg \exists x \Phi \equiv \forall x \neg \Phi $$

(в Вашем случае потребуется только первая). Проделаёте это и покажите, что получилось.

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

Хорошо бы ещё после этого (хотя и не обязательно) немного подсократить полученное, воспользовавшись эквивалентностями

$$ \neg( \Phi \vee \Psi) \equiv \neg \Phi \mathbin{\&} \neg \Psi $$

$$ \neg(\Phi \mathbin{\&} \Psi) \equiv \neg \Phi \vee \neg \Psi $$

$$ \neg\neg\Phi \equiv \Phi $$

[Виктория123]

Цитата:

Следует воспользоваться эквивалентностями

$$ \neg \forall x \Phi \equiv \exists x \neg \Phi $$

$$ \neg \exists x \Phi \equiv \forall x \neg \Phi $$

(в Вашем случае потребуется только первая). Проделаёте это и покажите, что получилось.

Правильно?

$$ (\neg \ Pxy \vee Qyz) \vee \exists x\neg (Pxz \vee \neg Qyx) \vee \exists z\, (Pzy \wedge \neg Qzx) $$

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

Цитата:

Хорошо бы ещё после этого (хотя и не обязательно) немного подсократить полученное, воспользовавшись эквивалентностями

$$ \neg( \Phi \vee \Psi) \equiv \neg \Phi \mathbin{\&} \neg \Psi $$

$$ \neg(\Phi \mathbin{\&} \Psi) \equiv \neg \Phi \vee \neg \Psi $$

$$ \neg\neg\Phi \equiv \Phi $$

$$ (\neg \ Pxy \vee Qyz) \vee (\exists x)( \neg\ Pxz \wedge Qyx) \vee \exists z\, (Pzy \wedge \neg Qzx) $$

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

Совершенно верно. А теперь осталось сделать ещё две вещи.

1) При условии, что переменная $u$ не входит в формулу $\Phi$, справедливы эквивалентности:

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

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

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

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

К сожалению, условие на то, что $u$ не должна входить в $\Phi$, очень важно. Поэтому взять и прямо сразу вынести кванторы вперёд у Вас не получится. Так что вынесение кванторов --- это вторая вещь, которую Вы будете делать. А первая --- это замена связанных переменных.

2) Если переменная $u$ не входит в формулу $\Phi(x)$, то имеют место следующие эквивалентности:

$$ \forall x \Phi(x) \equiv \forall u \Phi(u) $$

$$ \exists x \Phi(x) \equiv \exists u \Phi(u) $$

В частности,

$$ \exists x(\neg Pxz \mathbin{\&} Qyx) \equiv \exists u(\neg Puz \mathbin{\&} Qyu) $$

Ну и вторую связанную переменную тоже заменяйте аналогичным образом. А потом выносите кванторы вперёд по предыдущему пункту.

Удачи! Когда получите ответ --- напишите, мы проверим