Discrete Mathematics Fall 2023

Note

The room of my exercise session has changed. From now on it takes place in CHN F42.

I teach the exercise class on Mondays at 16:15 in CHN F42. As the semester progresses, I will upload summaries of my classes here. The summaries are not official course material, meaning they are not being checked by the lecturer. I cannot guarantee the correctness of them.

These are all the important websites for the course in one spot:
Course website
Exercise sheets and submission
Lecture script
Lecture script (tablet version)

This was my cheat sheet for the exam:
Cheat sheet

Week 1

Summary

Priority Rating

  • 1.6: similar questions frequently appear in the exam
  • 1.4: computing a truth table
  • 1.1, 1.2, 1.3, 1.5: introductory exercises

Week 2

Summary

Priority Rating

  • 2.3: same as 1.6
  • 2.1, 2.2: basic properties of formulas
  • 2.5: getting an understanding of formulas of predicate logic
  • 2.4, 2.6: challenge exercises

Week 3

Summary

Priority Rating

  • 3.1, 3.2, 3.3: get practice writing predicate logic formulas

I do not recommend solving the other exercises as part of your exam preparation. They are supposed to illustrate the various proof patterns, but some of them are rather difficult. I suggest looking at the master solution and making sure that you understand all the proof patterns.

Week 4

Summary

Priority Rating

  • 4.2, 4.3, 4.4, 4.5, 4.6, 4.7: all this exercises are great exam preparation
  • 4.1: very atypical exercise

Week 5

Summary

Priority Rating

  • 5.1, 5.2, 5.3 b), 5.4, 5.5: great exam preparation
  • 5.3 a): improves your understanding of relation proofs
  • 5.6: challenge exercise

Week 6

Summary

Priority Rating

  • 6.1, 6.2: good practice for set theory short questions
  • 6.5, 6.7 a), b), c): countability appears in almost every exam
  • 6.3, 6.4: practice relation and function proofs
  • 6.6, 6.7 d): challenge exercises

Week 7

Summary

Priority Rating

  • 7.1, 7.2, 7.3, 7.4 a), b), 7.5, 7.6, 7.7, 7.8: all of the exercises are great practice for the number theory part of the exam
  • 7.4 c): very laborous exercise

If you do not manage to solve 7.8, make sure to take a look at the master solution and memorize the result from 7.8 a), as it is useful in many CRT exam exercises.

Week 8

Summary
Note: This week, only tasks 8.3 a) and 8.4 c) give bonus points.

Priority Rating

  • 8.1: good algebra warm-up
  • 8.2, 8.3: proving elementary properties of groups
  • 8.4 a): algebra short question practice
  • 8.6: understand isomorphisms better
  • 8.4 b): proof with an interesting trick
  • 8.7: see an example of a non-integer group
  • 8.4 c), 8.5: challenge exercises

Week 9

Summary

Priority Rating
Some of you told me they would be interested in a “priority rating” of the exercises. Of course, your ambition should be to solve all exercises. But you may not always find the time to do that. So here it goes (ordered in descending priority):

  • 9.2 a), b): essential exam preparation
  • 9.4, 9.5, 9.6: great practice to get comfortable with proofs of ring properties and also very good exam preparation
  • 9.7: a ring exercise that is more abstract, can be a little tricky
  • 9.1, 9.3: also a little tricky, will deepen your understanding of DH and RSA
  • 9.2 c): challenge exercise

Week 10

Summary
Finite Field Calculator

Priority Rating
This week, a lot of the exercises are highly exam relevant. It is ok, if you do not manage to solve all of them. However, remember them for when you study for the exams. The exercises are again ordered in descending priority.

  • 10.1, 10.2 a), 10.3, 10.4, 10.5: essential exam preparation, try to solve all of them
  • 10.6: application of polynomials over finite fields, checks your understanding
  • 10.2 b), 10.7: challenge exercises

Week 11

Summary

Priority Rating

  • 11.6, 11.7: great warm-up exercises, recap fundamental concepts of propositional logic
  • 11.2, 11.4, 11.5: typical exam exercises
  • 11.1, 11.3: recap of DH and error-correcting codes

Week 12

It would be great if you could participate in the poll about the structure of the last exercise session if you intend to visit it. I am open to suggestions from your side.

Poll
Summary

Priority Rating

  • 12.4, 12.5, 12.6: proofs using the semantics of predicate logic appear in almost every exam
  • 12.1: essential preparation for resolution calculus exercises
  • 12.2: short exercise, but the notion of a free variable is important when devising interpretations
  • 12.3: checks your understanding of the semantics of predicate logic

Week 13

Summary

Priority Rating

  • 13.1: warm-up
  • 13.2, 13.5, 13.6, 13.7 a): typical exam exercises
  • 13.7 b), c): three-star exercises, but are not as difficult as they seem
  • 13.3, 13.4: fun exercises:)