教材一覧
教材一覧
教材検索

命題論理

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

目次

Twitterで共有
メールで共有

一様代入の法則

論理式\(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) \)は恒真式ではありません。
Twitterで共有
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

必要十分条件
命題論理における恒真式・恒偽式・事実式

論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 1 であるならば、その論理式を恒真式やトートロジーなどと呼びます。また、論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 0 であるならば、その論理式を恒偽式や矛盾式などと呼びます。恒真式や恒偽式ではない論理式を事実式と呼びます。

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

論理的に同値な2つの論理式が与えられたとき、それらの双対をとるとそれらもまた論理的に同値となります。これを双対原理と呼びます。

恒偽式
述語論理における恒真式・恒偽式・事実式

述語論理において論理式が恒真式であるとは、任意の解釈のもとで、そこから得られる命題が真であることを意味します。また、論理式が恒偽式であるとは、任意の解釈のもとで、そこから得られる命題が偽であることを意味します。