PhD course: Discrete structures and introduction to proofs

Description

The course is an introduction to the discrete math that computer scientists use. It piggybacks on the new undergraduate course "Discrete structures for computer science" given by Jörn Janneck, but goes into more depth and adds material on interactive proof assistants. If you already have taken a course similar to the undergraduate course (see EDAA40), you cannot get full points for this course.

Administrative details

Literature

Textbook: David Makinson: Sets, Logic and Maths for Computing, 2nd addition. It is freely available at the LU network here.

Additional material from EDAA40.

Material on the interactive proof assistant Coq:

Form

Advice on exercises and labs

Concerning the exercises: It will be too much work to do and hand in all the End-of-Chapter exercises. Therefore, it is sufficient to hand in 1/4 of them, including the first subexercise of each. Example: In Chapter 1 there are four End-of-Chapter exercises: 1.1, 1.2, 1.3, and 1.4. Of these you should do:

Advice for doing the exercises in Makinson's book. Try to follow the proofs. If you cannot prove something the way the book does it, try drawing a Venn diagram: Name all the different subsets in the diagram, and try to prove the statement that way. If you cannot do this, try to make an argument for why something is true.

Write your solutions for the Makinson exercises using pen and paper, not on the computer. Take a photo of your solution and email it to the marker, and with copy to Görel.

For the labs, email a zip file with your solution to the marker, and with copy to Görel.

For the Coq exercises: email your solved Coq file to the marker, and with copy to Görel.

All exercises and labs should be handed in by the deadline. All marking should be done within one week. Enter the results into the SAM system (PhD course in Discrete Structures).

If there are unclear things, exercises you could not solve, exercises with interesting solutions, let me (Görel) know, and we can gather the group and discuss.

Schedule

Week 12 (March 21...) Sets.

Week 13 (March 28...) Relations.

Week 14 (April 4...) Functions.

Week 15 (April 11...) To infinity and beyond.

Week 16 (April 18...) Induction and Recursion.

Week 17 (April 25...) Trees and Graphs.

Week 18 (May 2...) Propositional logic.

Week 20 (May 16...) Quantificational logic.

Week 21 (May 23...) Proofs.

Week 22 (May 30...) Coq 1.

Week 23 (June 7...) Coq 2.