Lpu10

Тука сложи заглавие


страницата се нуждае от дописване/преглеждане


Пренексна нормална форма

Задача 1

(1)
\begin{align} \varphi \land \exists x \psi |=|\neg \neg(\varphi \land \exists x \psi) |=| \neg (\neg \varphi \land \neg \exists x \psi) |=| \neg (\neg \varphi \land \forall x \neg\psi) |=| \neg \forall x (\neg \varphi \land \neg \psi) |=| \exists x (\neg(\neg\varphi \land \neg \psi)) |=| \exists x (\varphi \lor \psi) \end{align}

аналогично за $\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)
\begin{align} (\exists x \psi)\rightarrow \varphi |=| \neg \exists x \psi \land \varphi |=| \forall x \neg \psi \land \varphi |=| \forall x (\psi \rightarrow \varphi) \end{align}

Задача 4

(3)
\begin{align} \varphi \leftrightarrow \exists x \psi |=| (\varphi \rightarrow \exists x \psi) \land (\exists x \psi \rightarrow \varphi) |=| \exists x(\varphi \rightarrow \psi) \land \forall x(\psi \rightarrow \varphi) |=| \exists x( (\varphi \rightarrow \psi) \land \forall x(\psi \rightarrow \varphi) ) |=| \exists x \forall z ((\varphi \rightarrow \psi) \land (\psi [x / z] \rightarrow \varphi[x / z])) \end{align}

тук заместихме $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$

Алгоритъм за привеждане в ПНФ

  1. Първо премахваме $\leftrightarrow,\rightarrow$
  2. Преместваме $\neg$ до атомите
  3. Извеждаме кванторите, като преименуваме при нужда

За първото използваме следните праивла

$\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))$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License