/Users/billy/gits/moc-2021/problem-sets/solps02.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Solutions for Problem Set 2
P2.1 curry :: ((a,b) -> c) -> (a -> (b -> c))
curry f x y = f (x,y)
uncurry :: (a -> (b -> c)) -> ((a,b) -> c)
uncurry cf (x,y) = cf x y
P2.2 The function is well-typed: f :: Num a => [a] -> a and all the equations make sense. The
function takes a list of numbers and returns a number, where “number” means element of
some specific numeric type (Int, Integer, Float, Double). The first equation deals with an
input list that is empty, the second deals with any singleton list. The third deals with the
remaining case, that is, a list with more than one element. In the second equation, x gets
bound to a number, of the third, y gets bound to a list (instead of y it would be customary
to use the name xs, to suggest that we have a list (a plurality) of elements.
P2.3 (a) Not 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
X X
We see that the columns for the two implications are different.
(b) Not equivalent:
P Q ¬P ⇒ Q Q ⇒ ¬P
0 0 1 0 0 0 1 1
0 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0
1 1 0 1 1 1 0 0
X X
(c) Equivalent:
P Q ¬P ⇒ Q ¬Q ⇒ P
0 0 1 0 0 1 0 0
0 1 1 1 1 0 1 0
1 0 0 1 0 1 1 1
1 1 0 1 1 0 1 1
U u
(d) Equivalent:
P Q (P ⇒ Q) ⇒ P
0 0 0 1 0 0 0
0 1 0 1 1 0 0
1 0 1 0 0 1 1
1 1 1 1 1 1 1
U u
(e) and (f) : the pair in (e) equivalent; but the pair in (f) are not equivalent:
P Q R P ⇒ (Q ⇒ R) Q ⇒ (P ⇒ R) (P ⇒ Q) ⇒ R
0 0 0 0 1 0 1 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 1 1
0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0
0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 0 1 0
1 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1
1 1 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
U u
X X
Note that the formulas in (e) are both equivalent to (P ∧Q)⇒R, which explains why
the order of P and Q does not matter here.
(g) 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
U u
(h) Equivalent:
P Q R (P ∨ Q) ⇒ R (P ⇒ R) ∧ (Q ⇒ R)
0 0 0 0 0 0 1 0 0 1 0 1 0 1 0
0 0 1 0 0 0 1 1 0 1 1 1 0 1 1
0 1 0 0 1 1 0 0 0 1 0 0 1 0 0
0 1 1 0 1 1 1 1 0 1 1 1 1 1 1
1 0 0 1 1 0 0 0 1 0 0 0 0 1 0
1 0 1 1 1 0 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 0 0 1 0 0 0 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
U u
P2.4 Here’s an example
P Q P � Q
0 0 0 1 0
0 1 0 1 1
1 0 1 1 0
1 1 1 0 1
With this truth table for �, P � Q is logically equivalent to ¬(P ∧Q).
P2.5 There are four rows in the truth table, so that’s 2 choices for each row, which amounts to
2× 2× 2× 2 = 16 possibilities.
P2.6 (P ∧ ¬Q) ∨ P is logically equivalent to P . You can see this by reasoning by cases on the
truth value of P .
2
P2.7 (P ∧Q)⇔ P is logically equivalent to P ⇒Q. This is easily checked with a truth table, but
how can we simplify (P ∧Q)⇔P when we don’t know what it is supposed to be equivalent to?
Well, we can just try. Let us expand the biimplication and obtain (P⇒(P∧Q))∧((P∧Q)⇒P ).
Intuitively, the conjunct on the right is just true, and we can check that with a truth table.
So we have found that the original formula is equivalent to P ⇒ (P ∧ Q), which isn’t any
shorter, but still. We can rewrite the result as (P ⇒P )∧ (P ⇒Q), and now it becomes clear
that all we need is P ⇒Q.
P2.8 (¬P ∨Q) ∧R is logically equivalent to ¬((P ⇒Q)⇒¬R)
P2.9 We see that the columns for P and for (P ⊕Q)⊕Q are identical:
P Q (P ⊕ Q) ⊕ Q
0 0 0 0 0 0 0
0 1 0 1 1 0 1
1 0 1 1 0 1 0
1 1 1 0 1 1 1
U u
P2.10 There is no contradiction at all. The formula is true if (and only if) P is false. The point of
a conditional formula is to make a claim about the scenario where the premise (P ) is true. If
the premise of ⇒ is false, the formula is satisfied. For the same reason, ¬P ⇒P is satisfiable;
it is not a contradiction. But P ⇔¬P is clearly a contradiction. (If you disagree with any
of these statements, draw truth tables.)
P2.11 If you negate a satisfiable proposition, you can never get a tautology, since at least one truth
table row will yield false.
You will get another satisfiable proposition iff the original proposition is not valid. For
example, P is satisfiable (but not valid), and indeed ¬P is satisfiable.
Finally, if we have a satisfiable formula which is also valid, its negation will be a contradiction.
Example: P ∨ ¬P .
P2.12 Let us draw the truth tables.
(a)
P Q P ⇔ ((P ⇒ Q) ⇒ P )
0 0 0 1 0 1 0 0 0
0 1 0 1 0 1 1 0 0
1 0 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1
⇑
Hence satisfiable, and in fact valid (all 1).
(b)
P Q (P ⇒ ¬ Q) ∧ ((P ∨ Q) ⇒ P )
0 0 0 1 1 0 1 0 0 0 1 0
0 1 0 1 0 1 0 0 1 1 0 0
1 0 1 1 1 0 1 1 1 0 1 1
1 1 1 0 0 1 0 1 1 1 1 1
⇑
Hence satisfiable (at least one 1), but not valid (not all 1). The truth table shows the
formula is equivalent to ¬Q.
3
(c)
P Q ((P ⇒ Q) ⇒ Q) ∧ (Q ⊕ (P ⇒ Q))
0 0 0 1 0 0 0 0 0 1 0 1 0
0 1 0 1 1 1 1 0 1 0 0 1 1
1 0 1 0 0 1 1 0 0 0 1 0 0
1 1 1 1 1 1 1 0 1 0 1 1 1
⇑
Hence not satisfiable (and so certainly not valid).
P2.13
(a) F is satisfiable iff F is not unsatisfiable
(b) F is valid iff F is not non-valid
(c) F is non-valid iff F is not valid
(d) F is unsatisfiable iff F is not satisfiable
(e) F is satisfiable iff ¬F is non-valid
(f) F is valid iff ¬F is unsatisfiable
(g) F is non-valid iff ¬F is satisfiable
(h) F is unsatisfiable iff ¬F is valid
P2.14 Even with three variables the truth table is manageable, so let us construct it.
(1A) (1B) (2)
P Q R P ⇔ (Q ⇔ R) (P ⇔ Q) ⇔ R P ∧Q ∧R ∨ ¬P ∧ ¬Q ∧ ¬R
0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1
0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0
0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0
0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0
1 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0
1 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0
1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
U u D
B is a logical consequence of A (we write A |= B) iff B is true for any assignment of variables
which makes A true. So we see that (1) 6|= (2), because cases like 1 0 0 that make (1) true
but (2) false. Similarly, (2) 6|= (1), because the case 0 0 0 makes (2) true but (1) false.
P2.15 The connective ⇔ is part of the language that we study, namely the language of propositional
logic. So A⇔B is just a propositional formula.
The symbol ≡ belongs to a meta-language. The meta-language is a language which we use
when we reason about some language. In this case we use ≡ to express whether a certain
relation holds between formulas in propositional logic.
More specifically, F ≡ G means that we have both F |= G and G |= F . In other words, F
and G have the same value for every possible assignment of truth values to their variables.
The two formulas are logically equivalent.
On the other hand F⇔G is just a propositional formula (assuming F and G are propositional
formulas). For some values of the variables involved, F ⇔G may be false, for other values it
may be true. By the definition of validity, F ⇔G is valid iff it is true for every assignment
of propositional variables in F and G.
We want to show that F ≡ G iff F ⇔G is valid.
(a) Suppose F ≡ G. Then F and G have the same values for each truth assignment to their
variables1. But that means that, when we construct the truth table for F ⇔G, it will
have a t in every row, that is, F ⇔G is valid.
1
We should perhaps be more careful here, because F and G can be logically equivalent without F having the
exact same set of variables as G—can you see how? So we should say that we consider both of F and G to be
functions of the union of their sets of variables.
4
(b) Suppose F ⇔ G is valid. That means we find a t in each row of the truth table for
F ⇔G. But we get a t for F ⇔G iff the values for F and G agree, that is, either both
are f , or both are t. In other words, F and G agree for every truth assignment. Hence
F ≡ G.
You may think that this relation between validity and biimplication is obvious and should
always be expected, and indeed we will see that it carries over to first-order predicate logic.
But there are (still useful) logics in which it does not hold.
P2.16 Yes, (P ∧ Q) ⇔ P ≡ (P ∨ Q) ⇔ Q, and both of these formulas are logically equivalent to
P ⇒Q
P Q ( P ∧ Q ) ⇔ P ( P ∨ Q ) ⇔ Q
0 0 0 0 0 1 0 0 0 0 1 0
0 1 0 0 1 1 0 0 1 1 1 1
1 0 1 0 0 0 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
U u
P2.17 mytranspose :: [[a]] -> [[a]]
mytranspose ([]:_) = []
mytranspose rows = map head rows : mytranspose (map tail rows)
mmult :: [[Int]] -> [[Int]] -> [[Int]]
mmult mA mB = [ map (vmult row) (mytranspose mB) | row <- mA ]
where vmult row col = sum (zipWith (*) row col)
5