CS1231

Tutorial 2
Logic

It is recommended that you explore the available resources in the library and on the Internet to answer
the questions. This tutorial must be prepared in writing. Make two copies of your answers: one for you
and one for the tutor. Bring your lecture notes to the tutorial.

1. Prove that M U IIU is a theorem of the M U system.

2. Prove that one can prove anything (and its contrary) from inconsistent (contradictory) premisses.
3. Prove that ¬p ⇒ (p ⇒ q) ≡ p ∨ ¬p. (Hint: Draw the truth tables of ¬p ⇒ (p ⇒ q) and of p ∨ ¬p.)

4. Prove that ¬p |= (p ⇒ q).

5. Consider the following truth table for the mysterious connective ∇.

p q p∇q
true true false
true false false
false true true
false false false

Write a formula logically equivalent to p∇q with {¬, ∧} only.

6. Prove that a + (a × b) = a + b is a law of Boolean algebra. Use laws from Definition 2.4.2 of the
lecture only. Do not use laws from Proposition 2.4.3 of the lecture or other laws of Boolean algebra.

7. Translate the following statement from English to Predicate Logic. Choose appropriate predicates.
The Universe of Discourse is everything unless otherwise indicated.
1. All even natural numbers are divisible by 2. (The Universe of Discourse is natural Numbers.)
2. Some odd natural numbers are divisible by 3. (The Universe of Discourse is natural Numbers.)
3. All even natural numbers are divisible by 2.
4. Some odd natural numbers are divisible by 3.
5. When someone’s mother is Greek that person is also Greek.
6. Every person has a mother.

8. Let UH = {0, 1}. For each of the following formulae charaterize their models (tell what needs to be
true for the formulae to be true).
1. ∀X (p(X, 0, X))
2. ∀X ∃Y (p(X, Y, 0))
3. ∃Y ∀X (p(X, Y, 0))

9. Consider the following two formulae.

∃X (∀Y p(X, Y ))
∀Y (∃X p(X, Y ))

Translate both formulae in English. Prove that ∃X (∀Y p(X, Y )) |= ∀Y (∃X p(X, Y )). Start by
expressing the two formulae into English.
 CS1231

10. Fitch’s notation is a way of writing proofs using inference rules, in particular with Natural Deduction.
Christian Gottschall from the University of Vienna (Austria) proposes a Java applet to write proofs
in Fitch’s notation for propositional calculus with natural deduction.
(see http://logik.phl.univie.ac.at/c̃hris/gateway/formular-uk-fitch.html.)
The connectives in the applet are: & for ∧, v for ∨, ~ for ¬, -> for ⇒ and <-> for ⇔.
The following rules are available in the applet. Note that there are more rules in the Applet than in
the definition of Natural Deduction in the lecture. Note also that rules with the same name may be
slightly different (see the applet and the website for details).
• &I is conjunction introduction.
• &E is conjunction elimination.
• vI disjunction introduction.
• vE disjunction elimination.
• ~~I double negation introduction.
• ~~E double negation elimination.
• ->E Modus Ponens.
• MT Modus Tollens.
• DS disjuntive syllogism.
• The following rules were not seen in the lecture but are valid because of the facts that (p ⇒
q) ∧ (q ⇒ p) ≡ p ⇔ q and that (p ⇒ q) ∧ (q ⇒ p) ≡ q ⇔ p.
– <->I biconditional introduction
– <->E biconditional elimination
• ->I conditional introduction (Note this is a discharge rule used to complete some proofs).
• ~I and ~E are used to complete a proof by contradiction. The last line must be an explicit
contradiction. For instance p ∧ ¬p.
• Premisse sets the hypotheses.
• A is the rule of assumption to make assumptions during a proof.
For example we show that A, A ⇒ B, ¬B ∨ C ` C

1. A Premise
2. A -> B Premise
3. ~B v C Premise
4. B 2,1->E
5. ~~B 4~~I
6. C 3,5DS

For example we show that A ⇒ ¬B, B ∨ C ` A ⇒ C

1. A -> ~B Premise
2. B v C Premise
3. A * A
4. ~B * 1,3->E
5. C * 2,4DS
6. A -> C 3-5->I

For example we show that A ⇒ ¬B, B ∨ ¬C, C ` ¬A

1. A -> ~B Premise
2. B v ~C Premise
3. C Premise
4. A * A

Page 2
 CS1231

5. ~B * 1,4->E
6. ~C * 2,5DS
7. C & ~C * 3,6&I
8. ~A 4-7~I

Let us consider the following classic tale and logic puzzle of Knights and Knaves.
Knights never lie and knaves always lie. You meet two individuals, Aglovale and Bedwyr.
Aglovale tells you that Bedwyr is a knight.
Bedwyr tells you that one of them is a knight and that one of them is a knave but does not tell
you which one is what.
Who is what?
It can be formalized into propositional logic as follows.
• A stands for “Aglovale is knight”.
• B stands for “Bedwyr is knight”.
• Aglovale tells you that Bedwyr is a knight. If he is a knight then he tells the truth otherwise
he lies.
– A ⇒ B.
– ¬A ⇒ ¬B.
• Bedwyr tells you that one of them is a knight and that one of them is a knave. If he is a knight
then he tells the truth otherwise he lies.
– B ⇒ (A ⊕ B).
– ¬B ⇒ ¬(A ⊕ B).
• (A ⇒ B) ∧ (¬A ⇒ ¬B) ∧ (B ⇒ (A ⊕ B)) ∧ (¬B ⇒ ¬(A ⊕ B)).

Prove that Aglovale and Bedwyr are knaves. Write a proof in Fitch’s notation as in Christian
Gottschall’s applet. You may use his online applet to write the proof if you have access to it.
Namely, show that:

A ⇒ B, ¬A ⇒ ¬B, B ⇒ ((A ∨ B) ∧ (¬A ∨ ¬B)), ¬B ⇒ ((¬A ∨ B) ∧ (A ∨ ¬B)) ` (¬A ∧ ¬B)

(We have used the facts that (A ⊕ B) ≡ ((A ∨ B) ∧ (¬A ∨ ¬B)) and that ¬(A ⊕ B) ≡ ((¬A ∨ B) ∧ (A ∨
¬B)). You may want to double check that these are correct as an additional subsidiary exercise.)
The proof starts with:

1. A -> B Premise
2. ~A -> ~B Premise
3. B -> ((A v B) & (~A v ~B)) Premise
4. ~B -> ((~A v B) & (A v ~B))Premise

Page 3