Emacs LISP - DeMorgan'ify 列表

Question

我在上人工智能课程，我们被要求编写一个程序。程序看似简单，其他同学都在java完成了。但是我知道它可以用更少的工作在 LISP 中完成。出色地。少打字。但是我已经阅读了一个星期有关 LISP 的文章，我对它感到很惊讶。我决心学习更多，并使用 LISP 做更多的事情，而不仅仅是这个 class。我今年 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))

我想如果我能处理这个，我可能会处理剩下的事情。可能是。我创建了一个名为 boom 的函数，上面的语句就是我所说的 boomable 列表。

(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 的更改（对我来说非常失望）。

告诉我有什么是假的，指导一下。

Answer 1

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

(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)))))))))))

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

Answer 2

这两个函数应该将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)))))))

Answer 3

没有简化的 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))))))

Answer 4

使用模式匹配的 Emacs Lisp 解决方案，基于 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))))

Emacs LISP - DeMorgan'ify 列表

Emacs LISP - DeMorgan'ify a list

lisp

emacs

demorgans-law