与えられた論理式をそれと同値な別の論理式に交換することを同値変形と呼びます。
< 前のページ
次のページ >

同値変形の根拠

論理式\(A\)を任意に選んだとき、以下の真理値表
$$\begin{array}{cc}
\hline
A & A\leftrightarrow A \\ \hline
1 & 1 \\ \hline
0 & 1 \\ \hline
\end{array}$$

表:反射律

が得られます。つまり、論理式\(A\leftrightarrow A\)は恒真式であるため、\begin{equation*}
A\Leftrightarrow A
\end{equation*}が成り立ちます。\(\Leftrightarrow \)が満たすこのような性質を反射律(reflexive law)と呼びます。\(\Leftrightarrow \)が反射律を満たすことは、任意の論理式はそれ自身と論理的に同値である(必要十分条件である)ことを意味します。

論理式\(A,B\)を任意に選んだとき、以下の真理値表
$$\begin{array}{cccc}
\hline
A & B & A\leftrightarrow B & B\leftrightarrow A \\ \hline
1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 0 \\ \hline
0 & 1 & 0 & 0 \\ \hline
0 & 0 & 1 & 1 \\ \hline
\end{array}$$

表:対称律

が得られます。\(A\Leftrightarrow B\)が成り立つものとします。つまり、\(A\leftrightarrow B\)の値は常に\(1\)であるということです。このとき、上の真理値表の3行目と4行目は起こらないため、\(B\leftrightarrow A\)の値も常に\(1\)です。したがって、\(B\Leftrightarrow A\)が成り立ちます。つまり、\(A\Leftrightarrow B\)が成り立つならば\(B\Leftrightarrow A\)も成り立ちますが、\(\Leftrightarrow \)が満たすこのような性質を対称律(symmetric law)と呼びます。

論理式\(A,B,C\)を任意に選んだとき、以下の真理値表
$$\begin{array}{cccccc}
\hline
A & B & C & A\leftrightarrow B & B\leftrightarrow C & A\leftrightarrow C \\ \hline
1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 0 & 1 & 0 & 0 \\ \hline
1 & 0 & 1 & 0 & 0 & 1 \\ \hline
1 & 0 & 0 & 0 & 1 & 0 \\ \hline
0 & 1 & 1 & 0 & 1 & 0 \\ \hline
0 & 1 & 0 & 0 & 0 & 1 \\ \hline
0 & 0 & 1 & 1 & 0 & 0 \\ \hline
0 & 0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$

表:推移律

が得られます。\(A\Leftrightarrow B\)と\(B\Leftrightarrow C\)がともに成り立つものとします。つまり、\(A\leftrightarrow B\)と\(B\leftrightarrow C\)の値は常に\(1\)であるということです。このとき、上の真理値表の1行目と8行目しか起こり得ないため、\(A\leftrightarrow C\)の値も常に\(1\)です。したがって、\(A\Leftrightarrow C\)が成り立ちます。つまり、\(A\Leftrightarrow B\)と\(B\Leftrightarrow C\)が成り立つならば\(A\Leftrightarrow C\)も成り立ちますが、\(\Leftrightarrow \)が満たすこのような性質を推移律(transitive law)と呼びます。

命題(論理式の同値の性質)
任意の論理式\(A,B,C\)に対して以下が成り立つ。\begin{align*}
& \left( a\right) \ A\Leftrightarrow A\text{が成り立つ} \\
& \left( b\right) \ A\Leftrightarrow B\text{が成り立つならば}B\Leftrightarrow A\text{も成り立つ} \\
& \left( c\right) \ A\Leftrightarrow B\text{と}B\Leftrightarrow C\text{が成り立つならば}A\Leftrightarrow C\text{も成り立つ}
\end{align*}
証明を見る(プレミアム会員限定)

上の命題は、\(\Leftrightarrow \)を二項関係とみなしたとき、これが同値関係であることを意味します。

 

同値変形

論理式\(A,B\)の間に\(A\Leftrightarrow B\)が成り立つ場合には、つまり、\(A\)と\(B\)が論理的に同値である場合には、任意の解釈のもとで\(A\)
と\(B\)の真理値は常に一致するため、両者は交換可能です。そこで、与えられた論理式をそれと同値な別の論理式に交換することを同値変形(equivalence transformation)と呼びます。

論理式\(A,B\)の間に\(A\Leftrightarrow B\)が成り立つものとします。このとき、\(A\)と\(B\)は同値変形が可能です。さらに、別の論理式\(C\)が\(B\Leftrightarrow C\)を満たすものとします。すると、\(\Leftrightarrow \)の推移律より\(A\Leftrightarrow C\)が成り立つため、\(A\)と\(C\)も同値変形が可能です。つまり、ある論理式から出発して同値変形を繰り返したとき、最終的に得られる論理式は最初の論理式と同値であることが保証されます。

同値変形の過程で\(A\Leftrightarrow B\)を直接示すことが困難である場合には、間に別の論理式\(C\)を仲介させて\(A\Leftrightarrow C\)と\(B\Leftrightarrow C\)を示してもかまいません。なぜなら、\(\Leftrightarrow \)の推移律より、この場合には\(A\Leftrightarrow B\)であることが保証されるからです。

論理式\(A\)の部分論理式\(B\)に注目したとき、\(B\)と論理的に同値であるような論理式\(B^{\prime }\)が存在するものとします。さらに、\(A\)中の\(B\)を\(B^{\prime }\)に置き換えて得られる論理式を\(A^{\prime }\)で表します。\(B\)と\(B^{\prime }\)の真理値は任意の解釈のもとで一致するため、\(A\)と\(A^{\prime }\)の真理値もまた任意の解釈のもとで一致します。

例(同値変形)
命題変数\(P,Q,R\)に関する論理式\begin{equation}
P\wedge \left( Q\wedge R\right) \tag{1}
\end{equation}について考えます。\(\left( 1\right) \)の部分論理式\(Q\wedge R\)について、\begin{equation*}
Q\wedge R\Leftrightarrow R\wedge Q
\end{equation*}が成り立つため、\(\left( 1\right) \)は、\begin{equation*}
P\wedge \left( Q\wedge R\right) \Leftrightarrow P\wedge \left( R\wedge
Q\right)
\end{equation*}という形で同値変形が可能です。
例(同値変形)
命題変数\(P,Q\)に関する論理式\begin{equation}
\lnot \lnot P\vee \lnot \lnot Q \tag{1}
\end{equation}について考えます。\(\left( 1\right) \)の部分論理式\(\lnot \lnot P\)については、\begin{equation}
\lnot \lnot P\Leftrightarrow P \tag{2}
\end{equation}が成り立ち、\(\left( 1\right) \)の部分論理式\(\lnot \lnot Q\)については、\begin{equation}
\lnot \lnot Q\Leftrightarrow Q \tag{3}
\end{equation}が成り立つため、\(\left( 1\right) \)は、\begin{eqnarray*}
\lnot \lnot P\vee \lnot \lnot Q &\Leftrightarrow &\ P\vee \lnot \lnot Q\quad
\because \left( 2\right) \\
&\Leftrightarrow &\ P\vee Q\quad \because \left( 3\right)
\end{eqnarray*}という形で同値変形が可能です。

次回はベキ等律と呼ばれる同値変形に関する法則について解説します。

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
Share on print
< 前のページ
次のページ >

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するためにはログインが必要です
ログイン

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