Reference no: EM131022644

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.)