論理式の双対
命題論理では、論理積\(\wedge \)と論理和\(\vee \)を入れ替え、命題定数\(T\)と\(F \)を入れ替えることにより、論理式の双対を定義しました。述語論理では全称記号\(\forall \)と存在記号\(\exists \)が使われるため、述語論理において双対を考える際には全称記号と存在記号も互いに入れ替えます。以下では述語論理における論理式の双対を定義します。
論理演算子として\(\lnot ,\wedge ,\vee ,\rightarrow ,\leftrightarrow ,\veebar \)を定義しましたが、先に示したように\(\rightarrow ,\leftrightarrow ,\veebar \)はいずれも\(\lnot ,\wedge ,\vee \)に置き換え可能であるため、結局、論理演算子として\(\lnot ,\wedge ,\vee \)が与えられれば任意の論理式を表現することができます。具体的には、論理式\(A,B\)がそれぞれ任意に与えられたとき、以下の恒真式\begin{eqnarray*} &&\left( a\right) \ A\rightarrow B\Leftrightarrow \lnot A\vee B \\
&&\left( b\right) \ A\leftrightarrow B\Leftrightarrow \left( A\rightarrow
B\right) \wedge \left( B\rightarrow A\right) \\
&&\left( c\right) \ A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right)
\vee \left( \lnot A\wedge B\right)
\end{eqnarray*}が成り立つため、これらを利用することにより、論理式中の\(\rightarrow ,\leftrightarrow ,\veebar \)を\(\lnot ,\wedge ,\vee \)に置き換えることができます。したがって、論理式\(A\)を任意に選んだとき、そこに含まれる可能性のある論理演算子を\(\lnot ,\wedge ,\vee \)に限定しても一般性は失われません。したがって、以下では、必要に応じて\(\rightarrow ,\leftrightarrow ,\veebar \)をあらかじめ\(\lnot ,\wedge ,\vee \)を用いた形へ同値変形した上で双対を考えます。
論理式\(A\)の双対(dual)を、\begin{equation*} A^{D}
\end{equation*}で表記します。双対は、論理式の構成に応じて以下のように定義されます。
命題定数\(T,F\)を除く原子論理式\(P\)の双対を、\begin{equation*} P^{D}=P
\end{equation*}と定義し、命題定数\(T,F\)の双対を、\begin{eqnarray*} T^{D} &=&F \\
F^{D} &=&T
\end{eqnarray*}と定義します。
論理式\(A\)について、その否定の双対を、\begin{equation*} \left( \lnot A\right) ^{D}=\lnot A^{D}
\end{equation*}と定義します。つまり、否定の双対は双対の否定と一致します。
論理式\(A,B\)について、それらの論理積の双対を、\begin{equation*} \left( A\wedge B\right) ^{D}=A^{D}\vee B^{D}
\end{equation*}と定義します。つまり、論理積の双対は双対の論理和と一致します。
論理式\(A,B\)について、それらの論理和の双対を、\begin{equation*} \left( A\vee B\right) ^{D}=A^{D}\wedge B^{D}
\end{equation*}と定義します。つまり、論理和の双対は双対の論理積と一致します。
論理式\(A\)と変数\(x\in X\)について、全称命題と存在命題の双対をそれぞれ、\begin{eqnarray*} \left( \forall x\in X:A\right) ^{D} &=&\exists x\in X:A^{D} \\
\left( \exists x\in X:A\right) ^{D} &=&\forall x\in X:A^{D}
\end{eqnarray*}と定義します。つまり、全称命題や存在命題の双対をとる際には\(\forall \)と\(\exists \)を入れ替えた上で、作用域中の論理式\(A\)の双対\(A^{D}\)をとります。ただし、量化される変数とその定義域、量化記号の作用域は変更しません。
以上を踏まえた上で、論理式の双対を以下のように再帰的に定義します。
- 命題定数\(T,F\)について、\begin{eqnarray*} T^{D} &=&F \\
F^{D} &=&T
\end{eqnarray*}である。 - 命題定数\(T,F\)を除く原子論理式\(P\)について、\begin{equation*} P^{D}=P
\end{equation*}である。 - 論理式\(A\)について、\begin{equation*} \left( \lnot A\right) ^{D}=\lnot A^{D}
\end{equation*}である。 - 論理式\(A,B\)について、\begin{equation*} \left( A\wedge B\right) ^{D}=A^{D}\vee B^{D}
\end{equation*}である。 - 論理式\(A,B\)について、\begin{equation*} \left( A\vee B\right) ^{D}=A^{D}\wedge B^{D}
\end{equation*}である。 - 論理式\(A\)と変数\(x\in X\)について、\begin{equation*} \left( \forall x\in X:A\right) ^{D}=\exists x\in X:A^{D}
\end{equation*}である。 - 論理式\(A\)と変数\(x\in X\)について、\begin{equation*} \left( \exists x\in X:A\right) ^{D}=\forall x\in X:A^{D}
\end{equation*}である。
\(\rightarrow ,\leftrightarrow ,\veebar \)を含む論理式については、あらかじめ\(\lnot ,\wedge ,\vee \)だけを用いた論理式へ同値変形した上で双対を考えます。また、全称命題や存在命題の双対をとる際には、量化される変数とその定義域、量化記号の作用域は変更しません。
以上のルールが与えられれば、任意の論理式の双対を特定できます。なぜなら、議論の最小単位である原子論理式と命題定数\(T,F\)の双対が定められており、さらに、\(\lnot ,\wedge ,\vee ,\forall ,\exists \)を含む論理式の双対が定められているため、どれほど複雑な論理式でも、構造を内側から順にたどれば双対を決定できるからです。
\end{equation*}の双対は、\begin{equation*}
\exists x\in X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\end{equation*}です。
\forall x\in X:\left( \lnot P\left( x\right) \vee \left( \exists y\in
Y:Q\left( x,y\right) \right) \right)
\end{equation*}の双対は、
\begin{equation*}
\exists x\in X:\left( \lnot P\left( x\right) \wedge \left( \forall y\in
Y:Q\left( x,y\right) \right) \right)
\end{equation*}です。このとき、量化記号\(\forall ,\exists \)は入れ替わっていますが、変数\(x,y\)およびそれらの定義域\(X,Y\)は変化していません。
\left( \exists x\in X:P\left( x\right) \right) \wedge \left( \forall x\in
X:Q\left( x\right) \right)
\end{equation*}の双対は、
\begin{equation*}
\left( \forall x\in X:P\left( x\right) \right) \vee \left( \exists x\in
X:Q\left( x\right) \right)
\end{equation*}です。
\left( \forall x\in X:P\left( x\right) \right) \vee F
\end{equation*}の双対は、
\begin{equation*}
\left( \exists x\in X:P\left( x\right) \right) \wedge T
\end{equation*}です。
\forall x\in X:P\left( x\right) \quad \cdots (1)
\end{equation}の双対は、\begin{equation}
\exists x\in X:P\left( x\right) \quad \cdots (2)
\end{equation}である一方で、\(\left( 1\right) \)の否定は、\begin{equation} \exists x\in X:\lnot P\left( x\right) \quad \cdots (3)
\end{equation}ですが、\(\left( 2\right) \)と\(\left( 3\right) \)は論理的に同値ではありません。
双対と変数の束縛
述語論理において双対を求める際には\(\forall \)と\(\exists \)を互いに入れ替えますが、量化される変数と量化記号の作用域は変更しません。したがって、双対をとる前後で、各変数の表れが自由であるか束縛されているかという関係は変化しません。
任意の論理式\(A\)について、\(A\)と\(A^{D}\)に含まれる自由変数は一致する。また、\(A\)中の束縛変数の各表れは、\(A^{D}\)においても同じ変数によって束縛される。
以上の命題から明らかであるように、双対をとる操作そのものによって変数の捕獲が生じることはありません。変数の捕獲は、自由変数を含む別の論理式を量化記号の作用域の内部へ代入する場合などに問題になりますが、双対を求める操作では新たな変数の表れを導入しないからです。
双対の双対
双対を1回とると、\(\wedge \)と\(\vee \)、\(\forall \)と\(\exists \)、\(T\)と\(F\)がそれぞれ入れ替わります。同じ操作をもう1回行えば、これらはすべてもとの記号へ戻ります。
\left( A^{D}\right) ^{D}=A
\end{equation*}が成り立つ。
第1双対原理
原子論理式\(P_{1},\cdots ,P_{n}\)と命題定数\(T,F\)を被演算子とする論理式を、\begin{equation*} A\left( P_{1},\cdots ,P_{n},T,F\right)
\end{equation*}で表記します。ここでは、原子論理式\(P_{1},\cdots ,P_{n}\)の内部構造はいったん捨象し、それぞれを1つの論理的な単位として扱います。同じ原子論理式\(P_{i}\)が複数の箇所に現れる場合には、それらをすべて同一の論理式として扱います。
論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)中の\(P_{1},\cdots ,P_{n}\)を否定\(\lnot P_{1},\cdots ,\lnot P_{n}\)に置き換えることにより得られる論理式を、\begin{equation*} A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\end{equation*}で表記します。この置換では、それぞれの原子論理式の直前に否定を付加するだけであり、新たな変数の表れは導入されません。したがって、変数の捕獲は生じません。さらに、先の論理式の否定を、\begin{equation}
\lnot A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right) \quad \cdots (1)
\end{equation}で表記します。
その一方で、もとの論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)の双対を、\begin{equation} A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \quad \cdots (2)
\end{equation}で表記します。
実は、\(\left( 1\right) \)と\(\left( 2\right) \)は論理的に同値になります。つまり、\begin{equation*} A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Leftrightarrow \lnot A\left(
\lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\end{equation*}が成り立ちます。これを第1双対原理(first principle of duality)や第1双対定理(first duality theorem)などと呼びます。
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Leftrightarrow \lnot A\left(
\lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\end{equation*}が成り立つ。
\forall x\in X:\left( P\left( x\right) \vee \left( \exists y\in Y:Q\left(
x,y\right) \right) \right) \quad \cdots (1)
\end{equation}について考えます。\(\left( 1\right) \)の双対は、 \begin{equation}
\exists x\in X:\left( P\left( x\right) \wedge \left( \forall y\in Y:Q\left(
x,y\right) \right) \right) \quad \cdots (2)
\end{equation}です。その一方で、\(\left( 1\right) \)中の原子論理式\(P\left( x\right) ,Q\left( x,y\right) \)をそれぞれ否定した上で論理式全体を否定すると、 \begin{eqnarray*}
&&\lnot \left[ \forall x\in X:\left( \lnot P\left( x\right) \vee \left(
\exists y\in Y:\lnot Q\left( x,y\right) \right) \right) \right] \\
&\Leftrightarrow &\exists x\in X:\lnot \left[ \lnot P\left( x\right) \vee
\left( \exists y\in Y:\lnot Q\left( x,y\right) \right) \right] \\
&\Leftrightarrow &\exists x\in X:\left[ P\left( x\right) \wedge \lnot \left(
\exists y\in Y:\lnot Q\left( x,y\right) \right) \right] \\
&\Leftrightarrow &\exists x\in X:\left[ P\left( x\right) \wedge \left(
\forall y\in Y:Q\left( x,y\right) \right) \right] \end{eqnarray*}となりますが、これは\(\left( 2\right) \)と一致します。以上の結果は第1双対原理と整合的です。
恒真式と恒偽式の双対
第1双対原理から、恒真式と恒偽式の間にも双対関係が存在することが分かります。
\forall x\in X:\left( P\left( x\right) \vee \lnot P\left( x\right) \right)
\end{equation*}は恒真式です。その双対は、
\begin{equation*}
\exists x\in X:\left( P\left( x\right) \wedge \lnot P\left( x\right) \right)
\end{equation*}であり、これは恒偽式です。
第2双対原理
原子論理式\(P_{1},\cdots ,P_{n}\)と命題定数\(T,F\)に関する論理式である\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)と\(B\left( P_{1},\cdots ,P_{n},T,F\right) \)の間に以下の関係\begin{equation*} A\left( P_{1},\cdots ,P_{n},T,F\right) \Rightarrow B\left( P_{1},\cdots
,P_{n},T,F\right)
\end{equation*}が成り立つものとします。このとき、これらの論理式の双対の間に以下の関係\begin{equation*}
B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Rightarrow A^{D}\left(
P_{1},\cdots ,P_{n},T,F\right)
\end{equation*}が成り立つことが保証されます。つまり、双対をとると必要条件と十分条件としての立場が入れ替わるということです。これを第2双対原理(second principle of duality)や第2双対定理(second duality theorem)などと呼びます。証明では先に示した第1双対原理と一様代入法則を利用します。
,P_{n},T,F\right)
\end{equation*}が成り立つ場合には、それらの双対の間に、\begin{equation*}
B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Rightarrow A^{D}\left(
P_{1},\cdots ,P_{n},T,F\right)
\end{equation*}が成り立つ。
\forall x\in X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Rightarrow \forall x\in X:P\left( x\right) \quad \cdots (1)
\end{equation}が成り立ちます。\(\left( 1\right) \)の左辺の双対は、 \begin{equation*}
\exists x\in X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\end{equation*}であり、右辺の双対は、
\begin{equation*}
\exists x\in X:P\left( x\right)
\end{equation*}です。したがって、第2双対原理より、
\begin{equation*}
\exists x\in X:P\left( x\right) \Rightarrow \exists x\in X:\left( P\left(
x\right) \vee Q\left( x\right) \right)
\end{equation*}が成り立ちます。
第3双対原理
原子論理式\(P_{1},\cdots ,P_{n}\)と命題定数\(T,F\)に関する論理式である\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)と\(B\left( P_{1},\cdots ,P_{n},T,F\right) \)の間に以下の関係\begin{equation*} A\left( P_{1},\cdots ,P_{n},T,F\right) \Leftrightarrow B\left( P_{1},\cdots
,P_{n},T,F\right)
\end{equation*}が成り立つものとします。これは、\begin{eqnarray*}
A\left( P_{1},\cdots ,P_{n},T,F\right) &\Rightarrow &B\left( P_{1},\cdots
,P_{n},T,F\right) \\
B\left( P_{1},\cdots ,P_{n},T,F\right) &\Rightarrow &A\left( P_{1},\cdots
,P_{n},T,F\right)
\end{eqnarray*}がともに成り立つことを意味するため、第2双対原理より、\begin{eqnarray*}
B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &\Rightarrow &A^{D}\left(
P_{1},\cdots ,P_{n},T,F\right) \\
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &\Rightarrow &B^{D}\left(
P_{1},\cdots ,P_{n},T,F\right)
\end{eqnarray*}を得ますが、さらにこれは、\begin{equation*}
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Leftrightarrow B^{D}\left(
P_{1},\cdots ,P_{n},T,F\right)
\end{equation*}を意味します。つまり、論理式\(A,B\)が論理的に同値であるとき、それらの双対\(A^{D},B^{D}\)どうしも論理的に同値になることが保証されます。これを第3双対原理(third principle of duality)や第3双対定理(third duality theorem)などと呼びます。多くの場合、第3双対原理のことをシンプルに双対原理(principle of duality)と呼びます。
,P_{n},T,F\right)
\end{equation*}が成り立つ場合には、それらの双対の間に、\begin{equation*}
B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Leftrightarrow A^{D}\left(
P_{1},\cdots ,P_{n},T,F\right)
\end{equation*}が成り立つ。
\forall x\in X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \left( \forall x\in X:P\left( x\right) \right) \wedge \left(
\forall x\in X:Q\left( x\right) \right) \quad \cdots (1)
\end{equation}が成り立ちます。\(\left( 1\right) \)の左辺の双対は、 \begin{equation*}
\exists x\in X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\end{equation*}であり、右辺の双対は、
\begin{equation*}
\left( \exists x\in X:P\left( x\right) \right) \vee \left( \exists x\in
X:Q\left( x\right) \right)
\end{equation*}です。したがって、双対原理より、
\begin{equation*}
\exists x\in X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\Leftrightarrow \left( \exists x\in X:P\left( x\right) \right) \vee \left(
\exists x\in X:Q\left( x\right) \right)
\end{equation*}が成り立ちます。
\begin{equation}
\lnot \left( \forall x\in X:P\left( x\right) \right) \Leftrightarrow \exists
x\in X:\lnot P\left( x\right) \quad \cdots (1)
\end{equation}が成り立ちます。\(\left( 1\right) \)の双対をとると、 \begin{equation*}
\lnot \left( \exists x\in X:P\left( x\right) \right) \Leftrightarrow \forall
x\in X:\lnot P\left( x\right)
\end{equation*}を得ます。したがって、全称量化に関する否定の法則と存在量化に関する否定の法則は、互いに双対な関係にあります。
述語論理における双対原理の意味
命題論理における双対原理では、論理積と論理和の間に存在する対称性が明らかになります。述語論理では、この対称性がさらに全称量化と存在量化の間にも拡張されます。すなわち、
\begin{eqnarray*}
\wedge &\longleftrightarrow &\vee \\
\forall &\longleftrightarrow &\exists \\
T &\longleftrightarrow &F
\end{eqnarray*}という対応を同時に考えることにより、ある論理法則から、その双対にあたる別の論理法則を体系的に導くことができます。
ただし、\(\forall \)と\(\exists \)だけを入れ替えれば任意の恒真式から新たな恒真式が得られるわけではありません。双対は論理式全体に対して定義される操作であり、\(\wedge \)と\(\vee \)、\(T\)と\(F\)も含めて、双対の定義に従ってすべての対象を一貫して入れ替える必要があります。
また、双対原理は、ある式が恒真式ならその双対も恒真式になるという主張ではありません。先に示した通り、恒真式の双対は恒偽式になります。双対原理が保証するのは、2つの論理式の間に成立する論理的同値関係を双対化すれば、双対どうしの間にも論理的同値関係が成立するということです。
演習問題
\forall x\in X:\left[ P\left( x\right) \vee \left( \exists y\in Y: \left(
Q\left( x,y\right) \wedge \lnot R\left( y\right) \right) \right) \right] \end{equation*}の双対を求めてください。
\forall x\in X:\left( P\left( x\right) \rightarrow Q\left( x\right) \right)
\end{equation*}を\(\lnot ,\wedge ,\vee \)だけを用いた形に同値変形した上で、その双対を求めてください。
\begin{equation*}
\forall x\in X:\left( P\left( x,y\right) \vee \exists z\in Z:Q\left(
y,z\right) \right)
\end{equation*}の双対を求めてください。また、もとの論理式とその双対について、それぞれ自由変数と束縛変数を明らかにしてください。
\begin{equation*}
A= \exists x\in X:\left( P\left( x\right) \wedge \lnot Q\left( x\right)
\right)
\end{equation*}について、第1双対原理
\begin{equation*}
A^{D}\Leftrightarrow \lnot A\left( \lnot P,\lnot Q\right)
\end{equation*}が成り立つことを確認してください。
\exists x\in X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Rightarrow \exists x\in X:P\left( x\right)
\end{equation*}が成り立ちます。第2双対原理を利用して、新たな論理的帰結を導いてください。
\forall x\in X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \left( \forall x\in X:P\left( x\right) \right) \wedge \left(
\forall x\in X:Q\left( x\right) \right)
\end{equation*}が成り立つものとします。第3双対原理を利用して、この恒真式から新たな恒真式を導いてください。
\forall x\in X:\left( P\left( x\right) \vee \lnot P\left( x\right) \right)
\end{equation*}が恒真式であるものとします。この論理式の双対を求め、それが恒偽式であることを確認してください。
