PRAWA DE MORGANA DLA KWANTYFIKATORÓW

Podobnie jak istnieją prawa De Morgana dla rachunku zdań, tak też istnieją prawa De Morgana dla kwantyfikatorów.

Twierdzenie (Prawa De Morgana dla kwantyfikatorów)

Niech \(p(x)\) oznacza formę zdaniową zmiennej \(x\), wówczas prawdziwe są równoważności: \[ \sim{\underset{x}{\LARGE \forall}}\,\,p(x)\Leftrightarrow{\underset{x}{\LARGE \exists}}\sim p(x)\] \[ \sim{\underset{x}{\LARGE \exists}}\,\,p(x)\Leftrightarrow{\underset{x}{\LARGE \forall}}\sim p(x)\]

Za pomocą prawa De Morgana wyprowadzimy wzór na zaprzeczenie formy zdaniowej z dwoma kwantyfikatorami

\( \sim{\underset{x}{\large \forall}}\,\,{\underset{y}{\large \exists}}\,\,\varphi(x,y)\) Podstawiamy za \({\underset{y}{\large \exists}}\,\,\varphi(x,y)=\psi(x)\)

\( \sim{\underset{x}{\large \forall}}\,\,{\underset{y}{\large \exists}}\,\,\varphi(x,y)\Leftrightarrow\,\, \sim{\underset{x}{\large \forall}}\,\, \psi(x)\) Po prawej stronie równoważności stosujemy prawo De Morgana \(\sim{\underset{x}{\large \forall}}\,\,\psi(x)\Leftrightarrow{\underset{x}{\large \exists}}\sim \psi(x)\)

\( \sim{\underset{x}{\large \forall}}\,\,{\underset{y}{\large \exists}}\,\,\varphi(x,y)\Leftrightarrow\,\, \sim{\underset{x}{\large \forall}}\,\, \psi(x)\) \(\Leftrightarrow {\underset{x}{\large \exists}}\sim \psi(x) \Leftrightarrow {\underset{x}{\large \exists}}\sim {\underset{y}{\large \exists}}\,\,\varphi(x,y)\) Ponownie korzystamy z prawa De Morgana \(\sim{\underset{x}{\large \exists}}\,\,p(x)\Leftrightarrow{\underset{x}{\large \forall}}\sim p(x)\)

\( \sim{\underset{x}{\large \forall}}\,\,{\underset{y}{\large \exists}}\,\,\varphi(x,y)\Leftrightarrow\,\, \sim{\underset{x}{\large \forall}}\,\, \psi(x)\) \(\Leftrightarrow {\underset{x}{\large \exists}}\sim \psi(x) \Leftrightarrow {\underset{x}{\large \exists}}\sim {\underset{y}{\large \exists}}\,\,\varphi(x,y)\) \(\Leftrightarrow {\underset{x}{\large \exists}}\,\,{\underset{x}{\large \forall}}\sim \varphi(x,y)\) Po opuszczeniu wewnętrznych przekształceń otrzymujemy

\( \sim{\underset{x}{\large \forall}}\,\,{\underset{y}{\large \exists}}\,\,\varphi(x,y) \Leftrightarrow {\underset{x}{\large \exists}}\,\,{\underset{x}{\large \forall}}\sim \varphi(x,y)\)

Zatem możemy sformułować prawa zaprzeczenia dla formy zdaniowej z dwoma kwantyfikatorami.

Wzory

Niech \(\varphi(x,y)\) oznacza formę zdaniową dwóch zmiennych \(x\) i \(y\) wówczas prawdziwe są równoważności: \[ \sim{\underset{x}{\LARGE \forall}}\,\,{\underset{y}{\LARGE \exists}}\,\,\varphi(x,y) \Leftrightarrow {\underset{x}{\LARGE \exists}}\,\,{\underset{x}{\LARGE \forall}}\sim \varphi(x,y)\] \[ \sim{\underset{x}{\LARGE \exists}}\,\,{\underset{y}{\LARGE \forall}}\,\,\varphi(x,y) \Leftrightarrow {\underset{x}{\LARGE \forall}}\,\,{\underset{x}{\LARGE \exists}}\sim \varphi(x,y)\] \[ \sim{\underset{x}{\LARGE \exists}}\,\,{\underset{y}{\LARGE \exists}}\,\,\varphi(x,y) \Leftrightarrow {\underset{x}{\LARGE \forall}}\,\,{\underset{x}{\LARGE \forall}}\sim \varphi(x,y)\] \[ \sim{\underset{x}{\LARGE \forall}}\,\,{\underset{y}{\LARGE \forall}}\,\,\varphi(x,y) \Leftrightarrow {\underset{x}{\LARGE \exists}}\,\,{\underset{x}{\LARGE \exists}}\sim \varphi(x,y)\]

Tym samym sposobem co powyżej, można wyprowadzić wzory z trzema lub większą ilością kwantyfikatorów.

Przykład

\( \sim{\underset{x}{\large \forall}}\,\,{\underset{y}{\large \exists}}\,\,{\underset{z}{\large \forall}}\,\,\varphi(x,y,z)\Leftrightarrow {\underset{x}{\large \exists}}\,\,\underset{y}{\large \forall}\,\,{\underset{z}{\large \exists}}\sim\varphi(x,y,z)\)

KWANTYFIKATORY - ZADANIA

Zadanie 1

Przy pomocą prawa De Morgana dla kwantyfikatorów znajdź zaprzeczenie zdania \({\underset{x\in \mathbb{R}}{\large \forall} }x^2=0\)

Rozwiązanie

Zadanie 2

Za pomocą prawa De Morgana dla kwantyfikatorów znajdź zaprzeczenie zdania \({\underset{x\in \mathbb{R}}{\large \exists} }x^2=0\)

Rozwiązanie