使用 lisp 简化一个简单的布尔表达式

Question

我有一个简单的 布尔表达式 以 lisp 列表形式呈现，如下所示： '(OR 0 (AND A1 A2))

前面的列表是((A1 AND A2)OR 0)的表示。

无论如何，我正在编写一个函数来简化这个表达式.. 例如：

像这样调用函数 "reduce" :

(减少'(OR 0 (AND A1 A2)))

会产生

（和 A1 A2）

我首先尝试创建基本规则，所以我定义了 以下身份：

(AND 1 S) == S,

（或 0 S）== S，

(AND 0 S) == 0,

( 或 1 S) == 1,

（不是 O）== 1，

（非 1）== 0.*

我正在考虑定义 6 个函数，每个规则一个，然后在包装器中一个一个地调用它们，我是 lisp 的新手，所以我不知道如何实现它，我在 java 中做过一次，但我不知道如何使用语法处理此类问题口齿不清所以请帮助我..

Answer 1

我终于想到了这个解决方案。

(defun simplify (EXPR)
  (simplify-expr NIL EXPR))

(defun simplify-expr (EXPR1 EXPR2)
  (cond 
   ((or (atom EXPR2) (equal EXPR1 EXPR2)) EXPR2)
   (T (simplify-expr EXPR2 (simplify-boolean-expr EXPR2)))))

(defun simplify-boolean-expr (EXPR)
  (cond 
   ((and (equal (first EXPR) `and) (>= (length EXPR) 3)) 
    (simplify-and-expr (rest EXPR)))
   ((and (equal (first EXPR) `or) (>= (length EXPR) 3)) 
    (simplify-or-expr (rest EXPR)))
   ((and (equal (first EXPR) `not) (= (length EXPR) 2)) 
    (simplify-not-expr (rest EXPR)))
   (T 
    (error "~S is not a valid circuit descriptor expression or has an unknown operator." EXPR))))

(defun simplify-and-expr (EXPR)
  (let ((SIMPLIFIED_EXPR (remove `T (remove-duplicates EXPR))))
    (cond 
     ((null SIMPLIFIED_EXPR) `T)
     ((member `NIL SIMPLIFIED_EXPR) `NIL)
     ((null (second SIMPLIFIED_EXPR)) (first SIMPLIFIED_EXPR))
     (T (cons `and (simplify-operand SIMPLIFIED_EXPR))))))

(defun simplify-or-expr (EXPR)
  (let ((SIMPLIFIED_EXPR (remove `NIL (remove-duplicates EXPR))))
    (cond
     ((null SIMPLIFIED_EXPR) `NIL)
     ((member `T SIMPLIFIED_EXPR) `T)
     ((null (second SIMPLIFIED_EXPR)) (first SIMPLIFIED_EXPR))
     (T (cons `or (simplify-operand SIMPLIFIED_EXPR))))))

(defun simplify-not-expr (EXPR)
  (cond 
   ((equal (first EXPR) `NIL) `T)
   ((equal (first EXPR) `T) `NIL)
   ((and (listp (first EXPR)) (equal (first (first EXPR)) `not)) 
    (first (rest (first EXPR))))
   (T (cons `not (simplify-operand EXPR)))))

(defun simplify-operand (OPERAND_LIST)
  (cond 
   ((null OPERAND_LIST) NIL)
   ((atom (first OPERAND_LIST)) 
    (cons (first OPERAND_LIST) (simplify-operand (rest OPERAND_LIST))))
   (T 
    (cons (simplify-expr NIL (first OPERAND_LIST)) (simplify-operand (rest OPERAND_LIST))))))

它用 (nil , T) 代替 (0 , 1) 并减少任何布尔表达式，我试过了，效果很好。

Answer 2

考虑到您的解决方案的复杂性，这是我的实现，它更短且更易读：

(defun reduc (exp)
  (if (atom exp) 
      exp
      (flet ((helper (op args n) ; and and or is nearly the same code so we factor it out
               (let ((newargs (remove n args)) (cn (- 1 n)))
                 (cond
                  ((null newargs) n)
                  ((some (lambda (e) (eql cn e)) newargs) cn)
                  ((null (cdr newargs)) (car newargs))
                  ((cons op newargs))))))
        (let ((op (car exp)) (args (mapcar #'reduc (cdr exp))))
          (ecase op
            ((not) (if (= 1 (length args))
                       (let ((arg1 (car args)))
                         (if (and (numberp arg1) (<= 0 arg1 1)) (- 1 arg1) exp))
                       (error "'not' must have exactly one parameter")))
            ((and) (helper op args 1))
            ((or)  (helper op args 0)))))))

测试：

? (reduc '(OR 0 (AND A1 A2))) 
(AND A1 A2)
? (reduc '(OR 0 (AND A1 1 A2)))
(AND A1 A2)
? (reduc '(or ERROR (not 0)))
1
? (reduc '(AND ERROR (not 0)))
ERROR
? (reduc '(OR 0 (AND A1 0))) 
0
? (reduc '(OR 0 (AND A1 1))) 
A1

使用 lisp 简化一个简单的布尔表达式

simplifying a simple boolean expression using lisp

lisp

boolean-expression