教材一覧
教材検索
PREDICATE LOGIC

論理演算の同値表現

目次

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

含意の言い換え

論理式\(A,B\)に関する\(\lnot A\vee B\)は否定\(\lnot \)と論理和\(\vee \)から生成される論理式ですが、これは\(A\rightarrow B\)と同値です。

命題(含意の言い換え)

任意の論理式\(A,B\)に対して以下が成り立つ。\begin{equation*}
A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}

証明を見る(プレミアム会員限定)

上の命題より、含意\(\rightarrow \)は否定\(\lnot \)と論理和\(\vee \)から間接的に定義できるため、否定と論理和さえ定義されていれば含意を新たな論理演算として定義する必要はありません。とは言え、含意を独立した論理演算として定義しておくと何かと便利ですので、本稿ではこのまま\(\rightarrow \)を採用します。

 

同等の言い換え

論理式\(A,B\)に関する\(\left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) \)は含意\(\rightarrow \)と論理積\(\wedge \)から生成される論理式ですが、これは\(A\leftrightarrow B\)と同値です。

命題(同等の言い換え)

任意の論理式\(A,B\)に対して以下が成り立つ。\begin{equation*}
A\leftrightarrow B\ \Leftrightarrow \ \left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right)
\end{equation*}

証明を見る(プレミアム会員限定)

上の命題より、同等\(\leftrightarrow \)は含意\(\rightarrow \)と論理積\(\wedge \)から間接的に定義できるため、含意と論理積さえ定義されていれば同等を新たな論理演算として定義する必要はありません。さらに、先に示したように、含意\(\rightarrow \)は否定\(\lnot \)と論理和\(\vee \)から間接的に定義可能ですから、結局、否定、論理積、そして論理和さえ定義されていれば同等を新たな論理演算として定義する必要はありません。とは言え、同等を独立した論理演算として定義しておくと何かと便利ですので、本稿ではこのまま\(\leftrightarrow \)を採用します。

 

排他的論理和の言い換え

排他的論理和に関して以下の命題が成り立ちます。

命題(排他的論理和の言い換え)
任意の論理式\(A,B\)に対して以下が成り立つ。\begin{eqnarray*}
A\veebar B &\Leftrightarrow &\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \\
&\Leftrightarrow &\left( A\vee B\right) \wedge \left( \lnot A\vee \lnot B\right) \\
&\Leftrightarrow &\left( A\vee B\right) \wedge \lnot \left( A\wedge B\right)
\end{eqnarray*}
証明を見る(プレミアム会員限定)

命題中の 2 つ目以降の論理式は否定\(\lnot \)、論理積\(\wedge \)、そして論理和\(\vee \)から生成される論理式ですが、これが\(A\veebar B\)と同値であるということは、排他的論理和\(\veebar \)は否定\(\lnot \)と論理積\(\wedge \)と論理和\(\vee \)から間接的に可能であることを意味します。したがって、否定、論理積、そして論理和さえ定義されていれば、排他的論理和を新たな論理演算として定義する必要はありません。とは言え、排他的論理和を独立した論理演算として定義しておくと何かと便利ですので、本稿ではこのまま\(\veebar \)を採用します。

次回は移出律と移入律について学びます。

次へ進む 演習問題(プレミアム会員限定)
< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

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

述語論理