The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 2
6. 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.
7. (a)
(b)
(c)
(d)
Not equivalent:
PQ
¬P ⇒ Q
P ⇒ ¬Q
00 01 10 11
100 111 010 011
011 010 111 100
We see that the columns for the two implications are different. Not equivalent:
XX
PQ
¬P ⇒ Q
Q ⇒ ¬P
00 01 10 11
100 111 010 011
011 111 010 100
Equivalent:
Equivalent:
XX
PQ
¬P ⇒ Q
¬Q ⇒ P
00 01 10 11
100 111 010 011
100 010 111 011
PQ
(P ⇒ Q) ⇒ P
00 01 10 11
01000 01100 10011 11111
(e) and (f): the pair in (e) equivalent; but the pair in (f) are not equivalent:
XX
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:
(h) Equivalent:
8. The formula is equivalent to P .
9. We see that the columns for P and for (P ⊕ Q) ⊕ Q are identical:
PQR
P ⇒ (Q ⇒ R)
Q ⇒ (P ⇒ R)
(P ⇒ Q) ⇒ R
000 001 010 011 100 101 110 111
01010 01011 01100 01111 11010 11011 10100 11111
01010 01011 11010 11011 01100 01111 10100 11111
01000 01011 01100 01111 10010 10011 11100 11111
PQR
(P ∧ Q) ⇒ R
P ⇒ (Q ⇒ R)
000 001 010 011 100 101 110 111
00010 00011 00110 00111 10010 10011 11100 11111
01010 01011 01100 01111 11010 11011 10100 11111
PQR
(P ∨ Q) ⇒ R
(P⇒R) ∧ (Q⇒R)
000 001 010 011 100 101 110 111
00010 00011 01100 01111 11000 11011 11100 11111
0101010 0111011 0100100 0111111 1000010 1111011 1000100 1111111
PQ
(P ⊕ Q) ⊕ Q
00 01 10 11
00000 01101 11010 10111
2
10. Even with three variables the truth table is manageable, so let us construct it. (1A) (1B) (2)
PQR
P ⇔ (Q⇔R)
(P ⇔ Q) ⇔ R
P ∧Q∧R ∨ ¬P ∧¬Q∧¬R
000 001 010 011 100 101 110 111
00010 01001 01100 00111 11010 10001 10100 11111
01000 01011 00110 00101 10010 10001 11100 11111
011 000 000 000 000 000 000 110
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) ̸|= (2), because cases like 1 0 0 that make (1) true but (2) false. Similarly, (2) ̸|= (1), because the case 0 0 0 makes (2) true but (1) false.
11. Card 3 cannot be red, because red cannot lie, and Card 3 says it is the joker. So suppose Card 2 is red. Then Card 1 is black and Card 3 is the joker. But then Card 1 actually speaks a truth, which cannot happen. So we conclude that Card 1 is the red card. It follows that Card 3 is the joker and Card 2 is black.
12. There is no contradiction at all. The formula is true if (and only if) P is false. False implies anything. 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.)
13. 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.
(b) Suppose F ⇔ G is valid. That means we find a t in each row of the truth table for F ⇔G. ButwegetatforF ⇔GiffthevaluesforF andGagree,thatis,eitherboth 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.
1We 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.
3
14. 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.
15. Clearly the columns for P ⇔ Q and for ¬P ⇔ ¬Q are identical.
16. Yes, correct. You will want to check that with the truth tables.
17. The formula is 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.
18. Let us draw the truth tables. (a)
⇑
Hence satisfiable, and in fact valid (all 1). (b)
⇑
Hence satisfiable (at least one 1), but not valid (not all 1). The truth table shows the
formula is equivalent to ¬Q. (c)
⇑
Hence not satisfiable (and so certainly not valid). 4
PQ
P⇔Q
¬P⇔¬Q
00 01 10 11
010 001 100 111
10110 10001 01010 01101
PQ
P ⇔ ((P ⇒ Q) ⇒ P)
00 01 10 11
0101000 0101100 1110011 1111111
PQ
(P ⇒ ¬ Q) ∧ ((P ∨ Q) ⇒ P)
00 01 10 11
0110100010 0101001100 1110111011 1001011111
PQ
((P ⇒ Q) ⇒ Q) ∧ (Q ⊕ (P ⇒ Q))
00 01 10 11
01000001010 01111010011 10011000100 11111010111