Prawa rachunku kwantyfikatorów

Ważniejsze prawa rachunku kwantyfikatorów

• prawo dictum de omni – „orzekania o wszystkim”

$\forall \phi (x)\Rightarrow \phi (x)$

• prawo generalizacji egzystencjalnej

$\phi (x)\Rightarrow \exists \phi (x)$

• prawo subalternacji

$\forall \phi (x)\Rightarrow \exists \phi (x)$

• prawa zmiany zmiennych związanych

$\forall \phi (x)\Leftrightarrow \forall \phi (y)$

$\exists \phi (x)\Leftrightarrow \exists \phi (y)$

• prawa De Morgana (negowania kwantyfikatorów)

$\neg \forall x\phi (x)\Leftrightarrow \exists x\neg \phi (x)$

$\neg \exists x\phi (x)\Leftrightarrow \forall x\neg \phi (x)$

• przemienność:

kwantyfikatora ogólnego

$\forall x\forall y\phi (x,y)\Leftrightarrow \forall y\forall x\phi (x,y)$

kwantyfikatora egzystencjalnego

$\exists x\exists y\phi (x,y)\Leftrightarrow \exists y\exists x\phi (x,y)$

• Przeniesienie kwantyfikatora egzystencjalnego za ogólny (nie odwrotnie!)

$\exists x\forall y\phi (x,y)\Rightarrow \forall y\exists x\phi (x,y)$

→ Kontrprzykład: gdy ф(x,y) jest postaci: x<y (x,y należy do rzeczywistych)

• rozdzielność względem koniunkcji:

$\forall x(\phi (x)\land \psi (x))\Leftrightarrow \forall x\phi (x)\land \forall x\psi (x)$

• rozdzielność względem alternatywy:

$\exists x(\phi (x)\lor \psi (x))\Leftrightarrow \exists x\phi (x)\lor \exists x\psi (x)$

• brak rozdzielności:

$\forall x(\phi (x)\lor \psi (x))\Leftarrow \forall x\phi (x)\lor \forall x\psi (x)$

→ Kontrprzykład: gdy ф(x) prawdziwe dla x>2, Ψ(x) prawdziwe dla x≤2

$\exists x\phi (x)\land \exists x\psi (x)\Leftarrow \exists x(\phi (x)\land \psi (x))$

→ Kontrprzykład: gdy ф(x) prawdziwe dla x=1, Ψ(x) prawdziwe dla x=2

$\forall x(\phi (x)\Rightarrow \psi (x))\Rightarrow \forall x\phi (x)\Rightarrow \forall x\psi (x)$

→ Kontrprzykład: gdy ф(x) prawdziwe dla x>2, Ψ(x) prawdziwe dla x≤2

Zobacz też

• kwantyfikator
• kwantyfikator ogólny
• kwantyfikator egzystencjalny