08 — Discrete Mathematics for Computer Science

Foundations and the Computer Science Perspective

Discrete mathematics focuses on finite, countable, and other non-continuous structures. In computer science, it supplies precise ways to specify program behavior, represent data, analyze algorithms, and establish correctness.

The main ideas build on one another:

• Logic describes truth and conditions.

• Predicates and quantifiers describe properties of objects and collections of objects.

• Sets describe domains and collections.

• Relations describe connections, equivalence, and ordering.

• Functions describe deterministic input-output behavior.

• Proof methods justify correctness and impossibility claims.

A useful general workflow is to identify the objects and their domains, translate informal claims into definitions or symbolic statements, make assumptions explicit, and then select a proof strategy that matches the claim.

Takeaway: Discrete mathematics provides a common language for describing computational objects and reasoning rigorously about them.

Logic, Truth, and Inference

A proposition is a declarative statement with exactly one truth value: true or false. For example, “$7$ is prime” is true, while “$10$ is less than $3$” is false. A symbolic variable such as $P$ can stand for either proposition.

A logical connective forms compound propositions:

• Negation: $\neg P$, meaning “not $P$.”

• Conjunction: $P \land Q$, meaning “$P$ and $Q$.”

• Disjunction: $P \lor Q$, meaning inclusive “$P$ or $Q$.”

• Implication: $P \to Q$, meaning “if $P$, then $Q$.”

• Biconditional: $P \leftrightarrow Q$, meaning “$P$ if and only if $Q$.”

For an implication $P \to Q$, $P$ is the antecedent and $Q$ is the consequent. The implication is false only in the case where $P$ is true and $Q$ is false. A truth table checks every possible assignment of truth values.

Important equivalences include:

• Double negation: $\neg(\neg P) \equiv P$.

• 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$.

• Implication rewriting: $P \to Q \equiv \neg P \lor Q$.

A tautology is true for every assignment, whereas a contradiction is false for every assignment. Two propositions are logically equivalent when they have the same truth value in every possible case.

A rule of inference gives a valid pattern for deriving a conclusion from premises. Modus ponens uses $P$ and $P \to Q$ to conclude $Q$. Modus tollens uses $\neg Q$ and $P \to Q$ to conclude $\neg P$. These forms matter in program conditions, query languages, digital circuits, and formal verification.

Takeaway: Truth tables and equivalence laws let you analyze conditions independently of their application domain.

Predicates, Domains, and Quantifiers

A predicate is a statement containing variables whose truth depends on assigned values. For example, $Prime(x)$ can express that $x$ is prime. Before a value is assigned to $x$, the predicate is not yet a proposition.

A quantifier connects a predicate to its domain:

• $\forall x\,P(x)$ means that $P(x)$ is true for every $x$ in the domain.

• $\exists x\,P(x)$ means that at least one element $x$ makes $P(x)$ true.

For example,

asserts a property of every natural number, while

is true because both $x = 2$ and $x = -2$ satisfy the predicate.

Negating quantifiers reverses their type and negates the predicate:

Thus, “not every input is valid” means that there exists an invalid input. The order of multiple quantifiers must be examined carefully because changing it can change the meaning of a specification.

Takeaway: Always identify the domain and quantifier scope before deciding whether a quantified statement is true.

Sets and Set Operations

A set is a collection of distinct elements. It can be described by listing elements, as in $A = \{1,2,3\}$, or by a condition, as in $E = \{x \in \mathbb{Z} \mid x\text{ is even}\}$. The statement $x \in A$ expresses membership, and $\varnothing$ denotes the empty set.

If every element of $A$ is also in $B$, then $A$ is a subset of $B$, written $A \subseteq B$. Common operations are:

• Union: $A \cup B$ contains elements in $A$ or $B$.

• Intersection: $A \cap B$ contains elements in both $A$ and $B$.

• Difference: $A \setminus B$ contains elements in $A$ but not in $B$.

• Complement: $A^c$ contains elements in the chosen universal set that are not in $A$.

The Cartesian product is the set of ordered pairs

For $A = \{0,1\}$ and $B = \{x,y\}$,

The power set $\mathcal{P}(A)$ contains every subset of $A$. If $A$ has $n$ elements, then $\mathcal{P}(A)$ has $2^n$ elements.

To prove set equality, prove both inclusions: $A \subseteq B$ and $B \subseteq A$. Equivalently, choose an arbitrary element $x$ and show that $x \in A$ exactly when $x \in B$. For example, the distributive law

follows from the corresponding propositional equivalence $P \land (Q \lor R) \leftrightarrow (P \land Q) \lor (P \land R)$.

Takeaway: Set notation turns informal collections and membership conditions into objects that can be manipulated and proved equal.

Relations, Equivalence, and Order

A binary relation from $A$ to $B$ is a subset of $A \times B$. If $(a,b)$ belongs to the relation $R$, it may be written as $aRb$. Relations can represent enrollment, network connectivity, numerical comparison, or having the same remainder modulo a fixed number.

When a relation $R$ is defined on a set $A$, its properties include:

• Reflexive: $aRa$ for every $a \in A$.

• Symmetric: if $aRb$, then $bRa$.

• Antisymmetric: if $aRb$ and $bRa$, then $a=b$.

• Transitive: if $aRb$ and $bRc$, then $aRc$.

An equivalence relation is reflexive, symmetric, and transitive. It partitions a set into equivalence classes. For example, having the same remainder modulo $3$ is an equivalence relation on the integers.

A partial order is reflexive, antisymmetric, and transitive. The subset relation $\subseteq$ is a partial order on a power set. Partial orders model dependencies, version constraints, and task precedence.

Relations can be represented as ordered pairs, tables, Boolean matrices, or directed graphs. The representation can be chosen to suit an application such as a database, graph algorithm, access-control system, or state-transition model.

Takeaway: To classify a relation, test each defining property separately; combinations of properties reveal its mathematical structure.

Functions and Mappings

A function is written $f\colon A \to B$. It assigns every element of the domain $A$ exactly one element of the codomain $B$. The range, or image, is the set of values actually produced:

An injective function maps distinct inputs to distinct outputs:

A surjective function reaches every element of its codomain:

A bijection is both injective and surjective. For example, $f\colon \mathbb{Z} \to \mathbb{Z}$ defined by $f(n)=n+1$ is bijective, with inverse $f^{-1}(n)=n-1$. In contrast, $g(n)=n^2$ from $\mathbb{Z}$ to $\mathbb{Z}$ is not injective because $g(1)=g(-1)$, and it is not surjective because no integer maps to $-1$.

Functions can be composed. If $f\colon A \to B$ and $g\colon B \to C$, then

This composition applies $f$ first and then $g$. Functions therefore provide a formal model for algorithms, encodings, transformations, hash computations, and state updates.

Takeaway: When analyzing a function, distinguish its domain, codomain, and actual range before testing injectivity or surjectivity.

Proof Strategies and Mathematical Rigor

A proof is a logically valid argument that derives a conclusion from definitions, accepted facts, and established results. The best proof method depends on the structure of the claim.

Direct proof

To prove $P \to Q$ directly, assume $P$, apply definitions and valid deductions, and derive $Q$. If $a$ and $b$ are even, write $a=2m$ and $b=2n$. Then $a+b=2(m+n)$, so $a+b$ is even.

Proof by contrapositive

Because $P \to Q$ is equivalent to $\neg Q \to \neg P$, prove the contrapositive when it is easier. To prove that an even square has an even root, show that an odd root has an odd square. If $n=2k+1$, then

which is odd.

Proof by contradiction

Assume the negation of the desired statement and derive an impossibility such as $R \land \neg R$ or $0=1$. The original statement then follows because the assumption of its negation cannot hold.

Proof by cases

Divide the possibilities into exhaustive cases and prove the conclusion in each one. For example, an integer is either even or odd, so a claim about every integer can be addressed through those two cases.

Mathematical induction

To prove $P(n)$ for every natural number in a specified range:

1. Prove the base case, such as $P(0)$.

2. Assume $P(k)$ for an arbitrary allowed $k$; this is the inductive hypothesis.

3. Use that hypothesis to prove $P(k+1)$.

For example, induction establishes

Induction is especially useful for loops, recursive algorithms, data structures, and recursively generated objects.

Counterexamples

To disprove a universal claim, one counterexample is enough. The statement that every prime number is odd is false because $2$ is prime and even. The counterexample must satisfy the assumptions while violating the conclusion.

Takeaway: Match the proof technique to the logical form: direct reasoning for constructive implications, contrapositive for reversed conditions, contradiction for impossible negations, cases for exhaustive alternatives, induction for recursive structure, and counterexamples for universal claims.

Connecting the Tools in Computer Science

The concepts become most useful when combined in a formal specification. A sorting algorithm, for example, should produce an output that is a permutation of its input and is ordered. The ordering condition can be written as

The permutation requirement can be expressed using sets or multisets. Quantifiers state what must hold for every relevant pair of positions, relations express the ordering comparison, and functions can model the algorithm's transformation from input to output. A proof can then use induction on the number of elements or on the algorithm's recursive structure.

A disciplined reasoning process is:

1. State the objects and their domains precisely.

2. Translate informal language into definitions or symbolic statements.

3. Identify the assumptions and the desired conclusion.

4. Choose a proof strategy suited to the logical form.

5. Justify every non-obvious step.

6. Test universal claims with small examples and search for counterexamples.

These tools support algorithm correctness, security guarantees, type-system soundness, formal specifications, databases, networks, and theoretical computer science.

Final takeaway: Logic states what a computation should do, sets and relations describe its objects and structure, functions model its behavior, and proofs establish that the intended properties actually hold.