MA-351 Homework 5

Due Thursday December 4, 2008, 4:59pm in my mailbox in HA 245.


Solutions may be submitted in person in class or put in my mailbox, or you may email an ASCII text, Html, or postscipt/pdf-formatted document to me.
Note my office hours on my schedule.

  1. Consider the Boolean expression

    (a xor b) and (a xor c) and (b equiv c)

    where xor is the exclusive-or operator and equiv is the equivalence operator: (a and b) or ((not a) and (not b)).
    1. Find the CNF (with k clauses) equivalent to this expression.
    2. Draw the graph corresponding to the CNF that has a clique of size k iff the CNF is satisfiable. For a satisfying assignment, identify the clique.
  2. Please give an example of a group profile such that the Borda count group consensus function violates one of Arrow's axioms. Please explain which one and why. As weights, please use 0 to n-1 for the n alternatives from last to first place, respectively.