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