教材一覧
教材一覧
教材検索
PROPOSITIONAL LOGIC

命題論理における双対原理

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

論理式の双対

論理演算子として\(\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 \)に限定しても一般性は失われません。以上を踏まえた上で、論理式\(A\)に対して以下の操作を加えることにより得られる新たな論理式をもとの論理式\(A\)の双対(dual)と呼びます。\begin{eqnarray*}&&\left( a\right) \ A\text{中の}\wedge \text{を}\vee \text{に入れ替え、}\wedge \text{を}\vee
\text{に入れ替える。} \\
&&\left( b\right) \ A\text{中の}T\text{を}F\text{に入れ替え、}F\text{を}T\text{に入れ替える。}
\end{eqnarray*}ただし、\(T,F\)は命題定数です。

例(双対)
命題変数\(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\)を被演算子とする論理式を、\begin{equation*}A\left( P_{1},\cdots ,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}\)に置き換えることで得られる論理式を、\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) \)は常に論理的に同値になります。まずは例を通じて確認しましょう。

例(第1双対原理)
命題変数\(P,Q\)と命題定数\(T,F\)に関する論理式が、\begin{equation*}A\left( P,Q,T,F\right) =P\wedge Q
\end{equation*}で与えられているとき、その双対は、\begin{equation*}
A^{D}\left( P,Q,T,F\right) =P\vee Q
\end{equation*}となります。さて、\begin{eqnarray*}
\lnot A\left( \lnot P,\lnot Q,T,F\right) &=&\lnot \left( \lnot P\wedge
\lnot Q\right) \\
&\Leftrightarrow &P\vee Q\quad \because \text{ド・モルガンの法則}
\end{eqnarray*}となるため、\begin{equation*}
A^{D}\left( P,Q,T,F\right) \Leftrightarrow \lnot A\left( \lnot P,\lnot
Q,T,F\right)
\end{equation*}という関係が成り立つことが明らかになりました。つまり、論理式\(A\left( P,Q,T,F\right) \)の双対は、この論理式中の命題変数\(P,Q\)を否定\(\lnot P,\lnot Q\)にそれぞれ置き換えて得られる論理式の否定と論理的に同値です。
例(第1双対原理)
命題変数\(P,Q,R\)と命題定数\(T,F\)に関する論理式が、\begin{equation*}A\left( P,Q,R,T,F\right) =\left( P\wedge \lnot Q\right) \vee \left( \lnot
R\wedge T\right)
\end{equation*}で与えられているとき、その双対は、\begin{equation*}
A^{D}\left( P,Q,R,T,F\right) =\left( P\vee \lnot Q\right) \wedge \left(
\lnot R\vee F\right)
\end{equation*}となります。さて、\begin{eqnarray*}
\lnot A\left( \lnot P,\lnot Q,\lnot R,T,F\right) &=&\lnot \left( \left(
\lnot P\wedge \lnot \lnot Q\right) \vee \left( \lnot \lnot R\wedge T\right)
\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{二重否定、命題定数の定義}
\end{eqnarray*}となるため、\begin{equation*}
A^{D}\left( P,Q,R,T,F\right) \Leftrightarrow \lnot A\left( \lnot P,\lnot
Q,\lnot R,T,F\right)
\end{equation*}という関係が成り立つことが明らかになりました。つまり、論理式\(A\left( P,Q,R,T,F\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双対原理(firstprinciple of duality)や第1双対定理(first duality theorem)などと呼びます。

命題(第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*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(第1双対原理)
命題変数\(P,Q\)に関する論理式\(P\wedge Q\)が与えられたとき、第1双対原理より、その双対\(P\vee 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*}であることから確認できます。

例(第1双対原理)
命題変数\(P,Q\)と命題定数\(T\)に関する論理式\(P\wedge \left(\lnot Q\vee T\right) \)が与えられたとき、第1双対原理より、その双対\(P\vee \left( \lnot Q\wedge F\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*}
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双対原理を利用します。

命題(第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双対原理)
命題変数\(P,Q\)に関して、\begin{equation*}\left( P\wedge Q\right) \Rightarrow P
\end{equation*}が成り立ちますが、このとき、第2双対原理より、\begin{equation*}
P\Rightarrow \left( P\vee Q\right)
\end{equation*}もまた成り立つことが保証されます。実際、\begin{eqnarray*}
P\rightarrow \left( P\vee Q\right) &\Leftrightarrow &\lnot P\vee \left(
P\vee Q\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( P\vee \lnot P\right) \vee Q\quad \because \text{結合律と交換律} \\
&\Leftrightarrow &\top \vee Q\quad \because \text{排中律}
\\
&\Leftrightarrow &\top \quad \because \text{恒真式の性質}
\end{eqnarray*}となるため主張が正しいことが確認されました。

例(第2双対原理)
命題変数\(P,Q\)に関して、\begin{equation*}\lnot \left( P\wedge Q\right) \Rightarrow \lnot P\vee \lnot Q
\end{equation*}が成り立ちますが、このとき、第2双対原理より、\begin{equation*}
\lnot P\wedge \lnot Q\Rightarrow \lnot \left( P\vee Q\right)
\end{equation*}もまた成り立つことが保証されます。実際、\begin{eqnarray*}
\left( \lnot P\wedge \lnot Q\right) \rightarrow \lnot \left( P\vee Q\right)
&\Leftrightarrow &\lnot \left( \lnot P\wedge \lnot Q\right) \vee \lnot
\left( P\vee Q\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot \lnot P\vee \lnot \lnot Q\right) \vee \lnot
\left( P\vee Q\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\vee Q\right) \vee \lnot \left( P\vee Q\right)
\quad \because \text{二重否定} \\
&\Leftrightarrow &\top \quad \because \text{排中律}
\end{eqnarray*}となるため主張が正しいことが確認されました。

 

第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) \)を得ます。

 

演習問題

問題(双対)
命題変数\(P,Q,R,S\)に関する以下の論理式\begin{equation*}\lnot \left( \lnot P\vee Q\right) \vee \left( R\rightarrow \lnot S\right)
\end{equation*}を\(\lnot ,\wedge ,\vee \)以外の論理演算子を持たない論理式に同値変形した上で、その双対を明らかにしてください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(双対)
命題変数\(P,Q,R\)に関する以下の論理式\begin{equation*}\left( \lnot P\rightarrow Q\right) \rightarrow \left( Q\rightarrow \lnot
R\right)
\end{equation*}を\(\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 \)に置き換えることができます。したがって、論理演算子として\(\lnot,\wedge ,\vee \)だけ与えられれば任意の論理式を表現できます。以上を踏まえた上で、さらに以下が成り立つことをそれぞれ証明してください。

  1. 論理演算子として\(\lnot \)と\(\wedge \)だけ与えられれば任意の論理式を表現できる。
  2. 論理演算子として\(\lnot \)と\(\vee \)だけ与えられれば任意の論理式を表現できる。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回からは推論について学びます。

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

RELATED KNOWLEDGE
双対原理
集合演算における双対原理

等しい 2 つの集合が与えられたとき、それらの双対をとるとそれらもまた等しくなります。これを双対原理と呼びます。

命題論理