論理式\(A,B\)に関して同等\(A\leftrightarrow B\)が恒真式であるならば、\(A\)と\(B\)は論理的に同値であると言い、このことを\(A\Leftrightarrow B\)で表します。またこのとき、\(A\)と\(B\)はお互いに一方が他方であるための必要十分条件であると言います。

必要十分条件

論理式\(A,B\)に関して同等\(A\leftrightarrow B\)が恒真式であるならば、\(A\)と\(B\)は論理的に同値(logically equivalent)であると言い、このことを\(A\Leftrightarrow B\)で表します。またこのとき、\(A\)と\(B\)はお互いに一方が他方であるための必要十分条件(necessary and sufficient condition)であると言います。

恒真式について復習する

 

\begin{array}{ccccc}
\hline
A & B & T & A\leftrightarrow B & \left( A\leftrightarrow B\right) \leftrightarrow T \\ \hline
1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 1 & 0 & 0 \\ \hline
0 & 1 & 1 & 0 & 0 \\ \hline
0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}

表:同値

論理式\(A,B\)について\(A\Leftrightarrow B\)が成り立つことは、論理式\(A\leftrightarrow B\)の値が常に\(1\)であることを意味します。したがって、\(A\Leftrightarrow B\)の場合には、上の真理値表において 2 行目と 3 行目の場合は起こり得ません。

さらに上の真理値表より、\(A\leftrightarrow B\)の値が\(1\)であることと\(A\)と\(B\)の値が一致することは同義です。したがって\(A\Leftrightarrow B\)が成り立つことは\(A\)と\(B \)の値が常に一致することと同義です。

さらに、やはり上の真理値表より、\(A\leftrightarrow B\)と\(\left( A\leftrightarrow B\right) \leftrightarrow T\)の値は常に等しいため、\(A\Leftrightarrow B\)が成り立つことは\(\left( A\leftrightarrow B\right) \Leftrightarrow T\)が成り立つことと同義です。

 

必要条件や十分条件との関係

論理式\(A,B\)について\(A\Leftrightarrow B\)が成り立つことは、論理式\(A\leftrightarrow B\)の値が常に\(1\)であることを意味します。また、\(A\leftrightarrow B\)と\(\left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right)\)は論理的に同値です。したがって、\(A\Leftrightarrow B\)が成り立つことは\(\left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) \)の値が常に\(1\)であることを意味し、さらに\(\wedge \)の定義より、これは\(A\rightarrow B\)と\(B\rightarrow A\)の両方の値が常に\(1\)であること、すなわち、\(A\Rightarrow B\)と\(B\Rightarrow A\)がともに成り立つことを意味します。

以上を踏まえると、\(A\)が\(B\)であるための必要十分条件であることは、\(A\)が\(B\)であるための必要条件であると同時に十分条件であることを意味します。同様に、\(B\)が\(A\)であるための必要十分条件であることは、\(B\)が\(A \)であるための必要条件であると同時に十分条件であることを意味します。

 

同値の性質

同値を表す記号\(\Leftrightarrow \)は以下の性質を満たします。\(\left( a\right) \)は反射律(reflexive law)、\(\left( b\right) \)は対称律(symmetric law)、\(\left( c\right) \)は推移律(transitive law)と呼ばれる性質です。この命題は、\(\Leftrightarrow \)を二項関係(binary relation)とみなしたとき、これが同値関係(equivalence relation)であることを示唆します。二項関係や同値関係については場を改めて解説します。

命題(同値の性質)
任意の論理式\(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*}
証明を見る(プレミアム会員限定) 二項関係について学ぶ

 

同値変形

与えられた論理式をそれと同値な別の論理式に変換することを同値変形(equivalence transformation)と呼びます。

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

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

次回からは同値変形を行う際に役に立つ恒真式を紹介します。

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)

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

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

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

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

現在地
目次
アカウント
ログイン