Name:
COSC 290 Discrete Structures Final Exam
Spring 2019
This exam is designed to be completed in 120 minutes. This exam is closed book and collaboration is not permitted.
There are 7 questions and a total of 80 points available for this exam. Don’t spend too much time on any one question.
If you want partial credit, show as much of your work and thought process as possible.
If you run out of space for answering a question, you can continue your answer on one of the blank pages at the end of the exam. If you do so, be sure to indicate this in two places: (1) below the question, indicate which blank page contains your answer, and (2) on the blank page, indicate which question you are answering.
If the question has a blank line for your answer, please put your final answer on that line.
Question:
1
2
3
4
5
6
7
Total
Points:
10
14
9
10
10
13
14
80
Score:
1
COSC 290 Spring 2019 Final Exam
1. Potpourri.
(a) (2 points) If f : X → Y is one-to-one, then we know that…
⃝ |X|≥|Y| ⃝ |X|≤|Y| ⃝ |X|=|Y| ⃝ Noneoftheabove.
(b) (2 points) Let S be a set and A ⊆ S and B ⊆ S. If |S| = |A| + |B| then which of
the following statements must be true? Check all that apply:
⃝ |A|<|S| ⃝ |B|<|S| ⃝ A∩B=∅ ⃝ A∪B=|S| ⃝ Noneapply.
(c) (3 points) Let T akes be a relation on Students × Courses and T eaches be a re- lation on Professors × Courses. Write an expression—using set and relational operations—that produces a relation R on Students where ⟨s, s′⟩ ∈ R if and only if s and s′ have a professor in common (they need not take the same course).
(d) (3points) Let S := {−1,0,1}. Define R ⊆ P(S)×P(S) where ⟨a,b⟩ ∈ R iff |a| = |b|. Is R an equivalence relation? If you think it is, write out the equivalence classes below. If you think it is not, briefly explain why not.
2
COSC 290 Spring 2019 Final Exam Initials:
2. Probability. There are two coins, C1 and C2. A coin is chosen randomly such that C1 is chosen with probability p and C2 is chosen with probability (1 − p). The chosen coin is then flipped once. The probability of heads for Coin 2 is q and the probability of heads for Coin 1 is xq. In other words, Coin 1 is x times as likley to come up heads as Coin 2. If x < 1 that means Coin 1 is less likely than Coin 2 to come up heads.
For questions (a)-(d) only, you may assume that p = 2, q = 1 and x = 2. 32
(a) (1 point) What is the probability that Coin 1 is chosen and it comes up heads?
(a)
(b) (1 point) What is the probability of heads given that Coin 1 was not chosen (i.e., Coin 2 was chosen)?
(b)
(c) (2 points) What is the probability that the chosen coin comes up heads?
(c)
(d) (2 points) Suppose the chosen coin comes up heads. What is the probability that Coin 1 was chosen?
(d)
3
COSC 290 Spring 2019 Final Exam
Problem 2 continued...
For the remaining questions, you may assume only that 0 < p < 1 and 0 < q < 1 and 0 < x < ∞.
(e) (4 points) Consider the event “the chosen coin came up heads” and the event “Coin 1 was chosen”. Are these events independent? Explain your answer. Note: if your answer depends on the values of p, q, and x, then explain under what conditions independence occurs.
(f) (4 points) Suppose we learn that the chosen coin comes up heads. Under what conditions is it more likely that the chosen coin is Coin 1? Your answer should be some expression involving a subset of the variables x, p, q.
4
COSC 290 Spring 2019 Final Exam Initials:
3. Logic. Let P be a set of persons, C a set of ice-cream makers, and F a set of flavors. Define predicate Likes(p,f) to mean person p likes flavor f and predicate Makes(c,f) to mean company c makes flavor f.
(a) (3 points) Write a logical expression that states that ice-cream maker Ben makes exactly one flavor.
(b) (3 points) Define a new predicate AllGood(c) that is true when every flavor made by ice-cream maker c is liked by someone.
(c) (3 points) Write a logical expression that states any flavor that is liked by everyone is made by ice-cream maker Jerry. (Note: Jerry may make other flavors that not everyone likes.)
5
COSC 290 Spring 2019 Final Exam
4. Let P := { p, q, r, s } be a set of four boolean variables. Let Φ be the set of propositions
overthevariablesinP. Forexample,(p∨¬p)∈Φand((q∧s) =⇒ (p∨¬r))∈Φ.
Let R be a relation on Φ × Φ. The relation R is defined as follows: ⟨φa, φb⟩ ∈ R if and only if (φa =⇒ φb) is always true regardless of the truth values assigned to the variables in P.
(a) (1 point) Give an example ⟨φa, φb⟩ such that ⟨φa, φb⟩ ∈ R.
(b) (1 point) Give an example ⟨φa, φb⟩ such that ⟨φa, φb⟩ ̸∈ R.
(c) (3 points) A relation is a partial order if it satisfies which of the following properties? Check all that apply.
⃝ reflexivity
⃝ irreflexivity ⃝ symmetry
⃝ antisymmetry ⃝ asymmetry ⃝ transitivity
6
COSC 290 Spring 2019 Final Exam Initials:
Problem 4 continued...
(d) (1 point) Consider the following claim: R is a partial order. Is this claim true? ⃝Yes ⃝No
(e) (4 points) Prove your answer to part (d).
7
COSC 290 Spring 2019 Final Exam
5. The NAND connective, denoted ↑, is logically equivalent to the “NOT” of an “AND.”
In other words, p ↑ q ≡ ¬(p ∧ q). Here is its truth table:
(a) (2 points) Give an expression that is logically equivalent to ¬p but the only logical connective is ↑ (it can appear more than once).
pq
p∧q ¬(p∧q) p↑q
TT TF FT FF
TFF FTT FTT FTT
(a)
(b) (2 points) Give an expression that is logically equivalent to p∨q but the only logical
connective is ↑ (it can appear more than once).
(b) 8
COSC 290 Spring 2019 Final Exam Initials:
(c) (6 points) Let P := {p1,p2,...,pn } be a set of atomic propositions. Let S denote the set of propositions that use ∨ and ¬. Formally, a proposition φ is in S iff one of the following conditions is met:
1. φ:=pforsomep∈P,or
2. φ:=¬αwhereα∈S,or
3. φ := α ∨ β where α ∈ S and β ∈ S.
Let N be the set of propositions that use only ↑. Formally, ψ is in N iff one of the following conditions is met:
i. ψ:=pforsomep∈P,or
ii. ψ := α ↑ β where α ∈ N and β ∈ N.
Provethatforanyφ∈S,thereexistsψ∈N suchthatφ≡ψ.
9
COSC 290 Spring 2019 Final Exam
6. Counting. There are 8 kindegarten students – Alice, Bob, Ciao, Divesh, Elijah, Fernando, Greta, and Hans – who will be lined up for recess. The teacher has a set of rules and each day picks a subset of rules that must be followed. Here are the rules:
Rule 1 Alice must not be last.
Rule 2 Bob is adjacent to Ciao, but can be directly before or after Ciao. Rule 3 Divesh is always second.
(a) (2 points) How many possible lineups are there that satisfy rule 1?
(a)
(b) (2 points) How many possible lineups are there that satisfy rule 2?
(b)
(c) (2 points) How many possible lineups are there that satisfy rules 2 and 3?
(c)
10
COSC 290 Spring 2019 Final Exam Initials:
Problem 6 continued...
(d) (3 points) How many possible lineups are there that satisfy rule 1 or rule 3?
(d)
(e) (4 points) How many possible lineups are there that satisfy all three rules?
(e) 11
COSC 290 Spring 2019 Final Exam
7. Below is a set of statements. Each statement expresses a property that may hold on R, which is a relation on some set A. The question is: if the statement is true, then which property or properties are implied? Check all properties that are implied or N/A if none are implied.
The possible implied properties are: R reflexivity, IR irreflexivity, S symmetry, antiS antisymmetry, AS asymmetry, T transitivity.
For example, if the statement was ∀a ∈ A : ⟨a, a⟩ ̸∈ R, then the implied property is IR.
(a) (2points) ∀a∈A:∀b∈A:(⟨a,b⟩∈R) =⇒ (⟨b,a⟩∈R)
⃝R ⃝IR ⃝S ⃝antiS ⃝AS ⃝T ⃝N/A
(b) (2points) ∀a∈A:∀b∈A−{a}:(⟨a,b⟩∈R) ⇐⇒ (⟨b,a⟩̸∈R)
⃝R ⃝IR ⃝S ⃝antiS ⃝AS ⃝T ⃝N/A
(c) (2 points) R ⊆ R−1
⃝R ⃝IR ⃝S ⃝antiS ⃝AS ⃝T ⃝N/A
(d) (2 points) R ◦ R ⊆ R
⃝R ⃝IR ⃝S ⃝antiS ⃝AS ⃝T ⃝N/A
In the questions below, let AA := {⟨a,a⟩ : a ∈ A}.
(e) (2 points) R ∩ AA = ∅
⃝R ⃝IR ⃝S ⃝antiS ⃝AS ⃝T ⃝N/A
(f) (2 points) R ∩ R−1 ⊆ AA
⃝R ⃝IR ⃝S ⃝antiS ⃝AS ⃝T ⃝N/A
(g) (2 points) AA ⊆ R
⃝R ⃝IR ⃝S ⃝antiS ⃝AS ⃝T ⃝N/A
12
COSC 290 Spring 2019 Final Exam Initials:
This page is intentionally blank. Label any work with the corresponding problem number.
13
COSC 290 Spring 2019 Final Exam
This page is intentionally blank. Label any work with the corresponding problem number.
14