部分論理式
命題関数\(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) \quad \cdots (1)
\end{equation}が論理式であることを順番に確認します。まず、命題関数は論理式とみなされるため、\begin{equation}
P\left( x,y\right) ,\ Q\left( x\right) \quad \cdots (2)
\end{equation}はいずれも論理式です。\(P\left( x,y\right) \)が論理式であるならば、それに論理演算子\(\lnot \)をさせて得られる、\begin{equation}\lnot P\left( x,y\right) \quad \cdots (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) \quad \cdots (4)
\end{equation}は論理式です。したがってこれに量化記号\(\forall \)を作用させて得られる、\begin{equation*}\forall x\in X:\left( \lnot P\left( x,y\right) \wedge Q\left( x\right)
\right)
\end{equation*}は論理式ですが、これは\(\left( 1\right) \)に他なりません。以上で確認が完了しました。
論理式\(\left( 1\right) \)を生成する過程において登場した論理式\(\left( 2\right) ,\left( 3\right),\left( 4\right) \)に\(\left( 1\right) \)自身を加えたものを当初の論理式\(\left( 1\right) \)の部分論理式（subformula）と呼びます。つまり、ある論理式の部分論理式とは、その論理式を生成するために部品となるすべての論理式を指します。また、論理式自身をその論理式の部分論理式とみなします。
部分論理式を以下のように再帰的に定義します。
- 論理式\(A\)自身は\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B\)を用いて\(\left( \lnot B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式でもある。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\wedge C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\vee C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\veebar C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\rightarrow C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\leftrightarrow C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B\)と変数\(x\in X\)を用いて\(\left( \forall x\in X:B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B\)と変数\(x\in X\)を用いて\(\left( \exists x\in X:B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。
\end{equation*}の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\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}$$
\end{equation*}の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\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}$$
\end{equation*}の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\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:\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) ,\ \forall x\in X:\lnot P\left( x\right) \\ \hline
\end{array}$$
演習問題
\right)
\end{equation*}の部分論理式をすべて特定してください。
R\left( x,y\right) \right)
\end{equation*}の部分論理式をすべて特定してください。
\wedge \forall y\in Y:Q\left( y\right)
\end{equation*}の部分論理式をすべて特定してください。
次回は開論理式および閉論理式について解説します。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】