Mathematics Discrete Mathematics Syllabus

Discrete Mathematics syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Discrete Mathematics in Mathematics, not a summary of it.

1. 1

   Set Theory

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

2. 2

   Logic

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

3. 3

   Number Theory

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

4. 4

   Combinatorics

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

5. 5

   Graph Theory

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

6. 6

   Algorithms

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

7. 7

   Boolean Algebra

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

8. 8

   Cryptography

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

9. 9

   Mathematical Induction

   overview

   Examined as a single unit within Discrete Mathematics — no further topic split in the official outline.

Discrete Mathematics flashcards for Mathematics

23 of 50 cards from the Discrete Mathematics deck — real questions with worked answers.

1. What is a set, and what does it mean for an object to be an element of a set?

   A set is a well-defined, unordered collection of distinct objects. If an object $x$ belongs to a set $A$, we write $x \in A$; otherwise $x \notin A$.

2. State the formula for the number of subsets of a finite set with $n$ elements (the cardinality of its power set).

   A set with $n$ elements has $2^{n}$ subsets, so $|\mathcal{P}(A)| = 2^{n}$.

3. Define the union, intersection, and difference of two sets $A$ and $B$.

   $A \cup B = \{x : x \in A \text{ or } x \in B\}$, $A \cap B = \{x : x \in A \text{ and } x \in B\}$, and $A \setminus B = \{x : x \in A \text{ and } x \notin B\}$.

4. State De Morgan's laws for sets.

   $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

5. State the inclusion-exclusion principle for two finite sets.

   $|A \cup B| = |A| + |B| - |A \cap B|$.

6. State the inclusion-exclusion principle for three finite sets.

   $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.

7. What is the Cartesian product $A \times B$ of two sets, and what is its cardinality?

   $A \times B = \{(a,b) : a \in A,\ b \in B\}$, the set of all ordered pairs. Its cardinality is $|A \times B| = |A| \cdot |B|$.

8. Define a proposition in propositional logic.

   A proposition is a declarative statement that is either true or false, but not both.

9. Write the truth table outputs for the conditional $p \to q$.

   $p \to q$ is false only when $p$ is true and $q$ is false; in all other cases ($TT$, $FT$, $FF$) it is true.

10. What is the contrapositive of $p \to q$, and is it logically equivalent to the original?

    The contrapositive is $\neg q \to \neg p$, and it is logically equivalent to $p \to q$.

11. State the logical equivalence expressing a conditional in terms of disjunction.

    $p \to q \equiv \neg p \lor q$.

12. Define a tautology and a contradiction in propositional logic.

    A tautology is a compound proposition that is true under every assignment of truth values; a contradiction is one that is false under every assignment.

13. State De Morgan's laws for logic.

    $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$.

14. What is the negation of the quantified statement $\forall x\, P(x)$?

    $\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x)$.

15. What is the negation of the quantified statement $\exists x\, P(x)$?

    $\neg(\exists x\, P(x)) \equiv \forall x\, \neg P(x)$.

16. State the inference rule modus ponens.

    From $p \to q$ and $p$, conclude $q$. Symbolically: $[(p \to q) \land p] \to q$.

17. State the inference rule modus tollens.

    From $p \to q$ and $\neg q$, conclude $\neg p$. Symbolically: $[(p \to q) \land \neg q] \to \neg p$.

18. Define a reflexive relation on a set $A$.

    A relation $R$ on $A$ is reflexive if $(a,a) \in R$ for every $a \in A$.

19. Define a symmetric relation and an antisymmetric relation.

    $R$ is symmetric if $(a,b) \in R \Rightarrow (b,a) \in R$. $R$ is antisymmetric if $(a,b) \in R$ and $(b,a) \in R$ imply $a = b$.

20. What three properties must a relation satisfy to be an equivalence relation?

    It must be reflexive, symmetric, and transitive.

21. What three properties define a partial order relation?

    It must be reflexive, antisymmetric, and transitive.

22. Distinguish among injective, surjective, and bijective functions.

    Injective (one-to-one): distinct inputs give distinct outputs. Surjective (onto): every element of the codomain is hit. Bijective: both injective and surjective.

23. State the pigeonhole principle.

    If $n$ objects are placed into $k$ boxes and $n > k$, then at least one box contains at least two objects. More generally, some box contains at least $\lceil n/k \rceil$ objects.

See more Discrete Mathematics flashcards →

Planning Discrete Mathematics for Mathematics

Discrete Mathematics (Mathematics) FAQ