Instructions: Solve all of the problems below and provide explanation to every answer. Your project must be typed and should not be longer than 2-3 pages.
1. In this question, knights always tell truth and knaves always lie. All persons are either knights or knaves.
(a) There are two persons, X and Y. X says "At least one of us is a knave." What are X and Y?
(b) Y says "Either I am a knave or X is a knight". What are X, Y?
(c) X says "I am a knave, but Y isn't". What are X, Y?
(d) There are three persons, X, Y, and Z. X says "All of us are knaves", Y says "Exactly one of us is a knight". What are X, Y, Z?
2. Show that ∀xP(x) ν ∀xQ(x) is not always equivalent to ∀x (P(x) ν Q(x)). On the other hand, show that ∀xP(x) V ∀x∀yQ(x) is logically equivalent to ∀x∀y(P(x) V Q(y)). (Domains for x and y are the same).
Show that ∀x(P(x) V ∃xQ(x) is equivalent to ∀x∃y(P(x) V Q(y)). (Domains are the same and are non-empty).
3. A celebrity at a party is a guest who is known by every other guest at the party but doesn't know any of them.
• Show that there can be at most one celebrity at any party and give an example of a party with no celebrities.
• Show that if there are n guests at a party then the host of the party can identify the celebrity (if there is one) by asking at most 3(n - 1) questions of the following type: Does A know B.
4. Mike and Anne go to a dinner with n other couples. Each person shakes hands with everyone she or he doesn't know. Later, Mike discovers that every one of the remaining 2n + 1 people shook hand with a different number of people. How many people did Anne shake hands with? (Provide and argument.)