Sets

Basic properties of sets



Two characteristics of a set

  1. There are no repeated occurrences of elements
  2. There is no particular order or arrangement of the elements


How do you show A is a subset of B?
If A and B are sets and every element of A is also an element of B, then A is a subset of B.

How do you show A = B?
A is a subset of B, and B is a subset of A

Operations on sets

  • Union - A union B = set of x s.t. x is an element of A or x is an element of B
  • Intersection - A intersect B = set of x s.t. x is an element of A and x is an element of B 
  • Complement

Cardinality

Inclusion-Exclusion principle
|A ∪ B| = |A| + |B| − |A ∩ B|.

Inclusion-Exclusion for 3 sets
|A ∪ B ∪ C| = |A| + |B| + |C| − |B ∩ C| − |A ∩ B| − |A ∩ C| + |A ∩ B ∩ C|

Difference rule
|A − B| = |A| − |A ∩ B|.




Comments

Post a Comment

Popular posts from this blog

Grammars

Structure of grammar L is a language over an alphabet A then a grammar for L α → β α = strings of symbols taken from language A β = strings of symbols from a grammar disjoint from A. Can be interpreted as: replace α by β α produces β α rewrites β α reduces β --- Start symbol S → β Ex. Let A = { a, b, c }. S → Λ | aS | bS | cS Ex. Set of binary numerals that represent odd numbers O → B 1  B → Λ | B 0 | B 1. --- S  →  AB A  →  Λ |  aA B  →  Λ |  bB. Leftmost derivation S  ⇒  AB  ⇒  aAB   ⇒  aaAB   ⇒  aaB   ⇒  aabB   ⇒  aab . Rightmost Derivation S  ⇒  AB  ⇒  AbB   ⇒  Ab  ⇒  aAb   ⇒  aaAb   ⇒  aab . --- The Language of a Grammar (3.3.4) If G is a grammar with the start symbol S and the set of terminals T , then the language of G is the set L ( G ) = { s | s ∈ T * and S ⇒ + s }. Three simple grammars 1. {Λ, a, aa , …, a n , … } = { a n | n ∈ N}. • S → Λ | aS . 2. {Λ, ab, aabb , …, a n b n , … } = { a n b n
Read more