カリーヌ

CARINE (Computer Aided Reasoning Engine)は、一階述語論理に基づく自動定理証明器です。当初は、深さ優先探索に基づくアルゴリズムにおける遅延節構築 (DCC) および属性シーケンス (ATS) 戦略の強化効果を研究するために構築されました。^{[ 1 ]} CARINE の主な探索アルゴリズムは、反復的に深化させる深さ優先探索 (深さ優先反復深化 (DFID) とも呼ばれる) に基づく半線形分解 (SLR) であり、THEO などの定理証明器で使用されています。^{[ 3 ] SLR は、}高い推論率を実現するために DCC を使用し、探索空間を削減するために ATS を使用し^ます。

遅延節構築は、節の構築作業を最小限に抑えることで定理証明器のパフォーマンスを向上させる遅延戦略です。適用された推論規則のすべての結論（節）を構築する代わりに、そのような節を構築するための情報は、定理証明器が節を破棄するか構築するかを決定するまで一時的に保存されます。定理証明器が節を保持することを決定した場合、節は構築されてメモリに保存されますが、そうでない場合は、節を構築するための情報は消去されます。推論された節を構築できる情報を保存するのに、追加のCPU操作はほとんど必要ありません。ただし、節の構築には多くの時間がかかる場合があります。一部の定理証明器は、実行時間の30%～40%を節の構築と削除に費やしています。DCCを使用すると、この無駄な時間を節約できます。

DCCは、中間節（特に一階述語論理節）が短時間のうちに多数構築され、破棄される場合に有効です。なぜなら、そのような短命な節を構築するために実行される操作が回避されるからです。ただし、DCCは命題節のみで構成される定理にはあまり効果的ではないかもしれません。

定理証明における節とは、（非公式な定義によれば）リテラルの評価によって真偽が決まる命題のことである。節は、リテラルの論理和（OR）、論理積（AND）、集合、または多重集合（集合に似ているが、同一の要素を含むことができる）として表現される。

リテラルの選言として表現された節の例は次のとおりです。 $${\displaystyle \l裕福ではない (Y)\lor \l賢いではない (Y)\lor \l美しいではない (Y)\lor \operatorname {愛している} (X,Y)}$$ シンボルが${\displaystyle \lor }$そして${\displaystyle \lnot }$それぞれ、論理ORと論理NOTです。

上記の例は、Yが裕福で、賢くて、美しいならば、XはYを愛している、と述べています。ただし、 XとYが誰であるかは述べていません。上記の表現は、次の論理式から来ていることに注意してください。

人間領域に属する すべてのY、Xについて：$${\displaystyle \operatorname {裕福} (Y)\land \operatorname {賢い} (Y)\land \operatorname {美しい} (Y)\implies \operatorname {愛する} (X,Y)}$$

形式論理の変換規則を用いることで、上記の例で示したリテラルの選言を生成することができる。

XとYは変数です。${\displaystyle \lnot }$裕福な、${\displaystyle \lnot }$頭いい、${\displaystyle \lnot }$美しい、愛はリテラルです。定数Johnを変数Xに、定数Janeを変数Yに置き換えると、上記の節は次のようになります。

$$\lジェーンは裕福ではない、\lジェーンは賢いではない、\lジェーンは美しいではない、\lジェーンはジョンを愛している、\lジェーンはジョンを愛している。$$

節属性とは、節の特性のことです。節属性の例としては、以下のようなものがあります。

• 節に含まれるリテラルの数（つまり、節の長さ）
• 節内の用語記号の数
• 節内の定数の数
• 節内の変数の数
• 節内の関数の数
• 節内の否定リテラルの数
• 節内の肯定リテラルの数
• 節内の異なる変数の数
• 節内のすべてのリテラルにおける任意の項の最大深度

例

その条項$${\displaystyle C=\lnot P(x)\lor Q(a,b,f(x))}$$もっている：

• 2つのリテラルが含まれているため、長さは2です。
  • 1 つの否定リテラルは${\displaystyle \lnot P(x)}$
  • 1つの正のリテラル、つまりQ ( a , b , f ( x ))
• 定数aとbの2つ
• 2つの変数（xが2回出現）
• xという 1 つの明確な変数
• 1 つの関数f
• 最大項深度は2
• x、a、b、f、xの 5 つの項記号

属性シーケンスとは、長さ k の導出の集合の射影を表す、 k n個の節属性のタプルのシーケンスです。k と n は厳密に正の整数です。導出の集合は導出と属性シーケンス間のマッピングの定義域を形成し、属性シーケンスは終域を形成します。

例

<(2,2),(2,1),(1,1)> は、 k  =  3、n  = 2の属性シーケンスです 。

これは、例えば <(B1,B2),(R1,B3),(R2,B4)> のような導出に対応します。ここで、B1、B2、R1、B3、R2、B4 は節です。ここで属性は、節の長さであると想定されます。

最初のペア（2,2）は、導出におけるペア（B1,B2）に対応します。これは、B1の長さが2であり、B2の長さも2であることを示しています。

2番目のペア(2,1)はペア(R1,B3)に対応しており、R1の長さが2で、B3の長さが1であることを示しています。

最後のペア(1,1)はペア(R2,B4)に対応しており、R2の長さが1で、B4の長さが1であることを示しています。

注:節属性のnタプルは、 Stephan Schulz 博士が命名した特徴ベクトルに似ていますが、同じではありません( E 等式定理証明器を参照)。

• カリーヌのウェブサイト
• ACM出版物
• Eホームページ