CmSc 180 Discrete mathematics

Homework 03, due section A: 02/05 , section DM: 02/06, by 5 pm

1.  Represent as “if-then” sentences the following sentences:

Example:

Tom is a student or Tom is a broker

Let A = Tom is a student, B = Tom is a broker

The logical expression of the sentence is: A v B

We know that P → Q = ~P V Q

Therefore A v B = ~A → B = ~B → A

Therefore the sentence “Tom is a student or Tom is a broker” is equivalent to

1) If Tom is not a student then Tom is a Broker

2) If Tom is not a broker then Tom is a student

a. We have to take the bus now or we have to wait 3 hours for the next bus

b. Tom is on team A or Peter is on team B

c. You should have obtained 2 as an answer to this problem or you have not solved the problem correctly

2.  Represent as “if-then” sentences the negations of the following sentences:

Example:

They were unsure of the address but they didn't telephoned

Let A = They were unsure of the address, B = they telephoned

The logical expression of the sentence is: A Λ ~B

By De Morgan's laws ~( A Λ ~B) = ~A v B

By the equivalence P → Q = ~P v Q, we have ~A v B = A → B

Therefore the negation of the sentence is:

If they were unsure of the address they should have telephoned

a. We attended the seminar but we didn't get extra credit

b. This polygon is a triangle and the sum of its interior angles is 180 °

c. A new hearing is not granted and payments are due by the end of the month.

3.  Complete the logical equivalences

P Λ P =

P V P =

P V ~P =

P Λ ~P =

P V T =

P Λ T =

P V F =

P Λ F =

P Λ (P V Q) =

P V (P Λ Q) =

P V (P Λ ~Q) =

De Morgan’s Laws:

~( P V Q) =

~( P Λ Q) = Q

4.  For each conditional below write its contrapositive, converse, inverse , disjunctive representation and negation. If necessary, apply De Morgan's laws.

contrapositive / converse / inverse / Disjunctive repr. / negation
P → Q
~P → Q
~P → ~Q
P → ~Q
(P Λ Q ) → R
P → (Q Λ R)
(P v Q) → R
P → (Q v R)
P → (~R Λ ~Q)

5.  Give direct proof of the following statement: The sum of three consecutive integers is divisible by 3

6.  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 the 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?

Hint: see the solution of Sherlock Holmes problem at

http://faculty.simpson.edu/lydia.sinapova/www/cmsc180/LN180_Johnsonbaugh-07/L07-problems.htm

7.  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. Fist: 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

Hint: If you read carefully the statements, you will find that two of them are certainly false, and they will show you the answer.

8.  Some of the arguments below are valid by universal modus ponens or universal modus tollens, others are invalid and exhibit the converse or the inverse error. Represent the arguments in predicate logic (using appropriate predicates and the quantifiers " and $ ). For each argument state whether it is valid or invalid. If valid determine the inference rule (MP or MT), if invalid determine the type of the error (converse or inverse)

a. All young people do outdoor sports.

Helen does outdoor sports

\Helen is young

b. Senior students have to take a capstone class

Peter is a senior student

\Peter has to take a capstone class

c. Young people do outdoor sports.

Peter is not young

\Peter does not do outdoor sports

d. Honest people pay their taxes

Tom is not honest

\Tom does not pay his taxes

e. Honest people pay their taxes

Tom does not pay his taxes

\ Tom is not honest