Emacs LISP -DeMorgan的列表

Question

我正在参加人工智能课程，我们得到了一个可编写的程序。这个程序显然很简单，所有其他学生都是用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))

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

(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

我在最后打印以进行调试。对列表操作数的更改并不反映原始性别的变化(对我来说是很大的失望)。

告诉我我有什么是假的，并引导我。

Answer 1

一个使用模式匹配的Emacs解决方案，基于Rainer Joswigs公共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))))

Answer 2

普通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 3

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