ICS 6B
Fall 2015
Homework 1


Due: Wednesday, Oct 7, 5:30PM

Covers Sections 1.1-1.6

Please make sure to syaple together all the pages of your written homework before putting it in the ICS 6B slot. Also write your student ID number and your name very clearly in the upper right corner of every page. The written portion should be turned into the dropbox labeled "ICS 6B" on the first floor of Bren Hall.
  1. Challenge Activities:
    1. 1.2.1, 1.2.2, 1.2.3
    2. 1.3.1, 1.3.2
    3. 1.6.1

  2. 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!

  3. Define the following propositions: Translate the following Engilsh sentence into logical expressions using the definitions above:
    1. Not getting a job is a necessary 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.

  4. 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 not whistle.

  5. Conditional statement: "If there is a lunar eclipse tonight, I will bring my binoculars."
    1. Give the inverse of the statement
    2. Give the converse of the statement.
    3. Give the contrapositive of the statement.

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

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

  8. 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.

  9. Suppose that p, q, r, s, and t are all propositional variables.
    1. Describe in words when the expression p ∨ q ∨ r ∨ s ∨ t is true and when it is false.
    2. Describe in words when the expression p ∧ q ∧ r ∧ s ∧ t is true and when it is false.

  10. 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

  11. Determine whether the pair of logical expressions are logically equivalent. Prove your answer. If the pair is logically equivalent, then use a truth table to prove your answer.
    1. ¬(p ∨ ¬q) and ¬p ∧ q
    2. ¬(p ∨ ¬q) and ¬p ∧ ¬q
    3. p ∧ (p → q) and p → q
    4. p ∧ (p → q) and p ∧ q

  12. 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)


  13. Use the laws of propositional logic to prove the following:
    1. ¬p → ¬q ≡ q → p
    2. (p → r) ∨ (q → r) ≡ (p ∧ q) → r
    3. ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q

  14. Predicates P and Q are defined below. The domain of discourse is the set of all positive integers. Are the following logical expressions propositions? If the answer is yes, indicate whether the statement is true or false.
    1. P(x)
    2. P(2)
    3. ∀x (Q(x) → ¬P(x))
    4. (∀x Q(x)) ∧ P(x)
    5. P(3) ∧ Q(49)

  15. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse must be the set of all real numbers.
    1. There is a number whose cube is equal to -2.
    2. The square of every number is at least 0
    3. The reciprocal of every number between 0 and 1 is greater than 1.

  16. In the following question, the domain of discourse is a group of people. You can assume that Olga is a particular individual in the group. Define the following predicates: Translate the following English statements into a logical expression with the same meaning:
    1. At least one person was sick yesterday.
    2. No one went to work yesterday.
    3. Olga was sick yesterday, but she went to the gym.
    4. Someone who was sick yesterday went to work.
    5. Everyone who was sick yesterday did not go to work.
    6. Everyone who did not got work yesterday was sick.
    7. Someone who was sick yesterday went to the gym and work.
    8. Everyone who did not go to work or did not go to the gym was sick.

  17. In the following question, the domain of discourse is the set of employees of a company. Define the following predicates as follows: Translate the following logical expressions into English:
    1. ∀x (A(x)→E(x))
    2. ∃x (E(x) ∧ ¬W(x))
    3. ∀x (W(x) → E(x))
    4. ∃x (¬A(x) ∧ E(x))