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

部分論理式

命題関数\(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\)の部分論理式である。
例(部分論理式)
命題関数\(P\left( x\right)\) から生成される論理式\(\lnot P\left( x\right) \)の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\begin{array}{cc}
\hline
論理式 & 部分論理式 \\ \hline
P\left( x\right) & P\left( x\right) \\ \hline
\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) \\
\hline
\end{array}$$
例(部分論理式)
命題関数P\(\left( x\right) ,Q\left( y\right) \)から生成される論理式\(\lnot P\left( x\right) \wedge Q\left( y\right) \)の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\begin{array}{cc}
\hline
論理式 & 部分論理式 \\ \hline
P\left( x\right) & P\left( x\right) \\ \hline
Q\left( x\right) & Q\left( x\right) \\ \hline
\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) \\ \hline
\lnot P\left( x\right) \wedge Q\left( y\right) & P\left( x\right) ,\ \lnot P\left( x\right) ,\ Q\left( x\right) ,\ \lnot P\left( x\right) \wedge Q\left( y\right) \\ \hline
\end{array}$$
例(部分論理式)
命題関数\(P\left( x\right) ,Q\left( y\right) \)から生成される論理式\(\forall x\in X\ \left( \lnot P\left( x\right) \right) \)の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\begin{array}{cc}
\hline
論理式 & 部分論理式 \\ \hline
P\left( x\right) & P\left( x\right) \\ \hline
\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) \\ \hline
\forall x\in X\ \left( \lnot P\left( x\right) \right) & P\left( x\right) ,\ \lnot P\left( x\right) ,\ \forall x\in X\ \left( \lnot P\left( x\right) \right) \\ \hline
\end{array}$$

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

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
Share on print
< 前のページ

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するためにはログインが必要です
ログイン

述語論理
アカウント
ログイン