教材一覧
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 \)に置き換えることができます。

例(論理演算子の置き換え)
命題変数\(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( 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*}

論理式の双対の例をいくつか挙げます。

例(双対)
命題変数\(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}\)に、\(T\)を\(F\)に、\(F\)を\(T\)にそれぞれ入れ替えることで得られる論理式を、\begin{equation*}A\left( \lnot P_{1},\cdots ,\lnot P_{n},F,T\right)
\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)
\end{equation*}で表記します。

例(第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双対原理(first principle ofduality)や第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双対原理より、\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双対原理より、\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*}という関係が成り立つ。
例(第2双対原理)
命題変数\(P,Q\)に関して、\begin{equation*}\left( P\wedge Q\right) \Rightarrow P
\end{equation*}が成り立ちますが、このとき、第2双対原理より、\begin{equation*}
P\Rightarrow P\vee Q
\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
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

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

命題論理