Assignments for Math 300 

 

♦Please note that your instructor is likely to modify these assignments during the term. If you choose to make a hard copy then the hard copy will, of course, not be correct after modifications are made 

♦The order in which we will cover the sections in the text is reflected in the assignments given below. 

♦Many of the problems in the following list will appear verbatim on exams. Some problems will have to be modified for the exams, but working through the problems is the best way to prepare for the exams. Some problems are optional. Avoid skipping any non-optional problems, since these problems are more likely to appear on exams. 

♦The assignments are from Smith, Eggen and St Andre's   A Transition to Advanced Mathematics, Sixth Edition. 

♦When we write 2* we are referring to the parts of problem 2 that are marked with a star in the book including the parts that are marked with a solid or a non-solid star. 

 

 

Section 

Problems 

1.1 

1(a-i), 2*, 3*, 4*, 5, 6, 8(a-c), 9, 10*, 11, 12 

1.2 

1*, 2, 3(a-d), 4(a-h), 5(a-f), 7, 8(a-e), 9(a-b), 10, 11, 12, 13(a-d)  

1.3 

1*, 2*, 3, 4, 5(a-c), 5(f-k), 6, 7*, 8, 10 

Logical 

Equivalences 

Using only the logical equivalences from the first part of our formula sheet translate the following logical expressions to T. Supply reasons for each step of your translation. If your instructor has a mistake on any of these problems then you must supply a counterexample. 

 

1. p implies `or`(p, q)  

2.   

3.   

4.  `and`(p, p implies q) implies q 

 

Using only the logical equivalences from the first part of our formula sheet to derive the LHS of each equivalence starting with the RHS. (If you prefer to start with the LHS then you should derive the RHS.) Supply reasons from the logical equivalences for each step of your translation. If your instructor has a mistake on any of these problems then you must supply a counterexample. 

5. `and`(`∼`(`or`(`∼`(`or`(p, q)), `∼`(`or`(p, r)))) implies `or`(p, `and`(q, r)), `or`(p, `and`(q, r)) implies `∼`(`or`(`∼`(`or`(p, q)), `∼`(`or`(p, r))))) 

6.   (special case of resolution) 

7. `and`((`and`(p, r) implies q) implies (r implies (p implies q)), (r implies (p implies q)) implies (`and`(p, r) implies q))  (direct proof of implication) 

8. `and`((`or`(p, r) implies q) implies `and`(p implies q, r implies q), `and`(p implies q, r implies q) implies (`or`(p, r) implies q))  (proof by cases) 

 

Logic Proofs 1 

Supply a proof with each line of the proof numbered and each line having a justification for each of the following five problems. Use any of the logic laws from the first two sections of our logic laws sheet. If your instructor has a mistake on any of these problems then you must supply a counterexample. 

1. Hypotheses:   ;  Conclusion:  `or`(p, q) 

2. Hypotheses:    ; Conclusion:   

 

3. Hypotheses:    ; Conclusion:  `and`(b, c) 

4. Hypotheses:  `or`(a, b), a implies c ; Conclusion:  `or`(b, c) 

5. Hypothesis: ; Conclusion: D 

 

Supply a counterexample to show that the conclusion does not follow from the given hypothesis. Be careful to show that each hypothsis is true and the conclusion is false for your counterexample. If your instructor has a mistake on any of these problems then you must supply a proof(which could be truth table) that the conclusion follows from the given hypothesis. 

 

6. Hypotheses:    ; Conclusion:  r 

7. Hypotheses:    ; Conclusion: B  (⊻ is XOR since your instructor doesn't know how to type the symbol in the book at this point. 

8. Hypothesis: `xor`(`xor`(p, q), r)  ; Conclusion: `xor`(p, `xor`(q, r))     (associativity of XOR) 

9. Hypothesis: `and`(`xor`(p, q), r)  ; Conclusion: `xor`(`and`(p, r), `and`(q, r))     (distributivity of AND over XOR) 

Logic Proofs 2 

Supply a proof using direct proof of implication with each line of the proof numbered and each line having a justification for each of the following five problems. Use any of the logic laws from the three sections of our logic laws sheet. If your instructor has a mistake on any of these problems then you must supply a counterexample. 

1. Hypotheses:   ;  Conclusion:  q⇒ ∼r 

 

2. Hypotheses:  b implies c  ; Conclusion:   

 

3. Hypotheses:  `or`(p, q) implies r, r implies `and`(t, s)  ; Conclusion:  p implies t    

 

Supply a proof using direct proof of implication and contraposition with each line of the proof numbered and each line having a justification for each of the following five problems. Use any of the logic laws from the three sections of our logic laws sheet. If your instructor has a mistake on any of these problems then you must supply a counterexample. 

1. Hypotheses:   ;  Conclusion:  q⇒ ∼r 

 

2. Hypotheses:  b implies c  ; Conclusion:   

 

3. Hypotheses:  `or`(p, q) implies r, r implies `and`(t, s)  ; Conclusion:  p implies t   

 

Supply a counterexample to show that the conclusion does not follow from the given hypothesis. Be careful to show that each hypothsis is true and the conclusion is false for your counterexample. If your instructor has a mistake on any of these problems then you must supply a proof that the conclusion follows from the given hypothesis. 

 

7. Hypotheses:    ; Conclusion:  q implies r 

8. Hypotheses:  `∼`(`and`(A, B)), D implies B, D implies C, `or`(`or`(A, B), C)   ; Conclusion:   

1.4 

1(page 29), 2, 3(a-b), 4, 5, 7*, 8, 9(a,b,d), 10, 11 

1.5 

1(a,e), 3(c,d,e,f), 4*, 6(a,b), 7b, 9, 10,  12(a-d) 

1.6 

1(a-h), 2b, 5(a,b,c), 8(a,b,c,f,g) 

2.1 

1*, 2*, 3*, 4*, 5(all), 6*, 7*, 9*, 10*, 14, 18, 19(a-e, h,i) 

2.2 

1*,2*, 3*, 4*, 5*, 10(a,c,e), 11c, 12(a,c), 13(all), 14*, 17(a,b,d,e,i,j) 

2.3 

1*, 1d, 2*, 4(all), 5, 6*, 7*, 8b, 8c, 11*, 19*, 20(a,b,c,d,f)  

2.4 

2, 5(b-e), 6(all), 8(a,b,e,k,o, t), 9(a,c), 15(a,b,c,d,e,f) 

2.5 

1,2,5(a,b,c,d), 6d 

 

1. Prove using strong induction that any restaurant bill of $n, n≥5, can be paid exactly using only $2 and $5 bills. 

2. Prove using regular induction that any restaurant bill of $n, n≥5, can be paid exactly using only $2 and $5 bills. 

3. Prove that every integer greater than 27 can be written as the linear combination 5a+8b where a and b are nonnegative integers. 

 

4. Define y[n] = `+`(`*`(6, `*`(y[`+`(n, `-`(1))])), `-`(`*`(8, `*`(y[`+`(n, `-`(2))])))) for `>=`(n, 2)  , y[0] = 2   , y[1] = 6  . 

Show using induction that if y[n] is as defined above then y[n] = `*`(`^`(2, n), `*`(`+`(`^`(2, n), 1))) for all `>=`(n, 0) . 

5. Define `+`(y[`+`(n, 2)], y[n]) = `*`(`^`(n, 2)) for all `>=`(n, 0)  , y[0] = 0  ,  y[1] = -`/`(1, 2)  . 

Prove using induction  (or disprove) that y[n] = `+`(`*`(`/`(1, 2), `*`(`^`(n, 2))), `-`(n))  . 

6. Define `+`(y[`+`(n, 2)], y[n]) = `*`(`^`(n, 2)) for all `>=`(n, 0)  , y[0] = 0  ,  y[1] = 1  . 

Prove using induction  (or disprove) that for all `>=`(n, 0) y[n] = `+`(`*`(`^`(n, 2)), `-`(n))  . 

 

7. Prove that every natural number `>`(n, 1) can be expressed as a product of primes, . 

8. Use the well ordering principle to prove that every natural number `>`(n, 1) has a prime factor. 

9. Use strong induction to prove that every natural number `>`(n, 1) has a prime factor. 

10. Prove that if `in`(n, nonnegint) then their exists an odd natural number m and a nonnegative integer k such that n = `*`(`^`(2, k), `*`(m))  . 

3.1 

1b,3b, 6(a,c,e), 8(a,c,e,g,i), 9(b,d,g), 10(a,d,g,j,m), 11(a-f), 13(a,b,c,d), 20(a,b,d) 

3.2 

1(a,c,e,f,h,j,k), 2(a,b,c,d,e,f,h), 3, 4(a,c,d), 5(a,b,c,d), 6(a,b), 7(b,c,d,e,f,g,h),8(a,b), 16(a,d)   

3.3 

 

3.4 

 

4.1 

 

4.2 

 

4.3 

 

4.4 

 

4.5 

 

5.1 

 

5.2 

 

5.3