限定（論理）

サーカムスクリプションは、ジョン・マッカーシーが考案した非単調論理で、特に指定がない限り物事は予想通りであるという常識的な仮定を形式化したものである。 ^{[1] [2]サーカムスクリプションは後にマッカーシーによって}フレーム問題の解決に使用された。サーカムスクリプションを最初の定式化で実装するために、マッカーシーは一階述語論理を拡張して、述語の拡張 が最小化できるようにした。述語の拡張とは、述語が真となる値の組の集合である。この最小化は、真であると知られていないものは偽であるという閉世界仮定に似ている。 ^[3]

マッカーシーが最初に考えた問題は、宣教師と人食い人種の問題でした。川の片岸に宣教師 3 人と人食い人種 3 人がいて、2 人しか乗れない船を使って川を渡らなければなりません。さらに、人食い人種の数が両岸の宣教師の数を上回ってはならないという制約があります (さもないと宣教師は殺され、おそらく食べられてしまうでしょう)。マッカーシーが考えた問題は、ゴールに到達するための一連の手順を見つけることではなく (宣教師と人食い人種の問題に関する記事には、そのような解決策が 1 つ含まれています)、明示的に述べられていない条件を排除することです。たとえば、「南に半マイル進み、橋で川を渡る」という解決策は、問題の説明にそのような橋について触れられていないため、直感的に有効ではありません。一方、この橋の存在は、問題の説明によっても排除されません。橋が存在しないことは、問題の説明にその解決策に関連するすべてのものが含まれているという暗黙の仮定の結果です。橋が存在しないと明示的に述べることは、この問題の解決策にはなりません。なぜなら、除外すべき他の多くの例外的な条件（人食い人種を固定するためのロープの存在、近くに大きなボートの存在など）があるからです。

サーカムスクリプションは後にマッカーシーによって慣性の暗黙の仮定、つまり特に指定がない限り物事は変化しないという仮定を形式化するために使われた。サーカムスクリプションは、明示的に条件を変えることが分かっているものを除き、すべてのアクションによって条件が変化しないと指定することを避けるのに役立つように思われた。これはフレーム問題として知られている。しかし、マッカーシーによって提案された解決策は、後にイェール大学銃乱射事件のシナリオのように、場合によっては間違った結果につながることが示された。フレーム問題には、イェール大学銃乱射事件を正しく形式化する他の解決策も存在し、その中にはサーカムスクリプションを異なる方法で使うものもある。

制限は当初一階述語論理の場合に定義されましたが、命題の場合への特定化は定義が容易です。^[4]命題式 が与えられた場合、その制限は、必要な場合を除いて変数を真に割り当てない のモデルのみを持つ式です。${\displaystyle T}$${\displaystyle T}$

正式には、命題モデルは命題変数の集合によって表すことができます。つまり、各モデルは、それが true に割り当てる命題変数の集合によって表されます。たとえば、 に true を、 に false を、 に true を割り当てるモデルは、集合 によって表されます。これは、 とが、まさにこのモデルによって true に割り当てられる変数であるためです。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle \{a,c\}}$${\displaystyle a}$${\displaystyle c}$

2 つのモデルが与えられ、このように表現されると、条件はtrue に設定されるすべての変数を true に設定することと同等になります。言い換えると、モデルは「true に設定する変数が少ない」関係を表します。は、ただしこれら 2 つのモデルは一致しない ことを意味します。${\displaystyle M}$${\displaystyle N}$${\displaystyle N\subseteq M}$${\displaystyle M}$${\displaystyle N}$${\displaystyle \subseteq }$${\displaystyle N\subset M}$${\displaystyle N\subseteq M}$

これにより、必要な場合を除き、変数を true に割り当てないモデルを定義できます。理論のモデルは、となる のモデルが存在しない場合にのみ、 最小 と呼ばれます。 ${\displaystyle M}$ ${\displaystyle T}$${\displaystyle N}$${\displaystyle T}$${\displaystyle N\subset M}$

極小モデルのみを選択することで極小表現されます。次のように定義されます。

${\displaystyle CIRC(T)=\{M~|~M{\mbox{ は }}T\}} の最小モデルである$

あるいは、 を、まさに上記のモデルのセットを持つ式として定義することもできます。さらに、 の定義を与えることを避け、 のすべての最小モデルが のモデルでもある場合のみとして最小推論を定義することもできます。 ${\displaystyle CIRC(T)}$${\displaystyle CIRC}$${\displaystyle T\models _{M}Q}$${\displaystyle T}$${\displaystyle Q}$

例として、この式には3 つのモデルがあります。 ${\displaystyle T=a\land (b\lor c)}$

1. ${\displaystyle a}$、、は真である、すなわち；${\displaystyle b}$${\displaystyle c}$${\displaystyle \{a,b,c\}}$
2. ${\displaystyle a}$および は真ですが、は偽です。${\displaystyle b}$${\displaystyle c}$${\displaystyle \{a,b\}}$
3. ${\displaystyle a}$および は真ですが、は偽です。${\displaystyle c}$${\displaystyle b}$${\displaystyle \{a,c\}}$

最初のモデルは、true に割り当てる変数の集合において最小ではありません。実際、2 番目のモデルは、 を除いて同じ割り当てを行います。 は false に割り当てられ、true には割り当てられません。したがって、最初のモデルは最小ではありません。2 番目と 3 番目のモデルは比較できません。2 番目は true を に割り当てますが、3 番目は代わりに true を に割り当てます。したがって、外接するモデルは、リストの 2 番目と 3 番目のモデルです。これら 2 つのモデルを正確に含む命題式は次のようになります。 ${\displaystyle c}$${\displaystyle b}$${\displaystyle c}$${\displaystyle T}$

${\displaystyle a\land \neg (b\leftrightarrow c)}$

直感的には、制限内では、必要な場合にのみ変数が true に割り当てられます。双対的に、変数がfalse になる可能性がある場合は、必ずfalse になります。たとえば、との少なくとも 1 つがに従って true に割り当てられる必要があります。制限内では、2 つの変数のうち 1 つだけが true である必要があります。 のどのモデルでも、また制限内でも、 変数はfalse にはなれません。${\displaystyle b}$${\displaystyle c}$${\displaystyle T}$${\displaystyle a}$${\displaystyle T}$

固定述語と可変述語による限定の拡張は、ウラジミール・リフシッツによるものである。^[5]その考え方は、いくつかの条件は最小化されるべきではないというものである。命題論理の用語では、いくつかの変数は可能な限り偽にされるべきではない。特に、2種類の変数が考えられる。

様々

これらは最小化の過程ではまったく考慮されない変数です。

修理済み

これらは、最小化を行う際に固定されていると見なされる変数です。言い換えると、最小化はこれらの変数の値が同じモデルを比較することによってのみ実行できます。

違いは、変化する条件の値は単に重要ではないと想定されていることです。代わりに、固定された条件は起こり得る状況を特徴付けるため、これらの条件の値が異なる 2 つの状況を比較しても意味がありません。

正式には、可変変数と固定変数を組み込んだ極限の拡張は次のようになります。ここで、 は最小化する変数の集合、固定変数、可変変数は に含まれない変数です。 ${\displaystyle P}$${\displaystyle Z}$${\displaystyle P\cup Z}$

${\displaystyle {\text{CIRC}}(T;P,Z)=\{M~|~M\models T{\text{ かつ }}\not \exists N{\text{ が }}N\models T,~N\cap P\subset M\cap P{\text{ かつ }}N\cap Z=M\cap Z\}} となる$

つまり、true に割り当てられた変数の最小化は、 の変数に対してのみ行われます。さらに、モデルは、 の変数に同じ値を割り当てる場合にのみ比較されます。モデルを比較する際には、他のすべての変数は考慮されません。 ${\displaystyle P}$${\displaystyle Z}$

マッカーシーが提案したフレーム問題の解決法は、固定条件のない限定に基づいています。命題の場合、この解決法は次のように記述できます。既知の内容を直接エンコードする式に加えて、条件の値の変化を表す新しい変数も定義します。次に、これらの新しい変数を最小化します。

たとえば、時刻 0 にドアが閉じられ、時刻 2 にドアを開くアクションが実行されるドメインでは、明示的にわかっていることは次の 2 つの式で表されます。

${\displaystyle \neg {\text{open}}_{0}}$

${\displaystyle {\text{true}}\rightarrow {\text{open}}_{2}}$

この例では、フレーム問題は上記の公式の結果ではない問題として示されていますが、ドアは開くアクションが実行されるまで閉じられたままになっているはずです。変化をモデル化するための新しい変数を定義し、それらを最小化すること で、この目的に限界を使用できます。${\displaystyle \neg open_{1}}$${\displaystyle change\_open_{t}}$

${\displaystyle {\text{change open}}_{0}\equiv ({\text{open}}_{0}\not \equiv {\text{open}}_{1})}$

${\displaystyle {\text{change open}}_{1}\equiv ({\text{open}}_{1}\not \equiv {\text{open}}_{2})}$

...

イェール大学銃乱射事件で示されているように、この種の解決法は機能しません。たとえば、は上記の式の外接限定によってはまだ必然的に含意されません。が真でが偽であるモデルは、反対の値を持つモデルと比較できません。したがって、ドアが時刻 1 で開き、その後アクションの結果として開いたままになる状況は、外接限定によって排除されません。 ${\displaystyle \neg {\text{open}}_{1}}$${\displaystyle {\text{開く変更}}_{0}}$${\displaystyle {\text{開く変更}}_{1}}$

このような問題に悩まされない動的領域の形式化は他にもいくつか開発されています (概要についてはフレーム問題を参照)。多くはサーカムスクリプションを使用しますが、方法は異なります。

マッカーシーが提案したサーカムスクリプションの本来の定義は、一階論理に関するものである。命題論理における変数（真または偽になり得るもの）の役割は、一階論理では述語によって果たされる。すなわち、命題式は、各命題変数をゼロ引数の述語（つまり、引数のない述語）に置き換えることによって一階論理で表現できる。したがって、サーカムスクリプションの一階論理バージョンでは、述語の最小化が行われる。つまり、式の外接は、可能な限り述語を偽にすることで得られる。^[6]

述語を含む一階論理式が与えられた場合、この述語を囲むことは、値の組の最小セットで が true に割り当てられる のモデルのみを選択することに相当します。${\displaystyle T}$ ${\displaystyle P}$${\displaystyle T}$${\displaystyle P}$

正式には、一階モデルにおける述語の拡張は、モデル内でこの述語が真に割り当てる値の組の集合である。一階モデルには、各述語シンボルの評価が含まれる。このような評価は、述語がその引数の任意の可能な値に対して真か偽かを示す。 ^[7]述語の各引数は項でなければならず、各項は値に評価されるため、モデルは、任意の可能な値の組に対して が真かどうかを示す。モデル内の の拡張は、モデル内で が真となる ような項の組の集合である。${\displaystyle P(v_{1},\ldots,v_{n})}$${\displaystyle \langle v_{1},\ldots ,v_{n}\rangle }$${\displaystyle P}$${\displaystyle P(v_{1},\ldots,v_{n})}$

式内の述語の限定は、の最小拡張を持つ のモデルのみを選択することにより得られます。たとえば、式に 2 つのモデルのみがあり、1 つ目では が真で 2 つ目では が偽であるという点のみが異なる場合は、2 つめのモデルのみが選択されます。これは、 が最初のモデルでは の拡張内にあるが、2 つ目では の拡張内にないためです。${\displaystyle P}$${\displaystyle T}$${\displaystyle T}$${\displaystyle P}$${\displaystyle P(v_{1},\ldots,v_{n})}$${\displaystyle \langle v_{1},\ldots ,v_{n}\rangle }$${\displaystyle P}$

マッカーシーによる元の定義は意味論的というよりは統語論的でした。式と述語が与えられた場合、を で囲むのは次の 2 階の式です。 ${\displaystyle T}$${\displaystyle P}$${\displaystyle P}$${\displaystyle T}$

${\displaystyle T(P)\wedge \forall p\neg (T(p)\wedge p<P)}$

この式では、は と同じアリティの述語です。これは述語の量化を含んでいるため、2 階の式です。部分式は次の省略形です。 ${\displaystyle p}$${\displaystyle P}$${\displaystyle p<P}$

${\displaystyle \forall x(p(x)\rightarrow P(x))\wedge \neg \forall x(P(x)\rightarrow p(x))}$

この式では、 はn 個の項の組であり、n は のアリティです。この式は、拡張の最小化を行う必要があることを示しています。つまり、検討対象のモデルの に対する真理値評価を行うには、とは異なるが false に代入されるすべての組を他の述語が false に代入できないことが必要です。 ${\displaystyle x}$${\displaystyle P}$${\displaystyle P}$${\displaystyle p}$${\displaystyle P}$${\displaystyle P}$

この定義では、単一の述語のみを限定できます。複数の述語への拡張は簡単ですが、単一の述語の拡張を最小化することには、物事は通常は予想どおりであるという考えを捉えるという重要な用途があります。この考えは、状況の異常性を表現する単一の述語を最小化することで形式化できます。特に、既知の事実はすべて、その事実が通常の状況でのみ当てはまることを示すリテラルを追加して論理的に表現されます。この述語の拡張を最小化することで、物事は予想どおりである (つまり、異常ではない) という暗黙の仮定の下で推論することができ、この仮定は可能な場合にのみ行われます (異常性は、事実と一致する場合にのみ偽であると想定できます)。 ${\displaystyle \neg 異常(...)}$

点ごとのサーカムスクリプションは、ウラジミール・リフシッツ^[8]によって導入された一階サーカムスクリプションの変形です。点ごとのサーカムスクリプションの理論的根拠は、述語の拡張を最小化するのではなく、各値の組について述語の値を個別に最小化するというものです。たとえば、ドメインの 2 つのモデルがあり、1 つは を設定し、もう 1 つは を設定します。最初のモデルでのの拡張は であるのに対し、2 番目のモデルの拡張は であるため、サーカムスクリプションでは最初のモデルのみが選択されます。命題の場合、点ごとのサーカムスクリプションと述語サーカムスクリプションは一致します。 ${\displaystyle P(a)\equiv P(b)}$${\displaystyle \{a,b\}}$${\displaystyle P(a)=P(b)=偽}$${\displaystyle P(a)=P(b)=真}$${\displaystyle P}$${\displaystyle \emptyset}$${\displaystyle \{a,b\}}$

点ごとの制限では、値の各組は別々に考慮されます。たとえば、式では、の値はとは別に考慮されます。モデルが最小となるのは、式を満たしながら、そのような値を true から false に変更できない場合のみです。結果として、 をfalse に変更するだけでは式を満たさないため、点ごとの制限によって のモデルが選択され、 についても同じことが発生します。 ${\displaystyle P(a)\equiv P(b)}$${\displaystyle P(a)}$${\displaystyle P(b)}$${\displaystyle P(a)=P(b)=真}$${\displaystyle P(a)}$${\displaystyle P(b)}$

McCarthy によるサーカムスクリプションの以前の定式化は、述語の拡張ではなく、1 階モデルのドメインを最小化することに基づいています。つまり、あるモデルが他のモデルよりも小さいとみなされるのは、そのモデルがドメインがより小さく、2 つのモデルが共通の値の組の評価で一致する場合です。このバージョンのサーカムスクリプションは、述語サーカムスクリプションに縮小できます。

式サーカムスクリプションは、マッカーシーによって後から導入された形式主義です。これは、述語の拡張ではなく、式の拡張が最小化されるサーカムスクリプションの一般化です。言い換えると、式を満たすドメインの値の組の集合が可能な限り小さくなるように式を指定できます。

限定は必ずしも選言情報を正しく処理するわけではありません。Ray Reiter は次のような例を挙げました。コインがチェックボードの上で投げられ、その結果、コインは黒い領域か白い領域、またはその両方にあります。ただし、コインがあるはずのない場所は他にも多数あります。たとえば、コインが床の上、冷蔵庫の上、または月の表面の上にないことは暗黙的に示されています。したがって、限定は述語の拡張を最小限に抑えるために使用でき、明示的に述べられていなくても偽になります。 ${\displaystyle オン}$${\displaystyle On({\text{コイン}},{\text{月}})}$

一方、述語を最小化すると、コインは黒い領域か白い領域のいずれかにあり、両方にあるわけではないという誤った結果になります。これは、でのみ が真で、 でのみ が真であるのモデルはの最小拡張を持つのに対し、 の拡張が両方のペアで構成されるモデルは最小ではないためです。 ${\displaystyle オン}$${\displaystyle オン}$${\displaystyle ({\text{コイン}},{\text{白い領域}})}$${\displaystyle ({\text{コイン}},{\text{黒い領域}})}$${\displaystyle オン}$${\displaystyle オン}$

理論抑制は、トーマス・アイター、ゲオルク・ゴットロブ、ユーリ・グレヴィッチによって提案された解決策です。^[9]その考え方は、制限により選択できなかったモデル、つまり と が両方とも真であるモデルは、選択された 2 つのモデルの両方よりも大きい ( の拡張に関して) 式のモデルであるということです。より具体的には、式のモデルのうち、除外されたモデルは、選択された 2 つのモデルの最小上限です。理論抑制は、制限により選択されたモデルに加えて、このような最小上限モデルを選択します。この包含は、モデルの集合が閉じるまで、つまり、含まれるすべてのモデル集合のすべての最小上限が含まれるまで行われます。 ${\displaystyle On({\text{コイン}},{\text{白い領域}})}$${\displaystyle On({\text{コイン}},{\text{黒い領域}})}$${\displaystyle オン}$

• 無効化可能な推論 – 演繹的には有効ではないが、合理的に説得力のある推論
• 優先的含意

• 限定 – 非単調推論の一形式、マッカーシーの論文。
• スタンフォード哲学百科事典の説明