論理的に同値な 2 つの論理式が与えられたとき、それらの双対をとるとそれらもまた論理的に同値となります。これを双対原理と呼びます。
< 前のページ

論理式の定義:再論

論理演算子として\(\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 \)に置き換えることができます。

例(論理演算子の置き換え)
命題変数\(P,Q,R\)に関する論理式\(\lnot P\rightarrow \lnot \left( Q\rightarrow \lnot R\right) \)を同値変形すると、\begin{eqnarray*}
\lnot P\rightarrow \lnot \left( Q\rightarrow \lnot R\right)
&\Leftrightarrow &\lnot \lnot P\vee \lnot \left( \lnot Q\vee \lnot R\right)
\quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\lnot \lnot P\vee \left( \lnot \lnot Q\wedge \lnot \lnot
R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &P\vee \left( Q\wedge R\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(P\vee \left( Q\wedge R\right) \)には\(\rightarrow \)が含まれません。
例(論理演算子の置き換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \leftrightarrow \lnot R\)を同値変形すると、\begin{eqnarray*}
\left( P\wedge \lnot Q\right) \leftrightarrow \lnot R &\Leftrightarrow
&\left( \left( P\wedge \lnot Q\right) \rightarrow \lnot R\right) \wedge
\left( \lnot R\rightarrow \left( P\wedge \lnot Q\right) \right) \quad
\because \leftrightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot \left( P\wedge \lnot Q\right) \vee \lnot
R\right) \wedge \left( \lnot \lnot R\vee \left( P\wedge \lnot Q\right)
\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \left( \lnot P\vee \lnot \lnot Q\right) \vee \lnot
R\right) \wedge \left( \lnot \lnot R\vee \left( P\wedge \lnot Q\right)
\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot P\vee Q\vee \lnot R\right) \wedge \left(
R\vee \left( P\wedge \lnot Q\right) \right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( \lnot P\vee Q\vee \lnot R\right) \wedge \left( R\vee \left( P\wedge \lnot Q\right) \right) \)には\(\leftrightarrow \)や\(\rightarrow \)が含まれません。
例(論理演算子の置き換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \veebar \lnot R\)を同値変形すると、\begin{eqnarray*}
\left( P\wedge \lnot Q\right) \veebar \lnot R &\Leftrightarrow &\left(
\left( P\wedge \lnot Q\right) \wedge \lnot \lnot R\right) \vee \left( \lnot
\left( P\wedge \lnot Q\right) \wedge \lnot R\right) \quad \because \veebar
\text{の言い換え} \\
&\Leftrightarrow &\left( \left( P\wedge \lnot Q\right) \wedge \lnot \lnot
R\right) \vee \left( \left( \lnot P\vee \lnot \lnot Q\right) \wedge \lnot
R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\wedge \lnot Q\wedge R\right) \vee \left( \left(
\lnot P\vee Q\right) \wedge \lnot R\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( P\wedge \lnot Q\wedge R\right) \vee \left( \left( \lnot P\vee Q\right) \wedge \lnot R\right) \)には\(\veebar \)が含まれません。

以上の事実を踏まえると、論理式を以下のように定義しなおしても一般性は失われません。

  1. 命題変数\(P,Q,\cdots \)は論理式である。
  2. 命題定数\(T,F\)は論理式である。
  3. \(A\)が論理式ならば、\(\left( \lnot A\right) \)は論理式である。
  4. \(A,B\)が論理式ならば、\(\left( A\wedge B\right) \)は論理式である。
  5. \(A,B\)が論理式ならば、\(\left( A\vee B\right) \)は論理式である。
  6. 以上から論理式と判定されるものだけが論理式である。

 

論理式の双対

繰り返しになりますが、論理演算子として\(\lnot ,\wedge ,\vee \)だけ与えられれば任意の論理式を表現することができます。そのことを踏まえた上で、論理式\(A\)に対して以下の操作を加えることで得られる新たな論理式を\(A\)の双対(dual)と呼びます。\begin{eqnarray*}
&&\left( 1\right) \ A\text{中の}\wedge \text{を}\vee \text{に入れ替え、}\wedge \text{を}\vee
\text{に入れ替える。} \\
&&\left( 2\right) \ A\text{中の}T\text{を}F\text{に入れ替え、}F\text{を}T\text{に入れ替える。}
\end{eqnarray*}

例(双対)
命題変数\(P,Q\)に関する論理式\(\left( P\wedge Q\right) \vee P\)の双対は\(\left( P\vee Q\right) \wedge P\)です。
例(双対)
命題変数\(P,Q\)に関する論理式\(\lnot \left( P\wedge Q\right) \vee \left( \lnot P\wedge \lnot Q\right) \)の双対は\(\lnot \left( P\vee Q\right) \wedge \left( \lnot P\vee \lnot Q\right) \)です。
例(双対)
命題変数\(P,Q,R\)と命題定数\(T\)に関する論理式\(\left( \lnot P\wedge Q\right) \vee \lnot \left( T\wedge \lnot R\right) \)の双対は\(\left( \lnot P\vee Q\right) \wedge \lnot \left( F\vee \lnot R\right) \)です。

 

第1双対原理

命題変数\(P_{1},\cdots ,P_{n}\)と命題定数\(T,F\)に関する論理式を\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)と表記します。この論理式において、\(P_{1},\cdots ,P_{n}\)を\(\lnot P_{1},\cdots ,\lnot P_{n}\)に、\(T,F\)を\(F,T\)にそれぞれ置き換えることで得られる論理式を\(A\left( \lnot P_{1},\cdots ,\lnot P_{n},F,T\right) \)と表記します。また、論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)中の\(\wedge \)を\(\vee \)に、\(\vee \)を\(\wedge \)にそれぞれ置き換えて得られる論理式を\(A^{\ast }\left( P_{1},\cdots ,P_{n},T,F\right) \)と表記します。論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)の双対を\(A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \)で表すとき、双対の定義より、\begin{equation*}
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) =A^{\ast }\left( P_{1},\cdots
,P_{n},F,T\right)
\end{equation*}という関係が成り立ちます。

例(双対原理)
命題変数\(P,Q\)に関する論理式を、\begin{equation*}
A\left( P,Q\right) =P\wedge Q
\end{equation*}と定義すると、\begin{eqnarray}
A\left( \lnot P,\lnot Q\right) &=&\lnot P\wedge \lnot Q \tag{1} \\
A^{D}\left( P,Q\right) &=&A^{\ast }\left( P,Q\right) =P\vee Q \tag{2}
\end{eqnarray}などとなります。このとき、\begin{eqnarray*}
\lnot A\left( \lnot P,\lnot Q\right) &\Leftrightarrow &\lnot \left( \lnot
P\wedge \lnot Q\right) \quad \because \left( 1\right) \\
&\Leftrightarrow &P\vee Q\quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &A^{D}\left( P,Q\right) \quad \because \left( 2\right)
\end{eqnarray*}すなわち、\begin{equation*}
A^{D}\left( P,Q\right) \Leftrightarrow \lnot A\left( \lnot P,\lnot Q\right)
\end{equation*}という関係が成り立ちます。つまり、論理式\(A\left( P,Q\right) \)の双対は、その論理式の命題変数\(P,Q\)を\(\lnot P,\lnot Q\)にそれぞれ置き換えて得られる論理式の否定と同値です。
例(双対原理)
命題変数\(P,Q,R\)と命題定数\(T\)に関する論理式を、\begin{equation*}
A\left( P,Q,R,T\right) =\left( P\wedge \lnot Q\right) \vee \left( \lnot
R\wedge T\right)
\end{equation*}と定義します。このとき、\begin{eqnarray}
A\left( \lnot P,\lnot Q,\lnot R,T\right) &=&\left( \lnot P\wedge \lnot
\lnot Q\right) \vee \left( \lnot \lnot R\wedge T\right) \tag{1} \\
A^{D}\left( P,Q,R,T\right) &=&A^{\ast }\left( P,Q,R,F\right) =\left( P\vee
\lnot Q\right) \wedge \left( \lnot R\vee F\right) \tag{2}
\end{eqnarray}などとなります。このとき、\begin{eqnarray*}
\lnot A\left( \lnot P,\lnot Q,\lnot R,T\right) &\Leftrightarrow &\lnot
\left( \left( \lnot P\wedge \lnot \lnot Q\right) \vee \left( \lnot \lnot
R\wedge T\right) \right) \quad \because \left( 1\right) \\
&\Leftrightarrow &\lnot \left( \lnot P\wedge \lnot \lnot Q\right) \wedge
\lnot \left( \lnot \lnot R\wedge T\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot \lnot P\vee \lnot \lnot \lnot Q\right) \vee
\left( \lnot \lnot \lnot R\vee \lnot T\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\vee \lnot Q\right) \vee \left( \lnot R\vee
F\right) \quad \because \text{二重否定、命題定数の定義} \\
&\Leftrightarrow &A^{D}\left( P,Q,R,T\right) \quad \because \left( 2\right)
\end{eqnarray*}すなわち、\begin{equation*}
A^{D}\left( P,Q,R,T\right) \Leftrightarrow \lnot A\left( \lnot P,\lnot
Q,\lnot R,T\right)
\end{equation*}という関係が成り立ちます。つまり、論理式\(A\left( P,Q,R,T\right) \)の双対は、その論理式の命題変数\(P,Q,R\)を\(\lnot P,\lnot Q,\lnot R\)にそれぞれ置き換えて得られる論理式の否定と同値です。

以上の2つの例が示唆するように、一般に、命題変数\(P_{1},\cdots ,P_{n}\)と命題定数\(T,F\)に関する論理式\(A\left( P_{1},\cdots ,P_{n},T,F\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*}という関係が成り立ちます。つまり、論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)の双対は、その論理式の命題変数\(P_{1},\cdots ,P_{n}\)を\(\lnot P_{1},\cdots ,\lnot P_{n}\)にそれぞれ置き換えて得られる論理式の否定と同値になります。これを第1双対原理(first principle of duality)や第1双対定理(first duality theorem)などと呼びます。以下ではこれを証明します。

論理式\(A\)が論理演算子を含まない場合、すなわち\(A\)が命題変数や命題定数である場合、主張は明らかに成り立ちます。具体的には、\(A\left( P_{1},\cdots ,P_{n},T,F\right) =P_{i}\)であるとき、\begin{eqnarray*}
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &=&P_{i} \\
\lnot A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right) &=&\lnot \lnot
P_{i}
\end{eqnarray*}となりますが、二重否定より両者は同値です。また、\(A\left( P_{1},\cdots ,P_{n},T,F\right) =T\)であるとき、\begin{eqnarray*}
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &=&F \\
\lnot A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right) &=&\lnot T
\end{eqnarray*}となりますが、命題定数の定義より両者は同値です。\(A\left( P_{1},\cdots ,P_{n},T,F\right) =F\)の場合も同様です。

そこで以降では、\(m\ \left( \geq 1\right) \)個未満の論理演算子を含む任意の論理式に関して主張が成り立つものと仮定した上で、\(m\)個の論理演算子を含む論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)に関して主張が成り立つことを示します。論理式の定義より、この論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)に関して以下の3通りの可能性があります。

1つ目の可能性は、論理式\(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) =\lnot B\left( P_{1},\cdots
,P_{n},T,F\right) \tag{1}
\end{equation}という形で表される場合です。\(\left( 1\right) \)より、\(B\)に含まれる論理演算子の個数は\(m\)個未満であるため、仮定より、\begin{equation}
B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Leftrightarrow \lnot B\left(
\lnot P_{1},\cdots ,\lnot P_{n},T,F\right) \tag{2}
\end{equation}という関係が成り立ちます。このとき、\begin{eqnarray*}
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &\Leftrightarrow &A^{\ast
}\left( P_{1},\cdots ,P_{n},F,T\right) \quad \because \text{双対の定義} \\
&\Leftrightarrow &\lnot B^{\ast }\left( P_{1},\cdots ,P_{n},F,T\right) \quad
\because \left( 1\right) \\
&\Leftrightarrow &\lnot B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \quad
\because \text{双対の定義} \\
&\Leftrightarrow &\lnot \lnot B\left( \lnot P_{1},\cdots ,\lnot
P_{n},T,F\right) \quad \because \left( 2\right) \\
&\Leftrightarrow &\lnot A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\quad \because \left( 1\right)
\end{eqnarray*}となるため、\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)に関しても主張が成り立つことを確認できました。

2つ目の可能性は、論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)がその部分論理式\(B\left( P_{1},\cdots ,P_{n},T,F\right) ,\ C\left( P_{1},\cdots ,P_{n},T,F\right) \)を用いて、\begin{equation}
A\left( P_{1},\cdots ,P_{n},T,F\right) =B\left( P_{1},\cdots
,P_{n},T,F\right) \wedge C\left( P_{1},\cdots ,P_{n},T,F\right) \tag{3}
\end{equation}という形で表される場合です。\(\left( 3\right) \)より、\(B\)や\(C\)に含まれる論理演算子の個数は\(m\)個未満であるため、仮定より、\begin{eqnarray}
B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &\Leftrightarrow &\lnot B\left(
\lnot P_{1},\cdots ,\lnot P_{n},T,F\right) \tag{4} \\
C^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &\Leftrightarrow &\lnot C\left(
\lnot P_{1},\cdots ,\lnot P_{n},T,F\right) \tag{5}
\end{eqnarray}などの関係が成り立ちます。このとき、\begin{eqnarray*}
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) &\Leftrightarrow &A^{\ast
}\left( P_{1},\cdots ,P_{n},F,T\right) \quad \because \text{双対の定義} \\
&\Leftrightarrow &B^{\ast }\left( P_{1},\cdots ,P_{n},F,T\right) \vee
C^{\ast }\left( P_{1},\cdots ,P_{n},F,T\right) \quad \because \left(
1\right) \\
&\Leftrightarrow &B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \vee C^{\ast
}\left( P_{1},\cdots ,P_{n},T,F\right) \quad \because \text{双対の定義} \\
&\Leftrightarrow &\lnot B\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\vee \lnot C\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right) \quad \because
\left( 4\right) ,\left( 5\right) \\
&\Leftrightarrow &\lnot \left( B\left( \lnot P_{1},\cdots ,\lnot
P_{n},T,F\right) \wedge C\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\quad \because \left( 1\right)
\end{eqnarray*}となるため、\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)に関しても主張が成り立つことを確認できました。

3つ目の可能性は、論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)がその部分論理式\(B\left( P_{1},\cdots ,P_{n},T,F\right) ,\ C\left( P_{1},\cdots ,P_{n},T,F\right) \)を用いて、\begin{equation*}
A\left( P_{1},\cdots ,P_{n},T,F\right) =B\left( P_{1},\cdots
,P_{n},T,F\right) \vee C\left( P_{1},\cdots ,P_{n},T,F\right)
\end{equation*}という形で表される場合ですが、2番目の場合と同様に考えることにより、この場合にも\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)に関しても主張が成り立つことを確認できます(演習問題にします)。以上で、\(m\)に関する数学的帰納法により、第1双対原理の証明が完了しました。

命題(第1双対原理)
命題変数\(P_{1},\cdots ,P_{n}\)と命題定数\(T,F\)に関する論理式\(A\left( P_{1},\cdots ,P_{n},T,F\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*}という関係が成り立つ。
証明を見る(プレミアム会員限定)
例(双対原理)
命題変数\(P,Q\)に関する論理式\(P\wedge Q\)が与えられたとき、双対原理より、\begin{equation*}
P\vee Q\Leftrightarrow \lnot \left( \lnot P\wedge \lnot Q\right)
\end{equation*}が成り立ちます。実際、\begin{eqnarray*}
\lnot \left( \lnot P\wedge \lnot Q\right) &\Leftrightarrow &\lnot \lnot
\left( P\vee Q\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &P\vee Q\quad \because \text{二重否定}
\end{eqnarray*}であることから確認できます。
例(双対原理)
命題変数\(P,Q\)と命題定数\(T\)に関する論理式\(P\wedge \left( \lnot Q\vee T\right) \)が与えられたとき、双対原理より、\begin{equation*}
P\vee \left( \lnot Q\wedge F\right) \Leftrightarrow \lnot \left( \lnot
P\wedge \left( \lnot \lnot Q\vee T\right) \right)
\end{equation*}が成り立ちます。実際、\begin{eqnarray*}
\lnot \left( \lnot P\wedge \left( \lnot \lnot Q\vee T\right) \right)
&\Leftrightarrow &\lnot \lnot P\vee \lnot \left( \lnot \lnot Q\vee T\right)
\quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot \lnot P\vee \left( \lnot \lnot \lnot Q\wedge \lnot
T\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &P\vee \left( \lnot Q\wedge F\right) \quad \because \text{二重否定、命題定数の定義}
\end{eqnarray*}であることから確認できます。

 

第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*}
A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right) \Rightarrow B\left( \lnot
P_{1},\cdots ,\lnot P_{n},T,F\right)
\end{equation*}が成り立つため(演習問題にします)、対偶をとると、\begin{equation*}
\lnot B\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right) \Rightarrow \lnot
A\left( \lnot P_{1},\cdots ,\lnot P_{n},T,F\right)
\end{equation*}を得ます。第1双対原理を用いてこれを言い換えると、\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)などと呼びます。

命題(第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*}という関係が成り立つ。
証明を見る(プレミアム会員限定)

 

第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*}が成り立ちます。これを第3双対原理(third principle of duality)や第3双対定理(third duality theorem)などと呼びます。つまり、論理式\(A,B\)が論理的に同値であるとき、それらの双対\(A^{D},B^{D}\)どうしも論理的に同値になるということです。

命題(第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{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\)に対して、\begin{eqnarray*}
&&\left( a\right) \ A\wedge A\Leftrightarrow A \\
&&\left( b\right) \ A\vee A\Leftrightarrow A\
\end{eqnarray*}がともに成り立つという命題ですが、\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
交換律とは、任意の論理式\(A\)に対して、\begin{align*}
& \left( a\right) \ A\wedge B\Leftrightarrow B\wedge A \\
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}がともに成り立つという命題ですが、\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
結合律とは、任意の論理式\(A,B,C\)に対して、\begin{align*}
& \left( a\right) \ (A\wedge B)\wedge C\Leftrightarrow A\wedge \left(
B\wedge C\right) \\
& \left( b\right) \ (A\vee B)\vee C\Leftrightarrow A\vee \left( B\vee
C\right)
\end{align*}がともに成り立つという命題ですが、\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
分配律とは、任意の論理式\(A,B,C\)に対して、\begin{align*}
& \left( a\right) \ A\wedge (B\vee C)\Leftrightarrow (A\wedge B)\vee
(A\wedge C) \\
& \left( b\right) \ A\vee (B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee
C)
\end{align*}がともに成り立つという命題ですが、\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
吸収律とは、任意の論理式\(A,B,C\)に対して、\begin{align*}
& \left( a\right) \ A\wedge (A\vee B)\Leftrightarrow A \\
& \left( b\right) \ A\vee (A\wedge B)\Leftrightarrow A
\end{align*}がともに成り立つという命題ですが、\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
ド・モルガンの法則とは、任意の論理式\(A,B\)に対して、\begin{align*}
& \left( a\right) \ \lnot \left( A\wedge B\right) \Leftrightarrow \lnot
A\vee \lnot B \\
& \left( b\right) \ \lnot \left( A\vee B\right) \Leftrightarrow \lnot
A\wedge \lnot B
\end{align*}がともに成り立つという命題ですが、\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
任意の論理式\(A\)に対して、\begin{eqnarray*}
\left( a\right) \ A\wedge \lnot A &\Leftrightarrow &F \\
\left( b\right) \ A\vee \lnot A &\Leftrightarrow &T
\end{eqnarray*}がともに成り立つことはすでに示した通りです。\(\left( a\right) \)は矛盾律であり、\(\left( b\right) \)は排中律です。\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
命題定数\(T,F\)に対して、\begin{align*}
& \left( a\right) \ \lnot T\Leftrightarrow F \\
& \left( b\right) \ \lnot F\Leftrightarrow T
\end{align*}などの関係が成り立ちますが、\(\left( a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。また、論理式\(A\)を任意に選んだとき、\begin{eqnarray*}
\left( c\right) \ A\wedge T &\Leftrightarrow &A \\
\left( d\right) \ A\vee F &\Leftrightarrow &A
\end{eqnarray*}などの関係が成り立ちますが、\(\left( c\right) \)に双対原理を適用すれば\(\left( d\right) \)を得て、逆に、\(\left( d\right) \)に双対原理を適用すれば\(\left( e\right) \)を得ます。さらに、\begin{eqnarray*}
\left( e\right) \ A\wedge F &\Leftrightarrow &F \\
\left( f\right) \ A\vee T &\Leftrightarrow &T
\end{eqnarray*}などの関係が成り立ちますが、\(\left( e\right) \)に双対原理を適用すれば\(\left( f\right) \)を得て、逆に、\(\left( f\right) \)に双対原理を適用すれば\(\left( e\right) \)を得ます。

次回からは推論について学びます。
次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)

Share on facebook
Share on twitter
Share on email
< 前のページ

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

命題論理
アカウント
ログイン