Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Emacs LISP – DeMorgan'ify a list – Artificial Intelligence

I am in an Artificial Intelligence course and we were given a program to write. The program is apparently simple, and all other students did it in java. However I know that it can be done in LISP with less work. Well. Less typing. But I’ve been reading about LISP for a week now, and I am amazed by it. I am determined to learn more, and use LISP for a lot more than just this class. I’m 23 and am learning a language formed in 1958. It’s kind of romantic. I am having a lot of fun avoiding my mousepad like the plague.

The example he gives tells the entire program. He notes that he uses recursion, and 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 De Morgan’s laws. I just don’t get how I’m supposed to handle this! What I have so far is… embarrassing. My notebook is filled with pages of me trying to draw this out. I will give you my closest attempt at the simplest case which is:

(not (or a b))

I figure if I can handle this, I may be just fine to handle the rest. Maybe. I made a function called boom, and that above statement is what I call a boomable 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 to the list operands does not reflect changes in original sexp (huge let down for me).

Tell me what I have is bogus, and guide me.

Tags:

4

Answers


  1. 0

    It’s not too hard to write a quick and dirty version of this. You just need to check whether your formula is a raw propositional variable (in this case, an atom), a binary connective, or a negation. If it’s 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)))))))))))

    This could certainly be made a bit cleaner, though.

    Login or Signup to reply.
  2. 0

    This two functions should distribute the not into parentheses:

    (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)))))))
    Login or Signup to reply.
  3. 0

    Common Lisp, without simplification:

    (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))))))
    Login or Signup to reply.
  4. 0

    An Emacs Lisp solution using pattern matching, based on Rainer Joswigs Common Lisp solution:

    (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))))
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search