Lesson Plan - 6.001 SP04 - recitation 10

symbols and quote

quote & reader

equality operators

define "works on"
eq? - works on numbers < 2^25

symbols - 1 copy

self-evaluating compound exp - using quote, lambda, and list

(define (set-contains? elem set)
  (if (null? (cdr set))
      #f
      (if (eq? (cadr set) elem)
          #t
          (set-contains? elem (cons 'set (cddr set))))))

(define (set-add elem set)
  (if (not (set-contains? elem set))
      (cons 'set (cons elem (set-elements set)))
      set))

(define (not? exp)
  (and (pair? exp) (eq? (car exp) 'not)))
(define (make-not exp)
  (list 'not exp))
(define (not-operand exp)
  (cadr exp))

(define (formula-variables exp)
  (cond ((variable? exp)
         (set-add (variable-name exp) (empty-set)))
        ((not? exp)
         (formula-variables (not-operand exp)))
        ((or? exp)
         (set-union (formula-variables (or-first exp))
                    (formula-variables (or-second exp))))
        ((and? exp)
         (set-union (formula-variables (and-first exp))
                    (formula-variables (and-second exp))))
        (else (error "unknown exp" exp))))

(define (formula-value bindings exp)
  (cond ((variable? exp)
         (variable-value bindings (variable-name exp)))
        ((not? exp)
         (not (formula-value bindings (not-operand exp))))
        ((or? exp)
         (or (formula-value bindings (or-first exp))
             (formula-value bindings (or-second exp))))
        ((and? exp)
         (and (formula-value bindings (and-first exp))
              (formula-value bindings (and-second exp))))
        (else (error "unknown exp" exp))))

Notions of SAT - NP hard
change constructors to work better - demorgans law