Нормальная форма предикатов

[Armind]

Доброго времени суток. Пропустил в универе тему и сейчас не понимаю что и как.
Имеется такая формула:
$\exists x \forall y A(x,y) \bigvee \exists x \forall y B(x,y) $

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

$\exists x \forall y (A(x,y) \bigvee B(x,y)) $

Можно ли как нибудь ещё упростить или я всё сделал правильно?

[cyb12]

К такому виду формулу привести нельзя. Помните о том, что такое связанные переменные и область действия квантора. Лучше всего всегда переименовывать переменные по областям действия кванторов. Ваша формула тогда примет вид:

$$ \exists x_1 \forall y_1 A(x_1,y_1) \bigvee \exists x_2 \forall y_2 B(x_2,y_2), $$

то есть можно написать только так:

$$ \exists x_1 \forall y_1 \exists x_2 \forall y_2( B(x_2,y_2) \vee A(x_1,y_1) ). $$

Хотя в данном случае мешает только всему квантор всеобщности. Так как

$$ \forall z P(z) \vee \forall z Q(z) \neq \forall z (P(z)\vee Q(z)), $$

например, если рассмотреть натуральные числа и сказать, что $P(z)=1$ только когда $z$ -- четное, а $Q(z)=1$ только когда $z$ --нечетное.

[Joker_vD]

Нда. cyb12, для кванторов все-таки существуют дистрибутивные законы, а такое переименование переменных — это no-no. $\exists x \forall y A(x,y) \bigvee \exists x \forall y B(x,y) $ — двуместный предикат, а вы его превращаете в четырехместный и утверждаете, что они эквивалентны!

$$\forall x (P(x)\wedge Q(x))\equiv \forall x\; P(x)\wedge \forall x\; Q(x)$$

$$\exists x (P(x) \vee Q(x)) \equiv \exists x \; P(x) \vee \exists x\; Q(x)$$

[cyb12]

Joker_vD в сообщении #565996 писал(а):

двуместный предикат

Как это двуместный предикат? Насколько я понимаю, двуместный означает зависимость от двух переменных. Но это не так. Здесь ни одной свободной переменной. И в построенном мною эквивалентном тоже ни одной свободной переменной. Или вы хотите сказать, что можно написать так:

$$ f(x,y)=\exists x \forall y A(x,y) \bigvee \exists x \forall y B(x,y) $$

Это уж точно no-no, как Вы говорите.
И да, для кванторов существуют дистрибутивные законы. Именно те, которые вы выписали. Но здесь топикстартером была попытка применить закон дистрибутивности квантора всеобщности относительно дизъюнкции, которого нет.

[Joker_vD]

За двух- и четырехместные предикаты извините. Я почему-то думал о $P(x,y)\vee Q(x,y)$ — который именно двухместный, а не четырехместный.

cyb12 в сообщении #566160 писал(а):

Joker_vD в сообщении #565996 писал(а):

двуместный предикат

Или вы хотите сказать, что можно написать так:

$$ f(x,y)=\exists x \forall y A(x,y) \bigvee \exists x \forall y B(x,y) $$

Да. Так можно. Или погодите... $\exists x(P(x)\vee Q(x))\equiv \exists x\;P(x)\vee \exists y\; Q(y)$? Я понимаю, что обозначение связанной переменной несущественно. Но тогда зачем ее вообще трогать? Давайте возьмем что-нибудь попроще. $\exists x\;P(x,y)\vee \exists x\; Q(x,y)\equiv \exists x(P(x,y)\vee Q(x,y))$ — вы согласны?

[cyb12]

Joker_vD в сообщении #566186 писал(а):

$\exists x(P(x)\vee Q(x))\equiv \exists x\;P(x)\vee \exists y\; Q(y)$?

Да. Но это именно равенство потому, что то, что слева истинно тогда и только тогда, когда истинно то, что справа.

Joker_vD в сообщении #566186 писал(а):

$\exists x\;P(x,y)\vee \exists x\; Q(x,y)\equiv \exists x(P(x,y)\vee Q(x,y))$ — вы согласны?

Да.

Joker_vD в сообщении #566186 писал(а):

Так можно.

Нельзя. Ну или ответьте, чему равно $f(3,4)$ например (если у нас целые числа в универсуме).

[Joker_vD]

Ой! Все, я понял, к чему вы вели

$$f=\exists x \forall y A(x,y) \bigvee \exists x \forall y B(x,y).$$

Это просто высказывание, но оно эквивалентно высказыванию $f'=\exists x(\forall y\,A(x,y)\vee\forall y\,B(x,y))$.

[cyb12]

да