CS1800 Discrete Structures Spring 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS1800 Discrete Structures
Spring 2022
Homework # 3
Problem 1 [20 pts]: Plushies Everywhere
Consider the following set of plushies that one of your professors owns:
{Shark, Eevee, Kittencorn, Baibianguai, Octo, Toriel, Rokon, Morgana, Dragonair, Vaporeon, Gato}
From those there are 3 sets of interest, labeled below.
● A = {Baibianguai, Octo} for all the pink plushies.
● B = {Vaporeon, Dragonair, Octo, Kittencorn, Gato, Shark} for all the blue plushies.
● C = {Baibianguai, Vaporeon, Dragonair, Eevee, Rokon} for all the Pokemon plushies.
Figure 1 shows all of the plushes this professor owns (sans Shark), for your viewing pleasure.
Using the set definitions for A, B, C and the set of all plushies, write the following sets out in list notation. Simply writing the sets will result in full credit. You may also shorten using initials (e.g. B for Baibianguai).
i. A n B
ii. (A n B) × (A n C)
iii. C - A
iv. A∆(B∆C)
v. p((A n B) n C)
l Baibianguai is the romanized Mandarin name for Ditto. Rokon is the romanized Japanese name for Vulpix. Gato is the Spanish word for cat.
Problem 2 [20 pts]: Venn Diagrams
Use the stencil below to fill out Venn Diagrams for the following sets.
i. A n (B u C)
ii. B - (A - C)
iii. A u B
iv. A∆(C n B)
v. U - A u B
Problem 3 [20 pts]: Friendship is Logical
Let our domain be a set of plushies which include kitten plushies. In this domain, we know that plushies can befriend other plushies. We will define our predicates as follows
● kitten(x) = “x is a kitten plush”
● friends(x, y) = “x is friends with y”
i. Use the predicates, the boolean operators A, V, -, =÷ , =÷ , quantifiers V, a, and =, to translate the following statements to predicate logic.
1. Every plushie is friends with every plushie.
2. Every plushie is friends with at least three kitten plushies.
3. Every plushie is friends with a plushie who is friends with every kitten plushie.
4. None of the plushies are friends with exactly one kitten plushie.
ii. Negate the following formal logic statement:
axVy, (kitten(x) A -kitten(y)) =÷ az, friends(z, x) A -friends(z, y)
(Hint: For this one, it is a good idea to show each step of your negation. Doing so can help you catch subtle but important errors.)
Problem 4 [20 pts]: Deck Building
Let C represent a set of 52 playing cards with four suits (◇, ◇ , 品, ●) each having 13 ranks (Ace,2,3,4,5,6,7,8,9,10,Jack,Queen,King). We define the following additional sets.
● F =Face cards (Jack, Queen, and King)
● B =Black cards
● P =Cards having a rank that is a prime number (2,3,5,7)
● J =One-eyed Jacks (Jack of Hearts, Jack of Spades)
i. Depict these sets as a Venn Diagram and show the cardinality of each distinct region. The regions don’t have to be perfectly to scale - this can be hand-drawn. Only overlap sets that truly overlap. Disjoint sets, those sharing no members, should be rendered as non-overlapping.
ii. Using set operations and the above defined sets, give an expression for the set of cards that are red or face cards or prime numbered or one-eyed Jacks and compute its cardinality.
iii. Give a set expression and compute the cardinality for the set of cards that are not face cards or not prime-numbered cards.
iv. Give a set expression and compute the cardinality for the complement of the set of cards that are either black or prime-numbered but not one-eyed Jacks.
v. Give a set expression and compute the cardinality for the set of cards that are either black non-prime cards or one-eyed Jacks, but not both.
Problem 5 [20 pts]: Survey Says
180 people were surveyed about ice cream they liked. The choices were vanilla, chocolate, and strawberry.
● 18 people refused to answer.
● 6 people liked all three flavors.
● 16 liked vanilla and strawberry. 22 liked vanilla and chocolate. 19 liked chocolate and strawberry.
● Half of the people surveyed liked vanilla.
● Twice as many people liked chocolate as liked strawberry.
When we say half liked vanilla, we mean they liked vanilla and possibly other flavors of ice cream. Similarly, the 22 people that liked vanilla and chocolate include the 6 that like all three flavors.
i. How many people liked chocolate and how many people liked strawberry? Show your work. (Hint: Make a Venn Diagram and fill in the information you know as you go along.)
ii. How many people liked exactly one flavor?
2022-02-15