2

私は Common Lisp でこの問題を抱えています。スコーレム化のルールを導入して、存在変数を操作する必要があります。

たとえば、 を有効にする関数を作成する必要があり (exist ?x (p ?x))ます(p sk00042)。

sk00042変数です。ユニバーサル変数が含まれている場合、この関数は少し難しくなることに注意してください。

たとえば、式を与えられた関数(forall ?y (exist ?x (p ?x ?y))はそれを に変換し(forall ?y (p (sf666 ?y) ?y)ます。アイデアは、存在変数が、式を満たす何かがあることを教えてくれるというものです。この存在量指定子が外部である場合、この量指定子は何にも依存せず、上記の最初の例の変数は、この関数によって生成される ?x定数に置き換えられる必要があります。skoo42(defun skolem-variable () (gentemp "SV-"))

より困難な (2 番目の) ケースが発生し、存在量指定子の「外」に普遍量化子がある場合、その存在するものは、普遍的に量化された変数に依存します。つまり、関数はこの依存関係を処理する必要があり、普遍変数は変数に組み込まれます。例のような定数:

(forall ?y (exist ?x (p ?x ?y))->(forall ?y (p (sf666 ?y) ?y) これは次の機能も果たします。

(defun skolem-function* (&rest args) (cons (gentemp "SF-") args))
(defun skolem-function (args) (apply #'skolem-function* args))

アイデアをよりよく理解するためのいくつかの例を次に示します。

(skolemize '(forall ?y (exist ?x (p ?x ?y))))
;=> (forall ?y (P (SF-1 ?Y) ?Y))
(skolemize '(exist ?y (forall ?x (p ?x ?y))))
;=> (for all ?x (P ?X SV-2)
(skolemize '(exist ?y (and (p ?x) (f ?y))))
;=> (AND (P ?X) (F SV-4))
(skolemize '(forall ?x (exist ?y (and (p ?x) (f ?y)))))
;=> (forall ?x (AND (P ?X) (F (SF-5 ?X)))

外部が存在するかどうかを制御する式を指定して、変数を skolem-variable に置き換える関数を (skolem-variableおよび上記を使用して) 作成する必要があります。skolem-function外側が forall であり、その後に存在する場合、関数は上で説明したことを実行します。

4

1 に答える 1

2

ウィキペディアの skolem の標準形に関する記事をざっと読んだだけですが、正しく理解すれば、すべての存在は、バインドされたユニバーサルを引数として (またはユニバーサルがスコープ内にない場合は skolem 定数)、skolem 関数の呼び出しになります。単純なアプローチの 1 つは、式ツリーを再帰的にたどりながら、バインドされたユニバーサルのスタックを保持することです。

(defun skolemize (form &optional (universals nil))
  (cond ((null form) nil)                                  ; subtree done
        ((consp (car form))                                ; walk branches
         (cons (skolemize (car form) universals)
               (skolemize (cdr form) universals)))
        ((eq (car form) 'forall)                           ; universal binding
         (list 'forall
               (cadr form)
               (skolemize (caddr form)                     ; skolemize body
                          (cons (cadr form) universals)))) ; new var on the stack
        ((eq (car form) 'exist)                            ; existential binding
         (subst (if universals                             ; substitute variables
                    (cons (gentemp "SF-") universals)      ; with skolem function
                    (gentemp "SV-"))                       ; with skolem constant
                (cadr form)
                (skolemize (caddr form) universals)))
        (t (cons (car form) (skolemize (cdr form) universals)))))

これは単に開始するためのものであることに注意してください。私はこのトピックを掘り下げたわけではなく、パフォーマンスやエレガンスについて実際にテストまたは最適化したわけでもありません。また、不正な形式の入力も受け入れます(skolemize '(forall (foo bar)))。

あなたの例:

CL-USER> (skolemize '(exist ?x (p ?x)))
(P SV-16)
CL-USER> (skolemize '(forall ?y (exist ?x (p ?x ?y))))
(FORALL ?Y (P (SF-17 ?Y) ?Y))
CL-USER> (skolemize '(exist ?y (forall ?x (p ?x ?y))))
(FORALL ?X (P ?X SV-18))
CL-USER> (skolemize '(exist ?y (and (p ?x) (f ?y))))
(AND (P ?X) (F SV-19))
CL-USER> (skolemize '(forall ?x (exist ?y (and (p ?x) (f ?y)))))
(FORALL ?X (AND (P ?X) (F (SF-20 ?X))))

より複雑な式のテスト:

CL-USER> (skolemize '(exist ?a
                      (forall ?b
                       (exist ?c
                        (forall ?d
                         (exist ?e (and (or (and (f ?a) (g ?b))
                                            (and (f ?c) (g ?d)))
                                        (or (and (f ?c) (g ?e))
                                            (and (f ?d) (g ?e))))))))))
(FORALL ?B
  (FORALL ?D (AND (OR (AND (F SV-15) (G ?B))
                      (AND (F (SF-16 ?B)) (G ?D)))
                  (OR (AND (F (SF-16 ?B)) (G (SF-17 ?D ?B)))
                      (AND (F ?D) (G (SF-17 ?D ?B)))))))
于 2013-02-10T19:13:26.893 に答える