Discete lesson 1

• Discrete Mathematics


  The study of mathematical structures that can be considered "discrete" rather than "continuous"
• Discrete Mathematics


  • Objects studied include integers, graphs, and statements in logic
  • It is the foundation of computer science
  • It focuses on concepts and reasoning methods that are studied using math notations
  • It has long been argued that discrete math is better taught with programming, which takes concepts and computing methods and turns them into executable programs
• Sets, Functions, and Relations

  Fundamental logic-driven concepts of Discrete Mathematics that tackle the logical groupings of objects and effective strategies in object retrieval
• Set


  An unordered collection of objects
• Common sets and notations

  • { } - the empty set
  • {0, 1, 2, 3, . . . } - the non-negative integers
  • {1, 2, 3, . . . } - the positive integers
  • {. . . , −2, −1, 0, 1, 2 . . . } - the negative integers
• Set cardinality


  The number of (distinct) objects in a set, written as |A|
• Set equality


  Two sets S and T are equal, written as S = T, if S and T contains exactly the same elements
• Subset


  A set S is a subset of set T, written as S ⊆ T, if every element in S is also in T. Set S is a strict subset of T, written as S ⊂ T, if there exists some element of T that is not in S.
• Power Set


  The set of all subsets of a set S, written as P(S)
• Cartesian Product


  The set of all ordered pairs (x, y) where x is an element of set S and y is an element of set T, written as S × T
• Union


  The set of elements in S or T, written as S ∪ T
• Intersection


  The set of elements in S and T, written as S ∩ T
• Difference


  The set of elements in S but not T, written as S - T
• Complement


  The set of elements not in S
• Set operation examples

  • S = {1, 2, 3}, T = {3, 4}, V = {a, b}
  • P(T) = {{3}, {4}, {3, 4}}
  • P(S) = {{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}
  • S × V = {(1, a),(1, b),(2, a),(2, b),(3, a),(3, b)}
  • S ∪ T = {1, 2, 3, 3, 4} = {1, 2, 3, 4}
  • S ∩ T = {3}
  • S ∩ V = {}
  • S - T = {1, 2}
  • T - V = {3, 4}
  • T = {1, 2, a, b}
• Venn Diagram


  A visual representation of sets and set operations
• Venn Diagram examples

  • A = {1, 2, 4, 5, 2}, B = {2, 3, 4, 6, 9}, C = {4, 5, 6, 7, 10, 5}, U = {1, 2, 3, 5, 4, 6, 1, 7, 8, 9, 10, 3, 11}
  • A∩B = {2,4}
  • (A∩C)∪B = {5,4,2,3,9,6}
  • (A∪C)∩B = {2,4,6}
  • A-C = {1,2}
  • (A∪B)-C = {1,2,3,9}
  • C = {1,2,3,9,8,11}
• Venn diagrams help visualize sets and efficiently prove set operations
• Relation


  A subset of S ×T, where S and T are sets. A relation on a single set S is a subset of S × S.
• Set Relations


  • Can be graphed and categorized under properties: Reflexivity, symmetry, and transitivity
• Cartesian Product relation


  • A = {1,2,3}, B = {2,4}

  A x B = {(1,2),(1,4),(2,2),(2,4),(3,2),(3,4)}
• Reflexive relation


  Its graph has a self-loop on every node
• Symmetric relation


  In its graph, every edge goes both ways
• Transitive relation


  In its graph, for any three nodes x, y and z such that there is an edge from x to y and from y to z, there exists an edge from x to z
• Reflexive closure


  • {(1,1),(1,2),(2,2),(1,3),(3,3),(3,1)}
• Symmetric closure


  • {(1,2),(2,1),(2,4),(4,2),(2,3),(3,2),(2,2)}
• Transitive closure


  • {(1,2),(3,4),(4,1),(3,2),(1,3),(2,3),(3,3),(2,4)}
• Function


  A "mapping" from elements in set S to elements in set T. Formally, f is a relation on S and T such that for each s ∈ S, there exists a unique t ∈ T. S is the domain of f, and T is the range of f.
• Function


  • Mapping between sets
  • Domain
  • Range
• Function mapping


  • A = {1,2,4,5}, B = {2,4,8,10}, f(x) = 2x
  • A = {1,2,4,5}, B = {3,5,9,11}, f(x) = 2x + 1
  • A = {2, 4, 1, 0, -4}, f(x) = x + 1, B = {5,17,2,1}
  • A = {2, 4, 1, 3, 6}, B = {0, 0, 1, 1, 0}, Characteristic function checks for odd numbers
• Composite Functions


  1. A = {1, 2, 3, 4}, f(x) = x + 2, g(x) = 2x+1, h(x) = g(f(x))

  2. A = {1, 2, 3, 4}, f(x) = 3x + 5, g(x) = 2x - 1, h(x) = g(f(x))
• Injective Function


  • All elements in A must not share an element in B
• Surjective Function


  • |A| >= |B|, All elements in B must have an element in A
• Bijective Function


  • |A| = |B|, Surjective + Injective