Description
1 attachmentsSlide 1 of 1attachment_1attachment_1
Unformatted Attachment Preview
CSCI/MATH 2112
Discrete Structures I
Assignment 1
Due: May 18, 11:59PM Atlantic Standard Time
Please write down your name and B00 number on your solution
Note that the set of natural numbers N includes 0.
Problem 1 (4pts): The following sets are written in the set comprehension notation. Please list their
elements explicitly, e.g., {x | x ∈ N, x < 4} = {0, 1, 2, 3}.
• {x | x ∈ N, x is even and x is prime}
• {x | x ∈ N, x is even and x is odd}
• {S | S ∈ Pow({0, 1, 2, 3}), #S = 2}
• {A | A ∈ Pow(N), #A = 1}
Problem 2 (3pts): The set {2, 4, . . .} is ambiguous. It can mean at least three different sets. Please
describe three different sets using the set comprehension notation.
Problem 3 (3pts): Find the power sets of the following sets.
• {6, 7, 8}
• {∅}
• {∅, {∅}, {∅, {∅}}}
Problem 4 (8pts): Suppose A, B, C are sets. Are the following statements true? If it is true, give an
example. If it is not true, give a counter example.
• A ∪ (B ∪ C) = (A ∪ B) ∪ C.
• A × (B × C) = (A × B) × C.
• If A ⊆ B and B ⊆ C, then A ⊆ C.
• A − B ⊆ A.
1
Problem 5 (6pts): Suppose U is a set. Let X ⊆ U , we write X c to mean the set {x | x ∈ U, x ∈
/ X}. We
call X c the complement set of X with respect to U .
Now let U = {x | x ∈ N, 0 ≤ x ≤ 10}. Moreover, let S = {4, 3, 6, 7, 1, 9} and T = {5, 6, 8, 4} be subsets
of U . Write down the following sets explicitly. Note: the set of natural numbers N includes 0.
• Sc
• S ∩ Sc
• S ∪ Sc
• S − Sc
• S − Tc
• (S ∩ T c )c
Problem 6 (1pt):
Draw the diagram that represents the relation {(a, a), (a, b), (b, c), (c, b), (c, d), (d, a), (d, b)}.
Problem 7 (5pts): Here is a diagram for a relation R on a set A.
• Write down the sets A and R explicitly.
• Is the relation R reflexive? Symmetric? Transitive? If one of these properties fails to hold, explain
why.
x
y
z
u
v
w
Problem 8 (4pts) A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then
a = b is called antisymmetric. Give an example of a relation on a set that is
• Both symmetric and antisymmetric.
• Neither symmetric nor antisymmetric.
You must represent each relation in set notation as well as a directed graph.
Problem 9 (4pts): Let A = {a, b, c, d, e}. Find the transitive closure of the following relations on A. You
must represent each closure in set notation as well as a directed graph.
• {(a, c), (b, d), (c, a), (d, b), (e, d)}.
• {(a, b), (a, c), (a, e), (b, a), (b, c), (c, a), (c, b), (d, a), (e, d)}.
2
Problem 10 (2pts): Let A be the set {1, 2, 3}. Find an example of a relation R on A such that it satisfies
the following:
• Let R1 be the transitive closure of R.
• Let R2 be the reflexive closure of R1 .
• Let R3 be the symmetric closure of R2 .
• R3 is not transitive.
You must represent the relation R in set notation as well as a directed graph.
3
Purchase answer to see full
attachment
Tags:
math
algebra
notation
User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.
Reviews, comments, and love from our customers and community: