Here are some answers for the exercises.

2. All examples quantify over the natural numbers.

(a.) Take A(x) = "x is even" and B(x) = "x > 10". To show that this is false, we just have to find an example x where A(x) is true, and B(x) is false. My example is x = 6.

(b.) Take A(x) = "x > 10" and B(x) = "x > 5". To show that this is true, we have to argue that every x that is greater than 10 is also greater than 5. This is indeed the case.

3. All examples quantify over the natural numbers.

(a.) Take A(x) = "x is even" and B(x) = "x is odd". To show that this is false, we have to argue that there are no x that canbe even and odd at the same time. In other words, we have to argue that for all x, x is either not even or not odd. This is indeed the case.

(b.) Take A(x) = "x > 10" and B(x) = "x is odd". To show that this is true, we just have to find an example x where A(x) is true, and B(x) is also true. My example is x = 13.

4. We don't see this formula so often because it does not say anything interesting. There are two cases.

• Either A(x) is always true for any x, in which case the formula is overly complicated, and could just as well be written as ∃x : B(x).

• Or A(x) is false for some x. In this case, the whole formula is simply true! To see why, you have to realize that for the formula to become true, we just have to find one x such that A(x) -> B(x) is true. If A(x) is false, this implication is always true (look at the truth table for implication).

5. (a.) ~p   is the same as   p -> false.

(b.) p \/ q   can be written as   ~p -> q. And this is the same (by using the equivalence above) as   (p -> false) -> q.

(b.) p /\ q   can be written as   ~(p -> ~q). And this is the same (by using the equivalences above) as   (p -> (q -> false)) -> false.

(c.) p <-> q   can be written as   (p->q) /\ (q->p). And this is the same (by using the equivalence above) as   ((p->q) -> ((q->p) -> false)) -> false.

6. (a.)

a	b	c	median(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

(b.) We can see that median(a,b,c) is true precisely when at least two out of {a,b,c} are true. And thus: median(a,b,c) = (a/\b) \/ (b/\c) \/ (a/\c).

(c.) This is a formula that is equivalent, but smaller: (b /\ (a \/ c)) \/ (a/\c). (There may be a smaller one, you tell me!)

7. (a.) This is the same as ~p <-> q and also the same as p <-> ~q.

(b.) This is the same as p <-> q.

(c.) This is the same as q -> p.

8. (a.) implication is not commutative: false->true is true, but true->false is false.

implication is not commutative: (false->false)->false is false, but false->(false->false) is true.

(b.) equivalence is both commutative and associative. (Look at the truth tables to convince yourself.)

9. (a.) Yes. This is the definition of equivalence in terms of implication. (Look at the truth tables to convince yourself.)

(b.) Yes. This is case-split ("falluppdelning"). (Look at the truth tables to convince yourself.)

(c.) No. If p=false and q=true, the hypothesis is true but the conclusion is false.

(d.) Yes. (Look at the truth tables to convince yourself.)

(e.) No. If p=false and q=false, the hypotheses are true but the conclusion is false.

10. (a.) Yes. If we know ∀ x : (A(x) -> B(x)) then we also know A(a) -> B(a). So, if we then also know A(a), we definitely know B(a).

(b.) Yes. If we know ∀ x : (A(x) -> B(x)) then we also know A(a) -> B(a). So, if we then also know ~B(a), we also know ~A(a). (If A(a) were true, then B(a) would have to be true too!)

(c.) No. For example, if A is always false and B is always true, the hypotheses are true but the conclusion is false.