WIIS

命題論理

命題論理における一様代入の法則

目次

関連知識

Mailで保存
Xで共有

一様代入の法則

論理式\(A_{1},\cdots ,A_{n}\)に対して論理演算を行うことにより得られる論理式を、\begin{equation}A\left( A_{1},\cdots ,A_{n}\right) \quad \cdots (1)
\end{equation}で表記します。さらに、この論理式\(\left( 1\right) \)は恒真式であるものとします。つまり、それぞれの論理式\(A_{i}\ \left( i=1,\cdots ,n\right) \)は\(0\)または\(1\)を値として取り得るため、論理式\(A_{1},\cdots ,A_{n}\)の値の組み合わせとして全部で\(2^{n}\)通りが存在しますが、いずれの場合にも論理式\(\left( 1\right) \)の値は\(1\)になるということです。

さて、論理式\(\left( 1\right) \)中の論理式\(A_{1},\cdots ,A_{n}\)を論理式\(B_{1},\cdots ,B_{n}\)にそれぞれ置き換えることにより得られる論理式を、\begin{equation}A\left( B_{1},\cdots ,B_{n}\right) \quad \cdots (2)
\end{equation}で表記します。それぞれの論理式\(B_{i}\ \left( i=1,\cdots,n\right) \)は\(0\)または\(1\)を値として取り得るため、論理式\(B_{1},\cdots ,B_{n}\)の値の組み合わせとして全部で\(2^{n}\)通りが存在しますが、仮定より\(\left( 1\right) \)は恒真式であるため、いずれの場合にも\(\left( 2\right) \)の値が\(1\)になることが保証されます。つまり、論理式\(\left( 2\right) \)もまた恒真式になることが保証されます。

つまり、恒真式\(A\left(A_{1},\cdots ,A_{n}\right) \)が与えられたとき、その中の論理式\(A_{1},\cdots ,A_{n}\)を任意の論理式\(B_{1},\cdots ,B_{n}\)に置き換えることにより得られる論理式\(A\left( B_{1},\cdots ,B_{n}\right) \)もまた恒真式になるということです。これを一様代入の法則(lawof uniform substitution)と呼びます。

例(一様代入の法則)
論理式\(A\)を任意に選んだとき、ベキ等律より、以下の恒真式\begin{equation}A\wedge A\Leftrightarrow A \quad \cdots (1)
\end{equation}が成立します。否定\(\lnot A\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A\)を\(\lnot A\)に置き換えることにより得られる論理式もまた恒真式になります。つまり、\begin{equation*}\lnot A\wedge \lnot A\Leftrightarrow \lnot A
\end{equation*}が成り立つということです。また、論理式\(B,C\)を任意に選んだとき含意\(B\rightarrow C\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A\)を\(B\rightarrow C\)に置き換えることにより得られる論理式もまた恒真式になります。つまり、\begin{equation*}\left( B\rightarrow C\right) \wedge \left( B\rightarrow C\right)
\Leftrightarrow B\rightarrow C
\end{equation*}が成り立つということです。

例(一様代入の法則)
論理式\(A,B\)を任意に選んだとき、ド・モルガンの法則より、以下の恒真式\begin{equation}\lnot \left( A\vee B\right) \Leftrightarrow \lnot A\wedge \lnot B \quad \cdots (1)
\end{equation}が成立します。否定\(\lnot A,\lnot B\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A,B\)を\(\lnot A,\lnot B\)にそれぞれ置き換えることにより得られる論理式もまた恒真式になります。つまり、\begin{equation*}\lnot \left( \lnot A\vee \lnot B\right) \Leftrightarrow \lnot \left( \lnot
A\right) \wedge \lnot \left( \lnot B\right)
\end{equation*}が成り立つということです。また、論理式\(C,D\)を任意に選んだとき論理積\(C\wedge D\)と論理和\(C\vee D\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A,B\)を\(C\wedge D,C\vee D\)にそれぞれ置き換えることにより得られる論理式もまた恒真式になります。つまり、\begin{equation*}\lnot \left( \left( C\wedge D\right) \vee \left( C\vee D\right) \right)
\Leftrightarrow \lnot \left( C\wedge D\right) \wedge \lnot \left( C\vee
D\right)
\end{equation*}が成り立つということです。

例(一様代入の法則)
論理式\(A\)を任意に選んだとき、以下の恒真式\begin{equation}A\rightarrow \lnot A\Rightarrow \lnot A \quad \cdots (1)
\end{equation}が成り立ちます(確認してください)。否定\(\lnot A\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A\)を\(\lnot A\)に置き換えることにより得られる論理式もまた恒真式になります。つまり、\begin{equation*}\lnot A\rightarrow \lnot \left( \lnot A\right) \Rightarrow \lnot \left(
\lnot A\right)
\end{equation*}が成り立つということです。また、論理式\(B,C\)を任意に選んだとき含意\(B\rightarrow C\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A\)を\(B\rightarrow C\)に置き換えることにより得られる論理式もまた恒真式になります。つまり、\begin{equation*}\left( B\rightarrow C\right) \rightarrow \lnot \left( B\rightarrow C\right)
\Rightarrow \lnot \left( B\rightarrow C\right)
\end{equation*}が成り立つということです。

 

一様代入の法則に関する注意点

恒真式\(A\left( A_{1},\cdots ,A_{n}\right) \)中の論理式を別の論理式に置き換えて新たな恒真式を生成する場合、もとの恒真式に含まれるすべての論理式\(A_{1},\cdots ,A_{n}\)を別の論理式\(B_{1},\cdots ,B_{n}\)におきかえる必要はありません。特定の論理式\(A_{1},\cdots ,A_{m}\ \left(m<n\right) \)だけを別の論理式\(B_{1},\cdots ,B_{m}\)に置き換える場合にも一様代入の法則は成立します。つまり、論理式\begin{equation*}A\left( B_{1},\cdots ,B_{m},A_{m+1},\cdots ,A_{n}\right)
\end{equation*}もまた恒真式になることが保証されるということです。

例(一様代入の法則)
論理式\(A,B,C\)を任意に選んだとき、結合律より、以下の恒真式\begin{equation}(A\vee B)\vee C\Leftrightarrow A\vee \left( B\vee C\right) \quad \cdots (1)
\end{equation}が成り立ちます。否定\(\lnot A,\lnot B\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A,B\)を\(\lnot A,\lnot B\)にそれぞれ置き換えることにより得られる論理式もまた恒真式になります。ただし、\(\left(1\right) \)中の\(C\)は入れ替えません。つまり、\begin{equation*}(\lnot A\vee \lnot B)\vee C\Leftrightarrow \lnot A\vee \left( \lnot B\vee
C\right)
\end{equation*}が成り立つということです。

恒真式\(A\left( A_{1},\cdots ,A_{n}\right) \)中の論理式\(A_{i}\)を別の論理式\(B_{i}\)に置き換えて新たな恒真式を生成する場合、\(A\left( A_{1},\cdots ,A_{n}\right) \)の中に登場するすべての\(A_{i}\)を\(B_{i}\)に置き換える必要があります。\(A\left( A_{1},\cdots ,A_{n}\right) \)において\(A_{i}\)が複数の個所において登場する場合、その中の特定の個所だけを\(B_{i}\)に置き換えたのでは、得られる論理式が恒真式になることは保証されません。恒真式\(A\left( A_{1},\cdots ,A_{n}\right) \)中の論理式\(A_{i}\)を別の論理式\(B_{i}\)に置き換える場合、一様代入の法則が成り立つことを保証するためには、\(A\left( A_{1},\cdots ,A_{n}\right) \)において登場するすべての\(A_{i}\)を\(B_{i}\)に置き換える必要があるということです。

例(一様代入の法則)
論理式\(A\)を任意に選んだとき、ベキ等律より、以下の恒真式\begin{equation}A\wedge A\Leftrightarrow A \quad \cdots (1)
\end{equation}が成立します。否定\(\lnot A\)もまた論理式であるため、一様代入の法則より、\(\left( 1\right) \)中の\(A\)を\(\lnot A\)に置き換えることにより得られる論理式もまた恒真式になります。つまり、\begin{equation*}\lnot A\wedge \lnot A\Leftrightarrow \lnot A
\end{equation*}が成り立つということです。\(\left( 1\right) \)において\(A\)は3か所に登場しますが、その中でも、最初に登場する\(A\)だけを\(\lnot A\)に置き換えるとどうなるでしょうか。この場合、\begin{equation}\lnot A\wedge A\leftrightarrow A \quad \cdots (2)
\end{equation}となりますが、これは恒真式ではありません。実際、\(A\)が\(1\)であるような解釈において\(\lnot A\wedge A\)の値は\(0\)である一方で\(A\)の値は\(1\)であり、したがって、\(\left( 2\right) \)は恒真式ではありません。

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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