/Users/billy/gits/moc-2021/tutes/week02.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Tutorial Week 2
2–6 August 2021
Content: types, Haskell, propositional logic, truth tables, validity & satisfiability
The exercises
T2.1 Given any two types, a and b, we can form the type, a -> b, of functions with input type
a and output type b. So, -> takes two types and makes a new type (it’s a binary operation
on types). So then what is a -> b -> c? Should we interpret it as (a -> b) -> c or
a -> (b -> c)? What’s the difference?
(i) Explain the difference between functions of type (a -> b) -> c and functions of type
a -> (b -> c)
(ii) How many different ways can you interpret a -> b -> c -> d by bracketing differently?
T2.2 If we have a function f :: a -> (b -> c) 1, it has input type a and output type b -> c.
However, notice that we can view it as if it were a two-input function, the first input of type
a and the second of type b, and output type c. To feed two inputs x :: a and y :: b into
f, we apply first apply f to x to get f x :: b -> c, and then feed y into that function, f x,
to get (f x) y :: c. Continuing the same pattern, write the type of a function we can view
as a multi-input function in the same way.
(i) three inputs of types a, b, and c, output type d
(ii) two inputs of types a -> b and c, and output type d
(iii) four inputs of types a -> (b -> (c -> d)), a, b, c, and ouput type d
(iv) one input of type a -> b, and output type c -> d
(v) two inputs of types a and b, and output type c -> d
Which of these types are the same?
T2.3 For each pair of formulas, write down and compare their truth tables. In which rows (if any)
are they different?
(i) ¬P ⇒Q and P ⇒¬Q
(ii) ¬(P ∧ ¬Q) and P ⇒Q
(iii) (P ∧Q)⇒R and P ⇒ (Q⇒R)
(iv) P ⇒ (Q⇒R) and (P ⇒Q)⇒R
T2.4 Write down the meanings of the words satisfiable, valid, unsatisfiable and non-valid. Explain
why any given propositional formula must have exactly two of these properties, and describe
the following propositional formulas using these terms.
(i) P ∨Q
(ii) P ∧ ¬P
(iii) ((P ⇒Q)⇒ P )⇒ P
(iv) (P ∧ ¬P )⇒ P
If you finish early: work on questions from Problem Set 2 (from the week 2 module on Canvas)
1
We write t::T to say t is a term of type T.