Discrete mathematics

Syllabus:

1. Mathematical reasoning.

• Propositional logic (syntax, equivalence, deduction).

• Quantification.

• Basic proof methods (direct, contradiction, non-constructive, induction).

• Recursive definitions.

• Integer division.

1. Discrete structures.

• Sets.

• Graphs (coloring, connectivity).

• Trees (undirected, rooted, tree traversals).

• Relations (equivalence, partially ordered sets).

3.-Combinatorial analysis.

• Permutations and combinations (with and without repetition).

• Binomial and multinomial coefficients.

• Pigeonhole principle.

• Inclusion-exclusion principle.

UPF Notes:

• Glossary.

• Syllabus.

• Notes for Topic 1: Logic.

• Notes for Topic 2: Set Theory.

• Notes for Topic 3: Proof Techniques.

• Notes for Topic 4: Integer Division.

• Notes for Topic 5: Induction and Recursion.

Problems:

1. 1-12.

1. 13-24.

1. 25-34.

1. 35, 37-40.

1. 36, 41-46.

1. 47-49, 52-59.

1. 50-51, 60-63, 65, 66, 68, 71 and 72.

1. 64, 67, 69, 70, 73-82.

1. 83-98.

1. 99-101,103-109.

1. 112-116,118-120.

1. 121-125, 127, 128, 131.

1. 132, 133, 135, 136, 139, 140, 142-144.

1. 145-152.

1. 153, 154, 156, 160-162, 167.

1. 155, 157, 163, 164, 166 and 168.

1. 169, 170, 172, 175-178.

1. 182-191.

1. 193, 196, 198, 199, 200, 202, 204, 205, 207 and 208.

1. 209, 212-215.

1. 216, 219, 220, 221 and 230.

1. 233-236 and 238.

1. 241, 242, 244, 252, 254-256.

1. 237, 239, 243, 245, 248, 250, 257, 258, 260 and 261.

Exam 1.

Exam 2.