MUN Computer Science 1002 - Lab 2 Conditional statements and methods of proof

Review:

• Lectures 6-8.

Vocabulary

• Implication, contrapositive, converse, inverse, iff (if and only if)
• argument, valid/invalid argument, natural deduction, rules of inference, modus ponens, premises, conclusion
• Resolution rule, refutation, CNF

Individual work

Solve each of the following exercises.

1. Let A = "There is a blizzard", B = "MUN is closed".
1. Make English sentences using the propositions above which are equivalent to $A \to B$, using the following English sentence structures. For example, to express $A \to B$ using sentence structure " ... unless ...", you would have to say "MUN is closed unless there is no blizzard".
1. ... is sufficient for ...
2. ... when ...
3. ... follows from ...
4. ... if ...
5. ... implies ...
6. ... is a necessary condition for ...
7. ... only if ...
8. ... whenever ...
2. Now, for the same A and B as above, write in English the converse, inverse, contrapositive and negation (simplified) for each of the following sentences.
1. $A \to B$
2. $A \to \neg B$
3. $B \to A$
3. Now, group together the formulas you wrote above that are equivalent to each other.
4. For each of the groups of formulas above, say which assignments make them true, and which make them false.
2. In the following applications of modus ponens, fill in the blanks to make a valid argument (you might need to first convert some statements into implications); note which are premises and which is a conclusion. To make it non-trivial, insert statements that rely on all other statements in that example to make it a valid argument.

If it is February then it is winter
It is February
-----------------------------------------------------------------------
$\therefore$ ___________________________

If it is dark outside then it must be after 10pm
___________________________
-----------------------------------------------------------------------
$\therefore$ It is not dark outside

Today is either Monday or Friday
On Mondays I have to go to a lecture
___________________________
-----------------------------------------------------------------------
$\therefore$ I have to go to a lecture today

3. Which of the following arguments are valid and which are not? Explain why.
1. If x > 0 then x is divisible by 4. But x is not divisible by 4. Therefore, $x \leq 0$.
2. If there is a blizzard, then MUN is closed. Mun is closed. Therefore, there is a blizzard.
3. If today is Monday, then I have a lecture. Today is Friday (that is, not Monday). Therefore, I don't have a lecture.

Group exercises

For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

Topic 1: CNFs

Convert each of the following formulas into CNF form (an AND of ORs of possibly negated variables). Use the definition of implication, double negation and distributive laws, in particular $(p \wedge q) \vee r \equiv (p \vee r) \wedge (q \vee r)$.
1. $(A \to (\neg B \vee C))$.
2. $C \wedge ((A \wedge \neg B) \to (C \to \neg A))$.
3. $(A \vee \neg B) \to (C \wedge \neg A)$.

Topic 2: Resolution

For each of the following formulas, prove that they are unsatisfiable by giving a resolution refutation. That is, repeatedly use the rule that $(C \vee x)$ and $(D \vee \neg x)$ give $(C \vee D)$, until you derive FALSE (by resolving $(x)$ and $(\neg x)$). Here, $C$ and $D$ are ORs of variables, with some variables possibly negated.

• $(A \vee B) \wedge (A \vee \neg B) \wedge (\neg A \vee B) \wedge (\neg A \vee \neg B)$
• $(\neg B \vee A \vee C) \wedge (\neg A) \wedge (\neg C \vee \neg B) \wedge (B \vee A)$

Topic 3: Natural deduction

Use natural deduction to derive the given conclusion from premises. Write your solution in an argument form (as in question 2). In addition to modus ponens, you might find the following rules useful: 1) from $p$ and $q$, derive $p \wedge q$. 2) From $p \wedge q$, derive $p$ (also can derive $q$). To apply modus ponens, sometimes you need to convert an OR to an implication, or an implication into its contrapositive (technically, modus ponens applied to a contrapositive is called "modus tollens".)

• Premises: $A \to B$, $B \to C$, $\neg C$. Conclusion: $\neg A$.
• Premises: $(A \wedge B \to C)$, $A \vee \neg B$, $B$. Conclusion: $C$

Review after the group exercises

Let $(A \wedge \neg B \to C)$, $(\neg B \to A)$, $\neg B$ be premises, and $C$ be a conclusion

1. Use natural deduction to derive the conclusion from premises.
2. Now, convert all premises from the above argument which are not in CNF form into CNFs
3. Now, check that your argument is valid by showing that negation of "AND of premises imply conclusion" is a contradiction. Hint: use CNF forms for all statements from the previous subquestion, and remember that $\neg (F \to G) \equiv (F \wedge \neg G)$.