MUN Computer Science 1002 - Lab 2

Conditional statements and methods of proof

Review:

Vocabulary

 

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", and using sentence structure "... is sufficient for ...", you would say "A blizzard is sufficient for MUN to be closed".
      1. ... if ...
      2. ... implies ...
      3. ... is a necessary condition for ...
      4. ... only if ...
    2. Now, for the same A and B as above, write in English the converse, inverse, contrapositive and negation (simplified) for the sentence $\neg B \to \neg A$.
    3. Now, group together the formulas you wrote above that are equivalent to each other.

  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 Thursday (that is, not Monday). Therefore, I don't have a lecture.

  4. 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)$.

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

Group exercises

For this part of the lab, you will be working in groups of three to solve the following puzzle.

Imagine that it is a nice sunny day in late May, and you have a friend visiting from out of province. Your friend says: "I read yesterday on CBC that people taking boat tours could see a beautiful iceberg not too far away from St. John's, and that it might be visible there from the shore today". Now, you are thinking: if it is not too far from St. John's, it could be at Flatrock, Middle Cove, Petty Harbour or Cape Spear. The tour boats go either from St. John's or from Bay Bulls. The tour boats from St. John's go to Middle cove as well as to Petty Harbour, but not to Flatrock and not to Cape Spear. Tour boats from Bay Bulls may go only to Cape Spear. As the iceberg moves south, it would pass Flatrock, then Middle Cove, then Petty Harbour, then Cape Spear. If it got as far south as Petty Harbour or Cape Spear, it would have been visible from St. John's Signal Hill yesterday, unless it was foggy. If it were visible from Signal hill, that would surely be mentioned in that CBC article, but sounds like it wasn't. It was not foggy at all yesterday.

In this exercise, you will use logic (in particular natural deduction and resolution) to figure out where to take your friend to see the iceberg.

  1. List all propositions in this question that are relevant for finding the iceberg, and give each a name you could use in a formula. For example, you might want to have propositions $p_2:$ "the iceberg was seen from a Bay Bulls tour boat" and $q_4$: "the iceberg is at Cape Spear", but you would not need a proposition for "the iceberg is beautiful".
  2. Using these propositions, write logic formulas for all the relevant facts mentioned above. For example, you might have a formula for "If the iceberg was seen from a Bay Bulls tour boat, then it must be at Cape Spear" as one of the facts, which you would write as $(p_2 \to q_4)$ using propositions from the previous subquestion.
  3. Using rules of natural deduction such as modus ponens, derive from these facts the location of the iceberg. Say to which formulas each rule is applied, and what you derive at each step.
  4. Now let's check your reasoning using resolution refutation. First, convert each premise into CNF form (as well as negation of the conclusion, but the negation of the conclusion is just one proposition). Hint: remember that $A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C)$ for any logic formulas $A, B, C$.
  5. Now, write a CNF formula for "AND of premises AND NOT conclusion".
  6. Finally, do a resolution refutation on the resulting formula to check that your argument was valid

Review after the group exercises

Let $A$ be "Today is weekday", $B$ be "I can stay home all day" and $C$ be "It is the semester break".

Translate the following statements to logic:

  1. Now let two sentences above, together with a translation of "I cannot stay home today", be your premises. Let "It is not the semester break" be your conclusion. 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. Also convert negation of the conclusion to CNF.
  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.