Discrete Mathematics: High-Level Study and Review Notes
Propositional Logic and Truth Tables
Mathematical Statement (Proposition): A declarative sentence that is either strictly true ( or ) or strictly false ( or ), but never both. Statements with unassigned variables (e.g., ) are open statements until quantified or assigned a specific value.
Truth Table Construction: For logical variables, the truth table consists of rows. The first variable alternates blocks of ones and zeros; the second alternates blocks of , continuing to the final variable which alternates every row.
Logical Connectives:
Negation ( or ): Reverses truth value (, ).
Conjunction (): True () only when both and are .
Disjunction (): True () if at least one of or is .
Conditional (): False () only when and ; true () in all other cases.
Biconditional (): True () when and share identical truth values.
Exclusive OR (): True () when truth values differ; false () when both are equal.
Fundamental Logical Equivalences:
Domination Laws: ,
Identity Laws: ,
Commutative Laws: ,
Associative Laws: ,
Distributive Laws: ,
De Morgan's Laws: ,
Double Negation Law:
Absorption Laws: ,
Inverse (Negation) Laws: ,
Idempotent Laws: ,
Set Theory and Relations
Standard Number Sets:
Natural Numbers:
Integers:
Rational Numbers:
Irrational Numbers: (cannot be written as a simple fraction, e.g., , , )
Real Numbers: (all rational and irrational numbers)
Set Membership vs. Containment:
Element-to-set: (is an element of), (not an element of).
Set-to-set: or (subset); the empty set is a subset of every set ().
Core Set Operations:
Intersection (): Common elements belonging to both and .

Union (): All elements in , , or both.

Difference ( or ): Elements belonging to that do not belong to .

Complement ( or ): Elements of universal set not in .

Set Properties: Complements follow , , and . De Morgan's Laws state and .
Power Set (): The set of all subsets of . Cardinality is , where is the number of elements in .
Cartesian Product (): Set of ordered pairs , with total elements . Always .
Binary Relation: Any subset .
Partition of a Set: A collection of non-empty, pairwise disjoint subsets of whose union equals .
Functions and Properties
Function Definition (): A relation assigning each element in domain to exactly one element in codomain . The range/image is the set of actual outputs ().
Function Classifications:
One-to-One (Injective): Distinct inputs produce distinct codomain outputs ().
Onto (Surjective): Every element of codomain has at least one pre-image ().
Bijective (One-to-One Correspondence): Both injective and surjective; this is the necessary and sufficient condition for the existence of an inverse function ().
Symmetry:
Even Function: ; symmetric across the y-axis.
Odd Function: ; symmetric across the origin .
Operations and Special Types:
Composition: .
Identity Function: .
Constant Function: .
Floor & Ceiling: (greatest integer ); (least integer ).
Piecewise Functions: Functions defined by multiple sub-rules according to different intervals of .
Combinatorics and Counting Principles
Sum Rule: If tasks are mutually exclusive, total ways to choose = .
Product Rule: If a procedure consists of sequential, independent stages, total ways = .
Permutations (): Ordered arrangements of items from distinct elements:
Combinations (Binomial Coefficients): Unordered selections of items from distinct elements:
Core Combinatorial Identities:
Symmetry Identity:
Pascal's Identity:
Sum of Binomial Coefficients:
Binomial Theorem:
Stars and Bars Method: Distributes identical items into distinct categories (solutions to ):
Non-negative integer solutions ():
Positive integer solutions ():
Sequences and Finite Differences
Sequence: A function from positive integers to real values, expressed via explicit formulas () or recurrence formulas.
Arithmetic Sequence: Defined by a constant common difference .
General term:
Sum of first terms:
Geometric Sequence: Defined by a constant common ratio .
General term:
Sum of first terms ():
Method of Finite Differences (Polynomial Fitting):
Differences: First difference ; second difference .
Criterion: If the -th differences are constant, the sequence matches a polynomial of degree : .
Quadratic relation (): Leading coefficient satisfies .
Solving Recurrence Relations
Iteration / Substitution Method: Repeatedly substituting preceding terms backward until an algebraic pattern emerges, then generalizing into an explicit closed-form formula.
Second-Order Linear Homogeneous Recurrence Relations:
Standard Form: with .
Characteristic Equation: .
Solution Cases:
Distinct Real Roots ():
Repeated Real Root ():
Initial Conditions: Constants and are computed by setting and using given boundary conditions and .
Hashing and Hash Tables
Hash Table Fundamentals: Data structure storing key-value pairs providing average-case time complexity for search, insert, and delete ( worst case).
Hash Function Methods ():
Division Method: (where is typically prime).
Multiplication Method: (where ).
Collision Resolution Strategies:
Open Addressing: Stores all entries directly within table slots.
Linear Probing: (susceptible to primary clustering).
Quadratic Probing: (susceptible to secondary clustering).
Double Hashing: .
Separate Chaining: Each slot maintains an external linked list of colliding elements; the table never completely fills.
Load Factor () & Rehashing:
Formula: , where is total stored keys and is table size.
Constraints: in open addressing; can exceed in separate chaining.
Rehashing: Triggered when exceeds a threshold (typically ). The table size is doubled () and adjusted to the nearest subsequent prime number (), followed by re-inserting all keys.