MA-351 Homework 5

Due Thursday December 6, 2007, 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 U(a,b,c)

   where xor is the exclusive-or operator and U(a,b,c) is ``exactly one'': (a or b or c) and ((not a) or (not b)) and ((not a) or (not c)) and ((not b) or (not c)).
   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.