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

一様代入の法則

論理式\(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\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\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}\)に置き換える必要があるということです。