MA-351 Homework 5

Due Thursday December 2, 2010, 4:59pm in my mailbox in SAS 3151.

All solutions must be submitted in hardcopy either to me in class or placed in my mailbox. Note my office hours on my schedule.

1. Consider the Boolean expression

   (a implies b) nand (b xor c)

   where x implies y is the implication operator (not x) or y, x equiv y is the equivalence operator [(x and y) or ((not x) and (not y))], x xor y, is the exclusive or not (x equiv y), and x nand y is the Sheffer stroke not (x and y).
   1. Find a CNF (with k clauses and no more than 3 literals per clause) that is 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 corresponding clique.
2. Please give an example of a group profile such that the Borda count group consensus function, with weights n-1 to 0 from first to last place of the n alternatives violates Arrow's axiom 2 (irrelevant alternatives).