教材一覧
PREDICATE LOGIC

閉論理式・開論理式

次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

量化記号の作用域

量化記号\(\forall ,\exists \)が作用する対象である論理式をその量化記号の作用域(scope)と呼びます。つまり、論理式やその部分論理式が論理式\(A\)を用いて\(\forall x\in X:A\)や\(\exists x\in X:A\)などの形で表されているとき、\(\forall \)や\(\exists \)の作用域は\(A\)です。

例(量化記号の作用域)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:(\lnot P\left( x\right) \wedge Q\left( x\right) )
\end{equation*}において、\(\forall \)の作用域は\(\lnot P\left( x\right) \wedge Q\left( x\right) \)です。一方、論理式\begin{equation*}\forall x\in X:\left( \lnot P\left( x\right) \right) \wedge Q\left( x\right)
\end{equation*}において、\(\forall \)の作用域は\(\lnot P\left( x\right) \)です。この例が示唆するように、見た目が似ている論理式でも、括弧の位置に依存して量化記号の作用域が変わるため、演算子や量化記号を作用させる順番に注意しながら、それぞれの量化記号の作用域を見極める必要があります。
例(量化記号の作用域)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:\left( \forall y\in Y:\left( P\left( x\right) \wedge Q\left(
y\right) \right) \right)
\end{equation*}において、左側の\(\forall \)の作用域は\(\forall y\in Y:\left( P\left(x\right) \wedge Q\left( y\right) \right) \)であり、右側の\(\forall \)の作用域は\(P\left( x\right) \wedge Q\left( y\right) \)です。一方、論理式\begin{equation*}\left( \forall x\in X:\left( \forall y\in Y:P\left( x\right) \right) \right)
\wedge Q\left( y\right)
\end{equation*}において、左側の\(\forall \)の作用域は\(\forall y\in Y:P\left( x\right) \)であり、右側の\(\forall \)の作用域は\(P\left( x\right) \)です。

 

変数の現れ

論理式の中に変数を表す記号が出現するとき、それぞれの出現個所をその論理式におけるその変数の現れ(occurence)と呼びます。ただし、\(\forall x\in X\)や\(\exists x\in X\)など、量化記号\(\forall ,\exists \)の直後の\(x\)は変数\(x\)の現れとはみなされません。

例(変数の現れ)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:(\lnot P\left( x\right) \wedge Q\left( x\right) )
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)です。\(\forall x\in X\)中の\(x\)は変数\(x\)の現れではありません。
例(変数の現れ)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:\left( \forall y\in Y:\left( P\left( x\right) \wedge Q\left(
y\right) \right) \right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)の1か所であり、変数\(y\)の現れは\(Q\left(y\right) \)の1か所です。\(\forall x\in X\)中の\(x\)や、\(\forall y\in Y\)中の\(y\)はいずれも変数\(x,y\)の現れではありません。

 

自由な変数の現れ・束縛されている変数の現れ

論理式が\(\forall x\in X\)や\(\exists x\in X\)などの記述を含むとき、量化記号\(\forall ,\exists \)は変数\(x\)を束縛する(bound)と言います。論理式における変数\(x\)のそれぞれの現れに着目したとき、その現れが変数\(x\)を束縛する量化記号の作用域に属さない場合には、その現れは自由(free)であると言います。逆に、その現れが変数\(x\)を束縛する量化記号の作用域に属する場合には、その現れは束縛されている(bounded)と言います。

例(自由な変数の現れ・束縛されている変数の現れ)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:(\lnot P\left( x\right) \wedge Q\left( x\right) )
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)です。\(\forall \)は変数\(x\)を束縛しており、その作用域は\(\lnot P\left( x\right)\wedge Q\left( x\right) \)です。したがって、\(x\)の2つの現れはともに\(\forall \)によって束縛されています。一方、論理式\begin{equation*}\forall x\in X:\left( \lnot P\left( x\right) \right) \wedge Q\left( x\right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)です。\(\forall \)は変数\(x\)を束縛しており、その作用域は\(\lnot P\left( x\right) \)です。したがって、\(P\left( x\right) \)中の\(x\)の現れは\(\forall \)によって束縛されている一方で、\(Q\left( x\right) \)中の\(x\)の現れは自由です。
例(自由な変数の現れ・束縛されている変数の現れ)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:\left( \forall y\in Y:\left( P\left( x\right) \wedge Q\left(
y\right) \right) \right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)中の\(x\)であり、変数\(y\)の現れは\(Q\left(y\right) \)中の\(y\)です。左側の\(\forall \)は変数\(x\)を束縛しており、その作用域は\(\forall y\in Y:\left( P\left( x\right) \wedge Q\left( y\right) \right) \)です。したがって、\(x\)の現れは左側の\(\forall \)によって束縛されています。また、右側の\(\forall \)は変数\(y\)を束縛しており、その作用域は\(P\left( x\right) \wedge Q\left( y\right) \)です。したがって、\(y\)の現れは右側の\(\forall \)によって束縛されています。一方、論理式\begin{equation*}\left( \forall x\in X:\left( \forall y\in Y:P\left( x\right) \right) \right)
\wedge Q\left( y\right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)中の\(x\)であり、変数\(y\)の現れは\(Q\left(y\right) \)中の\(y\)です。左側の\(\forall \)は変数\(x\)を束縛しており、その作用域は\(\forall y\in Y:P\left( x\right) \)です。したがって、\(x\)の現れは左側の\(\forall \)によって束縛されています。また、右側の\(\forall \)は変数\(y\)を束縛しており、その作用域は\(P\left( x\right) \)です。したがって、\(y\)の現れは自由です。

 

閉論理式

変数の自由な現れを持たない論理式を閉論理式(closed formula)と呼びます。

論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つことを\(A\left( x_{1},\cdots ,x_{n}\right) \)で表記します。変数\(x_{1},\cdots ,x_{n}\)の自由な現れに代入する具体的な値\(\overline{x}_{1},\cdots ,\overline{x}_{n}\)をそれぞれ任意に選んだ上で、それを\(A\left( x_{1},\cdots ,x_{n}\right) \)に代入して得られる論理式を\(A\left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right) \)で表記します。この\(A\left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right) \)は閉論理式です。

例(閉論理式)
変数\(x\in X\)に関する命題関数\begin{equation*}P\left( x\right)
\end{equation*}は変数\(x\)の自由な現れを持ちます。値\(\overline{x}\in X\)を任意に選んだ上で代入すると、\begin{equation*}P\left( \overline{x}\right)
\end{equation*}という命題が得られますが、これは閉論理式です。
例(閉論理式)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)を被演算子として持つ論理式\begin{equation*}\lnot P\left( x\right) \wedge Q\left( y\right)
\end{equation*}は変数\(x,y\)の自由な現れを持ちます。値\(\overline{x}\in X,\overline{y}\in Y\)をそれぞれ任意に選んだ上で代入すると、\begin{equation*}\lnot P\left( \overline{x}\right) \wedge Q\left( \overline{y}\right)
\end{equation*}という命題が得られますが、これは閉論理式です。

論理式に含まれるすべての変数に関して、そのすべての現れが何らかの量化記号によって束縛されているならば、その論理式は閉論理式です。

例(閉論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:(\lnot P\left( x\right) \wedge Q\left( x\right) )
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)ですが、それらはともに\(\forall \)によって束縛されています。したがって、この論理式は閉論理式です。
例(閉論理式)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:\left( \forall y\in Y:\left( P\left( x\right) \wedge Q\left(
y\right) \right) \right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)中の\(x\)であり、変数\(y\)の現れは\(Q\left(y\right) \)中の\(y\)です。\(x\)の現れは左側の\(\forall \)によって、\(y\)の現れは右側の\(\forall \)によってそれぞれ束縛されているため、この論理式は閉論理式です。

 

開論理式

閉論理式ではない論理式を開論理式(open formula)と呼びます。つまり、開論理式とは少なくとも1つの変数について、その自由な現れが存在するような論理式です。

繰り返しになりますが、論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つことを\(A\left( x_{1},\cdots ,x_{n}\right) \)で表記します。この\(A\left( x_{1},\cdots ,x_{n}\right) \)は開論理式です。また、一部の変数\(x_{1},\cdots ,x_{m}\ (m<n)\)の現れに代入する具体的な値\(\overline{x}_{1},\cdots ,\overline{x}_{m}\)をそれぞれ任意に選んだ上で、それを\(A\left( x_{1},\cdots ,x_{n}\right) \)に代入して得られる論理式を\(A\left( \overline{x}_{1},\cdots ,\overline{x}_{m},x_{m+1},\cdots ,x_{n}\right) \)で表します。これは変数\(x_{m+1},\cdots ,x_{n}\)の自由な現れを持つ開論理式です。

例(開論理式)
変数\(x\in X\)に関する命題関数\begin{equation*}P\left( x\right)
\end{equation*}は変数\(x\)の自由な現れを持つ開論理式です。
例(開論理式)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)を被演算子とする論理式\begin{equation*}\lnot P\left( x\right) \wedge Q\left( y\right)
\end{equation*}は変数\(x,y\)の自由な現れを持つ開論理式です。また、値\(\overline{x}\in X\)を任意に選んだ上で代入すると、\begin{equation*}\lnot P\left( \overline{x}\right) \wedge Q\left( y\right)
\end{equation*}という論理式が得られますが、これは変数\(y\)の自由な現れを持つ開論理式です。

量化記号を含む論理式が少なくとも1つの変数について、量化記号によって束縛されない現れを持つ場合には、つまりその現れが自由であるならば、その論理式は開論理式です。

例(開論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を被演算子とする論理式\begin{equation*}\forall x\in X:\left( \lnot P\left( x\right) \right) \wedge Q\left( x\right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)です。\(P\left( x\right) \)における\(x\)の現れは\(\forall \)によって束縛されている一方で、\(Q\left( x\right) \)における\(x\)の現れは自由です。したがって、この論理式は変数\(x\)の自由な現れを持つ開論理式です。
例(開論理式)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)を被演算子とする論理式\begin{equation*}\left( \forall x\in X:\left( \forall y\in Y:P\left( x\right) \right) \right)
\wedge Q\left( y\right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)中の\(x\)であり、変数\(y\)の現れは\(Q\left(y\right) \)中の\(y\)です。\(x\)の現れは左側の\(\forall \)によって束縛されていますが、\(y\)の現れは自由です。したがって、この論理式は変数\(y\)の自由な現れを持つ開論理式です。

 

演習問題

問題(開論理式・閉論理式)
変数\(x\in X,y\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x,y\right) \)と値\(\overline{y}\in Y\)が与えられたとき、以下の論理式\begin{equation*}P\left( x\right) \wedge \lnot Q\left( x,\overline{y}\right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
解答を見る

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

問題(開論理式・閉論理式)
変数\(x\in X,y\in X\)に関する命題関数\(P\left( x,y\right) \)が与えられたとき、以下の論理式\begin{equation*}\exists x\in X:P\left( x,y\right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
解答を見る

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

問題(開論理式・閉論理式)
変数\(x\in X,y\in X\)に関する命題関数\(P\left( x,y\right) \)と値\(\overline{x}\in X\)が与えられたとき、以下の論理式\begin{equation*}\forall y\in Y:P\left( \overline{x},y\right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
解答を見る

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

問題(開論理式・閉論理式)
変数\(x\in X,y\in X\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) \)が与えられたとき、以下の論理式\begin{equation*}\forall x\in X:\left( \exists y\in Y:\left( P\left( x\right) \wedge Q\left(
y\right) \right) \right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
解答を見る

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

問題(開論理式・閉論理式)
変数\(x\in X,y\in X\)に関する命題関数\(P\left( x\right) ,Q\left( y\right) ,R\left(x,y\right) \)が与えられたとき、以下の論理式\begin{equation*}\forall y\in Y:\left( \left( \exists x\in X:\left( P\left( x\right) \wedge
Q\left( y\right) \right) \right) \rightarrow R\left( x,y\right) \right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
解答を見る

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

問題(開論理式・閉論理式)
変数\(x\in X,y\in X\)に関する命題関数\(P\left( x,y\right) ,Q\left( x\right) \)が与えられたとき、以下の論理式\begin{equation*}\exists y\in Y:\left( \forall x\in X:\left( \lnot P\left( x,y\right) \wedge
Q\left( x\right) \right) \right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
解答を見る

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

問題(開論理式・閉論理式)
変数\(x\in X,y\in X\)に関する命題関数\(P\left( x,y\right) ,Q\left( x\right) \)が与えられたとき、以下の論理式\begin{equation*}\exists y\in Y:\left( \forall x\in X:\left( \lnot P\left( x,y\right) \right)
\right) \wedge Q\left( x\right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
解答を見る

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

次回から論理式の解釈について学びます。

次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

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

述語論理