Computer Science 1002 Winter 2019

Homework Assignment 1
Due: Jan 24, 2019, by 10pm
(Type it up and upload on D2L)

YOUR NAME HERE


  1. Translations [50]

    Consider the following propositions:
    $p$: I do assignments
    $q$: I miss labs
    $r$: I get good marks on the midterm
    $s$: I get an $A$ in this class .

    Using these propositions as definitions of $p$, $q$, $r$ and $s$, answer the following questions.

    a) Write in English a sentence corresponding to $p \wedge \neg q \to r \wedge s$.

    Solution:

    b) Write a contrapositive of the formula in a) (in logic notation), and simplify it by moving negations onto variables using de Morgan's law and double negations rule. Then write an English sentence corresponding to your final (simplified) formula.

    Solution:

    c) Write a negation of the formula in a) (in logic notation), and simplify it until all negations are on variables. Then write an English translation of the resulting formula.

    Solution:

    d) Write a logic formula for "I get $A$ in this class only if I do assignments".

    Solution:

    e) Consider the formula $(p \to r) \wedge (\neg q \wedge r \to s)$. Suppose that you got $A$ in this class, and you did assignments. What values of $r$ and what values of $q$ would make this formula true? List all such pairs of values.

    Solution:

  2. Puzzles [20]

    Recall the island of knights and knaves, where knights never lie, whereas knaves lie always (that is, every statement made by a knight is true, every statement made by a knave is false). You meet two inhabitants of the island (call them Alice and Bob). Suppose that Alice says "Both Bob and I are knights" and Bob says "Alice is a knave". Which of them (if any) is a knight? A knave?

    Solution:

  3. Equivalences [30]
  4. a) Show that $(p \to r) \vee (q \to r)$ is logically equivalent to $(p \wedge q) \to r$ by writing (one common) truth table for both of these formulas, and checking that the columns for$(p \to r) \vee (q \to r)$ and for $(p \wedge q) \to r$ are the same.

    Solution:

    b) Now, show that they are equivalent by applying logical equivalences from the table in lab 1 to both of them until you get the same expression. Hint: remember that $A \to B \equiv \neg A \vee B$.

    Solution: