Discrete Mathematics — Study Notes

Mathematics splits broadly into continuous mathematics, which deals with quantities that vary smoothly (like the real number line), and discrete mathematics, which deals with separated, countable values. A discrete set can be listed as a sequence and placed in one-to-one correspondence with the natural numbers — something impossible for an uncountable set such as \(\mathbb{R}\). This chapter rests on two pillars: binary operations and mathematical logic.

1. Binary operations and closure

An operation is a rule that processes elements of a set. Acting on one element at a time (like taking a negative) is a unary operation; acting on two at a time is a binary operation. Formally, a binary operation \(*\) on a non-empty set \(S\) is a function \(*\,:\,S \times S \to S\): it takes an ordered pair \((a,b)\) and returns a single, well-defined element \(a*b\) that must lie back in \(S\). That last requirement is the closure property, and it powers most 'is this a binary operation?' questions. To disprove closure you only need one counterexample where the result leaves the set (e.g. subtraction on \(\mathbb{N}\): \(2-5=-3\notin\mathbb{N}\)).

A set together with one or more binary operations is an algebraic structure. Historically, number systems were extended — from \(\mathbb{N}\) to \(\mathbb{Z}\) to \(\mathbb{Q}\) — largely to restore closure for subtraction and division.

2. Properties of a binary operation

Commutative: \(a*b=b*a\) for all \(a,b\in S\).
Associative: \((a*b)*c=a*(b*c)\) for all \(a,b,c\in S\).
Identity element: an \(e\in S\) with \(a*e=e*a=a\) for every \(a\). For \((+)\) it is \(0\); for \((\times)\) it is \(1\).
Inverse element: for \(a\in S\) an element \(a'\in S\) with \(a*a'=a'*a=e\).

Two short uniqueness results are worth memorising: the identity of a structure, if it exists, is unique, and (when the operation is associative) the inverse of an element is also unique.

3. Boolean matrices and modular arithmetic

A Boolean matrix has every entry equal to \(0\) or \(1\). For two Boolean matrices of the same size, the join \(A\lor B\) takes the entrywise maximum and the meet \(A\land B\) the entrywise minimum. Both are commutative and associative; the null (all-zero) matrix is the identity for join, and the all-ones matrix is the identity for meet.

Modular arithmetic studies remainders. We write \(a\equiv b\ (\mathrm{mod}\ n)\) when \(n\) divides \(a-b\); equivalently \(b\) is the remainder when \(a\) is divided by \(n\). On the set \(\mathbb{Z}_n=\{0,1,\dots,n-1\}\), addition modulo \(n\) (written \(+_n\)) and multiplication modulo \(n\) (written \(\times_n\)) are defined by taking the ordinary result and keeping its remainder on division by \(n\).

4. Statements and truth values

A statement (proposition) is a declarative sentence that is definitely either true (\(T\)) or false (\(F\)), but not both. Questions, commands and exclamations are not statements. An open sentence such as \(x+7=35\) has a truth value that depends on \(x\), so it is not a statement until the variable is fixed. A sentence that cannot be broken into smaller statements is simple (atomic); one built from simpler statements using connectives is compound.

5. Logical connectives and truth tables

Negation \(\lnot p\): flips the truth value.
Conjunction \(p\land q\) ('and'): true only when both parts are true.
Disjunction \(p\lor q\) ('or'): false only when both parts are false.
Conditional \(p\to q\) ('if \(p\) then \(q\)'): false only in the single case \(p\) true and \(q\) false.
Biconditional \(p\leftrightarrow q\) ('\(p\) if and only if \(q\)'): true exactly when \(p\) and \(q\) match.
Exclusive OR \(p\veebar q\): true when exactly one of \(p,q\) is true.

A compound statement built from \(n\) simple statements needs \(2^{n}\) rows in its truth table — three statements give \(8\) rows, a fact that appears directly as an exam question.

6. Converse, inverse, contrapositive

From \(p\to q\) we derive three related conditionals: the converse \(q\to p\), the inverse \(\lnot p\to\lnot q\), and the contrapositive \(\lnot q\to\lnot p\). The key fact (and a frequent trap): a conditional and its contrapositive are logically equivalent, and the converse and inverse are equivalent to each other — but a statement is not equivalent to its converse or its inverse.

7. Tautology, contradiction, contingency

A compound statement that is always true (final column all \(T\)) is a tautology; always false (all \(F\)) is a contradiction; anything in between is a contingency. For example \(p\lor\lnot p\) is a tautology and \(p\land\lnot p\) a contradiction, while \(p\leftrightarrow q\) is only a contingency — a popular wrong option claims it is a tautology.

8. Duality and logical equivalence

The dual of a compound statement built only from \(\land,\lor,T,F\) is obtained by swapping \(\land\leftrightarrow\lor\) and \(T\leftrightarrow F\), leaving variables and negations unchanged. Two statements are logically equivalent (\(A\equiv B\)) when their truth-table columns are identical — equivalently when \(A\leftrightarrow B\) is a tautology. The standard laws (idempotent, commutative, associative, distributive, identity, complement, double negation, De Morgan's, and absorption) let you simplify expressions without writing out a full table.

Common exam traps

Forgetting that closure requires the result to stay in the same set — hunt for a single escaping counterexample.
Mis-applying De Morgan: negating an 'or' produces an 'and', not another 'or'.
Assuming a statement equals its converse or inverse; only the contrapositive is equivalent.
Calling \(p\leftrightarrow q\) a tautology — it is a contingency.
Treating \(a^{b}\) as always real; a negative base with a fractional exponent leaves \(\mathbb{R}\).
A conditional with a false hypothesis is automatically true — do not mark those rows false.

Discrete Mathematics — Study Notes