Discrete Mathematics for Computer Science Students

Discrete mathematics is the mathematics of separate, countable objects, and it is the language computer science is written in. Algorithms, databases, networks, cryptography and programming logic all rely on it. This guide covers the core topics every BS CS, SE and IT student meets in their first year, with worked examples showing every step.

Why Discrete Maths Matters in Computing

Computers store finite strings of bits and execute steps one at a time. That makes discrete structures, rather than continuous ones, the natural tools:

• Logic drives if conditions, circuit design and program verification.
• Sets and relations model databases and data types.
• Counting estimates how many inputs, passwords or states exist.
• Induction and recurrences prove algorithms correct and measure their running time.
• Graphs model networks, maps and dependencies.

Propositional Logic

A proposition is a statement that is either true (T) or false (F). We combine propositions with connectives:

• \( \neg p \): not \( p \)
• \( p \land q \): \( p \) and \( q \)
• \( p \lor q \): \( p \) or \( q \)
• \( p \to q \): if \( p \) then \( q \), which is false only when \( p \) is true and \( q \) is false
• \( p \leftrightarrow q \): \( p \) if and only if \( q \)

Two statements are logically equivalent (\( \equiv \)) if they have the same truth value in every case. Truth tables check this mechanically.

Worked Example 1: Proving an Equivalence

Show that \( p \to q \equiv \neg p \lor q \).

Step 1: List all combinations of \( p \) and \( q \) (there are \( 2^2 = 4 \)).

Step 2: Fill in each column.

Step 3: Compare. The last two columns agree in every row, so the statements are equivalent. Programmers use this constantly: if (!p || q) behaves exactly like "if \( p \), then require \( q \)".

Other Laws Worth Memorising

• De Morgan's laws: \( \neg(p \land q) \equiv \neg p \lor \neg q \) and \( \neg(p \lor q) \equiv \neg p \land \neg q \).
• Contrapositive: \( p \to q \equiv \neg q \to \neg p \).
• Note that the converse \( q \to p \) is not equivalent to \( p \to q \).

Sets and Functions

A set is an unordered collection of distinct elements. Key operations are union \( A \cup B \), intersection \( A \cap B \), difference \( A - B \) and complement \( \overline{A} \). A set with \( n \) elements has \( 2^n \) subsets, which is why an \( n \)-bit string can represent any subset of \( n \) items.

A function \( f: A \to B \) is injective (one-to-one) if different inputs give different outputs, surjective (onto) if every element of \( B \) is hit, and bijective if both. Hash functions, encodings and compression schemes are all studied through these properties.

Counting

Three principles solve most counting problems:

1. Product rule: if a task has stages with \( m \) and \( n \) choices, there are \( mn \) outcomes.
2. Sum rule: if a choice is from one of two disjoint groups of sizes \( m \) and \( n \), there are \( m + n \) options.
3. Inclusion–exclusion: for overlapping sets,

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

Worked Example 2: Counting with Inclusion–Exclusion

How many integers from 1 to 100 are divisible by 3 or 5?

Step 1: Define the sets. Let \( A \) be the multiples of 3 and \( B \) the multiples of 5.

Step 2: Count each set using the floor function:

$$ |A| = \left\lfloor \frac{100}{3} \right\rfloor = 33, \qquad |B| = \left\lfloor \frac{100}{5} \right\rfloor = 20 $$

Step 3: Count the overlap. A number divisible by both 3 and 5 is divisible by 15:

$$ |A \cap B| = \left\lfloor \frac{100}{15} \right\rfloor = 6 $$

Step 4: Apply the formula.

$$ |A \cup B| = 33 + 20 - 6 = 47 $$

Without subtracting the overlap, numbers like 15, 30 and 45 would be counted twice.

Mathematical Induction

To prove a statement \( P(n) \) for all \( n \geq 1 \):

1. Base case: prove \( P(1) \).
2. Inductive step: assume \( P(k) \) is true and prove \( P(k + 1) \).

Induction is how we prove loops and recursive functions behave correctly.

Worked Example 3: Solving and Proving a Recurrence

A recursive algorithm satisfies \( T(1) = 1 \) and \( T(n) = 2T(n - 1) + 1 \). Find a closed form and prove it.

Step 1: Compute small values.

$$ T(1) = 1, \quad T(2) = 2(1) + 1 = 3, \quad T(3) = 2(3) + 1 = 7, \quad T(4) = 2(7) + 1 = 15 $$

Step 2: Spot the pattern. These are one less than powers of 2, so conjecture

$$ T(n) = 2^n - 1 $$

Step 3: Base case. \( T(1) = 2^1 - 1 = 1 \). True.

Step 4: Inductive step. Assume \( T(k) = 2^k - 1 \). Then

$$ T(k + 1) = 2T(k) + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1 $$

which is the formula for \( n = k + 1 \).

Conclusion: \( T(n) = 2^n - 1 \) for all \( n \geq 1 \). This is exactly the number of moves in the Tower of Hanoi puzzle with \( n \) discs, and it tells us the algorithm runs in exponential time, \( O(2^n) \).

Tips for Success

• Translate English into logic carefully. "Only if" reverses direction: "\( p \) only if \( q \)" means \( p \to q \).
• Always check for overlaps before adding counts.
• Write out small cases before guessing a formula.
• State your inductive hypothesis clearly and point to where you use it.
• Connect topics to code. Writing a short program to check a count or recurrence builds intuition fast.

Key Takeaways

• Logic, sets, counting, induction and graphs are the foundations of computer science.
• Use truth tables to verify equivalences such as \( p \to q \equiv \neg p \lor q \).
• Inclusion–exclusion corrects for double counting: \( |A \cup B| = |A| + |B| - |A \cap B| \).
• Induction proves formulas for recurrences, such as \( T(n) = 2^n - 1 \).

Struggling with a discrete maths assignment or proof? Send it to Amathify on WhatsApp or through the "Ask a Question" form, and our experts and PhD scholars will provide clear, step-by-step solutions.