Plan
School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 2
12–14 August 2020
This is the week when you need to get through Grok modules 2 and 3, if you have not already done that. Don’t fall behind! We will often provide more exercises than can possibly be covered in a tutorial. That is so that those who want more practice can have that. Exercises that say “drill” will tend to cover old ground, rather than introduce new ideas.
The exercises
6. If any good questions or thoughts came up as you worked with Grok, now is a good time to share them. We have a question about list types. What is the type of f defined below? Is it well-typed? Did somebody forget the square brackets in the last equation? Explain the function’s behaviour in English.
f [] = 0 f [x] = x fy =42
7. For each of the following pairs, indicate whether the two formulas have the same truth table.
(a) ¬P ⇒Q and P ⇒¬Q (b) ¬P ⇒Q and Q⇒¬P (c) ¬P ⇒Q and ¬Q⇒P
(d) (P ⇒Q)⇒P and P
(e) P ⇒(Q⇒R) and Q⇒(P ⇒R) (f) P ⇒(Q⇒R) and (P ⇒Q)⇒R
(g) (P ∧Q)⇒R and P ⇒(Q⇒R)
(h) P ∨Q⇒R and (P ⇒R)∧(Q⇒R)
ˇ
P
8. Find a formula that is equivalent to (P ∧ ¬Q) ∨ P but simpler, that is, using fewer symbols.
9. Recall that ⊕ is the “exclusive or” connective. Show that (P ⊕ Q) ⊕ Q is equivalent to P .
11 1 Ol
10. ShowthatP⇔(Q⇔R)≡(P⇔Q)⇔R. Thistellsusthatwecouldinsteadwrite
P⇔Q⇔R (1)
without introducing any ambiguity. Mind you, that may not be such a good idea, because many people (incorrectly) tend to read “P ⇔ Q ⇔ R” as
P , Q, and R all have the same truth value (2) __
Show that (1) and (2) are incomparable, that is, neither is a logical consequence of the other.
三人心八QR 吣R
阷心 R
R
BJ
CI.C3
CI B
11. Three playing cards lie face down on a table. One is red, one is black, and one is the joker. On the back of each card is written a sentence:
JC2
33J
Card 1 Card 2 Card 3
The red card has a true sentence written on its back and the black card has a false sentence. Which card is red, which is black, and which is the joker?
12. Consider the formula P ⇒ ¬P . Is that a contradiction? Can a proposition imply its own negation?
13. Let F and G be propositional formulas. What is the difference between ‘F ≡ G’ and ‘F ⇔ G’ — do we really need both? Show that F ≡ G iff F ⇔ G is valid.
14. By negating a satisfiable proposition, can you get a tautology? A satisfiable proposition? A contradiction? Illustrate your affirmative answers.
15. (Drill.) Recall that ⇔ is the biimplication connective. Show that (P ⇔ Q) ≡ (¬P ⇔ ¬Q).
16. (Drill.) Is this claim correct: (P ∧ Q) ⇔ P is logically equivalent to (P ∨ Q) ⇔ Q? That is,
do we have
((P ∧ Q) ⇔ P ) ≡ ((P ∨ Q) ⇔ Q) ?
17. (Drill.) Find a formula equivalent to P ⇔ (P ∧ Q) but simpler, that is, using fewer symbols.
18. (Drill.) For each of the following propositional formulas, determine whether it is satisfiable, and if it is, whether it is a tautology:
(a) P ⇔((P ⇒Q)⇒P)
(b) (P ⇒¬Q)∧((P ∨Q)⇒P)
(c) ((P ⇒Q)⇒Q)∧(Q⊕(P ⇒Q))
Card 3 is the joker!
Card 1 is black!
I am the joker!
KeepOdds Tin圢 Int KeepOdds
keepOdds x xD
l oddx I even ㄨ
Othernays to Use tilt
List comprehension
keepOdds xs
to
0 truth argument 王 propositional formula
x
KeepOdds xs
invalid Tautology
all truth argument Q mak E true e.g.PV
Contradiction
def def
false
Q make 王 true we say 0 is a modelfor更
PSatifiable.io
making 王 true
able in Unsatifī
eg.PE
all 0 make王
王 is a logical consequenceofformula 4 41 王 if all model for 4 are models for 王
makes 4 true then 0 make王 true
if
modesfor 4
lm.net 到 014 are logically equivalenty
4 both011 4 and怍中
0 is a model for中计 0 is a modelfor4 P PM Q VP
101
PiIHPist.me