Тука сложи заглавие
страницата се нуждае от дописване/преглеждане
Пренексна нормална форма
Задача 1
(1)аналогично за $\varphi \lor \exists x \psi$
Задача 2
$\varphi \rightarrow \exists x \psi |=| \exists x (\varphi \rightarrow \psi)$
По втори начин
$\varphi \rightarrow \exists x \psi |=| \neg \varphi \lor \exists x \psi |=| \exists x (\neg \varphi \lor \psi) |=| \exists x (\varphi \rightarrow \psi)$
Задача 3
(2)Задача 4
(3)тук заместихме $x$ със $z$ и изнесохме квантора.
В случая няма значение наредбата на кванторите в ПНФ, но в други случай има значение ето такъв пример
$\exists x \forall y p(x,y)$ и $\forall y \exists x p(x,y)$
"Дистрибутивни" закони
$\forall x (\varphi \land \psi) |=| \forall x \varphi \land \forall x \psi$ - не е вярно за $\lor$
$\exists x (\varphi \lor \psi) |=| \exists x \varphi \lor \exists x \psi$ - не е вярно за $\land$
Алгоритъм за привеждане в ПНФ
- Първо премахваме $\leftrightarrow,\rightarrow$
- Преместваме $\neg$ до атомите
- Извеждаме кванторите, като преименуваме при нужда
За първото използваме следните праивла
$\neg(\varphi \overset{\land}{\lor} \psi) |=| \neg\varphi \overset{\lor}{\land} \neg \psi$ - законите на деморган
$\neg\neg \psi |=| \psi$
$\varphi \rightarrow \psi |=| \neg \varphi \lor \psi$
$\varphi \leftrightarrow \psi |=| (\varphi)\land(\psi) |=| (\neg \varphi \lor \psi)\land(\neg \psi \lor \varphi)$
$\neg\exists \varphi |=| \forall x \neg \varphi$
Задача 5
$\forall x \forall y (p(x,y)\leftrightarrow\exists z ( p(z,x) \land p (z,y)))$
$\forall x \forall y (( \neg p(x,y) \lor \exists z (p(z,x) \land p(z,y))) \land (p(x,y) \lor \neg \exists x (p(z,x) \land p(z,y))))$
$\forall x \forall y (\exists z (\neg p(x,y) \lor (p(z,x)\land p(z,y)) \land (\forall z (p(x,y) \lor (\neg p(z,x)\lor\neg p(z,y)))$
$\forall x \forall y \exists z ( \neg p(x,y) \lor (p(z,x) \land p(z,y)) \land \forall z (p(x,y) \lor (\neg p(z,x) \lor \neg p (z,y))$
$\forall x \forall y \exists z \forall z_1(\neg p(x,y)\lor (p(z,x)\land p(z,y)) \land ( p(x,y) \lor (\neg p(z_1,x) \lor \neg p(z_1,y))$
Задача 6
$\forall x p(x) \rightarrow \exists y (q(y,x)\land \neg q(x,y))$
$\neg \forall x p(x) \lor \exists y (q(y,x) \land \neg q (x,y)$
$\exists x \neg p (x) \lor \exists y (q(y,x) \land \neg q (x,y))$
$\exists y (\exists x \neg p(x) \lor (q(y,x) \land \neg q (x,y)))$
$\exists y \exists x_1 ( \neg p(x_1) \lor (q(y,x) \land \neg q(x,y)))$
Задача 7
$(\forall x \exists x p(z,x)) \rightarrow (\exists x q(x)\rightarrow \forall x \forall y p(x,y))$
$\neg \forall x \exists z p (z,x) \lor ( \neg \exists x q(x) \lor \forall x \forall y p(x,y))$
$\exists x \forall z \neg p (z,x) \lor \forall x \neg q(x) \lor \forall x \forall y p(x,y))$
$\exists x \forall z (\neg p(z,x) \lor \forall x \neg q(x) \lor \forall x \forall y p(x,y))$
$\exists x \forall z \forall x_1 (\neg p(z,x) \lor \neg q(x_1) \lor \forall x \forall y p(x,y))$
$\exists x \forall z \forall x_1 \forall x_2 \forall y_1(\neg p(z,x) \lor \neg q(x_1) \lor p(x_2,y_1))$