Emacs LISP - DeMorgan'ify List

Question

I am engaged in artificial intelligence, and we were given a program for writing. The program seems to be simple, and all the other students did it in java. However, I know that this can be done in LISP with less work. Well. Print less. But I've been reading about LISP for a week now, and I am amazed at this. I intend to learn more and use LISP much more than just this class. I am 23 years old and I am learning a language formed in 1958. It's romantic. I really like avoiding my mouse like a plague.

The example he gives tells the whole program. He notes that he uses recursion, not prog. I understand what that means, at least.

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

I understand the laws of De Morgan. I just don’t understand how I should deal with this! That I'm still ... embarrassing. My notebook is filled with pages of my pages, trying to figure it out. I will give you the closest attempt in the simplest case:

(not (or a b))

I believe that if I can handle this, I can be fine to handle the rest. May be. I made a function called "arrow", and this statement above is what I call an advanced list.

(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

I print at the end for debugging. Changes in the operands of the list do not reflect changes in the original sexp (huge ones give in to me).

Tell me that I have a fake, and guide me.

Answer 1

Emacs Lisp 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)))))))

Answer 4

It's not that hard to write a quick and dirty version of this. You just need to check if your formula is an unprocessed propositional variable (in this case, an atom), a binary bond, or negation. If this is a negation, then you need to process the inside.

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

Of course, this can be done a little cleaner.