Discrete Structure 

Question # 37

In the back of an old cupboard you discover a note signed by a pirate famous for his bizarre sense of humor and love of logical puzzles. In the note he wrote that he had hidden treasure somewhere on the property. He listed five true statements (a–e below) and challenged the reader to use them to figure out the location of the treasure.

a. If this house is next to a lake, then the treasure is not in the kitchen.

b. If the tree in the front yard is an elm, then the treasure is in the kitchen.

c. This house is next to a lake.

d. The tree in the front yard is an elm or the treasure is buried under the flagpole.

e. If the tree in the back yard is an oak, then the treasure is in the garage. Where is the treasure hidden?

Solution

p=this house is next to a lake.

q=treasure is not in the kitchen.

r=tree in the front yard is an elm.

s= treasure is buried under the flagpole.

t= tree in the back yard is an oak.

u= the treasure is in the garage.

(p → q) → (1)

(r → ¬q) → (2)

(p) → (3)

(r V   s) → (4)

(t → u) → (5)

(p → q)

(p)

∴q → (6) (From 1&3 by using modus ponens)

(r → ¬q)

(q)

∴¬r → (7) (From 2&6 by using modus tollens)

(r V    s)

(¬r)

∴s →(8) (From 4&7 by using elimination)

Hence:-

   Treasure is buried under the flagpole.

Question # 39

The famous detective Percule Hoirot was called in to solve a baffling murder mystery. He determined the following facts:

a. Lord Hazelton, the murdered man, was killed by a blow on the head with a brass candlestick.

b. Either Lady Hazelton or a maid, Sara, was in the dining room at the time of the murder.

c. If the cook was in the kitchen at the time of the murder, then the butler killed Lord Hazelton with a fatal dose of strychnine.

d. If Lady Hazelton was in the dining room at the time of the murder, then the chauffeur killed Lord Hazelton.

e. If the cook was not in the kitchen at the time of the murder, then Sara was not in the dining room when the murder was committed.

f. If Sara was in the dining room at the time the murder was committed, then the wine steward killed Lord Hazelton.

 Is it possible for the detective to deduce the identity of the murderer from these facts? If so, who did murder Lord Hazelton? (Assume there was only one cause of death.)

Solution

p= Lord Hazelton, the murdered man, was killed by a blow on the

      head with a brass candlestick.

q=Lady Hazelton was in the dining room at the time of the murder.

r= Sara, was in the dining room at the time of the murder.

s= the cook was in the kitchen at the time of the murder.

t= the butler killed Lord Hazelton with a fatal dose of strychnine.

u=the chauffeur killed Lord Hazelton.

v= the wine steward killed Lord Hazelton.

(p) → (1)

(q V r) → (2)

(s → t) → (3)

(q → u) → (4)

(¬s → ¬r) → (5)

(r → v) → (6)

Suppose that the cook was in the kitchen at the time of murder. Therefore:- (s) → (7)

(s)

(s → t)

∴t → (8) (from 7&3 by using modus ponens).

∴We have a contradiction that Lord Hazelton was killed by strychnine and a below on the head. (From 1&8).

∴Supposition that the cook was in the kitchen at the time of murder is false (by contradiction rule).

∴The cook was not in the kitchen at the time of murder. (Negation of Supposition).

∴¬s → (9)

(¬s → ¬r)

∴¬r → (10) (From 5&9 by using modus ponens).

(q V r)

∴q → (11) (From 2&10 by using elimination).

(q → u)

∴u → (12) (From 4&11 by using modus ponens). 

Hence:-

          The chauffeur killed Lord Hazelton.

Question # 40

Sharky, a leader of the underworld, was killed by one of his own band of four henchmen. Detective Sharp interviewed the men and determined that all were lying except for one. He deduced who killed Sharky on the basis of the following statements:

a. Socko: Lefty killed Sharky.

b. Fats: Muscles didn’t kill Sharky.

c. Lefty: Muscles was shooting craps with Socko when Sharky was knocked off.

d. Muscles: Lefty didn’t kill Sharky.

Who did kill Sharky.

Solution

p= Lefty killed Sharky. → (1)

q= Muscles didn’t kill Sharky. → (2)

If muscles didn’t kill sharky then lefty killed sharky.

(q → p) → (3) (From 1&2).

As we know that Lefty didn’t kill the sharky. (From c). It can be written as:-

(¬p) → (4)

Now we slove the equation as follows:-

(q → p)

      (¬p)

∴¬ q → (5) (from 3&4 by using modus tollens).

 Hence:-

            Muscles killed Sharky.