CO-205: Discrete Structures Tutorial #1
Summary
set a well defined (unordered) collection of Cartesian If 𝐴 and 𝐵 are two nonempty sets the
distinct objects Product product set or Cartesian product 𝐴 × 𝐵 is
element or an object in a set defined as the set of all ordered pairs
member of a (𝑎, 𝑏) with 𝑎 ∈ 𝐴 and 𝑏 ∈ B. i.e.
set 𝐴 × 𝐵 = {(𝑎, 𝑏) | 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵}.
roster method a method that describes a set by listing membership a table displaying the membership of
of set its elements table elements in sets
representation ⌊𝒙⌋ (floor the largest integer not exceeding x
set builder the notation that describes a set by function)
notation of set stating a property an element must have ⌈𝒙⌉ (ceiling the smallest integer greater than or equal
representation to be a member function) to x
∅ (empty set, the set with no members string a finite sequence
null set) empty string a string of length zero
Universal set the set containing all objects under recurrence a equation that expresses the 𝑛𝑡ℎ term 𝑎𝑛
consideration relation of a sequence in terms of one or more of
Venn diagram a graphical representation of a set or sets the previous terms of the sequence for all
S = T (set S and T have the same elements integers 𝑛 greater than a particular integer
equality) A function on a set may be thought of as
S ⊆ T (S is a every element of S is also an element of a set of rules that assign some ‘values’ to
subset of T) T each element of the set. If 𝐴 is a subset
S ⊂ T (S is a S is a subset of T and S ≠ T of the Universal set, 𝑈, the characteristic
proper subset function 𝑓𝐴 of 𝐴 is defined as 𝑓𝐴 (𝑥 ) =
of T) 1, 𝑥 ∈𝐴
{
finite set a set with n elements, where n is a 0, 𝑥 ∉ 𝐴
nonnegative integer Characteristic function is used for
infinite set a set that is not finite computer representation of sets.
Characteristic Characteristic functions of subsets satisfy
|S| (the the number of elements in S
Function the following properties: -
cardinality of
S) 𝑓𝐴∩𝐵 = 𝑓𝐴 ∙ 𝑓𝐵
𝑺∗ the set of all subsets of S 𝑖. 𝑒. 𝑓𝐴∩𝐵 (𝑥 ) = 𝑓𝐴 (𝑥 ) ⋅ 𝑓𝐵 (𝑥 )∀𝑥
(the power set 𝑓𝐴∪𝐵 = 𝑓𝐴 + 𝑓𝐵 − 𝑓𝐴 ∙ 𝑓𝐵
of S) 𝑖. 𝑒. 𝑓𝐴∪𝐵 (𝑥 ) = 𝑓𝐴 (𝑥 ) + 𝑓𝐵 (𝑥 )
A ∪ B (the {𝑥|𝑥 ∈ 𝐴 𝑜𝑟 𝑥 ∈ 𝐵} −𝑓𝐴 (𝑥 ) ⋅ 𝑓𝐵 (𝑥) ∀𝑥
union of sets A 𝑓𝐴⨁𝐵 = 𝑓𝐴 + 𝑓𝐵 − 2𝑓𝐴 ∙ 𝑓𝐵 i.e.
and B) 𝑓𝐴⨁𝐵 (𝑥) = 𝑓𝐴 (𝑥) + 𝑓𝐵 (𝑥 )
A∩B {𝑥|𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∈ 𝐵} −2 𝑓𝐴 (𝑥 ) ⋅ 𝑓𝐵 (𝑥 ) ∀𝑥
(the Properties of If 𝑎, 𝑏, 𝑐 are integers: -
intersection of divisibility of 𝑖𝑓 ( 𝑎|𝑏 𝑎𝑛𝑑 𝑎|𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|(𝑏 + 𝑐)
sets A and B) Integers 𝑖𝑓 ( 𝑎|𝑏 𝑎𝑛𝑑 𝑎|𝑐, 𝑏 > 𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|(𝑏 − 𝑐)
A−B the set containing those elements that are 𝑖𝑓 ( 𝑎|𝑏 𝑜𝑟 𝑎|𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|(𝑏 ⋅ 𝑐)
(complement in A but not in B 𝑖𝑓 ( 𝑎|𝑏 𝑎𝑛𝑑 𝑏|𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|𝑐
of B with i.e. 𝑮𝑪𝑫(𝒂, 𝒃) or • 𝑖𝑓 ( 𝑎, 𝑏 ∈ 𝑍 + 𝑎𝑛𝑑 𝑏 > 𝑎 )𝑡ℎ𝑒𝑛
respect to A {𝑥|𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∉ 𝐵} ≡ 𝐴 ∩ 𝐵̅ 𝑯𝑪𝑭(𝒂, 𝒃) (𝐺𝐶𝐷(𝑎, 𝑏) = 𝐺𝐶𝐷(𝑏, 𝑏 ± 𝑎))
(or the • Euclidean Algorithm to find
difference of A 𝐺𝐶𝐷(𝑎, 𝑏)
and B) ) 𝑳𝑪𝑴(𝒂, 𝒃) • If 𝑝1 , 𝑝2 , … , 𝑝𝑘 are the prime factors of
̅ (the
𝑨 the set of elements in the universal set either 𝑎 or 𝑏 then 𝑎 and 𝑏 can be
complement of that are not in A represented as
A) 𝑎 𝑎 𝑎
𝑎 = 𝑝1 1 ⋅ 𝑝2 2 ⋅⋅⋅ 𝑝𝑘 𝑘 and
A⊕B the set containing those elements in 𝑏 𝑏 𝑏
𝑏 = 𝑝1 1 ⋅ 𝑝2 2 ⋅⋅⋅ 𝑝𝑘 𝑘
(the symmetric exactly one of A or B (not in both) i.e.
{𝑥|(𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∉ 𝐵) 𝑜𝑟 (𝑥 ∈ 𝐵 𝑎𝑛𝑑 𝑥 ∉ 𝐴)} where some 𝑎𝑖 and 𝑏𝑖 may zero. Then it
difference of A
≡ (𝐴 ∩ 𝐵̅ ) ∪ (𝐴̅ ∩ 𝐵) follows that
and B) min(𝑎1 , 𝑏1 ) min(𝑎2 , 𝑏2 )
Inclusion If A and B are finite sets then |𝐴 ∪ 𝐵| = 𝐻𝐶𝐹 (𝑎, 𝑏) = 𝑝1 ⋅ 𝑝2 ⋅⋅⋅
min(𝑎𝑘, 𝑏𝑘)
Exclusion |𝐴| + |𝐵| − |𝐴 ∩ 𝐵| 𝑝𝑘
Principle Similarly |𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − 𝐿𝐶𝑀(𝑎, 𝑏) = 𝑝1
max(𝑎1 , 𝑏1 ) max(𝑎2 , 𝑏2 )
⋅ 𝑝2 ⋅⋅⋅
|𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶| max(𝑎 , 𝑏 )
𝑘 𝑘
𝑝𝑘
∴ 𝐻𝐶𝐹 (𝑎, 𝑏) ⋅ 𝐿𝐶𝑀(𝑎, 𝑏) = 𝑎 ⋅ 𝑏
CO-205: Discrete Structures Tutorial #1 (Pg - 1)
, Discrete A collection of objects with operations Binomial binomial coefficient 𝑛𝐶𝑟 , is also the
Structure defined on them and the accompanying Theorem number of combinations of r elements of
properties form a mathematical structure a set with n elements.
or system. Pascal’s 𝑛 𝑛−1 𝑛−1
( )=( )+( ) , ∀n>0 and
A structure is closed with respect to an Identity 𝑘 𝑘−1 𝑘
operation if that operation always 0≤𝑛≤𝑘
produces another member of the
collection of objects. Set Identities
Counting Multiplication principle of counting. Identity Name
Principles Permutation: an ordered arrangement of A∩U=A
Identity laws
the elements of a set A∪∅=A
r-permutation: an ordered arrangement of A∪U=U
Domination laws
r elements of a set A∩∅ = ∅
𝑛
𝑃𝑟 : the number of r-permutations of a A∪A=A
Idempotent laws
set with n elements A∩A=A
r-combination: an unordered selection of ̅̅̅
𝐴̅ = A Complementation law
r elements of a set
𝑛 A∪B=B∪A
𝐶𝑟 : the number of r-combinations of a Commutative laws
A∩B=B∩A
set with n elements
A ∪ (B ∪ C) = (A ∪ B) ∪ C
Pigeonhole When more than k pigeons are assigned Associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
principle: to k pigeon holes, then at least one pigeon
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
hole must have more than one pigeon. Distributive laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Generalized / If n pigeons are assigned to m pigeon
A∩B=A∪B
Extended holes (given: n>m), then one of the De Morgan’s laws
pigeonhole pigeon holes must contain at least A∪B=A∩B
principle 𝑛−1 A ∪ (A ∩ B) = A
⌊ ⌋ + 1 pigeons. Absorption laws
𝑚 A ∩ (A ∪ B) = A
A∪A=U
Alternately Complement laws
A∩A=∅
If n pigeons are assigned to m pigeon • The set of rational numbers is countable.
holes (given: n>m), then one of the • The set of real numbers is uncountable.
pigeon holes must contain at least ⌈𝑛/𝑚⌉
pigeons.
(𝑎 + 𝑏)𝑛 = ∑𝑛𝑟=0 𝑛𝐶𝑟 𝑎𝑛−𝑟 𝑏𝑟
1. List the members of these sets. b) {x ∈ R | x is the square of an integer}
a) {x | x is a real number such that x2 = 1} c) {2,{2}} d) {{2},{{2}} }
b) {x | x is a positive integer less than 12} e) {{2}, {2,{2}}} f) {{{2}}}
c) {x | x is the square of an integer and x < 100}
d) {x | x is an integer such that x2 = 2} 6. Determine whether each of these statements is true
or false.
2. Use set builder notation to give a description of each a) x ∈ {x} b) {x} ⊆ {x} c) {x} ∈ {x}
of these sets. d) {x} ∈ {{x}} e) ∅ ⊆ {x} f ) ∅ ∈ {x}
a) {0, 3, 6, 9, 12}
b) {−3, −2, −1, 0, 1, 2, 3} 7.1. What is the cardinality of each of these sets?
c) {𝑚, 𝑛, 𝑜, 𝑝} a) {a} b) {{a}}
c) {a, {a}} d) {a, {a}, {a, {a}}}
3. Determine whether each of these pairs of sets are
equal. 7.2. What is the cardinality of each of these sets?
a) {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1} a) ∅ b) {∅}
b) {{1}}, {1, {1}} c) ∅, {∅} c) {∅, {∅}} d) {∅, {∅}, {∅, {∅}}}
4. Suppose that 𝐴 = {2, 4, 6}, 𝐵 = {2, 6}, 𝐶 = {4, 6}, 8. Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑} and 𝐵 = {𝑦, 𝑧}. Find
and 𝐷 = {4,6,8}. Determine which of these sets are a) 𝐴 × 𝐵 b) 𝐵 × 𝐴.
subsets of the other set(s).
9. How many different elements does A × B have if A
5. For each of the following sets, determine whether 2 has m elements and B has n elements?
is an element of that set.
a) {x ∈ R | x is an integer greater than 1}
CO-205: Discrete Structures Tutorial #1 (Pg - 2)
Summary
set a well defined (unordered) collection of Cartesian If 𝐴 and 𝐵 are two nonempty sets the
distinct objects Product product set or Cartesian product 𝐴 × 𝐵 is
element or an object in a set defined as the set of all ordered pairs
member of a (𝑎, 𝑏) with 𝑎 ∈ 𝐴 and 𝑏 ∈ B. i.e.
set 𝐴 × 𝐵 = {(𝑎, 𝑏) | 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵}.
roster method a method that describes a set by listing membership a table displaying the membership of
of set its elements table elements in sets
representation ⌊𝒙⌋ (floor the largest integer not exceeding x
set builder the notation that describes a set by function)
notation of set stating a property an element must have ⌈𝒙⌉ (ceiling the smallest integer greater than or equal
representation to be a member function) to x
∅ (empty set, the set with no members string a finite sequence
null set) empty string a string of length zero
Universal set the set containing all objects under recurrence a equation that expresses the 𝑛𝑡ℎ term 𝑎𝑛
consideration relation of a sequence in terms of one or more of
Venn diagram a graphical representation of a set or sets the previous terms of the sequence for all
S = T (set S and T have the same elements integers 𝑛 greater than a particular integer
equality) A function on a set may be thought of as
S ⊆ T (S is a every element of S is also an element of a set of rules that assign some ‘values’ to
subset of T) T each element of the set. If 𝐴 is a subset
S ⊂ T (S is a S is a subset of T and S ≠ T of the Universal set, 𝑈, the characteristic
proper subset function 𝑓𝐴 of 𝐴 is defined as 𝑓𝐴 (𝑥 ) =
of T) 1, 𝑥 ∈𝐴
{
finite set a set with n elements, where n is a 0, 𝑥 ∉ 𝐴
nonnegative integer Characteristic function is used for
infinite set a set that is not finite computer representation of sets.
Characteristic Characteristic functions of subsets satisfy
|S| (the the number of elements in S
Function the following properties: -
cardinality of
S) 𝑓𝐴∩𝐵 = 𝑓𝐴 ∙ 𝑓𝐵
𝑺∗ the set of all subsets of S 𝑖. 𝑒. 𝑓𝐴∩𝐵 (𝑥 ) = 𝑓𝐴 (𝑥 ) ⋅ 𝑓𝐵 (𝑥 )∀𝑥
(the power set 𝑓𝐴∪𝐵 = 𝑓𝐴 + 𝑓𝐵 − 𝑓𝐴 ∙ 𝑓𝐵
of S) 𝑖. 𝑒. 𝑓𝐴∪𝐵 (𝑥 ) = 𝑓𝐴 (𝑥 ) + 𝑓𝐵 (𝑥 )
A ∪ B (the {𝑥|𝑥 ∈ 𝐴 𝑜𝑟 𝑥 ∈ 𝐵} −𝑓𝐴 (𝑥 ) ⋅ 𝑓𝐵 (𝑥) ∀𝑥
union of sets A 𝑓𝐴⨁𝐵 = 𝑓𝐴 + 𝑓𝐵 − 2𝑓𝐴 ∙ 𝑓𝐵 i.e.
and B) 𝑓𝐴⨁𝐵 (𝑥) = 𝑓𝐴 (𝑥) + 𝑓𝐵 (𝑥 )
A∩B {𝑥|𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∈ 𝐵} −2 𝑓𝐴 (𝑥 ) ⋅ 𝑓𝐵 (𝑥 ) ∀𝑥
(the Properties of If 𝑎, 𝑏, 𝑐 are integers: -
intersection of divisibility of 𝑖𝑓 ( 𝑎|𝑏 𝑎𝑛𝑑 𝑎|𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|(𝑏 + 𝑐)
sets A and B) Integers 𝑖𝑓 ( 𝑎|𝑏 𝑎𝑛𝑑 𝑎|𝑐, 𝑏 > 𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|(𝑏 − 𝑐)
A−B the set containing those elements that are 𝑖𝑓 ( 𝑎|𝑏 𝑜𝑟 𝑎|𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|(𝑏 ⋅ 𝑐)
(complement in A but not in B 𝑖𝑓 ( 𝑎|𝑏 𝑎𝑛𝑑 𝑏|𝑐 ) 𝑡ℎ𝑒𝑛 𝑎|𝑐
of B with i.e. 𝑮𝑪𝑫(𝒂, 𝒃) or • 𝑖𝑓 ( 𝑎, 𝑏 ∈ 𝑍 + 𝑎𝑛𝑑 𝑏 > 𝑎 )𝑡ℎ𝑒𝑛
respect to A {𝑥|𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∉ 𝐵} ≡ 𝐴 ∩ 𝐵̅ 𝑯𝑪𝑭(𝒂, 𝒃) (𝐺𝐶𝐷(𝑎, 𝑏) = 𝐺𝐶𝐷(𝑏, 𝑏 ± 𝑎))
(or the • Euclidean Algorithm to find
difference of A 𝐺𝐶𝐷(𝑎, 𝑏)
and B) ) 𝑳𝑪𝑴(𝒂, 𝒃) • If 𝑝1 , 𝑝2 , … , 𝑝𝑘 are the prime factors of
̅ (the
𝑨 the set of elements in the universal set either 𝑎 or 𝑏 then 𝑎 and 𝑏 can be
complement of that are not in A represented as
A) 𝑎 𝑎 𝑎
𝑎 = 𝑝1 1 ⋅ 𝑝2 2 ⋅⋅⋅ 𝑝𝑘 𝑘 and
A⊕B the set containing those elements in 𝑏 𝑏 𝑏
𝑏 = 𝑝1 1 ⋅ 𝑝2 2 ⋅⋅⋅ 𝑝𝑘 𝑘
(the symmetric exactly one of A or B (not in both) i.e.
{𝑥|(𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∉ 𝐵) 𝑜𝑟 (𝑥 ∈ 𝐵 𝑎𝑛𝑑 𝑥 ∉ 𝐴)} where some 𝑎𝑖 and 𝑏𝑖 may zero. Then it
difference of A
≡ (𝐴 ∩ 𝐵̅ ) ∪ (𝐴̅ ∩ 𝐵) follows that
and B) min(𝑎1 , 𝑏1 ) min(𝑎2 , 𝑏2 )
Inclusion If A and B are finite sets then |𝐴 ∪ 𝐵| = 𝐻𝐶𝐹 (𝑎, 𝑏) = 𝑝1 ⋅ 𝑝2 ⋅⋅⋅
min(𝑎𝑘, 𝑏𝑘)
Exclusion |𝐴| + |𝐵| − |𝐴 ∩ 𝐵| 𝑝𝑘
Principle Similarly |𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − 𝐿𝐶𝑀(𝑎, 𝑏) = 𝑝1
max(𝑎1 , 𝑏1 ) max(𝑎2 , 𝑏2 )
⋅ 𝑝2 ⋅⋅⋅
|𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶| max(𝑎 , 𝑏 )
𝑘 𝑘
𝑝𝑘
∴ 𝐻𝐶𝐹 (𝑎, 𝑏) ⋅ 𝐿𝐶𝑀(𝑎, 𝑏) = 𝑎 ⋅ 𝑏
CO-205: Discrete Structures Tutorial #1 (Pg - 1)
, Discrete A collection of objects with operations Binomial binomial coefficient 𝑛𝐶𝑟 , is also the
Structure defined on them and the accompanying Theorem number of combinations of r elements of
properties form a mathematical structure a set with n elements.
or system. Pascal’s 𝑛 𝑛−1 𝑛−1
( )=( )+( ) , ∀n>0 and
A structure is closed with respect to an Identity 𝑘 𝑘−1 𝑘
operation if that operation always 0≤𝑛≤𝑘
produces another member of the
collection of objects. Set Identities
Counting Multiplication principle of counting. Identity Name
Principles Permutation: an ordered arrangement of A∩U=A
Identity laws
the elements of a set A∪∅=A
r-permutation: an ordered arrangement of A∪U=U
Domination laws
r elements of a set A∩∅ = ∅
𝑛
𝑃𝑟 : the number of r-permutations of a A∪A=A
Idempotent laws
set with n elements A∩A=A
r-combination: an unordered selection of ̅̅̅
𝐴̅ = A Complementation law
r elements of a set
𝑛 A∪B=B∪A
𝐶𝑟 : the number of r-combinations of a Commutative laws
A∩B=B∩A
set with n elements
A ∪ (B ∪ C) = (A ∪ B) ∪ C
Pigeonhole When more than k pigeons are assigned Associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
principle: to k pigeon holes, then at least one pigeon
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
hole must have more than one pigeon. Distributive laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Generalized / If n pigeons are assigned to m pigeon
A∩B=A∪B
Extended holes (given: n>m), then one of the De Morgan’s laws
pigeonhole pigeon holes must contain at least A∪B=A∩B
principle 𝑛−1 A ∪ (A ∩ B) = A
⌊ ⌋ + 1 pigeons. Absorption laws
𝑚 A ∩ (A ∪ B) = A
A∪A=U
Alternately Complement laws
A∩A=∅
If n pigeons are assigned to m pigeon • The set of rational numbers is countable.
holes (given: n>m), then one of the • The set of real numbers is uncountable.
pigeon holes must contain at least ⌈𝑛/𝑚⌉
pigeons.
(𝑎 + 𝑏)𝑛 = ∑𝑛𝑟=0 𝑛𝐶𝑟 𝑎𝑛−𝑟 𝑏𝑟
1. List the members of these sets. b) {x ∈ R | x is the square of an integer}
a) {x | x is a real number such that x2 = 1} c) {2,{2}} d) {{2},{{2}} }
b) {x | x is a positive integer less than 12} e) {{2}, {2,{2}}} f) {{{2}}}
c) {x | x is the square of an integer and x < 100}
d) {x | x is an integer such that x2 = 2} 6. Determine whether each of these statements is true
or false.
2. Use set builder notation to give a description of each a) x ∈ {x} b) {x} ⊆ {x} c) {x} ∈ {x}
of these sets. d) {x} ∈ {{x}} e) ∅ ⊆ {x} f ) ∅ ∈ {x}
a) {0, 3, 6, 9, 12}
b) {−3, −2, −1, 0, 1, 2, 3} 7.1. What is the cardinality of each of these sets?
c) {𝑚, 𝑛, 𝑜, 𝑝} a) {a} b) {{a}}
c) {a, {a}} d) {a, {a}, {a, {a}}}
3. Determine whether each of these pairs of sets are
equal. 7.2. What is the cardinality of each of these sets?
a) {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1} a) ∅ b) {∅}
b) {{1}}, {1, {1}} c) ∅, {∅} c) {∅, {∅}} d) {∅, {∅}, {∅, {∅}}}
4. Suppose that 𝐴 = {2, 4, 6}, 𝐵 = {2, 6}, 𝐶 = {4, 6}, 8. Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑} and 𝐵 = {𝑦, 𝑧}. Find
and 𝐷 = {4,6,8}. Determine which of these sets are a) 𝐴 × 𝐵 b) 𝐵 × 𝐴.
subsets of the other set(s).
9. How many different elements does A × B have if A
5. For each of the following sets, determine whether 2 has m elements and B has n elements?
is an element of that set.
a) {x ∈ R | x is an integer greater than 1}
CO-205: Discrete Structures Tutorial #1 (Pg - 2)
