論理式を生成するために部品となるすべての論理式をもとの論理式の部分論理式と呼びます。

部分論理式

議論領域\(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)と呼びます。つまり、ある論理式の部分論理式とは、その論理式を生成するために部品となるすべての論理式を指します。ただし、論理式自身をその論理式の部分論理式とみなします。

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

定義(部分論理式)
  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_{i}\in D_{i}\)を用いて\(\left( \forall x_{i}\in D_{i}\ B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。
  9. 論理式\(A\)が論理式\(B\)と変数\(x_{i}\in D_{i}\)を用いて\(\left( \exists x_{i}\in D_{i}\ B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。
例(部分論理式)
議論領域\(D\)の変数\(x,y\)に関する論理式\(\left( \lnot P\left( x,y\right) \right) \)の部分論理式を特定します。まず、\(P\left( x,y\right) \)自身は\(P\left( x,y\right) \)の部分論理式です。\(P\left( x,y\right) \)の部分論理式\(P\left( x,y\right) \)は\(\left( \lnot P\left( x,y\right) \right) \)の部分論理式です。また、\(\left( \lnot P\left( x,y\right) \right) \)自身は\(\left( \lnot P\left( x,y\right) \right) \)の部分論理式です。したがって、\(\left( \lnot P\left( x,y\right) \right) \)の部分論理式は\(P\left( x,y\right) \)と\(\left( \lnot P\left( x,y\right) \right) \)です。
例(部分論理式)
議論領域\(D\)の変数\(x,y\)に関する論理式\begin{equation}
\left( \left( \lnot P\left( x,y\right) \right) \wedge Q\left( x\right) \right) \tag{1}
\end{equation}の部分論理式を特定します。まず、先に確認したように、\(\left( \lnot P\left( x,y\right) \right) \)の部分論理式は\(P\left( x,y\right) \)と\(\left( \lnot P\left( x,y\right) \right) \)です。また、\(Q\left( x\right) \)自身は\(Q\left( x\right) \)の部分論理式です。さらに、\(\left( \lnot P\left( x,y\right) \right) \)の部分論理式\(P\left( x,y\right) ,\left( \lnot P\left( x,y\right) \right) \)と\(Q\left( x\right) \)の部分論理式\(Q\left( x\right) \)はいずれも\(\left( 1\right) \)の部分論理式です。また、\(\left( 1\right) \)自身は\(\left( 1\right) \)の部分論理式です。
例(部分論理式)
議論領域\(D\)の変数\(x,y\)に関する論理式\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}の部分論理式を特定します。まず、先に確認したように、\(\left( \left( \lnot P\left( x,y\right) \right) \wedge Q\left( x\right) \right) \)の部分論理式は\(P\left( x,y\right) ,\ \left( \lnot P\left( x,y\right) \right) ,\ Q\left( x\right) ,\ \left( \left( \lnot P\left( x,y\right) \right) \wedge Q\left( x\right) \right) \)ですから、これらは\(\left( 1\right) \)の部分論理式です。また、\(\left( 1\right) \)自身も\(\left( 1\right) \)の部分論理式です。

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

次へ進む 演習問題(プレミアム会員限定)