/Users/billy/gits/moc-2021/tutes/sol02.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Answers to Tutorial Sheet 2 Exercises
T2.1 (i) Functions of type (a -> b) -> c can only be applied to things of type a -> b, that
is, a function with input type a and output type b. In contrast, functions of type
a -> (b -> c) can only be applied to things of type a. For example, if we have two
functions f :: (a -> b) -> c, g :: a -> (b -> c), and two inputs h :: a -> b,
x :: a, then we can apply f to h to get something of type c, but we cannot apply f to
x. Likewise we can apply g to x to get something of type b -> c, but we cannot apply
g to h. Always pay attention to the bracketing, the first simple type that appears (like
a), is not necessarily the first input type.
(ii) Here are the different types we could form via bracketing.
• a -> (b -> (c -> d))
• a -> ((b -> c) -> d)
• (a -> b) -> (c -> d)
• (a -> (b -> c)) -> d
• ((a -> b) -> c) -> d
Since Haskell interprets the -> operator to be right-associative (so that a -> b -> c
means a -> (b -> c)), we can write the above types in Haskell as follows (notice which
brackets we must keep).
• a -> b -> c -> d
• a -> (b -> c) -> d
• (a -> b) -> c -> d
• (a -> b -> c) -> d
• ((a -> b) -> c) -> d
T2.2 (i) and (v) are identical, and so are (ii) and (iv).
(i) a -> (b -> (c -> d))
(ii) (a -> b) -> (c -> d)
(iii) (a -> (b -> (c -> d))) -> a -> (b -> (c -> d))
(iv) (a -> b) -> (c -> d)
(v) a -> (b -> (c -> d))
Again, here are the least-brackets versions of those types, utilising Haskell’s right-associative
parsing of ->.
(i) a -> b -> c -> d
(ii) (a -> b) -> c -> d
(iii) (a -> b -> c -> d) -> a -> b -> c -> d
(iv) (a -> b) -> c -> d
(v) a -> b -> c -> d
(i) and (v) are identical, and so are (ii) and (iv). Notice that we specified these types in two
different ways. This highlights an equivalence between the idea of returning a function, and
taking another input, in the context of curried functions.
Thinking about the type a -> (b -> (c -> d)) as described in (v), we might think about
defining a function of its type in Haskell like this
f :: a -> (b -> (c -> d))
f x y =
Whereas the specification of a -> (b -> (c -> d)) in (i), sounds like we’d do something
like this
f :: a -> (b -> (c -> d))
f x y z =
We are still producing a function of type c -> d from an x and a y. We are just taking the
definition a step further by introducing the input z for that function of type c -> d.
Since these are defining a function of the same type, the relevance of these two views ((i)
and (v)) on the type is in our usage of f – not in how we define it. Often the second way
(introducing z), makes the definition easier to write, but it might still view and use f as a
function which makes a function (f x) y :: c -> d out of an x :: a and a y :: b.
T2.3 (i) Not logically equivalent:
P Q ¬P ⇒ Q P ⇒ ¬Q
0 0 1 0 0 0 1 1
0 1 1 1 1 0 1 0
1 0 0 1 0 1 1 1
1 1 0 1 1 1 0 0
× ×
(ii) Logically equivalent:
P Q ¬ ( P ∧ ¬Q ) P ⇒ Q
0 0 1 0 0 1 0 1 0
0 1 1 0 0 0 0 1 1
1 0 0 1 1 1 1 0 0
1 1 1 1 0 0 1 1 1
X X
(iii) Logically equivalent:
P Q R ( P ∧ Q ) ⇒ R P ⇒ ( Q ⇒ R )
0 0 0 0 0 0 1 0 0 1 0 1 0
0 0 1 0 0 0 1 1 0 1 0 1 1
0 1 0 0 0 1 1 0 0 1 1 0 0
0 1 1 0 0 1 1 1 0 1 1 1 1
1 0 0 1 0 0 1 0 1 1 0 1 0
1 0 1 1 0 0 1 1 1 1 0 1 1
1 1 0 1 1 1 0 0 1 0 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1
X X
2
(iv) Not logically equivalent:
P Q R P ⇒ ( Q ⇒ R ) ( P ⇒ Q ) ⇒ R
0 0 0 0 1 0 1 0 0 1 0 0 0
0 0 1 0 1 0 1 1 0 1 0 1 1
0 1 0 0 1 1 0 0 0 1 1 0 0
0 1 1 0 1 1 1 1 0 1 1 1 1
1 0 0 1 1 0 1 0 1 0 0 1 0
1 0 1 1 1 0 1 1 1 0 0 1 1
1 1 0 1 0 1 0 0 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1
× ×
T2.4 • A satisfiable formula has at least one truth assignment that makes it true (it can be
satisfied by a truth assignment).
• A valid formula is one which is made true by all truth assignments (it must be satisfied
by any truth assignment).
• An unsatisfiable formula is one which is made false by all truth assignments (it cannot
be satisfied by any truth assignment).
• A non-valid formula has at least one truth assignment that makes it false (it can be
made false by a truth assignment)
Consider the truth table of a propositional formula ϕ.
• If there are some rows of the truth table which make ϕ true and some rows that make
ϕ false, then ϕ is both satisfiable and non-valid. ϕ is not valid, since there are rows
much make ϕ false, and ϕ is not unsatisfiable, since there are rows that make ϕ true.
• If all rows of the truth table make ϕ true, then ϕ is valid and also satisfiable. ϕ is not
non-valid, nor unsatisfiable, since there are no rows which make ϕ false.
• If all rows of the truth table make ϕ false, then ϕ is unsatisfiable and also non-valid. ϕ
is not satisfiable, nor valid, since there are no rows which make ϕ true.
These are the only possibilites for the rows of any truth table. Note that valid is a stronger
property than satisfiable, and unsatisfiable is a stronger property than non-valid.
(i) P ∨Q is satisfiable and non-valid.
(ii) P ∧ ¬P is unsatisfiable and non-valid.
(iii) ((P ⇒Q)⇒ P )⇒ P is valid and satisfiable.
(iv) (P ∧ ¬P )⇒ P is valid and satisfiable.
3