CmSc 180 Discrete mathematics

Homework 02, due section A: 01/29 , section DM: 01/30, by 5 pm

  1. Write in English the negations of the following statements:

a. If P is a square, then P is a rectangle

P is a square but P is not a rectangle

b. If today is Thanksgiving then tomorrow is Friday

Today is Thanksgiving but tomorrow is not Friday

c. If x is nonnegative then x is positive or x is 0

x is nonnegative but x is not positive and x is not 0

  1. Re-write the following statements in if-then form in two ways (use the contrapositive of the first if-then form to get the second if-then form)

a. Catching the 8:05 bus is a sufficient condition for my being on time for work

If I catch the 8:05 bus then I will be on time for work

If I am not on time for work then I have not caught the 8:05 bus

b. Having two 45-degrees angles is a sufficient condition for this triangle to be a right triangle

If this triangle has two 45-degrees angles then it is a right triangle

If this triangle is not a right triangle then it does not have two 45-degrees angles

c. Being divisible by 3 is a necessary condition for this number to be divisible by 9

If this number is divisible by 9 then it is divisible by 3

If this number is not divisible by 3 then it is not divisible by 9

d. A necessary condition for this computer program to be correct is having no error messages during translation

If this program is correct then there are no error messages during translation

If there are error messages during translation then the program is not correct

  1. Taking the long view on your education, you go to the Prestige corporation and ask what you should do in college to be hired when you graduate. The Personnel Director replies that you will be hired only if you major in mathematics or computer science, get a B average or better, and take accounting. You do, in fact, graduate as a math major, get a B+ average, and take accounting. You return to Prestige Corporation, make a formal application, and are turned down. Did the Personnel Director lie to you? Explain your answer.

The Director didn't lie to your

Let P be “You are hired”, Q be “ you major in mathematics or computer science, get a B average or better, and take accounting”

The sentence “you will be hired only if you major in mathematics or computer science, get a B average or better, and take accounting. “ is represented as

P only if Q, which is equivalent to P → Q and ~Q → ~P

Thus, if you didn't fulfill any of the requirements then you would not be hired, however nothing is said what should happen if you have fulfilled the requirements.

The Director would have lied to you if P → Q is false, and ~( P → Q) is true

~( P → Q) = P Λ ~Q, i. e. you are hired without fulfilling all the requirements. Since this is not the case, the Director has not lied to you

  1. Write in English the negations of the following statements in if-then form

Hint: By De Morgan's laws, the negation of a conjunction is a disjunction. Since P → Q is equivalent to ~P V Q, any disjunction can be represented in if-then form

a. The security code is entered but the door does not open.

If the security code is entered then the door opens

b. There is an ice storm and classes are canceled

If there is an ice storm classes will not be canceled

  1. Translate in English the following statements

a. x (movie(x) Λ boring(x))

Some movies are boring

b.  x prime(x) → odd(x) V (x = 2)

All prime numbers are either odd or equal to 2.

c.  x elephant(x) → fly(x)

All elephants fly

  1. Represent in predicate logic the following sentences

a. Some books are interesting.

(use book(x) and interesting(x))

 x (book(x) Λ interesting(x))

b. All books written by Dickens are interesting.

(use book(x), written_by_dickens(x) and interesting(x))

 x (book(x) Λ written_by_dickens(x)  interesting(x))

c. No tests are difficult

(use test(x) , difficult(x))

 x (test(x)  ~difficult(x))

d. Cats do not like water

(use cat(x), like_water(x))

 x (cat(x)  ~like_water(x))

e. Some students live in dorms

(use student(x), live_in_dorms(x))

x (student(x) Λ live_in_dorms(x))

f. All students like games

(use student(x), like_games(x))

 x (student(x)  like_games(x))

g. Only integers can be even or odd (for extra credit)

(use integer(x), even(x), odd(x))

 x (even(x) V odd(x))  integer(x)

Explanation: “Only integers can be even or odd “ means that if a number is not an integer, it cannot be even and it cannot be odd, i. e.

 x ~integer(x)  ~(even(x) V odd(x))

The contrapositive of the above statement is:

 x (even(x) V odd(x))  integer(x)