232
Sets, Combinatorics, and Probability
Definition COmPlemeNt Of a Set
For a set A [ ℘(S), the complement of A, A′, is {x 0 x [ S and x o A}.
■
PraCtiCe 14 Illustrate A′ in a Venn diagram.
example 17
In Section 1.1 we discussed the use of logical connectives to formulate Web search
queries. A query such as
“used cars” AND (Ford OR Buick) AND NOT trucks
is asking the search engine to return a set of pages (or more properly, a set of links
to pages). If
U = set of used car pages
F = set of Ford pages
B = set of Buick pages
T = set of truck pages
then
U d (F c B) d T′
represents the set of Web pages that is the desired result of the query.
Another binary operation on sets A and B in ℘(S) is set difference: A − B =
{x 0 x [ A and x o B}. This operation can be rewritten as A − B = {x 0 x [ A and
x [ B′} and, finally, as A − B = A d B′.
■
PraCtiCe 15 Illustrate A − B in a Venn diagram.
Two sets A and B such that A d B = [ are said to be disjoint. Thus, A − B
and B − A, for example, are disjoint sets.
example 18
Let
A = {x 0 x is an even nonnegative integer}
B = {x 0 (E y)( y [ ℕ and x = 2y + 1)}
C = {x 0 (E y)( y [ ℕ and x = 4y)}
be subsets of ℕ. Because B represents the set of nonnegative odd integers, A and B
are disjoint sets. Also, every nonnegative integer is either even or odd, so A c B = ℕ.
These two facts also tell us that A′ = B. Every multiple of 4 is an even number,
so C is a subset of A, from which it follows that A c C = A. C is in fact a proper
subset of A, and A − C = {x 0 (E y)( y [ ℕ and x = 4y + 2)}.
Sets, Combinatorics, and Probability
Definition COmPlemeNt Of a Set
For a set A [ ℘(S), the complement of A, A′, is {x 0 x [ S and x o A}.
■
PraCtiCe 14 Illustrate A′ in a Venn diagram.
example 17
In Section 1.1 we discussed the use of logical connectives to formulate Web search
queries. A query such as
“used cars” AND (Ford OR Buick) AND NOT trucks
is asking the search engine to return a set of pages (or more properly, a set of links
to pages). If
U = set of used car pages
F = set of Ford pages
B = set of Buick pages
T = set of truck pages
then
U d (F c B) d T′
represents the set of Web pages that is the desired result of the query.
Another binary operation on sets A and B in ℘(S) is set difference: A − B =
{x 0 x [ A and x o B}. This operation can be rewritten as A − B = {x 0 x [ A and
x [ B′} and, finally, as A − B = A d B′.
■
PraCtiCe 15 Illustrate A − B in a Venn diagram.
Two sets A and B such that A d B = [ are said to be disjoint. Thus, A − B
and B − A, for example, are disjoint sets.
example 18
Let
A = {x 0 x is an even nonnegative integer}
B = {x 0 (E y)( y [ ℕ and x = 2y + 1)}
C = {x 0 (E y)( y [ ℕ and x = 4y)}
be subsets of ℕ. Because B represents the set of nonnegative odd integers, A and B
are disjoint sets. Also, every nonnegative integer is either even or odd, so A c B = ℕ.
These two facts also tell us that A′ = B. Every multiple of 4 is an even number,
so C is a subset of A, from which it follows that A c C = A. C is in fact a proper
subset of A, and A − C = {x 0 (E y)( y [ ℕ and x = 4y + 2)}.