22 Assignments W06Homework Assignments for Math 22 will be posted on this page during the quarter.
Assigned problems are from the textbook Discrete Mathematics, by R. Johnsonbaugh, 6th edition, unless it is clearly indicated that some of the problems are assigned from the accompanying discrete Mathematics Workbook by J. Bush, rather than the text.
Assignments consist of reading the appropriate section in the textbook as well as doing the assigned problems.
Section 1.1 Introduction to Symbolic Logic:
1,5,6,9,10,11,12,15,16,17,20,21,22,23,24,28,29,50,51,52,53,55,56
Also use the laws of logical equivalence on the handout (or page 24 in workbook or on website) to show that the following equivalences hold. See solutions page for links to answers. (Don't use truth tables this time - you already used truth tables when you did it following the instructions in the text.) Be sure to use the proper order of precedence of operations.
20. [(not p or not q) or p] is a tautology
21. [(p or q) and not p] is equivalent to [not p and q]
22. [(p and q) and not p] is a contradiction
23. [(p and q) or (not p or q)] is equivalent to [not p or q]
24. [(p amd q) or (r and not p)] is equivalent to [not (q and p)]
Section 1.2 Conditional and Biconditional:
1, 3, 4, 7, 8, 9, (do 8 and 9 for 1, 3, 4,7 only)
10 through 15, 28 through 31,
33, 34, 35, The statement Today is Monday proposition p. The text has an error and shows two statements lettered q but none lettered p.
38, 41 through 50
Section 1.3 Quantified Statements:
From Textbook
7, 9 through 15, 18(for 12 through 15 only)
19, 22 through 25. 33, 34, 35, 39, 41
also, from Workbook, page 35&36: 21, 22, 23, 24
Section 1.4 : Nested Quantifiers
16 through 39
See solutions page to links to answers
Section 1.5 : Valid Forms of Argument
31, 32, 34, 35, 38, 40, 41, 49, 50, 51, 53, 54
Optional: IF you need practice determining if arguments are valid or are having difficulty remembering the basic valid forms of argument, try problems 59 to 64 for extra pactice.
If you have the workbook and are looking for outlines, examples or additional practice problems, this material is in chapter 4 of the workbook.
Section 1.5 : Direct Proof
For your direct proofs, use the definitions of even, odd, and rational that were on the chalkboard in class on Friday and we used in class on Monday
7,9,10,11,12
For problem 12, if you need help getting started, there is a similar proof in the text in section 1.5 using minimum instead of maximum.
Also write a direct proof of the following theorem:
"The product of any two rational numbers is a rational number": which in "if then" form is
For all real numbers r and s, if r and s are rational numbers, then rs is a rational number.
If you want to check your answer when you have done this proof, the proof of this theorem can be found as a worked example in chapter 4 of the workbook.
Section 1.5 : Direct Proof using Cases
20, 22, 25, 26, 27
The answers to the assigned problems in this group that do not have answers in the text will get posted on the website, with a link through the Math 22 solutions page.
#21 is an important result used throughout mathematics.
#21 is NOT assigned because even through it appears to be very similar to #20, it is harder.
In case you try to prove #21 even though it was not assigned, a proof will be posted with the solutions to the assigned homework above. If you are interested, you can probably find other proofs of #21 on the web by searching for "The Triangle Inequality"
Section 1.5 : Direct Proof of Biconditional Theorems
The textbook does not have any homework problems for biconditional theorems, so prove the two relatively easy biconditional theorems given below. Remember that to prove a biconditional theorem, you need to prove an "if p then q" statement and its converse "if q then p", meaning the proof will have 2 parts.
Prove: For all integers n, -n is even if and only if n is even
Prove: For all integers n, -n is odd if and only if n is odd
The second theorem is a little (not much) harder than the first, because it will require more algebraic manipulation to get your result in the form of an odd number:
2(integer)PLUS 1 rather than in the form 2(integer) minus 1
2(integer) minus 1 is "almost" what you need to show but not quite.
Section 1.5 : Indirect Proof
Includes proof by contradiction and proof by contraposition
Prove by contraposition: For all integers n, if n^2 is even, then n is even.
Prove by contraposition: For all integers m and n, if mn is odd, then m and n are odd.
Proof by contradiction: The sum of a rational number and an irrational number is irrational
Proof by contradiction problems from the text: 14, 15, 17, 19
THE FOLLOWING TWO PROOFS were assigned on Thursday TO BE COLLECTED FRIDAY Distributed on blue half sheet handout. They will be graded.
DUE FRIDAY JANUARY 27:
Prove using contraposition:
For all real numbers r and s, if r + s is irrational, then r is irrational or s is irrational
Prove using contradiction:
For all real numbers r and s, if r is rational and s is irrational, then r + s is irrational
(The statement you are asked to prove by contradiction is actually the same as the proof assigned Wednesday:
"The sum of a rational number and an irrational number is irrational")
Section 1.7 Proof by Mathematical Induction for Sums
1, 3, 4, 6, 7, 24
Section 1.7: Proof by Mathematical Induction for Divisibility and Inequalities
14, 17, 21, 22
[(11^n)-1] is divisible by 5 for all integers n >= 1
(2^n) < n! for all integers n >= 4
Section 11.1&11.2 Combinatorial Circuits
11.1: 1-5, 10 - 13
11.2 1-5, 8, 9, 12 -15
Workbook pages 54 & 55, 39 - 45 (69 & 50 optional but fun)
Combinatorial circuits are in chapter 3 of the workbook, for those looking for more practice and review.
Section 2.1 Sets
Homework is from the textbook, but additional practice can be found chapter 1 in the workbook
3,4,12,13,14,16 Union, intersection, set difference
All problems from 1 to 16 are OK to do if you need more practice
17,18,20: Do each Venn Diagram for each of the following 4 situations:
..... (1) A and B intersect, but are not equal and are not subsets of each other.
..... (2) A and B are disjoint (intersection is the null set)
..... (3) B is a subset of A
..... (4) A is a subset of B
25 through 30 Counting elements of sets: Inclusion/Exclusion
32, 33, 34, 36, 57 Cartesian Products
40, 41, 42 Partitions
44, 45, 46, 47
53, 55, 56 Power sets and proper subsets
58 through 64 Prove or disprove set properties
.....Go to Math 10 solutions page to check which are true and which are false.
.....The proofs/disproofs for 58 through 64 will be in the Math 22 binder in the tutorial center.
70 Prove or disprove
71, 72, 74 (just answer, don't need to prove)
Two homework problems were handed out to be collected and graded:
Due Tuesday 2/14.
Seven segment display for a calculator doing arithmetic base 4
Proof by mathematical induction of extension of distributive law for sets ( intersection over union)
Section 2.2
1-5, 10, 12
16, 17, 18 (proof not needed for these problems)
19, 22, 35, 36, 38, 39, 40, 42
Section 3.1
2,5,10,11,13,14,15 basics
19 through 32, 35, 36 properties of relations (reflexive, symmetric, transitive, antisymmetric, partial order)
38 composition
Section 3.2
1,2,3,4
6,7,8 prove or disprove
15, 18, 20 through 23, 27, 28, 29, 31c
Section 3.3
1,2,4,5,6,8,9, 11 through 15, 25, 26, 27
Two problems were handed out on Thurs 2/23 to be collected and graded:
Due Monday 2/27.
PERT diagram and Inclusion/Exclusion diagram with Venn diagram.
Orange half sheet handout.
Extra practice problems were given in class for proofs using Boolean Algebra of sets
Problems: http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/M22SetAlgPractice.gif
Soltuions 1,2,3,4: http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/M22SetAlgPractSol1234.gif
Soltuions 5,6,7: http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/M22SetAlgPractSol567.gif
Soltuions 8: http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/M22SetAlgPractSol8.gif
Soltuions 9: http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/M22SetAlgPractSol9.gif
These will remain posted on the web for a limited time only, so print them out and save them. A hard copy will remain in the binder in the tutorial center for the rest of the quarter.
Section 2.3
Sequences: Problems 4, 6, 8, 10, 12-16, 27, 34, 51 - 58, 76, 77
Strings: 116, 117, 120, 121
Section 6.1
1, 3, 5, 6, 8, 13-16, 20-24, 26, 27, 28, 30, 31, 32, 34-41, 66, 67, 69
Section 6.2
1 through 13, 15, 16, 18
25 through 38, 41, 42, 44, 58 through 66
We are not covering sections 6.3, 6.4, 6.5
Section 6.6
2, 3, 4, 5, 7, 8, 9, 14 through 20, 35 through 44
We are skipping section 6.7 for now and will return to explore the ideas in section 6.7 at a later date.
Section 6.8
1, 2, 3, 24
Section 7.1
1 through 12, 18, 19, 50
Section 7.2
1 through 10
11, 12, 13, 14, 19 using iteration
15, 16, 17, 21, 22 linear homogeneous recurrence relations with constant cofficients
18 and 2O are optional - if you need more practice they are OK - their answers are fractions. The problems after number 27 in the text are more difficult and do not reflect what I will expect you to learn in this course.
The workbook also has examples and practice problems on this topic. They use the name "backtracking" for the method of iteration.
Student group presentations on recurrence relations during the week of March 13 to 17.
Let me know when you are ready - the earlier the better during the week. Presentations should be short.
The list of recurrence relations is on the main Math 22 website, but on Friday March 10 in class I will give each person in each group a more detailed statement of their group problem, information about the problem and about what they need to present. Each student in the group should speak for some part of the presentation.
If you were not assigned to a group, see me to get into a group.
Most of these problems are homework problems from our book, other books or other sources; some of them have resources in our text. Ask me for help if you are stuck or have questions.
Unfortunately, legally, I can not give group members contact information for other group members. Please take a couple of minutes at the start or end of class to get phone and/or email and/or instant message info from your other group members. The tutorial center in our classroom's building is open before and after class every day and is a good place for you to meet. There are tables, whiteboards, and sometimes conference rooms.
Section 8.1
1 thru 5, 8, 9, 11 thru 18, 21, 22, 25, 27, 38, 40, 41, 51
Section 8.2
1 thru 5, 10 thru 17, 22, 24, 25, 28, 29, 30, 35, 36, 38
Section 8.3
1, 3, 6, 9 thru 12, 14, 15, 16
Skip Section 8.4
Section 8.5
1 thru 9, 13, 16
Section 8.6
1 thru 5, 7, 21, 22, 23, 24
if stuck on 23, do 24 first and check your answers in the back of the text)
Skip Sections 8.7 & 8.8
Section 9.1 Trees
1 through 9, 11, 32
Section 9.2 Trees
7 through 15, 17 through 26, 30, 31, 33
Section 9.3 Spanning Trees
7,8,9
If you want to use breadth and depth first algorithms try 1 and 4 because answers are in the book
I will not hold you responsible to know these 2 algorithms for the final exam
Section 9.4 Spanning Trees
1,4
Tentative Problems for Binary Trees
In class on Friday I will specify which problems pertain to the material we actually cover and then will update the problems below to eliminate an inappropriate problems.
Section 9.5 1, 5, 6, 7 Binary Trees
Section 9.6 6, 7, 8, 9, 11, 16 prefix, postfix, infix and order of operations
Section 9.6 1, 3, 5 Preorder, postorder and inorder traversals of a tree
|
|
