## 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.