教材一覧
教材一覧
教材検索
PREDICATE LOGIC

述語論理における部分論理式

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

部分論理式

命題関数\(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\)の部分論理式を以下のように定義する。

  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) \)から生成される論理式\begin{equation*}\lnot P\left( x\right)
\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}$$

例(部分論理式)
命題関数\(P\left( x\right) ,Q\left( y\right) \)から生成される論理式\begin{equation*}\lnot P\left( x\right) \wedge Q\left( y\right)
\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}$$

例(部分論理式)
命題関数\(P\left( x\right) ,Q\left( y\right) \)から生成される論理式\begin{equation*}\forall x\in X:\lnot P\left( x\right)
\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}$$

 

演習問題

問題(部分論理式)
命題関数\(P\left( x\right) ,Q\left( x,y\right) \)に関する以下の論理式\begin{equation*}P\left( x\right) \leftrightarrow \lnot \left( \lnot Q\left( x,y\right)
\right)
\end{equation*}の部分論理式をすべて特定してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(部分論理式)
命題関数\(P\left( x\right) ,Q\left( y\right) ,R\left(x,y\right) \)に関する以下の論理式\begin{equation*}\lnot P\left( x\right) \rightarrow \left( Q\left( y\right) \vee \lnot
R\left( x,y\right) \right)
\end{equation*}の部分論理式をすべて特定してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(部分論理式)
命題関数\(Q\left( y\right) ,R\left( x,y\right) \)に関する以下の論理式\begin{equation*}\exists x\in X:\left( Q\left( y\right) \vee \lnot R\left( x,y\right) \right)
\wedge \forall y\in Y:Q\left( y\right)
\end{equation*}の部分論理式をすべて特定してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回は開論理式および閉論理式について解説します。

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

RELATED KNOWLEDGE

関連知識

述語論理