CmSc 180 – Discrete Mathematics

Homework 01

Part I with solutions.

Please solve the problems and then check your solutions

  1. Let P and Q be the propositions

P: You drive over 65 miles per hour

Q: You get a speeding ticket

Express each of the following propositions in English:

  1. ~P
  1. P  Q
  1. ~P  ~Q
  1. P  Q
  1. ~P  ~Q
  1. Translate the following sentences into propositional logic. Abbreviate the propositions and predicates as indicated. Do not introduce new propositional variables or predicates.
  1. If the operation succeeds, she will be fine.

P: the operation succeeds

Q: she will be fine

  1. If the operation succeeds and if she follows the doctor's instructions, she will be fine.

P: the operation succeeds

Q: she follows the doctor's instructions

R: she will be fine

  1. If A is a sub-expression of E and C is a sub-expression of A , then C is a sub-expression of E.

P: A is a sub-expression of E

Q: C is a sub-expression of A

R: C is a sub-expression of E

  1. A proposition is called a literal if it is of the form D or ~D.

P: the proposition is called a literal.

Q: the proposition is of the form D.

R: the proposition is of the form ~D.

  1. Neither the fox nor the lynx can catch the hare if the hare is alert and quick.

P: The fox can catch the hare

Q: The lynx can catch the hare.

R: The hare is alert

S: The hare is quick

  1. Show that the expression (A → B) V ~B is a tautology by building its truth table.
  1. Show that the expression (A → B) V ~B is a tautology by representing the conditional as a disjunction and then using the logical equivalences.
  1. Show that the expression ~((A → B) V (B → A)) is a contradiction, using De Morgan’s laws and the equivalence

A → B = ~A V B

  1. Given that P is true, Q is true, and R is false, determine whether each proposition below is true or false
  2. P V Q
  3. ¬ P V Q
  4. P V ¬Q
  5. ¬ P V ¬ (Q V R)
  6. ¬(P V Q) Λ (¬P V R)
  1. Write in English the contrapositive, converse and inverse of the following statements:
  1. If you miss the exam, then you fail the course
  2. Tax rates will be reduced if Anita wins the election
  3. The audience will go to sleep if the chairperson gives the lecture
  1. Write in English the negations of the statements
  1. If you miss the exam, then you fail the course
  2. Tax rates will be reduced if Anita wins the election
  3. The audience will go to sleep if the chairperson gives the lecture

Part II – this is the part that you have to solve and turn in

1. Construct the truth table of each expression below

P / Q / ~P / ~Q / Q  P / ~P  Q / P V ~Q / ~P  ~Q
T / T
T / F
F / T
F / F

2. Write down the following identities (underline the correct answer):

T means TRUE

F means FALSE

P is a proposition that can be either true or false

P v ~P =T F P

P ~P =T F P

P v F =T F P

P  F =T F P

P v T =T F P

P  T =T F P

P v P =T F P

P  P =T F P

  1. Represent the expression P  (Q  R) using only the basic logical operators
  1. Consider the statement: “Tom will not get a promotion if he continues to be late for work and doesn't submit his reports on time.

Let P = Tom gets the promotion

Let Q = Tom is always late for work

Let R = Tom submits his reports on time

using P, Q, and R as defined above, do the following:

a. represent the statement as a logical expression

b. write the contrapositive of the logical expression and its English equivalent

c. write the converse of the logical expression and its English equivalent

d. write the inverse of the logical expression and its English equivalent

e. Write the negation of the logical expression and its English equivalent