Discrete Mathematics Answers

The following exercises relate to inhabitants of an island on which there are three kinds of people: knights who always tell the truth,knaves who always lie, and spies who can either lie or tell the truth. You encounter three people,A,B, and C. You know one of these people is a knight, one is a knave, and one is a spy. Each of the three people knows the type of person each of other two is. For each of these situations, if possible, determine whether there is a unique solution and determine who the knave, knight, and spy are. When there is no unique solution, list all possible solutions or state that there are no solutions.
(a)A says “I am the knave”,B says “I am the knave”, and C says “I am the knave”.
b)A says “I am the knight”,B says “A is not the knave”, and C says“B is not the knave”.
(c)A says “I am not the spy”,B says “I am not the spy”, and C says“A is the spy”.

The following exercises relate to inhabitants of the island of knights and knaves created by
Smullyan, where knights always tell the truth and knaves always lie. You encounter two people,A and B.Determine, if possible, what A and B are if they address you in the ways described. If you cannot determine what these two people are, can you draw any conclusions?
(a)A says “At least one of us is a knave” and B says nothing.
(b)A says “If I am a knight, then so is B” and B says nothing.(c)A says “We are both knights” and B says “Either A is a knight, or I am a knight, but not both”.

1. Build up the operation tables for group G with orders 1, 2, 3 and 4 using the elements a, b, c, and e as the identity element in an appropriate way.
2. i. State the Lagrange’s theorem of group theory.
ii. For a subgroup H of a group G, prove the Lagrange’s theorem.
iii. Discuss whether a group H with order 6 can be a subgroup of a group with order 13 or not. Clearly state the reasons.

An explorer is captured by a group of cannibals. There are two types of cannibals: those who always tell the truth and those who always lie. The cannibals will barbecue the explorer unless he can determine whether a particular cannibal always lies or always tells the truth. He is allowed to ask the cannibal exactly one question.
(a) Explain why the question “Are you a liar?” does not work.
(b) Find a question that the explorer can use to determine whether the cannibal always lies or always tells the truth.

5. Let C(x, y) be the statement “x is a friend of y,” where the domain for x and y consists of all people.
Use quantifications to express each of the following statements.
a) Everyone is a friend of everyone.
b) Not everyone is a friend of someone.
c) Someone is not a friend of someone.
d) There is a friend of John.
e) Mary is not a friend of everyone.


6. Let P(x, y) be the statement “x dislike y”, where the domain for x is all students and the domain for y
consists of all subjects. Express each of these quantifications in English.
a) ∀x∃y P(x, y)
b) ∃x∃y ¬P(x, y)
c) ¬∀x∀y P(x, y)
d) ∀x P(x, Mathematics)
e) ∃y ¬ P(Maria, y)

Let P(x) be the statement “x likes subject mathematics,” where the domain for x consists of all
students. Express each of these quantifications in English.
a) ∃

Determine whether each of these functions from [a,b,c,d] to itself is one-to-one.
(a) f(a) = b, f(b) = a, f(c) = c, f(d) =d
(b) f(a) = b, f(b) = b, f(c) = d, f(d) = c

Draw the graph of the function f(x) = 3x
2 + 1 from the set of real numbers to the set
of real numbers.

Draw the graph of the function f(n) = 3n + 1 from the set of integers to the set of integers.

Draw the graph of the function f(n) = 1 - n
2
from the set of integers to set of integers.