COMP 1002 Winter 2019
Homework Assignment # 2
Due: Feb 5, by 10pm
(Type it up and upload on D2L)
YOUR NAME HERE


  1. Resolution [30]
    Give resolution refutations of the following formulas, converting to CNF first, if needed.

    1. $(x \vee \neg y) \wedge (y \vee \neg z \vee \neg x) \wedge (\neg y \vee z) \wedge \neg x \wedge (z \vee x) \wedge (x \vee \neg z \vee y)$

      Solution:

    2. $ ( x_1 \wedge (x_1 \to x_2\wedge \neg x_3) \wedge (x_3 \vee x_4) \wedge (x_4 \vee x_2 \to \neg x_1)$

      Solution:

  2. From argument to proof [40]
    Suppose you are reading a fictional university's password policy, and it says: "You can access university wifi with your phone or your computer by connecting using your university password. You have to change your password after 6 months. For your security, you will be locked out of your account at any time when multiple failed attempts to reconnect are detected". You know that if your phone cannot connect to wifi, it will make multiple failed attempts to reconnect. Similarly, if your computer cannot connect to wifi, will make multiple failed attempts to reconnect. Also, if you change the password, then for a few minutes until you update their wifi both your phone and your computer would not be able to connect to wifi.

    In this question, you need to find out whether there is a way to avoid being locked out if you change your password. Let us name the propositions occurring in this problem as follows:
    $p$: You changed the password
    $q$: You are locked out of your account
    $r$: Your phone can connect to wifi
    $s$: Your computer can connect to wifi
    $t$: There are multiple failed attempts to reconnect

    1. Convert the statements in the paragraph above (both the policy and your knowledge) into logic form using these variable names. For example, the last sentence would become $p \to \neg r \wedge \neg s$.

      Solution:

    2. Use natural deduction to see whether being locked out is unavoidable when you change your password, given these statements. Your proof should consist of several applications of modus ponens and/or transitivity rule (maybe converting $\vee$ to implication or taking a contrapositive of an implication first), and potentially some auxiliary rules listed in the slides.

      Solution:

    3. Now use resolution to verify that your argument in the previous subquestion is correct. Recall that to do that, you will need to write a negation of "AND of premises implies conclusion" (where premises are your formulas from part a)), convert all premises and negated conclusion into CNF form, and do a resolution refutation on the resulting formula.

      Solution:

  3. Complete set of connectives [30]
    Recall that in class we showed that $\neg, \wedge$ form a complete set of connectives (that is, we can encode any truth table by a formula with just $\neg$ and $\wedge$). Consider the set of connectives consisting of just $\to$ and $\oplus$, where $\oplus$ is an exclusive OR connective: $A \oplus B$ is true if and only if $A$ and $B$ have the opposite truth values (one is true and the other one false).

    1. First, show that $\to$, $\oplus$ form a complete set of connectives by showing how to write formulas equivalent to $A \wedge B$ and $\neg A$ using only $\to$ and $\oplus$.

      Solution:

    2. Now, rewrite the formula $(p \wedge \neg q) \to (r \vee p)$ using only $\to$ and $\oplus$. First write $A \vee B$ with only $\to$ and $\oplus$, then use this together with formulas from the previous subquestion to write a formula equivalent to $(p \wedge \neg q) \to (r \vee p)$ using just $\to$ and $\oplus$ as your connectives.

      Solution: