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:*