Tuesday, August 23, 2011

Properties of operations

Some binary operations are either commutative or associative, as defined by a properties on their domain:

(defn commutative?
  (∀ [a b]
    (= (op a b) 
       (op b a))))

(defn associative? 
  (∀ [a b c]
    (= (op (op a b) c) 
       (op a (op b c)))))

An example binary operation is nand:

(defn nand
  [& nums]
  (case nums
    [false false] true
    [false true ] true
    [true  false] true
    [true  true ] false))

From its truth table you can immediately see that it is commutative. However, it is not associative because it applies to the following lists of length three:

[[false false false] 
 [false true  false] 
 [true  false false] 
 [true  true  false] 
 [true  true  true ]]

Which implies that the following case doesn't hold.

(/= (nand (nand false true) false))
    (nand false (nand true false)))

Many functions are both associative and commutative, such as addition and multiplication. If both of these properties apply then the functions arguments are orderless.

If the function's arguments are orderless then they can be thought of as a multiset. Multiple instances of the same member can be replaced using a higher hyper-operation:

(= (+ x y z x x y)
   (+ (* x 3)
      (* y 2)
      (* z 1)))

Other properties of binary operations are the identity element and the inverse element. If an operation has all these properties over a set, then it forms a group. If it is also commutative it is an abelian group.

No comments:

Post a Comment