論理式 \(A,B\) について同等\(A\leftrightarrow B\)が恒真式であるならば、すなわち、任意の解釈のもとで\(A\leftrightarrow B\) の値が\(1\)であるならば、\(A\)と\(B\) はお互いに一方が他方であるための必要十分条件であると言います。
次のページ >

必要十分条件

論理式\(A,B\)に関して同等\(A\leftrightarrow B\)が恒真式であるならば、つまり、論理式\(A\leftrightarrow B\)の値が任意の解釈のもとで\(1\)になるならば、\(A\)と\(B\)は論理的に同値(logically equivlent)であると言い、このことを\(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,B\)はそれぞれ\(1\)または\(0\)を取り得るため、起こり得るすべての場合を記した真理値表は上のようになります。\(A\Leftrightarrow B\)の場合には真理値表の 2 行目と 3 行目の場合は起こり得ません。さらに、\(A\leftrightarrow B\)と\(\left( A\leftrightarrow B\right) \leftrightarrow T\)の値は任意の解釈のもとで等しいため、\(A\Leftrightarrow B\)が成り立つことは\(\left( A\leftrightarrow B\right) \Leftrightarrow T\)が成り立つことと同義です。

例(同値な論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)を部分論理式として持つ論理式\begin{equation}
\exists x\in X\ \left( \lnot P\left( x\right) \right) \leftrightarrow \lnot \left( \exists x\in X\ P\left( x\right) \right) \tag{1}
\end{equation}について考えます。存在記号\(\exists \)の定義より、上の論理式は、\begin{equation}
\bigvee\nolimits_{x\in X}\lnot P\left( x\right) \leftrightarrow \lnot \left( \bigwedge\nolimits_{x\in X}P\left( x\right) \right) \tag{2}
\end{equation}と言い換えられます。さらに、\(\left( 2\right) \)中の\(\leftrightarrow \)の左側の部分論理式はド・モルガンの法則より、\begin{equation*}
\bigvee\nolimits_{x\in X}\lnot P\left( x\right) \Leftrightarrow \lnot \left( \bigwedge\nolimits_{x\in X}P\left( x\right) \right)
\end{equation*}と言い換え可能ですが、これは\(\left( 2\right) \)中の\(\leftrightarrow \)の右側の部分論理式に他なりません。任意の解釈において\(\left( 2\right) \)中の\(\leftrightarrow \)の左右の部分論理式の値は一致するため、任意の解釈において\(\left( 1\right) \)は真になります。したがって\(\exists x\in X\ \left( \lnot P\left( x\right) \right) \)と\(\lnot \left( \exists x\in X\ P\left( x\right) \right) \)は論理的に同値です。

 

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

論理式\(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 \)は以下の性質を満たします。

命題(同値の性質)
任意の論理式\(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*}
証明を見る(プレミアム会員限定)

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

 

同値変形

与えられた論理式をそれと論理的に同値な別の論理式へ変換することを同値変形(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) \)は論理的に同値だからです。

次節では同値変形を行う際に役に立つ恒真式を紹介します。これらの多くは命題論理における同様の恒真式をそのまま引き継いだものですが、量化記号\(\forall ,\exists \)が関わる恒真式は述語論理に固有のものです。

次へ進む 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

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

述語論理
アカウント
ログイン