閉論理式・開論理式

述語論理において論理式は閉論理式と開論理式とに分類されます。変数の自由な現れを持たない論理式が閉論理式であり、変数の自由な現れを持つ論理式が開論理式です。
< 前のページ
次のページ >

量化記号の作用域

量化記号\(\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\)に関する命題関数\(P\left( x\right) \)は変数\(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\)に関する命題関数\(P\left( x\right) \)は変数\(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\)の自由な現れを持つ開論理式です。

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

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

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

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