スコーレム標準形

スコーレム標準形（スコーレムひょうじゅんけい、英: Skolem normal form）とは、数理論理学において一階述語論理における存在記号がすべて全称記号の前にある冠頭標準形の論理式を言う。

トアルフ・スコーレムによるスコーレムの定理により、第一階述語論理における任意の論理式に対して、演繹的に等価（deductive equivalence）^[1]なスコーレム標準形の論理式が存在する^[2]。

定義

冠頭標準形（prenex normal form）

→詳細は「冠頭標準形」を参照

第一階述語論理における任意の論理式は、論理式の一番前にすべて否定形でない前置記号を持ち、その作用域がどれも論理式の終わりまで及ぶような標準形に直すことができる。

このような標準形を冠頭標準形（prenex normal form）と呼ぶ^[3]。なお、冠頭標準形の一番前から数えて存在記号の前にある全称記号の数を、その冠頭標準形の次数（degree）と呼ぶ。

スコーレム標準形（Skolem normal form）

スコーレム化は、存在量化された変項 ${\displaystyle y}$ を新規の項 ${\displaystyle f(x_{1},\ldots ,x_{n})}$（シンボル ${\displaystyle f}$ は元の論理式には出現していない）に全て置き換えることでなされる。この項の各変項は、次のようなものである。もしその論理式が冠頭標準形なら、${\displaystyle x_{1},\ldots ,x_{n}}$ の各変項は全称量化されていて、その量化子は ${\displaystyle y}$ の量化子より前に置かれている。一般に、論理式には全称量化が行われていて、${\displaystyle \exists y}$ はその量化子のスコープ内にあると考えられる。ここで導入される関数 ${\displaystyle f}$ をスコーレム関数（Skolem function、アリティがゼロならスコーレム定項）と呼び、項全体をスコーレム項（Skolem term）と呼ぶ。

例として、論理式 ${\displaystyle \forall x\exists y\forall z.P(x,y,z)}$ を考える。これには存在量化子 ${\displaystyle \exists y}$ があるので、スコーレム標準形ではない。スコーレム化では ${\displaystyle y}$ を ${\displaystyle f(x)}$ で置き換える。このとき、${\displaystyle f}$ は新たな関数シンボルであり、置換と同時に ${\displaystyle y}$ の量化子を除去する。結果として得られる論理式は ${\displaystyle \forall x\forall z.P(x,f(x),z)}$ となる。スコーレム項 ${\displaystyle f(x)}$ は ${\displaystyle x}$ は含むが ${\displaystyle z}$ は含まない。これは除去された量化子 ${\displaystyle \exists y}$ が ${\displaystyle \forall x}$ のスコープには入っているが、${\displaystyle \forall z}$ のスコープには入っていないためである。この論理式は冠頭標準形なので、量化子のリストにおいて ${\displaystyle x}$ は ${\displaystyle y}$ の前にあるが ${\displaystyle z}$ はそうではない、と言うこともできる。この変換で得られた論理式は、元の論理式が充足される場合のみ充足される。

スコーレム化

スコーレム化は、一階述語論理での充足可能性の定義に二階述語論理の等価性を適用するものである。その等価性によれば、存在量化子は全称量化子の前に移動できる。

${\displaystyle \forall x{\Big (}g(x)\vee \exists yR(x,y){\Big )}\iff \forall x{\Big (}g(x)\vee R(x,f(x)){\Big )}}$

ここで

${\displaystyle f(x)}$ は y を x でマッピングする関数である。

直観的に、「全ての x について、ある y が存在し、R(x,y) が成り立つ」とは、「ある関数 f が全ての x を y にマッピングし、全ての x について R(x,f(x)) が成り立つ」と書き換えても等価である。

一階述語論理の充足可能性は、関数シンボルの評価に対して暗黙のうちに存在量化を施すような定義になっているため、この等価性が役立つ。ここで、一階述語論理式 ${\displaystyle \Phi }$ は、モデル ${\displaystyle M}$ が存在し、その論理式を「真」であると評価させるような自由変項の評価の組合せ ${\displaystyle \mu }$ があるとき、充足可能である。このモデルには、全関数シンボルの評価も含まれるので、スコーレム関数も暗黙のうちに存在量化される。上記の例 ${\displaystyle \forall x.R(x,f(x))}$ は、${\displaystyle \forall x.R(x,f(x))}$ が真となるような自由変項（この例では自由変項はない）の評価と ${\displaystyle f}$ の評価を含むモデル ${\displaystyle M}$ が存在するときのみ充足可能であると言える。これを二階述語論理で表すと ${\displaystyle \exists f\forall x.R(x,f(x))}$ となる。上記の等価性により、これは ${\displaystyle \forall x\exists y.R(x,y)}$ の充足可能性と同じである。

メタレベルとしては、論理式 ${\displaystyle \Phi }$ の一階述語論理としての充足可能性は ${\displaystyle \exists M\exists \mu ~.~(M,\mu \models \Phi )}$ と表され、ここで ${\displaystyle M}$ がモデル、${\displaystyle \mu }$ が自由変項群の評価である。一階述語モデルは全関数シンボルの評価を含むので、任意のスコーレム関数 ${\displaystyle \Phi }$ は ${\displaystyle \exists M}$ によって暗黙のうちに存在量化される。結果として、ある変項への存在量化子を論理式の最初での関数群への存在量化子に置換し、それら存在量化子を除去することで、論理式を一階述語論理式のまま扱うことができる。この最後の段階での ${\displaystyle \exists f\forall x.R(x,f(x))}$ を ${\displaystyle \forall x.R(x,f(x))}$ として扱うことは、関数が ${\displaystyle \exists M}$ によって暗黙に存在量化されるという一階述語の充足可能性の定義によるものである。

スコーレム化の正しさを示す例として、論理式 ${\displaystyle F_{1}=\forall x_{1}\dots \forall x_{n}\exists yR(x_{1},\dots ,x_{n},y)}$ を考える。この論理式がモデル ${\displaystyle M}$ で充足されるのは、そのモデルのドメインにおいて ${\displaystyle x_{1},\dots ,x_{n}}$ がとりうる全ての値について、同じモデルのドメインにおいて ${\displaystyle y}$ の値が存在し、それらの値を適用して評価したとき ${\displaystyle R(x_{1},\dots ,x_{n},y)}$ が真になる場合のみである。選択公理により、${\displaystyle y=f(x_{1},\dots ,x_{n})}$ となる関数 ${\displaystyle f}$ が存在する。結果として、${\displaystyle M}$ に ${\displaystyle f}$ の評価を加えたモデルを使えば、論理式 ${\displaystyle F_{2}=\forall x_{1}\dots \forall x_{n}R(x_{1},\dots ,x_{n},f(x_{1},\dots ,x_{n}))}$ は充足可能である。従って ${\displaystyle F_{2}}$ が充足可能であるときのみ ${\displaystyle F_{1}}$ も充足可能であると言える。これとは別に、${\displaystyle F_{2}}$ が充足可能であるなら、それを充足させるモデル ${\displaystyle M'}$ が存在し、関数 ${\displaystyle f}$ の評価が含まれ、全ての ${\displaystyle x_{1},\dots ,x_{n}}$ の値の組合せについて論理式 ${\displaystyle R(x_{1},\dots ,x_{n},f(x_{1},\dots ,x_{n}))}$ が成り立つ。結果として、${\displaystyle M'}$ における ${\displaystyle f}$ の評価を使って、全ての ${\displaystyle x_{1},\ldots ,x_{n}}$ の値の組合せについて ${\displaystyle y=f(x_{1},\dots ,x_{n})}$ となるような値を選択できるため、${\displaystyle F_{1}}$ も同じモデルで充足可能となる。