部分論理式

部分論理式

命題関数\(P\left( x,y\right) ,Q\left( x\right) \)から生成される、\begin{equation}
\forall x\in X\ \left( \lnot P\left( x,y\right) \wedge Q\left( x\right)
\right) \tag{1}
\end{equation}が論理式であることを順番に確認します。まず、命題関数は論理式とみなされるため、\begin{equation}
P\left( x,y\right) ,\ Q\left( x\right) \tag{2}
\end{equation}はいずれも論理式です。\(P\left( x,y\right) \)が論理式であるならば、それに論理演算子\(\lnot \)をさせて得られる、\begin{equation}
\lnot P\left( x,y\right) \tag{3}
\end{equation}は論理式です。\(Q\left( x\right) \)と\(\lnot P\left( x,y\right) \)が論理式であるならば、それらに論理演算子\(\wedge \)を作用させて得られる、\begin{equation}
\lnot P\left( x,y\right) \wedge Q\left( x\right) \tag{4}
\end{equation}は論理式です。\(\left( 4\right) \)が論理式であるならば、それに量化記号\(\forall \)を作用させて得られる\(\left( 1\right) \)は論理式です。

論理式\(\left( 1\right)\) を生成する過程において登場した\(\left( 2\right) ,\left( 3\right) ,\left( 4\right) \)の論理式に\(\left( 1\right)\) 自身を加えたものを\(\left( 1\right)\) の部分論理式（subformula）と呼びます。つまり、ある論理式の部分論理式とは、その論理式を生成するために部品となるすべての論理式を指します。また、論理式自身をその論理式の部分論理式とみなします。

論理式Aが与えられたとき、その部分論理式を以下のように再帰的に定義します。

1. 論理式\(A\)自身は\(A\)の部分論理式である。
2. 論理式\(A\)が論理式\(B\)を用いて\(\left( \lnot B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式でもある。
3. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\wedge C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
4. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\vee C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
5. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\veebar C\right)\)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
6. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\rightarrow C\right)\)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
7. 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\leftrightarrow C\right)\)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
8. 論理式\(A\)が論理式\(B\)と変数\(x\in X\)を用いて\( \left( \forall x\in X\ B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。
9. 論理式\(A\)が論理式\(B\)と変数\(x\in X\)を用いて\( \left( \exists x\in X\ B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。

次回は閉論理式と開論理式について学びます。