部分論理式

部分論理式

議論領域\(D\)の変数\(x,y\)に関する原子論理式\(P\left( x,y\right) ,Q\left( x\right) \)が与えられたとき、そこから生成される\begin{equation}
\left( \forall x\in X\ \left( \left( \lnot P\left( x,y\right) \right) \wedge Q\left( x\right) \right) \right) \tag{1}
\end{equation}が\(D\)の論理式であることを論理式の定義から確認しましょう。まず、\(P\left( x,y\right) \)と\(Q\left( x\right) \)はいずれも論理式です。\(P\left( x,y\right) \)が論理式ならば\(\left( \lnot P\left( x,y\right) \right) \)も論理式です。さらに、\(\left( \lnot P\left( x,y\right) \right) \)と\(Q\left( x\right) \)が論理式であるならば\(\left( \lnot P\left( x,y\right) \right) \wedge Q\left( x\right) \)も論理式です。さらにこれが論理式ならば\(\left( 1\right) \)は論理式です。

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

論理式の部分論理式を以下のように再帰的に定義します。

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