# List of theorems with proofs
# 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. $(n^{th})$ roots of a complex number (slide 21)

**Possible question:**
- State and prove the theorem about the formula for the $(n^{th})$ **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: $(0.5 + 0.5 = 1$) point  
    - Proofs: $(1.5 + 1.5 = 3$) points