CS计算机代考程序代写 Haskell /Users/billy/gits/moc-2021/tutes/week02.dvi

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