存在命題(論理和)と全称命題(論理積)の順序変更
存在命題(論理和)と全称命題(論理積)の順序変更
存在命題(論理和)と全称命題(論理積)の順番について以下が成り立つ。
\[ \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) \] または
\[ \bigvee_{x\in X}\bigwedge_{y\in Y}P\left(x,y\right)\Rightarrow\bigwedge_{y\in Y}\bigvee_{x\in X}P\left(x,y\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) \] または
\[ \bigvee_{x\in X}\bigwedge_{y\in Y}P\left(x,y\right)\Rightarrow\bigwedge_{y\in Y}\bigvee_{x\in X}P\left(x,y\right) \] となる。
逆は一般的に成り立たない。
\(\exists x\forall y,P\left(x,y\right)\)はある\(x\)が存在し、(その\(x\)に依らずに)任意の\(y\)に対し\(P\left(x,y\right)\)が成り立つということである。
\(\forall y\exists x,P\left(x,y\right)\)は任意の\(y\)に対し、(その\(y\)に依って変えてもいい)ある\(x_{y}\)が存在し\(P\left(x,y\right)\)が成り立つということである。
これより、\(\exists x\forall y,P\left(x,y\right)\)が成り立っていれば\(\forall y\exists x,P\left(x,y\right)\)が成り立つということである。
\(\forall y\exists x,P\left(x,y\right)\)は任意の\(y\)に対し、(その\(y\)に依って変えてもいい)ある\(x_{y}\)が存在し\(P\left(x,y\right)\)が成り立つということである。
これより、\(\exists x\forall y,P\left(x,y\right)\)が成り立っていれば\(\forall y\exists x,P\left(x,y\right)\)が成り立つということである。
(1)
\begin{align*} \bigvee_{x\in\left\{ 1,2\right\} }\bigwedge_{y\in\left\{ 1,2\right\} }P\left(x,y\right) & \Leftrightarrow\left(P\left(1,1\right)\land P\left(1,2\right)\right)\lor\left(P\left(2,1\right)\land P\left(2,2\right)\right)\\ & \Leftrightarrow\left(P\left(1,1\right)\lor P\left(2,1\right)\right)\land\left(P\left(1,2\right)\lor P\left(2,2\right)\right)\land\left(P\left(1,1\right)\lor P\left(2,2\right)\right)\land\left(P\left(1,2\right)\lor P\left(2,1\right)\right)\\ & \Rightarrow\left(P\left(1,1\right)\lor P\left(2,1\right)\right)\land\left(P\left(1,2\right)\lor P\left(2,2\right)\right)\\ & \Leftrightarrow\bigwedge_{y\in\left\{ 1,2\right\} }\bigvee_{x\in\left\{ 1,2\right\} }P\left(x,y\right) \end{align*}(2)
\begin{align*} \bigvee_{x\in\left\{ 1,2\right\} }\bigwedge_{y\in\left\{ 1,2,3\right\} }P\left(x,y\right) & \Leftrightarrow\left(P\left(1,1\right)\land P\left(1,2\right)\land P\left(1,3\right)\right)\lor\left(P\left(2,1\right)\land P\left(2,2\right)\land P\left(2,3\right)\right)\\ & \Leftrightarrow\left\{ P\left(1,1\right)\lor P\left(2,1\right)\right\} \land\left\{ P\left(1,1\right)\lor P\left(2,2\right)\right\} \land\left\{ P\left(1,1\right)\lor P\left(2,3\right)\right\} \land\left\{ P\left(1,2\right)\lor P\left(2,1\right)\right\} \land\left\{ P\left(1,2\right)\lor P\left(2,2\right)\right\} \land\left\{ P\left(1,2\right)\lor P\left(2,3\right)\right\} \land\left\{ P\left(1,3\right)\lor P\left(2,1\right)\right\} \land\left\{ P\left(1,3\right)\lor P\left(2,2\right)\right\} \land\left\{ P\left(1,3\right)\lor P\left(2,3\right)\right\} \\ & \Rightarrow\left\{ P\left(1,1\right)\lor P\left(2,1\right)\right\} \land\left\{ P\left(1,2\right)\lor P\left(2,2\right)\right\} \land\left\{ P\left(1,3\right)\lor P\left(2,3\right)\right\} \\ & \Leftrightarrow\bigwedge_{y\in\left\{ 1,2,3\right\} }\bigvee_{x\in\left\{ 1,2\right\} }P\left(x,y\right) \end{align*}(0)
\(\Rightarrow\)
\(X\ne\emptyset\land Y\ne\emptyset\)のとき
\(\bigwedge_{y\in Y}P\left(x,y\right)\rightarrow\bigvee_{x^{\prime}\in X}P\left(x^{\prime},y^{\prime}\right)\)は常に成り立つので、\[ \exists x\in X,\forall y^{\prime}\in Y,\bigwedge_{y\in Y}P\left(x,y\right)\rightarrow\bigvee_{x^{\prime}\in X}P\left(x^{\prime},y^{\prime}\right) \] も成り立つ。
これより、
\begin{align*} \top & \Leftrightarrow\exists x\in X,\forall y^{\prime}\in Y,\bigwedge_{y\in Y}P\left(x,y\right)\rightarrow\bigvee_{x^{\prime}\in X}P\left(x^{\prime},y^{\prime}\right)\\ & \Leftrightarrow\exists x\in X\bigwedge_{y\in Y}P\left(x,y\right)\rightarrow\forall y^{\prime}\in Y\bigvee_{x^{\prime}\in X}P\left(x^{\prime},y^{\prime}\right)\\ & \Leftrightarrow\bigvee_{x\in X}\bigwedge_{y\in Y}P\left(x,y\right)\rightarrow\bigwedge_{y^{\prime}\in Y}\bigvee_{x^{\prime}\in X}P\left(x^{\prime},y^{\prime}\right) \end{align*} となるので与式は成り立つ。
\(X=\emptyset\)のとき
\begin{align*} \bigvee_{x\in\emptyset}\bigwedge_{y\in Y}P\left(x,y\right)\rightarrow\bigwedge_{y\in Y}\bigvee_{x\in\emptyset}P\left(x,y\right) & \Leftrightarrow\bot\rightarrow\bigwedge_{y\in Y}\bot\\ & \Leftrightarrow\top \end{align*} となるので与式は成り立つ。\(Y=\emptyset\)のとき
\begin{align*} \bigvee_{x\in X}\bigwedge_{y\in\emptyset}P\left(x,y\right)\rightarrow\bigwedge_{y\in\emptyset}\bigvee_{x\in X}P\left(x,y\right) & \Leftrightarrow\bigvee_{x\in X}\top\rightarrow\top\\ & \Leftrightarrow\top \end{align*} となるので与式は成り立つ。-
これらより、\(X,Y\)が空集合か空集合でないかに関わらず成り立つので与式は成り立つ。\(\Leftarrow\)は一般的に成り立たない。
逆は成り立たないを反例で示す。\[ \bigvee_{x\in\left\{ 0,1\right\} }\bigwedge_{y\in\left\{ 0,-1\right\} }x+y=0\nLeftarrow\bigwedge_{y\in\left\{ 0,-1\right\} }\bigvee_{x\in\left\{ 0,1\right\} }x+y=0 \] となることを示す。
右辺は、
\begin{align*} \bigwedge_{y\in\left\{ 0,-1\right\} }\bigvee_{x\in\left\{ 0,1\right\} }x+y=0 & \Leftrightarrow\bigwedge_{y\in\left\{ 0,-1\right\} }\left(0+y=0\right)\lor\left(1+y=0\right)\\ & \Leftrightarrow\left\{ \left(0+0=0\right)\lor\left(1+0=0\right)\right\} \land\left\{ \left(0-1=0\right)\lor\left(1-1=0\right)\right\} \\ & \Leftrightarrow\left(\top\lor\bot\right)\land\left(\bot\lor\top\right)\\ & \Leftrightarrow\top\land\top\\ & \Leftrightarrow\top \end{align*} 左辺は、
\begin{align*} \bigvee_{x\in\left\{ 0,1\right\} }\bigwedge_{y\in\left\{ 0,-1\right\} }x+y=0 & \Leftrightarrow\bigvee_{x\in\left\{ 0,1\right\} }\left(x+0=0\right)\land\left(x-1=0\right)\\ & \Leftrightarrow\left\{ \left(0+0=0\right)\land\left(0-1=0\right)\right\} \lor\left\{ \left(1+0=0\right)\land\left(1-1=0\right)\right\} \\ & \Leftrightarrow\left(\top\land\bot\right)\lor\left(\bot\land\top\right)\\ & \Leftrightarrow\bot\lor\bot\\ & \Leftrightarrow\bot \end{align*} となるので、
\[ \bigvee_{x\in\left\{ 0,1\right\} }\bigwedge_{y\in\left\{ 0,-1\right\} }x+y=0\nLeftarrow\bigwedge_{y\in\left\{ 0,-1\right\} }\bigvee_{x\in\left\{ 0,1\right\} }x+y=0 \] となるので一般に逆は成り立たない。
反例2
逆は成り立たないを反例で示す。\[ \exists x\in\mathbb{R}\setminus\left\{ 0\right\} ,\forall y\in\mathbb{R}\setminus\left\{ 0\right\} ,xy>0\nLeftarrow\forall y\in\mathbb{R}\setminus\left\{ 0\right\} ,\exists x\in\mathbb{R}\setminus\left\{ 0\right\} ,xy>0 \] 右辺は任意の\(y\in\mathbb{R}\setminus\left\{ 0\right\} \)に対し、\(x\)を\(x=y\)ととれば\(xy=y^{2}>0\)なので常に成り立つ。
しかし左辺は\(x=1\)ととると、任意の\(y\in\mathbb{R}\setminus\left\{ 0\right\} \)に対し\(xy=y>0\)とはならないので成り立たない。
従って逆は一般的に成り立たない。
(0)-2
\(X,Y\)を可算無限として\(X=\left\{ x_{1},\cdots,x_{m}\right\} ,Y=\left\{ y_{1},\cdots,y_{n}\right\} \)とする。\begin{align*} \bigvee_{x\in X}\bigwedge_{y\in Y}P\left(x,y\right) & \Leftrightarrow\bigwedge_{y_{1}\in\left\{ y_{1},y_{2},\cdots,y_{n}\right\} }\cdots\bigwedge_{y_{m}\in\left\{ y_{1},y_{2},\cdots,y_{n}\right\} }P\left(x_{1},y_{1}\right)\lor\cdots\lor P\left(x_{m},y_{m}\right)\\ & \Leftrightarrow\bigwedge_{y\in\left\{ y_{1},y_{2},\cdots,y_{n}\right\} }P\left(x_{1},y\right)\lor\cdots\lor P\left(x_{m},y\right)\bigwedge_{y_{i}\ne y_{j}\left(i\ne j\right)}P\left(x_{1},y_{1}\right)\lor\cdots\lor P\left(x_{m},y_{m}\right)\\ & \Rightarrow\bigwedge_{y\in\left\{ y_{1},y_{2},\cdots,y_{n}\right\} }P\left(x_{1},y\right)\lor\cdots\lor P\left(x_{m},y\right)\\ & \Leftrightarrow\bigwedge_{y\in Y}\bigvee_{x\in X}P\left(x,y\right) \end{align*} これより、与式は成り立つ。
ページ情報
タイトル | 存在命題(論理和)と全称命題(論理積)の順序変更 |
URL | https://www.nomuramath.com/k3srzdl7/ |
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)
\]
論理演算の定義
\[
P\rightarrow Q\Leftrightarrow\lnot P\lor Q
\]
論理演算の基本
\[
P\lor\left(P\land Q\right)\Leftrightarrow P
\]
否定同値の否定同値は同値の同値
\[
P\nleftrightarrow Q\nleftrightarrow R\Leftrightarrow P\leftrightarrow Q\leftrightarrow R
\]