量化記号の作用域
述語論理における論理式の定義より、議論領域\(D\)上の変数\(x\in X\)および論理式\(A\)が与えられたとき、全称命題と存在命題\begin{eqnarray*}\forall x &\in &X:A \\
\exists x &\in &X:A
\end{eqnarray*}はともに\(D\)における論理式です。これらの論理式において量化記号\(\forall ,\exists \)が作用する対象となっている論理式\(A\)を量化記号\(\forall ,\exists \)の作用域（scope）と呼びます。
例（量化記号の作用域）
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)が与えられているものとします。以下の論理式\begin{equation*}\forall x\in X:\left( \lnot P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}において、\(\forall \)の作用域は\(\left( \lnot P\left( x\right) \wedge Q\left( x\right)\right) \)です。一方、以下の論理式\begin{equation*}\left( \forall x\in X:\lnot P\left( x\right) \right) \wedge Q\left( x\right)
\end{equation*}において、\(\forall \)の作用域は\(\lnot P\left( x\right) \)です。これらの例が示唆するように、見た目が似ている論理式でも括弧の位置に依存して量化記号の作用域が変わるため、論理演算子や量化記号を作用させる順番に注意しながら、それぞれの量化記号の作用域を慎重に見極める必要があります。
\end{equation*}において、\(\forall \)の作用域は\(\left( \lnot P\left( x\right) \wedge Q\left( x\right)\right) \)です。一方、以下の論理式\begin{equation*}\left( \forall x\in X:\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 \)の作用域は\(\left( \forall y\in Y:\left(P\left( x\right) \wedge Q\left( y\right) \right) \right) \)であり、右側の\(\forall \)の作用域は\(\left( P\left( x\right) \wedge Q\left( y\right) \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 \)の作用域は\(\left( \forall y\in Y:P\left(x\right) \right) \)であり、右側の\(\forall \)の作用域は\(P\left( x\right) \)です。
y\right) \right) \right)
\end{equation*}において、左側の\(\forall \)の作用域は\(\left( \forall y\in Y:\left(P\left( x\right) \wedge Q\left( y\right) \right) \right) \)であり、右側の\(\forall \)の作用域は\(\left( P\left( x\right) \wedge Q\left( y\right) \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 \)の作用域は\(\left( \forall y\in Y:P\left(x\right) \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:\left( \lnot P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)です。\(\forall x\in X\)中の\(x\)は変数\(x\)の現れではありません。
\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\)の現れではありません。
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:\left( \lnot P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)です。\(\forall \)は変数\(x\)を束縛しており、その作用域は\(\left( \lnot P\left(x\right) \wedge Q\left( x\right) \right) \)です。したがって、\(x\)の2つの現れはともに\(\forall \)によって束縛されています。一方、論理式\begin{equation*}\left( \forall x\in X:\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\)の現れは自由です。
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)です。\(\forall \)は変数\(x\)を束縛しており、その作用域は\(\left( \lnot P\left(x\right) \wedge Q\left( x\right) \right) \)です。したがって、\(x\)の2つの現れはともに\(\forall \)によって束縛されています。一方、論理式\begin{equation*}\left( \forall x\in X:\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\)を束縛しており、その作用域は\(\left( \forall y\in Y:\left( P\left( x\right) \wedge Q\left( y\right)\right) \right) \)です。したがって、\(x\)の現れは左側の\(\forall \)によって束縛されています。また、右側の\(\forall \)は変数\(y\)を束縛しており、その作用域は\(\left( P\left( x\right) \wedge Q\left( y\right) \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\)を束縛しており、その作用域は\(\left( \forall y\in Y:P\left( x\right) \right) \)です。したがって、\(x\)の現れは左側の\(\forall \)によって束縛されています。また、右側の\(\forall \)は変数\(y\)を束縛しており、その作用域は\(P\left( x\right) \)です。したがって、\(y\)の現れは自由です。
y\right) \right) \right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)中の\(x\)であり、変数\(y\)の現れは\(Q\left(y\right) \)中の\(y\)です。左側の\(\forall \)は変数\(x\)を束縛しており、その作用域は\(\left( \forall y\in Y:\left( P\left( x\right) \wedge Q\left( y\right)\right) \right) \)です。したがって、\(x\)の現れは左側の\(\forall \)によって束縛されています。また、右側の\(\forall \)は変数\(y\)を束縛しており、その作用域は\(\left( P\left( x\right) \wedge Q\left( y\right) \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\)を束縛しており、その作用域は\(\left( \forall y\in Y:P\left( x\right) \right) \)です。したがって、\(x\)の現れは左側の\(\forall \)によって束縛されています。また、右側の\(\forall \)は変数\(y\)を束縛しており、その作用域は\(P\left( x\right) \)です。したがって、\(y\)の現れは自由です。
閉論理式
変数の自由な現れを持たない論理式を閉論理式（closed formula）と呼びます。
論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つことを、\begin{equation*}A\left( x_{1},\cdots ,x_{n}\right)
\end{equation*}で表記します。変数\(x_{1},\cdots ,x_{n}\)の自由な現れに代入する具体的な値\(\overline{x}_{1},\cdots ,\overline{x}_{n}\)を選んだ上で、それを\(A\left( x_{1},\cdots,x_{n}\right) \)に代入すれば命題\begin{equation*}A\left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right)
\end{equation*}が得られます。命題は変数の自由な現れを持たないため\(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*}が得られますが、これは閉論理式です。
\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*}が得られますが、これは閉論理式です。
\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:\left( \lnot P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)ですが、それらはともに\(\forall \)によって束縛されています。したがって、この論理式は閉論理式です。
\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 \)によってそれぞれ束縛されているため、この論理式は閉論理式です。
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}\)の自由な現れを持つことを、\begin{equation*}A\left( x_{1},\cdots ,x_{n}\right)
\end{equation*}で表記します。これは開論理式です。
開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)が与えられた状況において、変数の現れ\(x_{1},\cdots ,x_{n}\)の中から特定の変数の現れ\(x_{1},\cdots ,x_{m}\ \left( m\leq n\right) \)を任意に選びます。その上で、これらの現れ\(x_{1},\cdots ,x_{m}\)に具体的な値\(\overline{x}_{1},\cdots ,\overline{x}_{m}\)を代入すれば論理式\begin{equation*}A\left( \overline{x}_{1},\cdots ,\overline{x}_{m},x_{m+1},\cdots
,x_{n}\right)
\end{equation*}が得られますが、これは変数\(x_{m+1},\cdots ,x_{n}\)の自由な現れを持つ開論理式です。
例（開論理式）
変数\(x\in X\)に関する命題関数\begin{equation*}P\left( x\right)
\end{equation*}は変数\(x\)の自由な現れを持つ開論理式です。
\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\)の自由な現れを持つ開論理式です。
\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*}\left( \forall x\in X:\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\)の自由な現れを持つ開論理式です。
\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\)の自由な現れを持つ開論理式です。
\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*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
\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*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
\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*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
\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*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
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*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
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*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
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*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
\right) \wedge Q\left( x\right)
\end{equation*}が閉論理式と開論理式のどちらであるか、理由とともに答えてください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】