4

我正在学习人工智能课程，我们得到了一个程序来编写。该程序显然很简单，所有其他学生都是用 java 完成的。但是我知道它可以在 LISP 中以更少的工作完成。好。少打字。但是我已经读了一周的 LISP 了，我对它感到惊讶。我决心学习更多，并使用 LISP 做更多的事情，而不仅仅是这门课。我今年 23 岁，正在学习一门 1958 年形成的语言。这有点浪漫。避免像瘟疫一样躲避鼠标垫让我很开心。

他给出的例子告诉了整个程序。他指出他使用递归，而不是 prog。至少我明白这意味着什么。

(rewrite '(or a (and b (not (or c d)))))

--> (OR A (AND B (AND (NOT C) (NOT D))))

(rewrite '(and a (or b (not (and c (and d e))))))

--> (AND A (OR B (NOT C) (OR (NOT D) (NOT E)))))

我了解德摩根的法律。我只是不明白我应该如何处理这个！到目前为止我所拥有的是......令人尴尬。我的笔记本上满是我试图把它画出来的页面。我将在最简单的情况下为您提供最接近的尝试，即：

(not (or a b))

我想如果我能处理好这个，我可能会处理剩下的。也许。我做了一个叫做繁荣的函数，上面的语句就是我所说的繁荣列表。

(defun boom (sexp)

  (let ((op (car (car (cdr sexp)))) 

    (operands (cdr (car (cdr sexp))))))

  (if (equal op 'and)

      (setcar sexp 'or)

    (setcar sexp 'and))

  (print operands)

  (print sexp))

                ;end boom

我在最后打印以进行调试。对列表操作数的更改不反映原始 sexp 的更改（对我来说非常失望）。

告诉我我所拥有的是虚假的，并指导我。

4

4 回答 4

5

使用模式匹配的 Emacs Lisp 解决方案，基于Rainer Joswigs Common Lisp 解决方案：

(defun de-morgan (exp)
  (pcase exp
    ((pred atom) exp)
    (`(not (and ,a ,b)) `(or ,(de-morgan `(not ,a))
                             ,(de-morgan `(not ,b))))
    (`(not (or ,a ,b)) `(and ,(de-morgan `(not ,a))
                             ,(de-morgan `(not ,b))))
    (x (cons (car x) (mapcar #'de-morgan (rest x))))))

(de-morgan '(not (or 1 2))) ; => (and (not 1) (not 2))
(de-morgan '(not (and 1 2))) ; => (or (not 1) (not 2))
(de-morgan '(or a (and b (not (or c d))))) ; => (or a (and b (and (not c) (not d))))
于 2016-02-09T16:56:45.623 回答
2

Common Lisp，没有简化：

(defun de-morgan (exp)
  (cond ;; atom
        ((atom exp) exp)
        ;; (not (and p q))  or  (not (or p q))
        ((and (consp exp)
              (equal (car exp) 'not)
              (consp (cadr exp))
              (or (equal (caadr exp) 'and)
                  (equal (caadr exp) 'or)))
         (list (case (caadr exp)
                 (and 'or)
                 (or 'and))
               (de-morgan (list 'not (car  (cdadr exp))))
               (de-morgan (list 'not (cadr (cdadr exp))))))
        ;; otherwise some other expression
        (t (cons (car exp) (mapcar #'de-morgan (rest exp))))))
于 2016-02-09T16:24:28.060 回答
1

这两个函数应该将 分配not到括号中：

(defun de-morgan (formula)
  (if (listp formula)
      (let ((op (first formula)))
        (case op
          (and `(and ,(de-morgan (second formula)) ,(de-morgan (third formula))))
          (or `(or ,(de-morgan (second formula)) ,(de-morgan (third formula))))
          (not (de-morgan-negate (second formula)))))
    formula))

(defun de-morgan-negate (formula)
  (if (listp formula)
      (let ((op (first formula)))
        (case op
          (and `(or ,(de-morgan-negate (second formula)) ,(de-morgan-negate (third formula))))
          (or `(and ,(de-morgan-negate (second formula)) ,(de-morgan-negate (third formula))))
          (not (de-morgan (second formula)))))
    `(not ,formula)))



(de-morgan 'a)
(de-morgan '(not a))
(de-morgan '(not (not a)))
(de-morgan '(and a b))
(de-morgan '(not (and a b)))
(de-morgan '(not (or a b)))
(de-morgan '(not (and (and (not a) b) (not (or (not c) (not (not d)))))))
于 2016-02-09T16:00:41.600 回答
0

编写一个快速而肮脏的版本并不难。您只需要检查您的公式是原始命题变量（在本例中为原子）、二元连接词还是否定。如果它是一个否定，那么你需要处理里面。

(defun demorganify (formula)
  (if (atom formula)
      formula
    (let ((operator (first formula)))
      (case operator
        ((and or)
         (list* operator (mapcar 'demorganify (rest formula))))
        ((not)
         (let ((subformula (second formula)))
           (if (atom subformula)
               formula
             (let* ((suboperator (first subformula))
                    (new-suboperator (case suboperator
                                       ((not) 'not)
                                       ((and) 'or)
                                       ((or) 'and)))
                    (demorganify-and-negate (lambda (f)
                                              (demorganify (list 'not (demorganify f))))))
               (list* new-suboperator (mapcar demorganify-and-negate (rest subformula)))))))))))

不过，这当然可以做得更干净一些。

于 2016-02-09T16:00:29.880 回答