Mathematics1 course

Discrete Math

Logic, sets, induction, number theory and graphs.

About Discrete Math

Discrete mathematics studies structures made of separate pieces rather than smooth quantities: integers, sets, logical statements, graphs and finite counts. It is the mathematical language of computer science, used to reason about algorithms, networks, databases and cryptography.

The course is also where proof becomes central. Direct proof, proof by contradiction and mathematical induction are practised on concrete statements such as $1 + 2 + \dots + n = \frac{n(n + 1)}{2}$ . Modular arithmetic, the remainder arithmetic behind clocks and checksums, leads to the number theory used in modern encryption.

Programmers use these ideas daily: boolean logic in every condition, counting arguments to estimate how many cases a program must handle, graphs to model networks and maps, and modular arithmetic in hashing and encryption. Interviews for software roles regularly draw on this material.

Discrete Mathematics

The mathematics behind computer science. (College)

Logic and Sets

Logic studies statements that are either true or false and how connectives combine them: and ( $\land$ ), or ( $\lor$ ), not ( $\neg$ ) and if-then ( $\to$ ). Truth tables list every case. An implication $p \to q$ is false only when $p$ is true and $q$ is false, and it is logically equivalent to its contrapositive $\neg q \to \neg p$ , but not to its converse $q \to p$ .

Mathematical Induction

Mathematical induction proves that a statement $P(n)$ holds for every whole number $n \ge n_0$ . It works like dominoes: show the first case is true (the base case), then show that whenever one case is true, the next one must be too (the inductive step). Together these push the truth through every integer.

Full Discrete Mathematics course outline

How to study Discrete Math

Test a claim on small cases (n = 1, 2, 3) before trying to prove it.
In induction, write the inductive hypothesis explicitly and point to the line where you use it.
Translate logic statements into plain English and back again; negations of "for all" and "there exists" trip many students.
Draw graphs and Venn diagrams; most counting arguments become clearer as pictures.

Before you start: Algebra and some comfort with formal reasoning. You do not need calculus; what matters more is patience with precise definitions and willingness to check small examples.
Where it leads: Algorithms and data structures, or further proof-based mathematics.

Key terms in Discrete Math

Proposition: A statement that is either true or false. Connectives such as and, or, not and implies build compound propositions.
Set: An unordered collection of distinct objects. Union, intersection and complement combine sets, and Venn diagrams show the overlaps.
Induction: A proof method: show a base case, then show that truth for $n$ forces truth for $n+1$ , so the claim holds for every $n$ from the base on.
Permutation: An ordered arrangement. The number of ways to order $r$ of $n$ distinct items is $\tfrac{n!}{(n-r)!}$ .
Graph: A set of vertices joined by edges, used to model networks. The degree of a vertex is the number of edges meeting it.
Modular arithmetic: Arithmetic with remainders, written $a \equiv b \pmod n$ when $n$ divides $a - b$ ; clock time is arithmetic mod 12.