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

同値変形の根拠

論理式\(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
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

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

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

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

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

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

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