変数を持たない論理式を閉論理式と呼び、変数を持つ論理式を開論理式と呼びます。

2018年11月29日:公開

量化記号の作用域

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

例(量化記号の作用域)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x,y\right) ,Q\left( x\right) \)を部分論理式として持つ論理式\begin{equation*}
\forall x\in X\ (\lnot P\left( x,y\right) \wedge Q\left( x\right) )
\end{equation*}を生成するためには、\(P\left( x,y\right) \)と\(Q\left( x\right) \)を出発点として、\begin{eqnarray*}
&&\left( 1\right) \ P\left( x,y\right) \text{から}\lnot P\left( x,y\right) \text{を得る。} \\
&&\left( 2\right) \ \lnot P\left( x,y\right) \text{と}Q\left( x\right) \text{から}\lnot P\left( x,y\right) \wedge Q\left( x\right) \text{を得る。} \\
&&\left( 3\right) \ \lnot P\left( x,y\right) \wedge Q\left( x\right) \text{から}\forall x\in X\ \left( \lnot P\left( x,y\right) \wedge Q\left( x\right) \right) \text{を得る。}
\end{eqnarray*}という手続きを踏みます。\(\forall \)は\(\left( 3\right) \)において登場するため、\(\forall \)の作用域は\(\lnot P\left( x,y\right) \wedge Q\left( x\right) \)です。
例(量化記号の作用域)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x,y\right) ,Q\left( x\right) \)を部分論理式として持つ論理式\begin{equation*}
\forall x\in X\ \left( \lnot P\left( x,y\right) \right) \wedge Q\left( x\right)
\end{equation*}を生成するためには、\(P\left( x,y\right) \)と\(Q\left( x\right) \)を出発点として、\begin{eqnarray*}
&&\left( 1\right) \ P\left( x,y\right) \text{から}\lnot P\left( x,y\right) \text{を得る。} \\
&&\left( 2\right) \ \lnot P\left( x,y\right) \text{から}\forall x\in X\ \left( \lnot P\left( x,y\right) \right) \text{を得る。} \\
&&\left( 3\right) \ \forall x\in X\ \left( \lnot P\left( x,y\right) \right) \text{と}Q\left( x\right) \text{から}\forall x\in X \
\left( \lnot P\left( x,y\right) \right) \wedge Q\left( x\right) \text{を得る。}
\end{eqnarray*}という手続きを踏みます。\(\forall \)は\(\left( 2\right) \)において登場するため、\(\forall \)の作用域は\(\lnot P\left( x,y\right) \)です。

以上の 2 つの例からわかるように、見た目が似た論理式でも括弧の位置によって量化記号の作用域が変わってくるため、演算子や量化記号を作用させる順番に注意しながら量化記号の作用域をしっかり見極める必要があります。

 

変数の現れ

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

例(変数の表れ)
変数\(x\in X,y\in Y\)に関する命題関数\(P\left( x,y\right) ,Q\left( x\right) \)を部分論理式として持つ論理式\begin{equation*}
\forall x\in X\ (\lnot P\left( x,y\right) \wedge Q\left( x\right) )
\end{equation*}における変数\(x\)の現れは\(P\left( x,y\right) \)と\(Q\left( x\right) \)の中の 2 か所の\(x\)であり、変数\(y\)の表れは\(P\left( x,y\right) \)の中の 1 か所の\(y\)です。\(\forall x\in X\)の中の\(x\)は変数\(x \)の表れではありません。

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

例(自由な現れ・束縛された現れ)
変数\(x\in X,y\in Y\)に関する命題関数\(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\)の現れは\(P\left( x,y\right) \)と\(Q\left( x\right) \)の中の 2 か所です。\(\forall x\in X\)において\(\forall \)は\(x\)を束縛しており、その作用域は\(\lnot P\left( x,y\right) \wedge Q\left( x\right) \)です。したがって、\(x\)の 2 つの現れはともに\(\forall \)によって束縛されています。また、この論理式における変数\(y\)の現れは\(P\left( x,y\right) \)の中の 1 か所です。\(\exists y\in Y\)において\(\exists \)は\(y\)を束縛しており、その作用域は\(\forall x\in X\ \left( \lnot P\left( x,y\right) \wedge Q\left( x\right) \right) \)です。したがって、\(y\)の現れは\(\exists \)によって束縛されています。
例(自由な現れ・束縛された現れ)
変数\(x\in X,y\in Y\)に関する命題関数\(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*}における変数\(x\)の現れは\(P\left( x,y\right) \)と\(Q\left( x\right) \)の中の 2 か所です。\(\forall x\in X\)において\(\forall \)は\(x\)を束縛しており、その作用域は\(\lnot P\left( x,y\right) \)です。したがって、\(P\left( x,y\right) \)の中の\(x\)の現れは\(\forall \)によって束縛されていますが、\(Q\left( x\right) \)の中の\(x\)の現れは自由です。また、この論理式における変数\(y\)の現れは\(P\left( x,y\right) \)の中の 1 か所です。\(\exists y\in Y\)において\(\exists \)は\(y\)を束縛しており、その作用域は\(\forall x\in X\ \left( \lnot P\left( x,y\right) \right) \)です。したがって、\(P\left( x,y\right) \)の中の\(y\)の現れは\(\exists \)によって束縛されています。

 

閉論理式

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

論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)のすべての変数に特定の値の組\(\left( \bar{x}_{1},\cdots ,\bar{x}_{n}\right) \)を代入して得られる\(A\left( \bar{x}_{1},\cdots ,\bar{x}_{n}\right) \)は閉論理式です。

命題定数\(T,F\)は明らかに閉論理式です。

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

例(閉論理式)
変数\(x\in X,y\in Y\)に関する命題関数\(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\)の現れは\(P\left( x,y\right) \)と\(Q\left( x\right) \)の中の 2 か所であり、変数\(y \)の現れは\(P\left( x,y\right) \)の 1 か所です。先に示したように、これらの変数の現れはいずれも量化記号によって束縛されているため、この論理式は閉論理式です。

 

開論理式

閉論理式ではない論理式を開論理式(open formula)と呼びます。つまり、開論理式とは変数を持つ論理式です。

論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)や、その一部の変数\(x_{1},\cdots ,x_{m}\ (m<n)\)に特定の値\(\bar{x}_{1},\cdots ,\bar{x}_{m}\)を代入して得られる\(A\left( \bar{x}_{1},\cdots ,\bar{x}_{m},x_{m+1},\cdots ,x_{n}\right) \)は開論理式です。

論理式に含まれる少なくとも 1 つの変数に対して、その少なくとも 1 つの現れが自由であれば、その論理式は開論理式になります。以下に例を示します。

例(開論理式)
変数\(x\in X,y\in Y\)に関する命題関数\(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*}における変数\(x\)の現れは\(P\left( x,y\right) \)と\(Q\left( x\right) \)の中の 2 か所であり、変数\(y \)の現れは\(P\left( x,y\right) \)の 1 か所です。先に示したように、\(P\left( x,y\right) \)における\(x\)や\(y\)の現れは量化記号によって束縛されている一方で、\(Q\left( x\right) \)における\(x\)の現れは自由です。したがって、この論理式は開論理式です。

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

次へ進む 演習問題(プレミアム会員限定)