Discrete Math

• Sets


  Well defined collection of distinct objects
• Objects


  Members or elements of a set
• ϵ


  Belongs to
• ϵ


  Does not belong to
• 2 Ways in defining a set

  • Tabular or roster form
  • Rule form
• Rule form


  • {x|x is a natural number less than 4} = {1,2,3}
  • {x|x is an even integer between 0 and 8} = {2,4,6}
• Empty set


  Set which contains no elements
• Kinds of Sets


  • Equal sets
  • Equivalent sets
  • Finite sets
  • Infinite sets
  • Universal sets
  • Joint Sets
  • Disjoint Sets
• Equal sets


  Sets A and B are equal if they have the same elements
• Equal sets


  • A = {1,2,3} and {2,1,3}
• Equivalent sets


  Same number of elements
• Equivalent sets


  • C = {x,y,z} and D = {1,2,3}
• Finite sets


  Contains only a countable number of elements
• Finite set


  • {1,2,3}
• Infinite sets


  Counting of elements has no end
• Infinite sets


  • Set of positive integers
  • Negative Integers
• Universal sets


  Totality of elements
• Universal set


  • U = {1,2,3,4,5}
• Joint Sets


  Sets that have common elements
• Joint Sets


  • A = {4,5,6} and B = {6,11,12}
• Disjoint Sets


  No common elements
• Disjoint Sets


  • E = {a,b,c} and F = {e,f,g}
• Operations on sets


  • Union
  • Intersection
  • Complement
  • Difference
  • Symmetric Difference
• Complement


  • A= {1,2} U = {1,2,3,4,5} A' = {3,4,5}
• Difference


  • A = {4,5,6,7} B = {1,6,7,8,9} A - B = {4,5} B - A = {1,8,9}
• Symmetric Difference


  • A = {1,2,3,4} B = {1,a,2,b,5,d} A + B = {3,4,a,b,5,d}
• Laws of Sets


  • Commutative laws
  • Associative laws
  • Distributive Property
  • Idempotent
  • De Morgan's theorem
  • Properties of Universal Set
  • Properties of complements
• Commutative laws


  Order of sets does not affect the result. A U B = B U A, A ∩ B = B ∩ A
• Associative laws


  Grouping of sets does not affect the result. A U (B U C) = (A U B) U C, A ∩ (B ∩ C) = (A ∩ B) ∩ C
• Distributive Property


  A ∩ (B U C) = (A ∩ B) U (A ∩ C), A U (B ∩ C) = (A U B) ∩ (A U C)
• Sets that are equal

  Sets that have exactly the same elements in the same order