CSCI/Math 2112, Discrete Structures I, Section 1 Fall 2005 Peter Selinger

### Section 1, MWF 11:35-12:25

 Logic is the hygiene the mathematician practices to keep his ideas healthy and strong. - Hermann Weyl (1885 - 1955)

### Course Information

 See the updated Course Information Sheet.

### Announcements

 Final Marks (posted Dec 21). The final exam has been marked; the marks, as well as your as yet (unofficial) course marks are on WebCT. Marking: All problems on the final exam were okay, except problem 5 (proving the correctness of a "while" loop), which went badly. I calculated your marks with and without taking problem 5 into account, and took whichever mark was higher. I also dropped the lowest homework and the lowest quiz. Viewing your final exam: I am away until January 12; you are welcome to see your final exam after that date. Thanks to everybody for making this a great course, and have a great holiday! -- P. Selinger

1. Sep 19 1.1-3 [WebCT]
2. Sep 26 2.1 N/A
3. Oct 7 2.2-3 [WebCT]
4. Oct 12 2.4 N/A
5. Oct 17 3.1-5 [WebCT]
6. Oct 24 3.6-7, 4.1-3 N/A
7. Oct 31 5.1-3 N/A
8. Nov 7 3.8, 4.5 [WebCT]
9. Nov 14 4.4, 8.1, 8.2 N/A
10. Nov 27 9.1-4 N/A

### Homework Assignments

Due Homework suggested Tutorial problems Answers Marks
1. Sep 23 1.1 #44, 46; 1.2 #4, 15, 20(g); Handout 1 #1, 4(1-5). 1.1 #38, 41-43, 49; 1.2 #5-8, 12, 16-20(a-f); 1.3 #6-11, 22-23; Handout 1 #2-3, 5. [ps, pdf] [WebCT]
2. Sep 30 Handout 1 #6. Prove in natural deduction: 1.3 #42; Handout 2 #19, 31, 33, 38, 50 Handout 2, all problems [ps, pdf] [WebCT]
3. Oct 7 Handout 2 #30, 36, 43, 53; 2.1 #6, 18, 25, 28. Handout 2; 2.1 #5, 7, 13, 22. [ps, pdf] [WebCT]
4. Oct 17 2.3 #20, 40; Handout 4 #1-6. Handout 4 [ps, pdf] [WebCT]
5. Oct 21 Handout 3 #1 (f,h,j,k,q) Handout 3 [ps, pdf] [WebCT]
6. Nov 2 3.1 #6; 3.2 #19; 3.3 #26; 3.4 #18; 3.5 #13. Ch. 3.1-6 [ps, pdf] [WebCT]
7. Nov 4 Handout 5 #1,5; 4.2 #12; 4.3 #25. Handout 5 #2-4 [ps, pdf] [WebCT]
8. Nov 14 5.1 #25; 5.2 #4, 17; 5.3 #4, 16, 17. Chapter 5 [ps, pdf] [WebCT]
9. Nov 23 Handout 6 #1; 4.5 #2, 7, 9. Program Correctness Proofs [ps, pdf] [WebCT]

### Handouts

 Handout 1: Translation and statement algebra (Sep 14): [ps] [pdf]. Handout 2: Rules of natural deduction (Sep 23): [ps] [pdf]. Handout 3: Natural Deduction for Quantifiers (Oct 7): [ps] [pdf]. Handout 4: Problems for Predicate Logic (Oct 7): [ps] [pdf]. Handout 5: Problems for Induction (Oct 28): [ps] [pdf]. Handout 6: Rules for Program Correctness Proofs (Nov 14): [ps] [pdf]. Handout 7: Program Correctness Proof Example (Nov 18): [ps] [pdf].

### Supplemental Materials (web only)

 Worked-out natural deduction examples (Sep 28, updated Sep 29): [ps] [pdf].

To Peter Selinger's Homepage:
Peter Selinger / Department of Mathematics and Statistics / Dalhousie University
selinger@mathstat.dal.ca / PGP key