Prawa rachunku kwantyfikatorów

 Zasugerowano, aby zintegrować ten artykuł z artykułem Rachunek predykatów pierwszego rzędu (dyskusja). Nie opisano powodu propozycji integracji.

Ważniejsze prawa rachunku kwantyfikatorów

  • prawo dictum de omni – „orzekania o wszystkim”
∀ ϕ ( x ) ⇒ ϕ ( x ) {\displaystyle \forall \phi (x)\Rightarrow \phi (x)}
  • prawo generalizacji egzystencjalnej
ϕ ( x ) ⇒ ∃ ϕ ( x ) {\displaystyle \phi (x)\Rightarrow \exists \phi (x)}
  • prawo subalternacji
∀ ϕ ( x ) ⇒ ∃ ϕ ( x ) {\displaystyle \forall \phi (x)\Rightarrow \exists \phi (x)}
  • prawa zmiany zmiennych związanych
∀ ϕ ( x ) ⇔ ∀ ϕ ( y ) {\displaystyle \forall \phi (x)\Leftrightarrow \forall \phi (y)}
∃ ϕ ( x ) ⇔ ∃ ϕ ( y ) {\displaystyle \exists \phi (x)\Leftrightarrow \exists \phi (y)}
  • prawa De Morgana (negowania kwantyfikatorów)
¬ ∀ x ϕ ( x ) ⇔ ∃ x ¬ ϕ ( x ) {\displaystyle \neg \forall x\phi (x)\Leftrightarrow \exists x\neg \phi (x)}
¬ ∃ x ϕ ( x ) ⇔ ∀ x ¬ ϕ ( x ) {\displaystyle \neg \exists x\phi (x)\Leftrightarrow \forall x\neg \phi (x)}
  • przemienność:

kwantyfikatora ogólnego

∀ x ∀ y ϕ ( x , y ) ⇔ ∀ y ∀ x ϕ ( x , y ) {\displaystyle \forall x\forall y\phi (x,y)\Leftrightarrow \forall y\forall x\phi (x,y)}

kwantyfikatora egzystencjalnego

∃ x ∃ y ϕ ( x , y ) ⇔ ∃ y ∃ x ϕ ( x , y ) {\displaystyle \exists x\exists y\phi (x,y)\Leftrightarrow \exists y\exists x\phi (x,y)}
  • Przeniesienie kwantyfikatora egzystencjalnego za ogólny (nie odwrotnie!)
∃ x ∀ y ϕ ( x , y ) ⇒ ∀ y ∃ x ϕ ( x , y ) {\displaystyle \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:
∀ x ( ϕ ( x ) ∧ ψ ( x ) ) ⇔ ∀ x ϕ ( x ) ∧ ∀ x ψ ( x ) {\displaystyle \forall x(\phi (x)\land \psi (x))\Leftrightarrow \forall x\phi (x)\land \forall x\psi (x)}
  • rozdzielność względem alternatywy:
∃ x ( ϕ ( x ) ∨ ψ ( x ) ) ⇔ ∃ x ϕ ( x ) ∨ ∃ x ψ ( x ) {\displaystyle \exists x(\phi (x)\lor \psi (x))\Leftrightarrow \exists x\phi (x)\lor \exists x\psi (x)}
  • brak rozdzielności:
∀ x ( ϕ ( x ) ∨ ψ ( x ) ) ⇐ ∀ x ϕ ( x ) ∨ ∀ x ψ ( x ) {\displaystyle \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

∃ x ϕ ( x ) ∧ ∃ x ψ ( x ) ⇐ ∃ x ( ϕ ( x ) ∧ ψ ( x ) ) {\displaystyle \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

∀ x ( ϕ ( x ) ⇒ ψ ( x ) ) ⇒ ∀ x ϕ ( x ) ⇒ ∀ x ψ ( x ) {\displaystyle \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ż