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

[Sverest]

Приведенная и нормальная формы предикатов это одно и тоже или разные вещи?

-- Вс ноя 20, 2011 15:38:38 --

$\exists y \forall x P(x,y) \to \forall x \exists y Q(x,y) \equiv \overline{\exists y \forall x P(x,y)} ~\vee ~\forall x \exists y Q(x,y)\equiv \forall y\exists x \overline {P(x,y)}~\vee~ \forall x \exists y Q(x,y)$

Я правильно привел к нормальной форме?

[cyb12]

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

[Sverest]

$\exists y \forall x P(x,y) \to \forall x \exists y Q(x,y) \equiv \overline{\exists y \forall x P(x,y)} ~\vee ~\forall x \exists y Q(x,y)\equiv \forall y\exists x \overline {P(x,y)}~\vee~ \forall x \exists y Q(x,y)\equiv$

$\equiv \forall x \forall y (\exists x \overline {P(x,y)} ~\vee~ \exists y Q(x,y)) \equiv \forall x \forall y \exists x (\overline {P(x,y)} ~\vee~ \exists y Q(z,y))\equiv$

$\equiv \forall x \forall y \exists x \exists y(\overline {P(k,y)} ~\vee~ Q(z,y))$

Так правильно?