Sunday, May 15, 2011

Converting finite functions into discrete maps

Maps are the extensional analogue of functions. For example, here is the nand function expressed as a map:
(defn unapplify
  [func]

  (fn [& args]
    (apply func args)))

(def nand
  (unapplify
   '{(false false) true
     (false true)  true
     (true  false) true
     (true  true)  false}))

Now if a function is finite and we have a complete description of its domain, then we can turn it into a map:
(defn function-to-map
  [func domain]

  (zipmap
   domain
   (map (partial apply func) domain)))

Now we have the machinery necessary to prove De Morgan's Laws:

(def boolean-pairs
 '((false false)
   (false true )
   (true  false)
   (true  true )))

(= (function-to-map
     (fn [a b] 
       (not (and a b)))
     boolean-pairs)
  
   (function-to-map
     (fn [a b]
       (or (not a) (not b)))
     boolean-pairs))

(= (function-to-map
     (fn [a b] 
       (not (or a b)))
     boolean-pairs)
  
   (function-to-map
     (fn [a b]
       (and (not a) (not b)))
     boolean-pairs))

This method works for all finite functions. On the other hand, infinite functions require more sophisticated mathematically machinery.

No comments:

Post a Comment