Discrete Structures: Full Exam Preparation Notes
CLO1: Understand the key concepts of Discrete Structures
1. Sets
• Definition: A set is a collection of distinct objects, often called elements or members.
• Set Notations:
• Roster: A = {1, 2, 3},
• Set-builder: B = {x | x > 0}
• Types:
• Finite, Infinite, Empty (null), Singleton
• Set Operations:
• Union (A ∪ B): All elements from A and B
• Intersection (A ∩ B): Elements common to both
• Difference (A - B): Elements in A not in B
• Complement (A'): Elements not in A
• Venn Diagrams: Visual tool to represent sets and operations
• Countable/Uncountable Sets: ℕ is countable; ℝ is uncountable
• Relations: A set of ordered pairs; describe a relationship between elements of two sets
• Equivalence Relations: Must satisfy reflexive, symmetric, transitive properties
• Partitions: Dividing a set into disjoint subsets such that every element belongs to one and only one
subset
• Partial Orderings: A relation that is reflexive, antisymmetric, and transitive
• Recurrence Relations: Equations defining a sequence based on previous terms
CLO2: Apply Logical Reasoning
2. Propositional Logic
• Proposition: A declarative statement that is either true or false
• Logical Operators:
• Conjunction (AND, ∧)
• Disjunction (OR, ∨)
• Negation (NOT, ¬)
• Implication (→)
• Biconditional (↔)
• Equivalences:
• Laws like DeMorgan's, Identity, Domination, Double Negation
• Translation: From English to symbolic logic and vice versa
3. Predicate Logic
• Predicate: Function that returns true/false based on input
1
• Quantifiers:
• Universal (∀): For all
• Existential (∃): There exists
• Nested Quantification: Multiple quantifiers within a statement
• Translation: Converting statements from symbolic to formal English and vice versa
4. Rules of Inference
• Direct Proof: Start with known truths and apply logic
• Contrapositive Proof: Prove ¬Q → ¬P instead of P → Q
• Proof by Contradiction: Assume the opposite and show contradiction
• Proof by Induction: Prove base case and then prove step case
• Existence Proof: Show at least one example exists
• Uniqueness Proof: Show only one such example exists
• Trivial & Vacuous Proofs: For statements with always true/false premises
CLO3: Apply Discrete Structures to Computing
5. Functions
• Injective (One-to-One): No two elements map to same value
• Surjective (Onto): Every output has a pre-image
• Bijective: Both injective and surjective
• Function Composition: Combining two functions: (f ∘ g)(x) = f(g(x))
• Inverse Functions: f(f⁻¹(x)) = x
• Recursive Functions: Function defined in terms of itself
• Compositions: Multiple functions applied in sequence
6. Applications in Computing
• Formal Specification: Logic used to specify system behavior
• Verification: Ensuring correctness using proofs
• Databases: Use of relations and sets
• AI and Cryptography: Use of graphs, trees, logic, and functions
CLO4: Differentiate Discrete Structures in Computing
7. Counting & Combinatorics
• Product Rule: Multiply options for each choice
• Sum Rule: Add options when tasks are exclusive
• Permutations: nPr = n! / (n−r)! (order matters)
• Combinations: nCr = n! / (r!(n−r)!) (order doesn’t matter)
• Inclusion-Exclusion Principle: Avoid overcounting common elements
• Pigeonhole Principle: If n items in m containers and n > m, some container has ≥2 items
2
• Binomial Theorem: (a + b)^n expansion with nCr
• Pascal’s Triangle: Used to find coefficients of binomial expansions
8. Recursion and Recurrences
• Recursion: Function calls itself with smaller input
• Recurrence Relation: T(n) = T(n−1) + T(n−2)
• Closed Formula: Direct formula for nth term
• Solution Techniques: Iteration, substitution, characteristic equations
9. Integers and Divisibility
• Division Algorithm: a = bq + r
• GCD & LCM: Greatest/Least Common Divisor/Multiple
• Euclidean Algorithm: Method to find GCD
• Extended Euclidean Algorithm: ax + by = gcd(a, b)
• Modular Arithmetic: Clock arithmetic, a ≡ b mod n
10. Primes and Theorems
• Prime Number: Divisible only by 1 and itself
• Mersenne Primes: Primes of the form 2^p − 1
• Fundamental Theorem of Arithmetic: Unique prime factorization
11. Mathematical Induction
• Weak Induction: Base case + inductive step
• Strong Induction: Assume all previous cases true, then prove next
Relations and Graph Theory
12. Relations
• Properties:
• Reflexive: aRa
• Symmetric: aRb ⇒ bRa
• Transitive: aRb and bRc ⇒ aRc
• Antisymmetric: aRb and bRa ⇒ a = b
• Equivalence Relations: Satisfy reflexive, symmetric, transitive
• Equivalence Classes: Sets grouped by equivalence
• Partial Orders: Not all elements comparable
13. Graph Theory
• Basic Terms: Vertices, edges, loops, parallel edges
• Types of Graphs:
• Simple, Directed (digraph), Weighted
3
• Traversals: BFS, DFS
• Paths and Cycles:
• Eulerian Path: Every edge once
• Hamiltonian Path: Every vertex once
• Planar Graphs: Can be drawn without edge crossings
• Coloring: Assign colors so adjacent nodes differ
• Trees:
• Rooted Tree: One node is root, hierarchical structure
• Binary Tree, Spanning Tree
• Theorems:
• Handshaking Lemma: Sum of degrees = 2 × edges
• Euler's Theorem: Related to cycles and circuits
• Hamiltonian Graphs: Contain Hamiltonian cycle
Tip for Exam: Focus on understanding definitions, practicing proofs, and solving sample problems from
each section.
