MA-351 Homework 5

Due Thursday December 3, 2009, 4:59pm in my mailbox in SAS 3151.


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 implies b) equiv (b implies c)

    where x implies y is the implication operator (not x) or y and x equiv y is the equivalence operator: [(x and y) or ((not x) and (not 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 plurality with instant elimination group consensus function violates Arrow's axiom 2 (irrelevant alternatives).