Solutions for Sample Final Exam

There will be 25 reasonable questions on the exam including the history question.

6. See combinatorial argument from last class or use the binomial theorem argument from earlier classes.

7. True for n=0. The empty set has only itself as a subset.

8. x<=x hence reflexive x<=y and y<=x implies x=y (anti symmetric) but not symmetric x<=y and y<=z implies x<=z

9. no, transitive

10. ACA reflexive

11. f is 1-1 and onto 1-1 f(a(1),b(1))= a(1)+b(1) g(a(2),b(2))=a(2)-b(2) implies a(1)=a(2) b(1)=b(2) onto Take any z in the range there exist a,b in the domain such that z=f(a,b).

12. z=a-b w=a+b a =(z+w)/2 b=(w-z)/2

13. Use a truth table one of the two laws is ~(pVq) <-> ~p and ~q T T T F T F F F T F T F T F F T F T T F T F T F F F F T T T T T

14. Show that ~(AUB) subset (~A int ~B) x el ~(AUB) implies ~(x el AUB) implies ~ (x el A v x el B) implies x el ~A and x el ~ B implies x el ~A int ~B implies x el (~A int ~B) We leave (~A int ~B) subset ~(AUB) to you.

15. 11111 00000 | 10 10 10 10 10 == 11111 0 10 10 11111 00000 & 10 10 10 10 10 == 10 10 10 00 00

16. no! (rule...if...else ... exactly one statement is executed if one of the conditions is true ...then jump to the next line of code following the logical code block.)

17. x>=0, y>=0 implies |x+y|= x +y <= |x| + |y|

18. 51 is not generated, the claim is not true

19. Tells you how fast or how much memory the algorithm uses given an input of size n as n gets very large. This info can be very useful.

20. directed graph - a set of elements called vertices and ordered pairs of these elements called arcs (binary relation). example p->q

undirected graph- a set of elements called vertices and pairs of these elements called edges. example p<->q is an undirected graph

• About this document ...