HW1

1. there are 2^(2^3) = 256 functions on B^3.  of these a number don't actually
depend on all three dimensions. associated these dimensions with x, y, z variables.

  - there are 2^(2^2) = 16 functions on B^2.  multiply this by 3 to get the total
    number of functions that are only functions of {x,y}, {x,z}, and {y,z}

    subtracting 3 * 16 from 256 we get 208.

  - however, we subtracted some functions more than once, since not all the 16 functions
    on x,y depend on x,y.   there are 2^(2^1) = 4 functions of x only, 4 of y only, and
    4 of z only, and we add these back to 208, get 220

  - however, the 4 functions of x include 0,1 as do the 4 functions on y and z.  
    so we need to subtract 4 from 220 to get the final result of 216.

2. cover F is unate in x ==> function is unate in x (follows from cofactoring F wrt x' and x)
   cover F is not unate in x =/=> function is unate (e.g., a + a'b is not unate in a, but function
   is)

3. direct analysis of kmap

4. cofactoring properties:   the general approach is to pick a minterm
   (a_0,...,a_{n-1}); then f_{x_i}(a_0,...a_{n-1}) = f(a_0,...,a_{i-1},1,a_{i+1},...a_{n-1}).
   then f_{{x_i}'}(a_0,...a_{n-1}) = f(a_0,...,a_{i-1},0,a_{i+1},...a_{n-1}).  now
   it's just a matter of showing that for any minterm the LHS equals the RHS.

5. duality follows from an argument like the above.  

   for showing \exists x . f is the smallest
   function indep of x containing f, we need to show (1) it's indep of x, and (2) any
   function indep of x  containing f must contain \exists x . f   
   
   note about smallest - we say f is smaller than g if by defn the onset of f is 
   contained in the onset of g. note that f may not be smaller than g and g may not 
   be smaller than f.)  

   (1) follows from the same approach as in 4.  
   
   the proof of (2) goes as follows:

   let g be independent of x, and g contain f.  let A be any minterm in
   the input space.  
   
   suppose \exists x . f (A) is 1.  
   
   let A0 be A with the x-coordinate being assigned to 0, similarly A1.

   if \exists x. f(A) is 1, we must have f(A0) = 1 or f(A1) = 1 (or both).

   note that one of A0 and A1 must equal A itself.  

   since g is indep of x, it follows that g(A0) = g(A1).  
   so since g contains f, we must have g(A0) = g(A1) = 1 (because
   f is 1 on one of A0 or A1)

   so g is 1 everywhere \exists x . f is 1 QED

6. i talked about this in class.  the main idea is that a symm function on n vars only depends
   on the number of bits in the input that are set to 1.  so once you have this count,
   you can use it to select the right output, e.g., via a large mux.

   the number of bits set to 1 in an n-dim minterm ranges from 0 to n.  so you need a (n+1):1 mux,
   which can be built recursively from 2-1 muxes; you need n 2-1 muxes, each is a (small) constant number of
   2-ip NAND gates.

   to compute the number of bits set to 1, use recursion - split the minterm in two subminterms, as
   balanced as possible, and then find the number of bits set to 1 in each, and add the two results.
   the final adder takes \log n bit data values, so it can be built in O( \log n ) gates.  if you
   recursively look at the number of gates for the subcases and add them up you get O( n \log n) gates total.

7. (a) throw away all of the n variables in which all vectors in A agree.

       look at the rest: pick any variable x;  some vectors in A have this
       set to 1, others have it set to 0.  suppose more have it set to 1 than 0,
       then focus on the subset B that sets it to 0.  again, pick a variable y
       that they don't all agree in, and suppose the subset C that sets y to 0 is
       smaller than the one that sets it to 1.  if you continue in this way, always
       choosing the smaller subset (if they are the same pick arbitrily), you get a set
       of variables which takes you to a single vector in \log_2 A steps (since 
       we're at least halving the size of the remaining subset at each iteration)

  (b) Every vector v in A differs from the m-1 other vectors in A, so pick variables x1...x(m-1)
      which diff v from the others; right there you have a set of size at most m-1 (since some 
      xi's may be repeated, it may be less than size m-1)

  (c) 000..00, 1000..00, 010..00, 0010..00, 000..010, 000..001

  (d) bondy's theorem - this is surprisingly tricky to prove (and that it is true is not 
      obivous either).  consider all the subsets of {1,..n} of size |A| and apply
      the pigeonhole principle.