ICS 6B
Fall 2013
Homework 1


Due: Wednesday, Oct 9

Covers Sections 1.1-1.4

  1. Which of the following problems are propositions?
    1. Have a nice day.
    2. The soup is cold.
    3. The patient has diabetes.
    4. The light is on.
    5. It's a beautiful day.
    6. Do you like my new shoes?
    7. Bummer!

  2. Define the following propositions: Translate the following Engilsh sentence into logical expressions using the definitions above:
    1. Not getting a job is a sufficient condition for me to return to college.
    2. If I return to college then I won't get a job
    3. I am not getting a job, but I am still not returning to college.
    4. I will return to college only if I won't get a job
    5. There's no way I am returning to college.
    6. I will get a job and return to college.

  3. Which of the following conditional statements are true and why?
    1. If pigs could whistle then donkeys could fly
    2. If 5 is a prime number then pigs can whistle.
    3. Pigs can whistle if and only if donkeys can fly
    4. If pigs can not whistle, then 5 is a prime number.
    5. If 5 is not a prime number, then pigs can whistle.

  4. Give the inverse, converse and contrapositive for each of the following statements:
    1. It it rains, I will bring my umbrella.
    2. If you get your homework done, you can go out tonight.
    3. If the patient takes the medication, then he will have some side effects.

  5. The values for the propositional variables p, q, r, s, are determined as follows: Determine the truth values for the following propositions:
    1. p ∨ ¬(q ∧ s)
    2. (r → q) ∨ ¬p
    3. (s ↔ ¬q) ∨ (p ∧ ¬q)
    4. (r ∧ p) → s
    5. p ∧ q ∨ s

  6. Give a truth table for the following propositions:
    1. (p → q) ∧ (q → p)
    2. p ∧ (¬p ∨ q)
    3. (p → ¬r) ∨ (r ∧ q)

  7. You land in on an island in which all of the inhabitants are knights or knaves. Knights always tell the truth and knaves always lie. Arthur and Merlin are inhabitants of the island. You would like to determine whether each is a knight or a knave depending on statements that they make. Can you tell who is who from the following information?
    1. Arthur says: we are both knaves.
    2. Arrthur says: we are the same. Merlin says: we are different kinds.
    3. Arthur says Merlin is a knave. Merlin says that neither he nor Arthur are knaves.

  8. Show whether the following logical expressions are tautologies, contradictions or neither.
    1. (p ∨ q) ∨ (q → p)
    2. (p → q) ↔ (p ∧ ¬q)
    3. (p → q) ↔ p

  9. Use truth tables to show that the following pairs of expressions are logically equivalent.
    1. p ↔ q and (p → q) ∧ (q → p)
    2. ¬(p ↔ q) and ¬p ↔ q
    3. p → q and ¬p ∨ q

  10. Below are several proofs showing that two logical expressions are logically equivalent. Label the steps each proof with the law used.
    1. (p → q) ∧ (p ∨ q)
      (¬p ∨ q) ∧ (p ∨ q)
      (¬p ∧ p) ∨ q
      F ∨ q
      q

    2. (¬p ∨ q) → (p ∧ q)
      ¬(¬p ∨ q) ∨ (p ∧ q)
      (¬¬p ∧ ¬q) ∨ (p ∧ q)
      (p ∧ ¬q) ∨ (p ∧ q)
      p ∧ (¬q ∨ q)
      p ∧ (T)
      p

    3. (p → q) ∧ (p → r)
      (¬p ∨ q) ∧ (p → r)
      (¬p ∨ q) ∧ (¬p ∨ r)
      ¬p ∨ (q ∧ r)
      p →(q ∧ r)

  11. Prove that the following pairs of logical expressions are logically equivalent by applying the laws of logic.
    1. ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q
    2. p ∨ (p ∧ q) and p. (Actually you can use a truth table for this one.)

  12. Give a logical expression with variables p, q, and r that is true only if p and q are false and r is true.

  13. Consider the following pieces of identification a person might have in order to apply for a credit card: Write a logical expression for the requirements under the following conditions.
    1. The applicant must present either a birth certificate, a drivers license or a marriage license.
    2. The applicant must present any two of the following forms of identification: birth certificate, drivers license, marriage license.
    3. Applicant must present either a birth certificate or both a drivers license and a marriage license.

  14. Find a logical expression whose truth table is the table below:
    p q r ????
    T T T F
    T T F F
    T F T T
    T F F T
    F T T F
    F T F F
    F F T T
    F F F F