量化記号(全称命題・存在命題)の分配
量化記号(全称命題・存在命題)の分配
量化記号(全称命題・存在命題)の分配は次が成り立つ。
量化記号(全称命題・存在命題)の分配は次が成り立つ。
(1)
\[ \exists x\left(P\left(x\right)\lor Q\left(x\right)\right)\Leftrightarrow\exists xP\left(x\right)\lor\exists xQ\left(x\right) \](2)
\[ \forall x\left(P\left(x\right)\lor Q\left(x\right)\right)\Leftarrow\forall xP\left(x\right)\lor\forall xQ\left(x\right) \] 逆は一般的に成り立たない。(3)
\[ \exists x\left(P\left(x\right)\land Q\left(x\right)\right)\Rightarrow\exists xP\left(x\right)\land\exists xQ\left(x\right) \] 逆は一般的に成り立たない。(4)
\[ \forall x\left(P\left(x\right)\land Q\left(x\right)\right)\Leftrightarrow\forall xP\left(x\right)\land\forall xQ\left(x\right) \](5)
\[ \exists x\left(P\left(x\right)\rightarrow Q\left(x\right)\right)\Leftrightarrow\forall xP\left(x\right)\rightarrow\exists xQ\left(x\right) \](6)
\[ \forall x\left(P\left(x\right)\rightarrow Q\left(x\right)\right)\Leftarrow\exists xP\left(x\right)\rightarrow\forall xQ\left(x\right) \] 逆は一般的に成り立たない。(7)
\[ \exists x\left(P\left(x\right)\downarrow Q\left(x\right)\right)\Rightarrow\forall xP\left(x\right)\downarrow\forall xQ\left(x\right) \] 逆は一般的に成り立たない。(8)
\[ \forall x\left(P\left(x\right)\downarrow Q\left(x\right)\right)\Leftrightarrow\exists xP\left(x\right)\downarrow\exists xQ\left(x\right) \](9)
\[ \exists x\left(P\left(x\right)\uparrow Q\left(x\right)\right)\Leftrightarrow\forall xP\left(x\right)\uparrow\forall xQ\left(x\right) \](10)
\[ \forall x\left(P\left(x\right)\uparrow Q\left(x\right)\right)\Leftarrow\exists xP\left(x\right)\uparrow\exists xQ\left(x\right) \] 逆は一般的に成り立たない。(11)
\[ \exists x\left(P\left(x\right)\nrightarrow Q\left(x\right)\right)\Rightarrow\forall xP\left(x\right)\nrightarrow\exists xQ\left(x\right) \] 逆は一般的に成り立たない。(12)
\[ \forall x\left(P\left(x\right)\nrightarrow Q\left(x\right)\right)\Leftrightarrow\forall xP\left(x\right)\nrightarrow\exists xQ\left(x\right) \](1)
\begin{align*} \exists x\left(P\left(x\right)\lor Q\left(x\right)\right) & \Leftrightarrow\bigvee_{x}\left(P\left(x\right)\lor Q\left(x\right)\right)\\ & \Leftrightarrow\left\{ \bigvee_{x}P\left(x\right)\right\} \lor\left\{ \bigvee_{x}Q\left(x\right)\right\} \\ & \Leftrightarrow\exists xP\lor\exists xQ \end{align*}(1)-2
\begin{align*} \exists x\left(P\lor Q\right) & \Leftrightarrow\exists x\exists y\left(P\left(x\right)\lor Q\left(y\right)\right)\\ & \Leftrightarrow\exists xP\lor\exists xQ \end{align*}(2)
\(\Leftarrow\)
\begin{align*} \forall x\left(P\left(x\right)\lor Q\left(x\right)\right) & \Leftrightarrow\bigwedge_{x}\left\{ P\left(x\right)\lor Q\left(x\right)\right\} \\ & \Leftarrow\left\{ \bigwedge_{x}P\left(x\right)\right\} \lor\left\{ \bigwedge_{x}Q\left(x\right)\right\} \\ & \Leftrightarrow\forall xP\lor\forall xQ \end{align*}逆は一般的に成り立たない
逆は成り立たないことを反例で示す。\[ \forall x\in\left\{ 0,1\right\} ,\left(\left(x=0\right)\lor\left(x=1\right)\right)\nRightarrow\left(\forall x\in\left\{ 0,1\right\} ,x=0\right)\lor\left(\forall x\in\left\{ 0,1\right\} ,x=1\right) \] 左辺は真、右辺は偽となる。
\[ \forall x\in\mathbb{R},\left(\left(0\leq x^{2}<1\right)\lor\left(1\leq x^{2}\right)\right)\nRightarrow\left(\forall x\in\mathbb{R},0\leq x^{2}<1\right)\lor\left(\forall x\in\mathbb{R},1\leq x^{2}\right) \] 左辺は真、右辺は偽となる。
故に逆は一般的に成り立たない。
(2)-2
\begin{align*} \forall x\left(P\lor Q\right) & \Leftrightarrow\forall x\forall y\left(P\left(x\right)\lor Q\left(y\right)\right)\lor\left(x\ne y\right)\\ & \Leftarrow\forall x\forall y\left(P\left(x\right)\lor Q\left(y\right)\right)\\ & \Leftrightarrow\forall xP\lor\forall xQ \end{align*}(3)
(2)の対偶をとると、\[ \exists x\left(\lnot P\land\lnot Q\right)\Rightarrow\exists x\lnot P\land\exists x\lnot Q \] \(\lnot P\)を\(P\)に、\(\lnot Q\)を\(Q\)に置き換えると、
\[ \exists x\left(P\land Q\right)\Rightarrow\exists xP\land\exists xQ \] 故に与式は成り立つ。
逆が一般的に成り立たないことも同様となる。
(3)-2
\begin{align*} \exists x\left(P\land Q\right) & \Leftrightarrow\bigvee_{x}\left(P\left(x\right)\land Q\left(x\right)\right)\\ & \Rightarrow\left\{ \bigvee_{x}P\left(x\right)\right\} \land\left\{ \bigvee_{x}Q\left(x\right)\right\} \\ & \Leftrightarrow\exists xP\left(x\right)\land\exists xQ\left(x\right) \end{align*}逆は一般的に成り立たない
逆は一般的に成り立たないことを反例で示す。\[ \exists x\in\left\{ 0,1\right\} ,\left(x=0\right)\land\left(x=1\right)\nLeftarrow\left(\exists x\in\left\{ 0,1\right\} ,x=0\right)\land\left(\exists x\in\left\{ 0,1\right\} ,x=1\right) \] 左辺は偽、右辺は真となる。
\[ \exists x\in\mathbb{R},\left(0<x\right)\land\left(x<0\right)\nLeftarrow\left(\exists x\in\mathbb{R},0<x\right)\land\left(\exists x\in\mathbb{R},x<0\right) \] 左辺は偽、右辺は真となる。
故に逆は一般的に成り立たない。
(3)-3
\begin{align*} \exists x\left(P\land Q\right) & \Leftrightarrow\exists x\exists y\left(P\left(x\right)\land Q\left(y\right)\right)\land\left(x=y\right)\\ & \Rightarrow\exists x\exists y\left(P\left(x\right)\land Q\left(y\right)\right)\\ & \Leftrightarrow\exists xP\left(x\right)\land\exists xQ\left(x\right) \end{align*}(4)
(1)の対偶をとると、\[ \forall x\left(\lnot P\land\lnot Q\right)\Leftrightarrow\forall x\lnot P\land\forall x\lnot Q \] \(\lnot P\)を\(P\)に、\(\lnot Q\)を\(Q\)に置き換えると、
\[ \forall x\left(P\land Q\right)\Leftrightarrow\forall xP\land\forall xQ \] 故に与式は成り立つ。
(4)-2
\begin{align*} \forall x\left(P\land Q\right) & \Leftrightarrow\bigwedge_{x}\left\{ P\left(x\right)\land Q\left(x\right)\right\} \\ & \Leftrightarrow\left\{ \bigwedge_{x}P\left(x\right)\right\} \land\left\{ \bigwedge_{x}Q\left(x\right)\right\} \\ & \Leftrightarrow\forall xP\land\forall xQ \end{align*}(4)-3
\begin{align*} \forall x\left(P\land Q\right) & \Leftrightarrow\forall x\forall y\left(P\left(x\right)\land Q\left(y\right)\right)\lor\left(x\ne y\right)\\ & \Leftrightarrow\forall x\forall y\left(P\left(x\right)\land Q\left(y\right)\right)\\ & \Leftrightarrow\forall xP\land\forall xQ \end{align*}(5)
(1)で\(\lnot P\)を\(P\)に置き換えると、\[ \exists x\left(\lnot P\lor Q\right)\Leftrightarrow\exists x\lnot P\lor\exists xQ \] これより、
\[ \exists x\left(P\rightarrow Q\right)\Leftrightarrow\forall xP\rightarrow\exists xQ \] となる。
故に与式は成り立つ。
(5)-2
(1)より、\begin{align*} \exists x\left(P\left(x\right)\rightarrow Q\left(x\right)\right) & \Leftrightarrow\exists x\left(\lnot P\left(x\right)\lor Q\left(x\right)\right)\\ & \Leftrightarrow\exists x\left(\lnot P\left(x\right)\right)\lor\exists xQ\left(x\right)\\ & \Leftrightarrow\lnot\left(\forall xP\left(x\right)\right)\lor\exists xQ\left(x\right)\\ & \Leftrightarrow\forall xP\left(x\right)\rightarrow\exists xQ\left(x\right) \end{align*}
(6)
(2)で\(\lnot P\)を\(P\)に置き換えると、\[ \forall x\left(\lnot P\lor Q\right)\Leftarrow\forall x\lnot P\lor\forall xQ \] これより、
\[ \forall x\left(P\rightarrow Q\right)\Leftarrow\exists xP\rightarrow\forall xQ \] となる。
故に与式は成り立つ。
逆が一般的に成り立たないことも同様となる。
(6)-2
(2)より、\begin{align*} \forall x\left(P\left(x\right)\rightarrow Q\left(x\right)\right) & \Leftrightarrow\forall x\left(\lnot P\left(x\right)\lor Q\left(x\right)\right)\\ & \Leftarrow\forall x\left(\lnot P\left(x\right)\right)\lor\forall xQ\left(x\right)\\ & \Leftrightarrow\lnot\left(\exists xP\left(x\right)\right)\lor\forall xQ\left(x\right)\\ & \Leftrightarrow\exists xP\left(x\right)\rightarrow\forall xQ\left(x\right) \end{align*}
逆は一般的に成り立たない
逆は一般的に成り立たないことを反例で示す。\begin{align*} \forall x\in\left\{ 0,1\right\} \left(\left(x=0\right)\rightarrow\left(x=0\right)\right) & \nRightarrow\left(\exists x\in\left\{ 0,1\right\} \left(x=0\right)\right)\rightarrow\left(\forall x\in\left\{ 0,1\right\} \left(x=0\right)\right) \end{align*} 左辺は真、右辺は偽となる。
故に逆は一般的に成り立たない。
(7)
(2)の対偶をとると、\[ \exists x\left(\lnot P\land\lnot Q\right)\Rightarrow\exists x\lnot P\land\exists x\lnot Q \] これより、
\[ \exists x\left(P\downarrow Q\right)\Rightarrow\forall xP\downarrow\forall x\lnot Q \] 故に与式は成り立つ。
逆が一般的に成り立たないことも同様となる。
(7)-2
(3)より、\begin{align*} \exists x\left(P\left(x\right)\downarrow Q\left(x\right)\right) & \Leftrightarrow\exists x\left(\lnot P\left(x\right)\land\lnot Q\left(x\right)\right)\\ & \Rightarrow\exists x\left(\lnot P\left(x\right)\right)\land\forall x\left(\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\lnot\left(\forall xP\left(x\right)\right)\land\lnot\left(\forall xQ\left(x\right)\right)\\ & \Leftrightarrow\forall xP\left(x\right)\downarrow\forall xQ\left(x\right) \end{align*}
逆は一般的に成り立たない
逆は一般的に成り立たないことを反例で示す。\begin{align*} \exists x\in\left\{ 0,1\right\} \left(\left(x=0\right)\downarrow\left(x=1\right)\right) & \nLeftarrow\forall x\in\left\{ 0,1\right\} \left(x=0\right)\downarrow\forall x\in\left\{ 0,1\right\} \left(x=1\right) \end{align*} 左辺は偽、右辺は真となる。
故に逆は一般的に成り立たない。
(8)
(1)の対偶をとると、\[ \forall x\left(\lnot P\land\lnot Q\right)\Leftrightarrow\forall x\lnot P\land\forall x\lnot Q \] これより、
\[ \forall x\left(P\downarrow Q\right)\Leftrightarrow\exists xP\downarrow\exists xQ \] 故に与式は成り立つ。
(8)-2
(4)より、\begin{align*} \forall x\left(P\left(x\right)\downarrow Q\left(x\right)\right) & \Leftrightarrow\forall x\left(\lnot P\left(x\right)\land\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\forall x\left(\lnot P\left(x\right)\right)\land\forall x\left(\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\lnot\left(\exists xP\left(x\right)\right)\land\lnot\left(\exists xQ\left(x\right)\right)\\ & \Leftrightarrow\exists xP\left(x\right)\downarrow\exists xQ\left(x\right) \end{align*}
(9)
(1)で\(\lnot P\)を\(P\)に、\(\lnot Q\)を\(Q\)に置き換えると、\[ \exists x\left(\lnot P\lor\lnot Q\right)\Leftrightarrow\exists x\lnot P\lor\exists x\lnot Q \] これより、
\[ \exists x\left(P\uparrow Q\right)\Leftrightarrow\forall xP\uparrow\forall xQ \] 故に与式は成り立つ。
(9)-2
(1)より、\begin{align*} \exists x\left(P\left(x\right)\uparrow Q\left(x\right)\right) & \Leftrightarrow\exists x\left(\lnot P\left(x\right)\lor\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\exists x\left(\lnot P\left(x\right)\right)\lor\forall x\left(\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\lnot\left(\forall xP\left(x\right)\right)\lor\lnot\left(\forall xQ\left(x\right)\right)\\ & \Leftrightarrow\forall xP\left(x\right)\uparrow\forall xQ\left(x\right) \end{align*}
(10)
(2)で\(\lnot P\)を\(P\)に、\(\lnot Q\)を\(Q\)に置き換えると、\[ \forall x\left(\lnot P\lor\lnot Q\right)\Leftarrow\forall x\lnot P\lor\forall x\lnot Q \] これより、
\[ \forall x\left(P\uparrow Q\right)\Leftarrow\exists xP\uparrow\exists xQ \] 故に与式は成り立つ。
逆が一般的に成り立たないことも同様となる。
(10)-2
(2)より、\begin{align*} \forall x\left(P\left(x\right)\uparrow Q\left(x\right)\right) & \Leftrightarrow\forall x\left(\lnot P\left(x\right)\lor\lnot Q\left(x\right)\right)\\ & \Leftarrow\forall x\left(\lnot P\left(x\right)\right)\lor\forall x\left(\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\lnot\left(\exists xP\left(x\right)\right)\lor\lnot\left(\exists xQ\left(x\right)\right)\\ & \Leftrightarrow\exists xP\left(x\right)\uparrow\exists xQ\left(x\right) \end{align*}
逆は一般的に成り立たない
逆は成り立たないことを反例で示す。\[ \forall x\in\left\{ 0,1\right\} \left(\left(x=0\right)\uparrow\left(x=1\right)\right)\nRightarrow\exists x\in\left\{ 0,1\right\} \left(x=0\right)\uparrow\exists x\in\left\{ 0,1\right\} \left(x=1\right) \] 左辺は真、右辺は偽となる。
故に逆は一般的に成り立たない。
(11)
(2)の対偶をとると、\[ \exists x\left(\lnot P\land\lnot Q\right)\Rightarrow\exists x\lnot P\land\exists x\lnot Q \] \(\lnot P\)を\(P\)に置き換えると、
\[ \exists x\left(P\nrightarrow Q\right)\Rightarrow\exists xP\rightarrow\forall xQ \] 故に与式は成り立つ。
逆が一般に成り立たないことも同様となる。
(11)-2
(3)より、\begin{align*} \exists x\left(P\left(x\right)\nrightarrow Q\left(x\right)\right) & \Leftrightarrow\exists x\left(P\left(x\right)\land\lnot Q\left(x\right)\right)\\ & \Rightarrow\exists xP\left(x\right)\land\exists x\left(\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\exists xP\left(x\right)\land\lnot\forall xQ\left(x\right)\\ & \Leftrightarrow\exists xP\left(x\right)\nrightarrow\forall xQ\left(x\right) \end{align*}
逆は一般的に成り立たない
反例を示す。\[ \exists x\in\left\{ 0,1\right\} \left(\left(x=0\right)\nrightarrow\left(x=0\right)\right)\nLeftarrow\exists x\in\left\{ 0,1\right\} \left(x=0\right)\nrightarrow\forall x\in\left\{ 0,1\right\} \left(x=0\right) \] 左辺は偽、右辺は真となる。
故に逆は一般的に成り立たない。
(12)
(1)の対偶をとると、\[ \forall x\left(\lnot P\land\lnot Q\right)\Leftrightarrow\forall x\lnot P\land\forall x\lnot Q \] \(\lnot P\)を\(P\)に置き換えると、
\[ \forall x\left(P\nrightarrow Q\right)\Leftrightarrow\forall xP\nrightarrow\exists xQ \] 故に与式は成り立つ。
(12)-2
(4)より、\begin{align*} \forall x\left(P\left(x\right)\nrightarrow Q\left(x\right)\right) & \Leftrightarrow\forall x\left(P\left(x\right)\land\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\forall xP\left(x\right)\land\forall x\left(\lnot Q\left(x\right)\right)\\ & \Leftrightarrow\forall xP\left(x\right)\land\lnot\exists xQ\left(x\right)\\ & \Leftrightarrow\forall xP\left(x\right)\nrightarrow\exists xQ\left(x\right) \end{align*}
ページ情報
タイトル | 量化記号(全称命題・存在命題)の分配 |
URL | https://www.nomuramath.com/q1g92rp6/ |
SNSボタン |
LK推論規則での包含関係
\[
\left(P\rightarrow Q\right)\land\left(R\rightarrow S\right)\Rightarrow\left(P\lor R\right)\rightarrow\left(Q\land S\right)
\]
逆・裏・対偶の定義と対偶の法則
\[
\left(P\rightarrow Q\right)\Leftrightarrow\left(\lnot P\leftarrow\lnot Q\right)
\]
3引数論理演算の括弧外しと優先順位変更全パターン
\[
P\lor\left(Q\land R\right)\Leftrightarrow\left(P\lor Q\right)\land\left(P\lor R\right)
\]
存在命題(論理和)と全称命題(論理積)の順序変更
\[
\exists x\in X,\forall y\in Y,P\left(x,y\right)\Rightarrow\forall y\in Y,\exists x\in X,P\left(x,y\right)
\]