Math 470 Spring ’05

HW #1 Solutions

Section 1.1

1. One possibility: Consider a tree in which each node at level n has n+1 children. So the root has one child, it has 2 children. Each of those children has 3, etc. This tree is finitely branching (each node has a finite number of children) but it is not n-branching for any n.

3. If a node N is at two levels, it has immediate predecessors at 2 different levels. Since neither of these is a predecessor of the other, the predecessors of N are not well-ordered by <T.

4. If N is a node other than the root, it must have a predecessor. If it is at level n and has n predecessors, these are well-ordered by <T and only one of them is an immediate predecessor. If A and B were both immediate predecessors of N, then neither A<t B nor B<t A is true . This violates the well-ordering requirement.

5. By exercise 3, each element exists at a unique level. If x1 <t x2 <t … <t xn and x1=xn, then x1 has two distinct levels.

Section 1.2

1. a) yes

b) no – missing outer ()

c) no – missing outer ()

d) yes

e) no – and ambiguous as to where to insert the inner ()

f) yes

g) no – and incorrect since V has no 1^st operand

h) no and incorrect. Extra )

4. Use exercise 3 and induction.

If a proposition P has a proper initial segment P’, P must be of the form ( not Q) or (Q * R) where * is a binary operation. In the first case, the initial segment P’ is ( or ( not – which each have one ( and no ) or (not Q’ where Q’ is a proper initial segment of Q . P’ has the same number of ) and one more ( than Q’ so it has more ( than ).

Otherwise P’ is P without the final ) and then has one more ( than ).

A similar argument works for (Q * R).

5. One way to do this is to construct the truth table for each proposition and then take the rows with “T”. This gives

a) ( A ^ B ^ C) v (A ^not B ^ C) v ( A ^ not B ^ not C) v (not A ^ B ^ C) v (not A ^ not B ^ C).

b) (A^B ^C) v (A^B^ not C) v (A^ not B ^ not C) v (not A ^ B ^ not C) v (not A ^ not B ^ C) v (not A ^ B ^ not C) v (not A ^ not B ^ not C)

It is also possible to derive shorter forms.

a) (A ^ not B) v C

b) (A^B) v (not A ^ not B) v (not C)

6. We know that { ^, v, not } is adequate. (A v B) is equivalent to not ( not A ^ not B) . So every proposition can be expressed in terms of { ^, not}

8. not A is equivalent to A | A.

A ^ B is equivalent to not (A | B) or (A| B) | (A | B)

10. Every proposition made from A and ^ and v will be true when A is true, as can be shown by induction. Hence not A is not equivalent to any such proposition.

13. A DNF for a proposition that is always false is ( A ^ not A).

14. Consider 2 cases.

a) the case of exercise 13. Both the proposition and (A ^ not A) evaluate to F in every truth table row. So they are equivalent,

b) the case treated in Theorem 2.8. In each T row of the truth table, one of the disjuncts is true and A is true. In the remaining rows, all of the disjuncts are false and A is false. Thus the disjunction and A have the same truth table.