10/29/23, 9:14 PM Discrete Structure 1
Discrete Structures
1. Sets and Subsets
1.1 . Sets
A set is any well-defined collection of objects called the elements or members
of the set. For example, the collection of all wooden chairs, the collection of all
one-legged black birds, or the collection of real numbers between zero and one
are all sets.
We use uppercase letters such as A, B, C to denote sets, and lowercase letters
such as a, b, c, x, y, z, t to denote the members (or elements) of sets.
We indicate the fact that x is an element of the set A by writing x * A, and we
indicate the fact that x is not an element of A by writing x +A.
Example 1
Let A = {1, 3, 5, 7}. Then 1 * A, 3 * A, but 2 +A.
Example 2
The set consisting of all the letters in the word <byte= can be denoted by {b, y,
t, e} or by {x | x is a letter in the word <byte=}.
Example 3
We introduce here several sets and their notations.
(a) Z+ = {x | x is a positive integer}.
Thus Z+ consists of the numbers used for counting: 1, 2, 3 . . . .
(b) N = {x | x is a positive integer or zero} = {x | x is a natural number}.
Thus N consists of the positive integers and zero: 0, 1, 2, . . . .
(c) Z = {x | x is an integer}.
Thus Z consists of all the integers: . . . , 23, 22, 21, 0, 1, 2, 3, . . . .
(d) Q = {x | x is a rational number}.
Thus Q consists of numbers that can be written as a/b, where a and b are
integers and b is not 0.
about:blank 1/19
,10/29/23, 9:14 PM Discrete Structure 1
(e) R = {x | x is a real number}.
(f) The set that has no elements in it is denoted either by { } or the symbol ∅
and is called the empty set.
Example 4
Since the square of a real number is always nonnegative,
{x | x is a real number and x2 = 21} = ∅.
Sets are completely known when their members are all known. Thus we say
two sets A and B are equal if they have the same elements, and we write A =
B.
Example 5
If A = {1, 2, 3} and B = {x | x is a positive integer and x2 < 12}, then A = B.
Example 6
If A = {JAVA, PASCAL, C++} and B = {C++, JAVA, PASCAL}, then A =
B.
1.2. Subsets
If every element of A is also an element of B, that is, if whenever x * A then x * B, we say
that A is a subset of B or that A is contained in B, and we write A ⊆ B. If A is not a subset
of B, we write A ⊈ B. (See Figure 1.)
Diagrams, such as those in Figure 1, which are used to show relationships between sets, are
called Venn diagrams after the British logician John Venn. Venn diagrams will be used
extensively in Section 2.
Example 7
about:blank 2/19
, 10/29/23, 9:14 PM Discrete Structure 1
Example 8
Example 9
Example 10
In Venn diagrams, the universal set U will be denoted by a rectangle, while
sets within U will be denoted by circles (A) as shown in Figure 2.
about:blank 3/19
Discrete Structures
1. Sets and Subsets
1.1 . Sets
A set is any well-defined collection of objects called the elements or members
of the set. For example, the collection of all wooden chairs, the collection of all
one-legged black birds, or the collection of real numbers between zero and one
are all sets.
We use uppercase letters such as A, B, C to denote sets, and lowercase letters
such as a, b, c, x, y, z, t to denote the members (or elements) of sets.
We indicate the fact that x is an element of the set A by writing x * A, and we
indicate the fact that x is not an element of A by writing x +A.
Example 1
Let A = {1, 3, 5, 7}. Then 1 * A, 3 * A, but 2 +A.
Example 2
The set consisting of all the letters in the word <byte= can be denoted by {b, y,
t, e} or by {x | x is a letter in the word <byte=}.
Example 3
We introduce here several sets and their notations.
(a) Z+ = {x | x is a positive integer}.
Thus Z+ consists of the numbers used for counting: 1, 2, 3 . . . .
(b) N = {x | x is a positive integer or zero} = {x | x is a natural number}.
Thus N consists of the positive integers and zero: 0, 1, 2, . . . .
(c) Z = {x | x is an integer}.
Thus Z consists of all the integers: . . . , 23, 22, 21, 0, 1, 2, 3, . . . .
(d) Q = {x | x is a rational number}.
Thus Q consists of numbers that can be written as a/b, where a and b are
integers and b is not 0.
about:blank 1/19
,10/29/23, 9:14 PM Discrete Structure 1
(e) R = {x | x is a real number}.
(f) The set that has no elements in it is denoted either by { } or the symbol ∅
and is called the empty set.
Example 4
Since the square of a real number is always nonnegative,
{x | x is a real number and x2 = 21} = ∅.
Sets are completely known when their members are all known. Thus we say
two sets A and B are equal if they have the same elements, and we write A =
B.
Example 5
If A = {1, 2, 3} and B = {x | x is a positive integer and x2 < 12}, then A = B.
Example 6
If A = {JAVA, PASCAL, C++} and B = {C++, JAVA, PASCAL}, then A =
B.
1.2. Subsets
If every element of A is also an element of B, that is, if whenever x * A then x * B, we say
that A is a subset of B or that A is contained in B, and we write A ⊆ B. If A is not a subset
of B, we write A ⊈ B. (See Figure 1.)
Diagrams, such as those in Figure 1, which are used to show relationships between sets, are
called Venn diagrams after the British logician John Venn. Venn diagrams will be used
extensively in Section 2.
Example 7
about:blank 2/19
, 10/29/23, 9:14 PM Discrete Structure 1
Example 8
Example 9
Example 10
In Venn diagrams, the universal set U will be denoted by a rectangle, while
sets within U will be denoted by circles (A) as shown in Figure 2.
about:blank 3/19
