我正在上人工智能课程，我们得到了一个程序来编写。该程序显然很简单，所有其他学生都是用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 的函数，上面的陈述就是我所说的 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 的变化(对我来说非常失望(。
告诉我我所拥有的是假的，并引导我。
一个使用模式匹配的 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))))
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))))))
这两个函数应将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)))))))
写一个快速而肮脏的版本并不难。 你只需要检查你的公式是原始命题变量(在本例中是原子(、二元连接词还是否定。 如果是否定，那么你需要处理内部。
(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)))))))))))
不过，这当然可以做得更干净一些。