المحاضرة السابعة هياكل متقطعة

Sets and set operations
Basic discrete structures
• Discrete math =
– study of the discrete structures used to represent discrete
objects
• Many discrete structures are built using sets
– Sets = collection of objects
Examples of discrete structures built with the help of sets:
• Combinations
• Relations
• Graphs
Set
• Definition:A set is a (unordered) collection of objects. These
objects are sometimes called elements or members of the set.
(Cantor s naive definition)
• Examples:
– Vowels in the English alphabet
V = { a, e, i, o, u }
– First seven prime numbers.
X = { 2, 3, 5, 7, 11, 13, 17 }
Representing sets
Representing a set by:
1) Listing (enumerating) the members of the set.
2) Definition by property, using the set builder notation
{x| x has property P}.
Example:
• Even integers between 50 and 63.
1) E = {50, 52, 54, 56, 58, 60, 62}
2) E = {x| 50 <= x < 63, x is an even integer}
If enumeration of the members is hard we often use ellipses.
Example: a set of integers between 1 and 100
• A= {1,2,3 …, 100}
3
CS 441 Discrete mathematics for CS M. Hauskrecht
Important sets in discrete math
• Natural numbers:
– N = {0,1,2,3, …}
• Integers
– Z = {…, -2,-1,0,1,2, …}
• Positive integers
– Z+ = {1,2, 3.…}
• Rational numbers
– Q = {p/q | p ? Z, q ? Z, q ? 0}
• Real numbers
– R
CS 441 Discrete mathematics for CS M. Hauskrecht
Russell’s paradox
Cantor s naive definition of sets leads to Russell s paradox:
• Let S = { x | x ? x },
is a set of sets that are not members of themselves.
• Question: Where does the set S belong to?
– Is S ? S or S ? S?
• Cases
– S ? S ?: S does not satisfy the condition so it must hold that
S ? S (or S ? S does not hold)
– S ? S ?: S is included in the set S and hence S ? S does not
hold
• A paradox: we cannot decide if S belongs to S or not
• Russell’s answer: theory of types – used for sets of sets
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Equality
Definition: Two sets are equal if and only if they have the same
elements.
Example:
• {1,2,3} = {3,1,2} = {1,2,1,3,2}
Note: Duplicates don t contribute anything new to a set, so remove
them. The order of the elements in a set doesn t contribute
anything new.
Example: Are {1,2,3,4} and {1,2,2,4} equal?
No!
CS 441 Discrete mathematics for CS M. Hauskrecht
Special sets
• Special sets:
– The universal set is denoted by U: the set of all objects
under the consideration.
– The empty set is denoted as ? or { }.
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Venn diagrams
• A set can be visualized using Venn Diagrams:
– V={ A, B, C }
U
A
B
C
CS 441 Discrete mathematics for CS M. Hauskrecht
A Subset
• Definition: A set A is said to be a subset of B if and only if
every element of A is also an element of B. We use A ? B to
indicate A is a subset of B.
• Alternate way to define A is a subset of B:
?x (x ? A) ? (x ? B)
U
A
B
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Empty set/Subset properties
Theorem ? ? S
• Empty set is a subset of any set.
Proof:
• Recall the definition of a subset: all elements of a set A must be
also elements of B: ?x (x ? A ? x ? B).
• We must show the following implication holds for any S
?x (x ? ? ? x ? S)
• Since the empty set does not contain any element, x ? ? is
always False
• Then the implication is always True.
End of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Subset properties
Theorem: S ? S
• Any set S is a subset of itself
Proof:
• the definition of a subset says: all elements of a set A must be
also elements of B: ?x (x ? A ? x ? B).
• Applying this to S we get:
• ?x (x ? S ? x ? S) which is trivially True
• End of proof
Note on equivalence:
• Two sets are equal if each is a subset of the other set.
7
CS 441 Discrete mathematics for CS M. Hauskrecht
A proper subset
Definition: A set A is said to be a proper subset of B if and only
if A ? B and A ? B. We denote that A is a proper subset of B
with the notation A ? B.
U
A
B
CS 441 Discrete mathematics for CS M. Hauskrecht
A proper subset
Definition: A set A is said to be a proper subset of B if and only
if A ? B and A ? B. We denote that A is a proper subset of B
with the notation A ? B.
Example: A={1,2,3} B ={1,2,3,4,5}
Is: A ? B ? Yes.
U
A
B
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Cardinality
Definition: Let S be a set. If there are exactly n distinct elements
in S, where n is a nonnegative integer, we say S is a finite set
and that n is the cardinality of S. The cardinality of S is
denoted by | S |.
Examples:
• V={1 2 3 4 5}
| V | = 5
• A={1,2,3,4, …, 20}
|A| =20
• | ? | = 0
CS 441 Discrete mathematics for CS M. Hauskrecht
Infinite set
Definition: A set is infinite if it is not finite.
Examples:
• The set of natural numbers is an infinite set.
• N = {1, 2, 3, ... }
• The set of reals is an infinite set.
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Power set
Definition: Given a set S, the power set of S is the set of all subsets
of S. The power set is denoted by P(S).
Examples:
• Assume an empty set ?
• What is the power set of ? ? P(?) = { ? }
• What is the cardinality of P(?) ? | P(?) | = 1.
• Assume set {1}
• P( {1} ) = { ?, {1} }
• |P({1})| = 2
CS 441 Discrete mathematics for CS M. Hauskrecht
Power set
• P( {1} ) = { ?, {1} }
• |P({1})| = 2
• Assume {1,2}
• P( {1,2} ) = { ?, {1}, {2}, {1,2} }
• |P({1,2} )| =4
• Assume {1,2,3}
• P({1,2,3}) = {?, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
• |P({1,2,3} | = 8
• If S is a set with |S| = n then | P(S) | = ?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Power set
• P( {1} ) = { ?, {1} }
• |P({1})| = 2
• Assume {1,2}
• P( {1,2} ) = { ?, {1}, {2}, {1,2} }
• |P({1,2} )| =4
• Assume {1,2,3}
• P({1,2,3}) = {?, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
• |P({1,2,3} | = 8
• If S is a set with |S| = n then | P(S) | = 2n
CS 441 Discrete mathematics for CS M. Hauskrecht
N-tuple
• Sets are used to represent unordered collections.
• Ordered-n tuples are used to represent an ordered collection.
Definition: An ordered n-tuple (x1, x2, ..., xN) is the ordered
collection that has x1 as its first element, x2 as its second
element, ..., and xN as its N-th element, N ? 2.
Example:
• Coordinates
Representing sets
Representing a set by:
1) Listing (enumerating) the members of the set.
2) Definition by property, using the set builder notation
{x| x has property P}.
Example:
• Even integers between 50 and 63.
1) E = {50, 52, 54, 56, 58, 60, 62}
2) E = {x| 50 <= x < 63, x is an even integer}
If enumeration of the members is hard we often use ellipses.
Example: a set of integers between 1 and 100
• A= {1,2,3 …, 100}
3
CS 441 Discrete mathematics for CS M. Hauskrecht
Important sets in discrete math
• Natural numbers:
– N = {0,1,2,3, …}
• Integers
– Z = {…, -2,-1,0,1,2, …}
• Positive integers
– Z+ = {1,2, 3.…}
• Rational numbers
– Q = {p/q | p ? Z, q ? Z, q ? 0}
• Real numbers
– R
CS 441 Discrete mathematics for CS M. Hauskrecht
Russell’s paradox
Cantor s naive definition of sets leads to Russell s paradox:
• Let S = { x | x ? x },
is a set of sets that are not members of themselves.
• Question: Where does the set S belong to?
– Is S ? S or S ? S?
• Cases
– S ? S ?: S does not satisfy the condition so it must hold that
S ? S (or S ? S does not hold)
– S ? S ?: S is included in the set S and hence S ? S does not
hold
• A paradox: we cannot decide if S belongs to S or not
• Russell’s answer: theory of types – used for sets of sets
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Equality
Definition: Two sets are equal if and only if they have the same
elements.
Example:
• {1,2,3} = {3,1,2} = {1,2,1,3,2}
Note: Duplicates don t contribute anything new to a set, so remove
them. The order of the elements in a set doesn t contribute
anything new.
Example: Are {1,2,3,4} and {1,2,2,4} equal?
No!
CS 441 Discrete mathematics for CS M. Hauskrecht
Special sets
• Special sets:
– The universal set is denoted by U: the set of all objects
under the consideration.
– The empty set is denoted as ? or { }.
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Venn diagrams
• A set can be visualized using Venn Diagrams:
– V={ A, B, C }
U
A
B
C
CS 441 Discrete mathematics for CS M. Hauskrecht
A Subset
• Definition: A set A is said to be a subset of B if and only if
every element of A is also an element of B. We use A ? B to
indicate A is a subset of B.
• Alternate way to define A is a subset of B:
?x (x ? A) ? (x ? B)
U
A
B
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Empty set/Subset properties
Theorem ? ? S
• Empty set is a subset of any set.
Proof:
• Recall the definition of a subset: all elements of a set A must be
also elements of B: ?x (x ? A ? x ? B).
• We must show the following implication holds for any S
?x (x ? ? ? x ? S)
• Since the empty set does not contain any element, x ? ? is
always False
• Then the implication is always True.
End of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Subset properties
Theorem: S ? S
• Any set S is a subset of itself
Proof:
• the definition of a subset says: all elements of a set A must be
also elements of B: ?x (x ? A ? x ? B).
• Applying this to S we get:
• ?x (x ? S ? x ? S) which is trivially True
• End of proof
Note on equivalence:
• Two sets are equal if each is a subset of the other set.
7
CS 441 Discrete mathematics for CS M. Hauskrecht
A proper subset
Definition: A set A is said to be a proper subset of B if and only
if A ? B and A ? B. We denote that A is a proper subset of B
with the notation A ? B.
U
A
B
CS 441 Discrete mathematics for CS M. Hauskrecht
A proper subset
Definition: A set A is said to be a proper subset of B if and only
if A ? B and A ? B. We denote that A is a proper subset of B
with the notation A ? B.
Example: A={1,2,3} B ={1,2,3,4,5}
Is: A ? B ? Yes.
U
A
B
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Cardinality
Definition: Let S be a set. If there are exactly n distinct elements
in S, where n is a nonnegative integer, we say S is a finite set
and that n is the cardinality of S. The cardinality of S is
denoted by | S |.
Examples:
• V={1 2 3 4 5}
| V | = 5
• A={1,2,3,4, …, 20}
|A| =20
• | ? | = 0
CS 441 Discrete mathematics for CS M. Hauskrecht
Infinite set
Definition: A set is infinite if it is not finite.
Examples:
• The set of natural numbers is an infinite set.
• N = {1, 2, 3, ... }
• The set of reals is an infinite set.
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Power set
Definition: Given a set S, the power set of S is the set of all subsets
of S. The power set is denoted by P(S).
Examples:
• Assume an empty set ?
• What is the power set of ? ? P(?) = { ? }
• What is the cardinality of P(?) ? | P(?) | = 1.
• Assume set {1}
• P( {1} ) = { ?, {1} }
• |P({1})| = 2
CS 441 Discrete mathematics for CS M. Hauskrecht
Power set
• P( {1} ) = { ?, {1} }
• |P({1})| = 2
• Assume {1,2}
• P( {1,2} ) = { ?, {1}, {2}, {1,2} }
• |P({1,2} )| =4
• Assume {1,2,3}
• P({1,2,3}) = {?, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
• |P({1,2,3} | = 8
• If S is a set with |S| = n then | P(S) | = ?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Power set
• P( {1} ) = { ?, {1} }
• |P({1})| = 2
• Assume {1,2}
• P( {1,2} ) = { ?, {1}, {2}, {1,2} }
• |P({1,2} )| =4
• Assume {1,2,3}
• P({1,2,3}) = {?, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
• |P({1,2,3} | = 8
• If S is a set with |S| = n then | P(S) | = 2n
CS 441 Discrete mathematics for CS M. Hauskrecht
N-tuple
• Sets are used to represent unordered collections.
• Ordered-n tuples are used to represent an ordered collection.
Definition: An ordered n-tuple (x1, x2, ..., xN) is the ordered
collection that has x1 as its first element, x2 as its second
element, ..., and xN as its N-th element, N ? 2.
Example:
• Coordinates