WIIS

述語論理

述語論理における対偶律

目次

関連知識

Mailで保存
Xで共有

逆・裏・対偶

論理式\(A,B\)に対して、\begin{equation*}B\rightarrow A
\end{equation*}を含意\(A\rightarrow B\)の(converse)と呼び、\begin{equation*}\lnot A\rightarrow \lnot B
\end{equation*}を\(A\rightarrow B\)の(inverse)と呼び、\begin{equation*}\lnot B\rightarrow \lnot A
\end{equation*}を\(A\rightarrow B\)の対偶(contraposition)と呼びます。

例(逆・裏・対偶)
整数を値としてとる変数\(x\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ、\begin{eqnarray*}P\left( x\right) &:&x\text{は}4\text{の倍数である} \\
Q\left( x\right) &:&x\text{は偶数である}
\end{eqnarray*}と定義すると、\begin{equation*}
P\left( x\right) \rightarrow Q\left( x\right) :x\text{が}4\text{の倍数であるならば偶数である}
\end{equation*}となります。逆、裏、対偶はそれぞれ、\begin{eqnarray*}
Q\left( x\right) &\rightarrow &P\left( x\right) :x\text{が偶数であるならば}4\text{の倍数である} \\
\lnot P\left( x\right) &\rightarrow &\lnot Q\left( x\right) :x\text{が}4\text{の倍数でなければ偶数ではない} \\
\lnot Q\left( x\right) &\rightarrow &\lnot P\left( x\right) :x\text{が偶数でなければ}4\text{の倍数ではない}
\end{eqnarray*}などとなります。

例(逆・裏・対偶)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)および\(R\left( x\right) \)が任意に与えられたとき、以下の論理式\begin{equation*}P\left( x\right) \rightarrow \left( Q\left( x\right) \wedge R\left( x\right)
\right)
\end{equation*}の逆、裏、対偶はそれぞれ、\begin{eqnarray*}
\text{逆} &:&\left( Q\left( x\right) \wedge R\left( x\right) \right)
\rightarrow P\left( x\right) \\
\text{裏} &:&\lnot P\left( x\right) \rightarrow \lnot \left( Q\left(
x\right) \wedge R\left( x\right) \right) \\
\text{対偶} &:&\lnot \left( Q\left( x\right) \wedge R\left(
x\right) \right) \rightarrow \lnot P\left( x\right)
\end{eqnarray*}となります。ド・モルガンの法則より、\begin{equation*}
\lnot \left( Q\left( x\right) \wedge R\left( x\right) \right)
\Leftrightarrow \lnot Q\left( x\right) \vee \lnot R\left( x\right)
\end{equation*}という関係が成り立つため、裏および対偶を、\begin{eqnarray*}
\text{裏} &:&\lnot P\left( x\right) \rightarrow \lnot Q\left( x\right)
\vee \lnot R\left( x\right) \\
\text{対偶} &:&\lnot Q\left( x\right) \vee \lnot R\left(
x\right) \rightarrow \lnot P\left( x\right)
\end{eqnarray*}と表すこともできます。

 

対偶律

論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理における対偶律より、\begin{eqnarray*}&&\left( a\right) \ \overline{A}\rightarrow \overline{B}\Leftrightarrow
\lnot \overline{B}\rightarrow \lnot \overline{A} \\
&&\left( b\right) \ \overline{B}\rightarrow \overline{A}\Leftrightarrow
\lnot \overline{A}\rightarrow \lnot \overline{B}
\end{eqnarray*}がともに成り立ちます。任意の解釈において同様の議論が成立するため、\begin{eqnarray*}
&&\left( a\right) \ A\rightarrow B\Leftrightarrow \lnot B\rightarrow \lnot A
\\
&&\left( b\right) \ B\rightarrow A\Leftrightarrow \lnot A\rightarrow \lnot B
\end{eqnarray*}がともに成り立つことが示されました。つまり、述語論理においても対偶律(law of contraposition)が成り立つということです。

命題(対偶律)
任意の論理式\(A,B\)に対して、\begin{eqnarray*}&&\left( a\right) \ A\rightarrow B\Leftrightarrow \lnot B\rightarrow \lnot A
\\
&&\left( b\right) \ B\rightarrow A\Leftrightarrow \lnot A\rightarrow \lnot B
\end{eqnarray*}が成り立つ。

上の命題は、含意\(A\rightarrow B\)とその対偶が論理的に同値であること、含意\(A\rightarrow B\)の逆と裏が論理的に同値であるという主張です。

例(対偶律)
命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ任意に選んだとき、対偶律より、\begin{eqnarray*}&&\left( a\right) \ P\left( x\right) \rightarrow Q\left( x\right)
\Leftrightarrow \lnot Q\left( x\right) \rightarrow \lnot P\left( x\right) \\
&&\left( b\right) \ Q\left( x\right) \rightarrow P\left( x\right)
\Leftrightarrow \lnot P\left( x\right) \rightarrow \lnot Q\left( x\right)
\end{eqnarray*}が成り立ちます。

 

量化と対偶律

対偶律を踏まえると、全称命題や存在命題に関して以下が成り立ちます。

命題(量化と対偶律)
任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\rightarrow B\right)
\Leftrightarrow \forall x\in X:\left( \lnot B\rightarrow \lnot A\right) \\
&&\left( b\right) \ \exists x\in X:\left( A\rightarrow B\right)
\Leftrightarrow \exists x\in X:\left( \lnot B\rightarrow \lnot A\right)
\end{eqnarray*}が成り立つ。

証明

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

例(量化と対偶律)
命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ任意に選んだとき、上の命題より、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( P\left( x\right) \rightarrow
Q\left( x\right) \right) \Leftrightarrow \forall x\in X:\left( \lnot Q\left(
x\right) \rightarrow \lnot P\left( x\right) \right) \\
&&\left( b\right) \ \exists x\in X:\left( P\left( x\right) \rightarrow
Q\left( x\right) \right) \Leftrightarrow \exists x\in X:\left( \lnot Q\left(
x\right) \rightarrow \lnot P\left( x\right) \right)
\end{eqnarray*}などが成り立ちます。

例(量化と対偶律)
「任意の整数\(x\)について、\(7x+9\)が偶数ならば\(x\)は奇数である」という主張について考えます。変数\(x\)の定義域はすべての整数からなる集合\(\mathbb{Z} \)です。主張を定式化すると、\begin{equation}\forall x\in \mathbb{Z} :\left( 7x+9\text{は偶数}\rightarrow x\text{は奇数}\right) \quad \cdots (1)
\end{equation}となりますが、先の命題より、この論理式は、\begin{equation*}
\forall x\in \mathbb{Z} :\left( \lnot \left( x\text{は奇数}\right) \rightarrow
\lnot \left( 7x+9\text{は偶数}\right) \right)
\end{equation*}すなわち、\begin{equation}
\forall x\in \mathbb{Z} :\left( x\text{は偶数}\rightarrow 7x+9\text{は奇数}\right) \quad \cdots (2)
\end{equation}と論理的に同値です。偶数であるような整数\(x\in \mathbb{Z} \)を任意に選びます。偶数の定義より、何らかの整数\(a\in \mathbb{Z} \)を用いて、\begin{equation*}x=2a
\end{equation*}と表すことができます。このとき、\begin{eqnarray*}
7x+9 &=&7\left( 2a\right) +9 \\
&=&14a+9 \\
&=&2\left( 7a+4\right) +1
\end{eqnarray*}となり、これは奇数であるため\(\left( 2\right) \)が真であることが示されました。したがって、\(\left( 2\right) \)と論理的に同値である\(\left( 1\right) \)もまた真です。

 

演習問題

問題(対偶律)
「任意の整数\(x\)について、\(x^{2}-6x+5\)が偶数ならば\(x\)は奇数である」という主張を論理式として定式化した上で、その真偽を判定してください。
解答を見る

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

問題(対偶律)
「任意の実数\(x,y\)について、\(x^{3}+xy^{2}\geq y^{3}+yx^{2}\)ならば\(x\geq y\)である」という主張を論理式として定式化した上で、その真偽を判定してください。
解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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