Prawa rachunku kwantyfikatorów

Ważniejsze prawa rachunku kwantyfikatorów

• prawo dictum de omni – „orzekania o wszystkim”

$\mathrm{\forall }\varphi (x)\Rightarrow \varphi (x)$

• prawo generalizacji egzystencjalnej

$\varphi (x)\Rightarrow \mathrm{\exists }\varphi (x)$

• prawo subalternacji

$\mathrm{\forall }\varphi (x)\Rightarrow \mathrm{\exists }\varphi (x)$

• prawa zmiany zmiennych związanych

$\mathrm{\forall }\varphi (x)\iff \mathrm{\forall }\varphi (y)$

$\mathrm{\exists }\varphi (x)\iff \mathrm{\exists }\varphi (y)$

• prawa De Morgana (negowania kwantyfikatorów)

$\mathrm{\neg }\mathrm{\forall }x\varphi (x)\iff \mathrm{\exists }x\mathrm{\neg }\varphi (x)$

$\mathrm{\neg }\mathrm{\exists }x\varphi (x)\iff \mathrm{\forall }x\mathrm{\neg }\varphi (x)$

• przemienność:

kwantyfikatora ogólnego

$\mathrm{\forall }x\mathrm{\forall }y\varphi (x,y)\iff \mathrm{\forall }y\mathrm{\forall }x\varphi (x,y)$

kwantyfikatora egzystencjalnego

$\mathrm{\exists }x\mathrm{\exists }y\varphi (x,y)\iff \mathrm{\exists }y\mathrm{\exists }x\varphi (x,y)$

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

$\mathrm{\exists }x\mathrm{\forall }y\varphi (x,y)\Rightarrow \mathrm{\forall }y\mathrm{\exists }x\varphi (x,y)$

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

• rozdzielność względem koniunkcji:

$\mathrm{\forall }x(\varphi (x)\wedge \psi (x))\iff \mathrm{\forall }x\varphi (x)\wedge \mathrm{\forall }x\psi (x)$

• rozdzielność względem alternatywy:

$\mathrm{\exists }x(\varphi (x)\vee \psi (x))\iff \mathrm{\exists }x\varphi (x)\vee \mathrm{\exists }x\psi (x)$

• brak rozdzielności:

$\mathrm{\forall }x(\varphi (x)\vee \psi (x))\Leftarrow \mathrm{\forall }x\varphi (x)\vee \mathrm{\forall }x\psi (x)$

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

$\mathrm{\exists }x\varphi (x)\wedge \mathrm{\exists }x\psi (x)\Leftarrow \mathrm{\exists }x(\varphi (x)\wedge \psi (x))$

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

$\mathrm{\forall }x(\varphi (x)\Rightarrow \psi (x))\Rightarrow \mathrm{\forall }x\varphi (x)\Rightarrow \mathrm{\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