Page 44 - Discrete Mathematics and Its Applications

1.2 Applications of Propositional Logic 23

10. Are these system specifications consistent? “Whenever become unhappy if Samir is there, Samir will attend only
the system software is being upgraded, users cannot ac- if Kanti will be there, and Kanti will not attend unless Jas-
cess the file system. If users can access the file system, minealsodoes.Whichcombinationsofthesethreefriends
then they can save new files. If users cannot save new can you invite so as not to make someone unhappy?
files, then the system software is not being upgraded.” Exercises 19–23 relate to inhabitants of the island of knights
11. Are these system specifications consistent? “The router and knaves created by Smullyan, where knights always tell
can send packets to the edge system only if it supports the the truth and knaves always lie. You encounter two people,
new address space. For the router to support the new ad- A and B. Determine, if possible, what A and B are if they
dress space it is necessary that the latest software release address you in the ways described. If you cannot determine
be installed. The router can send packets to the edge sys- what these two people are, can you draw any conclusions?
tem if the latest software release is installed, The router 19. A says “At least one of us is a knave” and B says nothing.
does not support the new address space.”
20. A says “The two of us are both knights” and B says “A
12. Are these system specifications consistent? “If the file
system is not locked, then new messages will be queued. is a knave.”
If the file system is not locked, then the system is func- 21. A says “I am a knave or B is a knight” and B says nothing.
tioning normally, and conversely. If new messages are not 22. Both A and B say “I am a knight.”
queued, then they will be sent to the message buffer. If
the file system is not locked, then new messages will be 23. A says “We are both knaves” and B says nothing.
sent to the message buffer. New messages will not be sent Exercises 24–31 relate to inhabitants of an island on which
to the message buffer.” there are three kinds of people: knights who always tell the
truth, knaves who always lie, and spies (called normals by
13. What Boolean search would you use to look for Web
pages about beaches in New Jersey? What if you wanted Smullyan [Sm78]) who can either lie or tell the truth. You
to find Web pages about beaches on the isle of Jersey (in encounter three people, A, B, and C. You know one of these
the English Channel)? 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
14. What Boolean search would you use to look for Web each of these situations, if possible, determine whether there
pages about hiking in West Virginia? What if you wanted is a unique solution and determine who the knave, knight, and
to findWeb pages about hiking inVirginia, but not inWest spy are. When there is no unique solution, list all possible
Virginia?
solutions or state that there are no solutions.
∗ 15. Each inhabitant of a remote village always tells the truth
24. A says “C is the knave,” B says, “A is the knight,” and C
or always lies.A villager will give only a “Yes” or a “No”
response to a question a tourist asks. Suppose you are a says “I am the spy.”
tourist visiting this area and come to a fork in the road. 25. A says “I am the knight,” B says “I am the knave,” and
One branch leads to the ruins you want to visit; the other C says “B is the knight.”
branch leads deep into the jungle. A villager is standing 26. A says “I am the knave,” B says “I am the knave,” and C
at the fork in the road. What one question can you ask the says “I am the knave.”
villager to determine which branch to take?
27. A says “I am the knight,” B says “A is telling the truth,”
16. An explorer is captured by a group of cannibals. There are
two types of cannibals—those who always tell the truth and C says “I am the spy.”
and those who always lie. The cannibals will barbecue 28. A says “I am the knight,” B says, “A is not the knave,”
the explorer unless he can determine whether a particu- and C says “B is not the knave.”
lar cannibal always lies or always tells the truth. He is 29. A says “I am the knight,” B says “I am the knight,” and
allowed to ask the cannibal exactly one question. C says “I am the knight.”
a) Explain why the question “Are you a liar?” does not 30. A says “I am not the spy,” B says “I am not the spy,” and
work. C says “A is the spy.”
b) Find a question that the explorer can use to determine
whether the cannibal always lies or always tells the 31. A says “I am not the spy,” B says “I am not the spy,” and
truth. C says “I am not the spy.”
17. When three professors are seated in a restaurant, the host- Exercises 32–38 are puzzles that can be solved by translating
ess asks them: “Does everyone want coffee?” The first statements into logical expressions and reasoning from these
professor says: “I do not know.” The second professor expressions using truth tables.
then says: “I do not know.” Finally, the third professor 32. The police have three suspects for the murder of Mr.
says: “No, not everyone wants coffee.”The hostess comes Cooper: Mr. Smith, Mr. Jones, and Mr. Williams. Smith,
back and gives coffee to the professors who want it. How Jones, and Williams each declare that they did not kill
did she figure out who wanted coffee? Cooper. Smith also states that Cooper was a friend of
18. When planning a party you want to know whom to in- Jones and that Williams disliked him. Jones also states
vite. Among the people you would like to invite are three that he did not know Cooper and that he was out of town
touchy friends.You know that if Jasmine attends, she will the day Cooper was killed. Williams also states that he