CS计算机代考程序代写 Haskell /Users/billy/gits/moc-2021/problem-sets/ps02.dvi

/Users/billy/gits/moc-2021/problem-sets/ps02.dvi

School of Computing and Information Systems

COMP30026 Models of Computation Problem Set 2

Content: types, Haskell, propositional logic, truth tables, validity & satisfiability

P2.1 In Haskell, the product of two types a and b is a type written (a,b), and its inhabitants are

pairs of the form (x,y), where x :: a and y :: b. Given any function f :: (a,b) -> c,

there is an “equivalent” curried function cf :: a -> (b -> c), with the property that

(cf x) y == f (x,y)

for any x :: a and y :: b. Notice the different ways these functions accept their arguments.

Write a function which takes a function like f as input and produces its curried version. Then

write a function that un-curries a function like cf.

P2.2 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

f y = 42

P2.3 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)

P2.4 Define your own binary connective � by writing out a truth table for P � Q (fill in the

middle column however you like). Can you write a formula with the same truth table using

only P,Q,¬,∧,∨,⇒? Repeat this exercise a few times.

P2.5 How many distinct truth tables are there involving two fixed propositional letters? In other

words, how many meaningfully distinct connectives could we have defined in the previous

question?

P2.6 Find a formula that is equivalent to (P ∧ ¬Q) ∨ P but simpler, that is, using fewer symbols.

P2.7 Find a formula that is equivalent to P ⇔ (P ∧Q) but simpler, that is, using fewer symbols.

P2.8 Find a formula that is equivalent to (¬P ∨Q)∧R using only ⇒ and ¬ as logical connectives.

P2.9 Recall that ⊕ is the “exclusive or” connective. Show that (P ⊕Q)⊕Q is logically equivalent

to P .

P2.10 Consider the formula P ⇒¬P . Is that a contradiction (is it unsatisfiable)? Can a proposition

imply its own negation?

P2.11 By negating a satisfiable proposition, can you get a tautology? A satisfiable proposition?

A contradiction? Illustrate your affirmative answers.

P2.12 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))

P2.13 Complete the following sentences, using the words “satisfiable, valid, non-valid, unsatisfiable”.

(a) F is satisfiable iff F is not

(b) F is valid iff F is not

(c) F is non-valid iff F is not

(d) F is unsatisfiable iff F is not

(e) F is satisfiable iff ¬F is

(f) F is valid iff ¬F is

(g) F is non-valid iff ¬F is

(h) F is unsatisfiable iff ¬F is

P2.14 Show that P ⇔ (Q⇔R) ≡ (P ⇔Q)⇔R. This tells us that we could instead write

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.

P2.15 Let F and G be propositional formulas. What is the difference between ‘F ≡ G’ and ‘F⇔G’ ?

Show that F ⇔G is valid iff F ≡ G.

P2.16 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) ?

P2.17 (Challenge) We can encode a matrix as a list of lists, where each list represents a row of the

matrix. For example, the matrix

1 2 3

4 5 6

7 8 9

would be represented by the list [[1,2,3],[4,5,6],[7,8,9]] :: [[Int]]. Write a function

mytranspose :: [[a]] -> [[a]], which transposes the matrix, i.e. swaps the rows and

columns. For example, the transpose of the above matrix would be.

1 4 7

2 5 8

3 6 9

If you are familiar with matrix multiplication, use mytranspose to write a function

mmult :: [[Int]] -> [[Int]] -> [[Int]]

which multiplies two matrices (assume the inputs are sensible).