Page 45 - Discrete Mathematics and Its Applications

24 1 / The Foundations: Logic and Proofs

saw both Smith and Jones with Cooper the day of the whose favorite drink is mineral water (which is one of the
killing and that either Smith or Jones must have killed favorite drinks) given these clues: The Englishman lives
him. Can you determine who the murderer was if in the red house. The Spaniard owns a dog. The Japanese
a) one of the three men is guilty, the two innocent men man is a painter. The Italian drinks tea. The Norwegian
are telling the truth, but the statements of the guilty lives in the first house on the left. The green house is
man may or may not be true? immediately to the right of the white one. The photogra-
b) innocent men do not lie? pher breeds snails.The diplomat lives in the yellow house.
33. Steve would like to determine the relative salaries of three Milk is drunk in the middle house. The owner of the green
coworkers using two facts. First, he knows that if Fred house drinks coffee. The Norwegian’s house is next to the
is not the highest paid of the three, then Janice is. Sec- blue one. The violinist drinks orange juice. The fox is in
ond, he knows that if Janice is not the lowest paid, then a house next to that of the physician. The horse is in a
Maggie is paid the most. Is it possible to determine the house next to that of the diplomat. [Hint: Make a table
relative salaries of Fred, Maggie, and Janice from what where the rows represent the men and columns represent
Steve knows? If so, who is paid the most and who the the color of their houses, their jobs, their pets, and their
least? Explain your reasoning. favorite drinks and use logical reasoning to determine the
34. Five friends have access to a chat room. Is it possible to correct entries in the table.]
determine who is chatting if the following information is 39. Freedonia has fifty senators. Each senator is either honest
known? Either Kevin or Heather, or both, are chatting. or corrupt. Suppose you know that at least one of the Free-
Either Randy or Vijay, but not both, are chatting. If Abby donian senators is honest and that, given any two Free-
is chatting, so is Randy. Vijay and Kevin are either both donian senators, at least one is corrupt. Based on these
chatting or neither is. If Heather is chatting, then so are facts, can you determine how many Freedonian senators
Abby and Kevin. Explain your reasoning. are honest and how many are corrupt? If so, what is the
35. A detective has interviewed four witnesses to a crime. answer?
From the stories of the witnesses the detective has con- 40. Find the output of each of these combinatorial circuits.
cluded that if the butler is telling the truth then so is the
cook; the cook and the gardener cannot both be telling the a) p
truth; the gardener and the handyman are not both lying;
and if the handyman is telling the truth then the cook is
lying. For each of the four witnesses, can the detective de- q
termine whether that person is telling the truth or lying?
Explain your reasoning. b) p
36. Four friends have been identified as suspects for an unau- p
thorized access into a computer system. They have made
q
statements to the investigating authorities. Alice said
“Carlos did it.” John said “I did not do it.” Carlos said 41. Find the output of each of these combinatorial circuits.
“Diana did it.” Diana said “Carlos lied when he said that
I did it.” a) p
a) If the authorities also know that exactly one of the q
four suspects is telling the truth, who did it? Explain r
your reasoning.
b) If the authorities also know that exactly one is lying,
who did it? Explain your reasoning. b) p
37. Suppose there are signs on the doors to two rooms. The
sign on the first door reads “In this room there is a lady, q
and in the other one there is a tiger”; and the sign on the
second door reads “In one of these rooms, there is a lady, p
and in one of them there is a tiger.” Suppose that you r
know that one of these signs is true and the other is false.
Behind which door is the lady? 42. Construct a combinatorial circuit using inverters,
∗ 38. Solve this famous logic puzzle, attributed to Albert Ein- OR gates, and AND gates that produces the output
stein, and known as the zebra puzzle. Five men with (p ∧¬r) ∨ (¬q ∧ r) from input bits p, q, and r.
different nationalities and with different jobs live in con- 43. Construct a combinatorial circuit using inverters,
secutive houses on a street. These houses are painted dif- OR gates, and AND gates that produces the output
ferent colors. The men have different pets and have dif- ((¬p ∨¬r) ∧¬q) ∨ (¬p ∧ (q ∨ r)) from input bits p,
ferent favorite drinks. Determine who owns a zebra and q, and r.