WIIS

述語論理

述語論理における同値変形

目次

関連知識

Mailで保存
Xで共有

論理的同値関係

論理式\(A,B\)が与えられたとき、解釈を任意に選んだ上で、その場合に\(A,B\)から得られる命題を\(\overline{A},\overline{B}\)で表記します。任意の解釈において、\begin{equation*}\overline{A}\leftrightarrow \overline{B}
\end{equation*}が真である場合には、すなわち、任意の解釈において\(\overline{A}\)の真理値と\(\overline{B}\)の真理値が一致する場合には、\(A\)は\(B\)と論理的に同値(logically equivalent)であるとか、\(A\)と\(B\)はお互いに必要十分条件(necessary and sufficient condition)であるなどと言い、そのことを、\begin{equation*}A\Leftrightarrow B
\end{equation*}で表記します。その上で、記号\(\Leftrightarrow \)を論理的同値関係(logical equivalence relation)と呼ぶこととします。

例(論理的同値関係)
命題関数\(P\left( x\right) \)に関する以下の論理式\begin{equation*}\left( P\left( x\right) \wedge P\left( x\right) \right) \leftrightarrow
P\left( x\right)
\end{equation*}について考えます。これは開論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状および変数\(x\)に代入する値を指定する必要があります。そこで、\(x\)の定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) \)および変数に代入する値\(\overline{x}\in \overline{X}\)をそれぞれ任意に選ぶと、以下の命題\begin{equation*}\left( \overline{P}\left( \overline{x}\right) \wedge \overline{P}\left(
\overline{x}\right) \right) \leftrightarrow \overline{P}\left( \overline{x}\right)
\end{equation*}が得られます。

$$\begin{array}{ccc}
\hline
\overline{P}\left( \overline{x}\right) & \overline{P}\left( \overline{x} \right) \wedge \overline{P}\left( \overline{x}\right) & \left( \overline{P }\left( \overline{x}\right) \wedge \overline{P}\left( \overline{x}\right) \right) \leftrightarrow \overline{P}\left( \overline{x}\right) \\ \hline
1 & 1 & 1 \\ \hline
0 & 0 & 1 \\ \hline
\end{array}$$

以上の真理値表から明らかであるように先の命題は常に真であるため、\begin{equation*}
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\end{equation*}が成り立ちます。つまり、\(P\left( x\right) \wedge P\left( x\right) \)と\(P\left( x\right) \)は論理的に同値です。

例(論理的同値変形)
命題関数\(P\left( x\right) \)と恒偽式\(\bot \)に関する以下の論理式\begin{equation*}\left( \forall x\in X:\left( P\left( x\right) \wedge \lnot P\left( x\right)
\right) \right) \leftrightarrow \bot
\end{equation*}について考えます。これは閉論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状を指定する必要があります。そこで、\(x\)の定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left(x\right) \)をそれぞれ任意に選ぶと、以下の命題\begin{equation*}\left( \forall x\in \overline{X}:\left( \overline{P}\left( x\right) \wedge
\lnot \overline{P}\left( x\right) \right) \right) \leftrightarrow \bot
\end{equation*}が得られます。全称命題の定義より、以下の命題\begin{equation*}
\forall x\in \overline{X}:\left( \overline{P}\left( x\right) \wedge \lnot
\overline{P}\left( x\right) \right)
\end{equation*}は以下の命題\begin{equation*}
\bigwedge_{x\in \overline{X}}\left( \overline{P}\left( x\right) \wedge
\lnot \overline{P}\left( x\right) \right)
\end{equation*}と同一視されます。論理積の定義より\(\overline{P}\left( x\right) \wedge \lnot \overline{P}\left( x\right) \)は偽であり、したがってやはり論理積の定義より上の命題は偽です。以上より、\begin{equation*}\left( \forall x\in X:\left( P\left( x\right) \wedge \lnot P\left( x\right)
\right) \right) \Leftrightarrow \bot
\end{equation*}であることが明らかになりました。つまり、\(\forall x\in X:\left( P\left( x\right) \wedge \lnot P\left(x\right) \right) \)と\(\bot \)は論理的に同値です。

 

同値変形

論理式\(A,B\)が論理的に同値である場合には、任意の解釈のもとで\(A\)から生成される命題\(\overline{A}\)と\(B\)から生成される命題\(\overline{B}\)の真理値は常に一致するため、\(A\)と\(B\)は交換可能です。そこで、与えられた論理式をそれと論理的に同値な論理式に交換することを同値変形(equivalence transformation)と呼びます。

例(恒真式であることの証明)
論理式\(A\)が恒真式であることを示そうとしている状況を想定します。この場合、\(A\)を別の論理式\(B\)へ同値変形した上で\(B\)が恒真式であることを示しても問題ありません。なぜなら、\(A\)と\(B\)の真理値は常に一致するからです。
例(恒偽式であることの証明)
論理式\(A\)が恒偽式であることを示そうとしている状況を想定します。この場合、\(A\)を別の論理式\(B\)へ同値変形した上で\(B\)が恒偽式であることを示しても問題ありません。なぜなら、\(A\)と\(B\)の真理値は常に一致するからです。

論理式\(A\)の部分論理式\(B \)に注目したとき、\(B\)と論理的に同値であるような論理式\(B^{\prime }\)が存在するものとします。さらに、\(A\)中の\(B\)を\(B^{\prime }\)に同値変形することにより得られる論理式を\(A^{\prime }\)で表します。\(B\)と\(B^{\prime }\)の真理値は任意の解釈のもとで一致するため、この場合、\begin{equation*}A\Leftrightarrow A^{\prime }
\end{equation*}が成り立ちます。

例(部分論理式の同値変形)
命題関数\(P\left( x\right) ,Q\left( x\right) \)に関する以下の論理式\begin{equation}Q\left( x\right) \vee \left( P\left( x\right) \wedge P\left( x\right)
\right) \quad \cdots (1)
\end{equation}に注目します。先に示したように、\begin{equation}
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\quad \cdots (2)
\end{equation}が成り立ちます。\(\left(2\right) \)を用いて\(\left( 1\right) \)を同値変形することにより、\begin{equation*}Q\left( x\right) \vee \left( P\left( x\right) \wedge P\left( x\right)
\right) \Leftrightarrow Q\left( x\right) \vee P\left( x\right)
\end{equation*}を得ます。

 

論理的同値関係の反射律

論理式\(A\)を任意に選んだとき、\begin{equation*}A\Leftrightarrow A
\end{equation*}が成り立つことが保証されます。つまり、任意の論理式は自身と論理的に同値であるということです。論理的同値関係\(\Leftrightarrow \)が満たす以上の性質を反射律(reflexive law)と呼びます。

命題(論理的同値関係の反射律)
任意の論理式\(A\)について、\begin{equation*}A\Leftrightarrow A
\end{equation*}が成り立つ。

証明

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

以上の命題は、任意の論理式は自身へ同値変形可能であることを保証します。

例(論理的同値関係の反射律)
命題関数\(P\left( x\right) \)を任意に選んだとき、\(\Leftrightarrow \)の反射律より、\begin{equation*}P\left( x\right) \Leftrightarrow P\left( x\right)
\end{equation*}が成り立ちます。

例(論理的同値関係の反射律)
命題関数\(P\left( x\right) ,Q\left( x\right) \)を任意に選んだとき、\(\Leftrightarrow \)の反射律より、\begin{equation*}P\left( x\right) \wedge Q\left( x\right) \Leftrightarrow P\left( x\right)
\wedge Q\left( x\right)
\end{equation*}が成り立ちます。

 

論理的同値関係の対称律

論理式\(A,B\)を任意に選んだとき、\begin{equation*}A\Leftrightarrow B
\end{equation*}が成り立つ場合には、\begin{equation*}
B\Leftrightarrow A
\end{equation*}もまた成り立つことが保証されます。つまり、\(A\)が\(B\)と論理的に同値である場合には、逆に、\(B\)が\(A\)と論理的に同値であることも保証されるということです。論理的同値関係\(\Leftrightarrow \)が満たす以上の性質を対称律(symmetric law)と呼びます。

命題(論理的同値関係の対称律)
論理式\(A,B\)を任意に選んだとき、\begin{equation*}A\Leftrightarrow B
\end{equation*}が成り立つ場合には、\begin{equation*}
B\Leftrightarrow A
\end{equation*}もまた成り立つ。

証明

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

以上の命題は、論理式\(A,B\)が与えられたとき、\(A\)が\(B\)へ同値変形可能である場合には、逆に、\(B\)が\(A\)へ同値変形可能であることを保証します。

例(論理的同値関係の対称律)
命題関数\(P\left( x\right) \)を任意に選んだとき、\begin{equation*}P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\end{equation*}が成り立つことは先に示した通りです。したがって、対称律より、\begin{equation*}
P\left( x\right) \Leftrightarrow P\left( x\right) \wedge P\left( x\right)
\end{equation*}もまた成り立ちます。

例(論理的同値関係の対称律)
命題関数\(P\left( x\right) \)を任意に選んだとき、\begin{equation*}\left( \forall x\in X:\left( P\left( x\right) \wedge \lnot P\left( x\right)
\right) \right) \Leftrightarrow \bot
\end{equation*}が成り立つことは先に示した通りです。したがって、対称律より、\begin{equation*}
\bot \Leftrightarrow \left( \forall x\in X:\left( P\left( x\right) \wedge
\lnot P\left( x\right) \right) \right)
\end{equation*}もまた成り立ちます。

 

論理的同値関係の推移律

論理式\(A,B,C\)を任意に選んだとき、\begin{eqnarray*}A &\Leftrightarrow &B \\
B &\Leftrightarrow &C
\end{eqnarray*}がともに成り立つ場合には、\begin{equation*}
A\Leftrightarrow C
\end{equation*}もまた成り立つことが保証されます。つまり、\(A\)が\(B\)と論理的に同値であり、\(B\)が\(C\)と論理的に同値である場合には、\(A\)が\(C\)と論理的に同値であることが保証されるということです。論理的同値関係\(\Leftrightarrow \)が満たす以上の性質を推移律(transitive law)と呼びます。

命題(論理的同値関係の推移律)
論理式\(A,B,C\)を任意に選んだとき、\begin{eqnarray*}A &\Leftrightarrow &B \\
B &\Leftrightarrow &C
\end{eqnarray*}がともに成り立つ場合には、\begin{equation*}
A\Leftrightarrow C
\end{equation*}もまた成り立つ。

証明

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

例(論理的同値関係の推移律)
命題関数\(P\left( x\right) ,Q\left( x\right) ,R\left(x\right) \)について、\begin{eqnarray*}P\left( x\right) &\Leftrightarrow &Q\left( x\right) \\
Q\left( x\right) &\Leftrightarrow &R\left( x\right)
\end{eqnarray*}がともに成り立つ場合には、\(\Leftrightarrow \)の推移律より、\begin{equation*}P\left( x\right) \Leftrightarrow R\left( x\right)
\end{equation*}が成り立つことが保証されます。

例(論理的同値関係の推移性)
命題関数\(P\left( x\right) ,Q\left( x\right) ,R\left(x\right) \)について、\begin{eqnarray}P\left( x\right) &\Leftrightarrow &Q\left( x\right) \quad \cdots (1) \\
R\left( x\right) &\Leftrightarrow &Q\left( x\right) \quad \cdots (2)
\end{eqnarray}がともに成り立つものとします。\(\left( 2\right) \)および\(\Leftrightarrow \)の対称律より、\begin{equation*}Q\left( x\right) \Leftrightarrow R\left( x\right)
\end{equation*}を得ます。これと\(\left(1\right) \)および\(\Leftrightarrow \)の推移律より、このとき、\begin{equation*}P\left( x\right) \Leftrightarrow R\left( x\right)
\end{equation*}が成り立ちます。

論理式\(A,B,C\)が与えられたとき、\begin{equation*}A\Leftrightarrow B\Leftrightarrow C
\end{equation*}という形で\(A\)から出発して同値変形を繰り返して最終的に\(C\)へ至った場合、\(\Leftrightarrow \)の推移律より、出発点\(A\)と終着点\(C\)は論理的に同値であることが保証されます。

3個以上の論理式\(A_{1},A_{2},\cdots,A_{n}\)についても、\begin{equation*}A_{1}\Leftrightarrow A_{2}\Leftrightarrow \cdots \Leftrightarrow A_{n}
\end{equation*}という形で\(A_{1}\)から出発して同値変形を繰り返して最終的に\(A_{n}\)へ至った場合、\(\Leftrightarrow \)の推移律を繰り返し適用することにより、出発点\(A_{1}\)と終着点\(A_{n} \)は論理的に同値であることが保証されます。

2つの論理式\(A,B\)が論理的に同値であること、すなわち、\begin{equation}A\Leftrightarrow B \quad \cdots (1)
\end{equation}が成り立つことを示そうとしている状況を想定します。これを直接示すことが困難である場合、別の論理式\(C\)を仲介させて、\begin{eqnarray}A &\Leftrightarrow &C \quad \cdots (2) \\
C &\Leftrightarrow &B \quad \cdots (3)
\end{eqnarray}をともに示しても構いません。なぜなら、\(\left( 2\right) \)と\(\left( 3\right) \)がともに成り立つ場合、\(\Leftrightarrow \)の推移律より\(\left(1\right) \)が成り立つことが保証されるからです。

 

演習問題

問題(同値変形)
命題関数\(P\left( x\right) \)について、\begin{equation*}P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\vee P\left( x\right)
\end{equation*}が成り立つことを示してください。

解答を見る

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

問題(同値変形)
命題関数\(P\left( x\right) ,Q\left( x\right) \)について、\begin{equation*}\lnot \lnot P\left( x\right) \vee \lnot \lnot Q\left( x\right)
\Leftrightarrow P\left( x\right) \vee Q\left( x\right)
\end{equation*}が成り立つことを示してください。

解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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