List of theorems with proofs - Spring 2026
This list contains all proof questions that you may be asked in Part 2 of the exam.
Other theorems and statements covered in the lectures can also be asked, but without proof.
Logic
1. Properties of logical operators (10 properties, slide 8)
Possible questions:
- State and prove two properties of the logical operator ‘and’ (∧) learnt. (Any two properties, except the definition.)
- State and prove two properties of the logical operator ‘inclusive or’ (∨) learnt. (Any two properties, except the definition.)
- State and prove the distributive properties of ‘and’ (∧) and ‘inclusive or’ (∨).
- State and prove De Morgan’s laws for ‘and’ (∧) and ‘inclusive or’ (∨).
- State and prove one of the inference rules: the law of contrapositive, modus ponens, or syllogism.
Sets
2. Properties of the subset relation (4 properties, slide 6)
Possible questions:
- State and prove the transitive property of the subset relation.
- State and prove the anti‑symmetric property of the subset relation.
3. Properties of set union and set intersection (5 properties, slide 12)
Possible questions:
- State and prove two properties of set union (any two, except the definition).
- State and prove two properties of set intersection (any two, except the definition).
4. Distributive properties of set union and intersection (slide 14)
Possible question:
- State and prove the distributive properties of set union and set intersection.
5. Properties of set complement (8 properties, including De Morgan’s laws, slide 17)
Possible questions:
- State and prove two properties of set complement (any two, excluding the definition).
- State and prove De Morgan’s laws for sets.
Relations
6. Associativity of composition of binary relations (slide 13)
Possible question:
- State and prove the proposition about the associativity of the composition of binary relations.
7. Inverse of the composition of binary relations (slide 13)
Possible question:
- State and prove the proposition about the inverse of the composition of binary relations.
8. Composition of functions is a function (slide 29)
Possible question:
- State and prove the theorem that the composition of functions is also a function.
9. Composition of injective functions is injective (slide 29)
Possible question:
- State and prove the theorem that the composition of injective functions is also injective.
Complex Numbers
10. Properties of conjugation and absolute value (first 10 properties, slide 14; triangle inequality proof not required)
Possible questions:
- Write down and prove two properties of the conjugation of complex numbers (any two, except the definition).
- Write down and prove two properties of the absolute value of complex numbers (any two, except the definition).
11. Multiplication in polar form (slide 19)
Possible question:
- State and prove the theorem about the formula for multiplying complex numbers in polar form.
- Use a complete sentence when formulating, not just the formula, and refer to the meaning of notation.
12. roots of a complex number (slide 21)
Possible question:
- State and prove the theorem about the formula for the roots of a complex number in polar form.
- Use a complete sentence when formulating, not just the formula, and refer to the meaning of notation.
Combinatorics
13. Permutations without repetition (slide 7)
Possible question:
- State and prove the theorem about the number of permutations without repetition of a finite set.
- Use a complete sentence when formulating, referring to the meaning of notation.
14. Permutations with repetition (slide 11)
Possible question:
- State and prove the theorem about the number of permutations with repetition.
- Use a complete sentence when formulating, referring to the meaning of notation.
15. Variations without repetition (slide 13)
Possible question:
- State and prove the theorem about the number of variations without repetition of a finite set.
- Use a complete sentence when formulating, referring to the meaning of notation.
16. Variations with repetition (slide 15)
Possible question:
- State and prove the theorem about the number of variations with repetition of a finite set.
- Use a complete sentence when formulating, referring to the meaning of notation.
17. Combinations without repetition (slide 18)
Possible question:
- State and prove the theorem about the number of combinations without repetition of a finite set.
- Use a complete sentence when formulating, referring to the meaning of notation.
18. Combinations with repetition (slide 21)
Possible question:
- State and prove the theorem about the number of combinations with repetition of a finite set.
- Use a complete sentence when formulating, referring to the meaning of notation.
19. Binomial theorem (slide 24)
Possible question:
- State and prove the Binomial theorem.
- Use a complete sentence when formulating, referring to the meaning of notation.
20. Properties of binomial coefficients (slide 25)
Possible questions:
- State and prove two properties of the binomial coefficients (any two, except the definition).
- State and prove Pascal’s identity for the binomial coefficients.
Graphs
21. Handshaking theorem (slide 6)
Possible question:
- State and prove the Handshaking theorem (the theorem about the sum of the degrees of all vertices in a graph).
- Use a complete sentence when formulating, referring to the meaning of notation.
Scoring of Proof Questions in the Exam
- Each proof question is worth 4 points in total.
- For one theorem/statement:
- Statement: 1 point
- Proof: 3 points
- For two statements (e.g., two properties):
- Statements: ) point
- Proofs: ) points