共计 4681 个字符，预计需要花费 12 分钟才能阅读完成。
COMP1805ABC (Winter 2021) − “Discrete Structures I”
Practice Questions for the Final Exam
This semester, the final exam for COMP1805ABC will be completed online as a multiple-choice activity in
cuLearn. The exam will be 2 hours long. It will open up at 7:00 pm. You can start your exam between 7:00 pm
and 7:30 pm. Once you begin the exam you will have 2.0 hours to complete and submit it. Please follow this
link for the exact dates and times. https://carleton.ca/ses/exam-… The exam will be open-book (in that
you may refer to the lecture slides, the textbook, the discrete math study center website, or your handwritten
notes) and basic, non-graphing calculators will be permitted. Any other electronic devices or unauthorized web
sites will be prohibited.
This collection of questions is presented here to help prepare for your final exam. Solutions will not be provided
but you may email your instructors and/or teaching assistants with any questions you might have. Best of luck
with your preparations!
Is a logical expression like (¬ ( ¬ (((𝑄 → 𝑅) ∨ 𝑄) ∨ 𝑃))) a tautology, a contradiction, or a contingency?
Justify your answer using only truth tables and then again using only the logical equivalences.
Is (¬ ((𝑅 ∨ (𝑃 ∧ 𝑄)) ∨ (𝑅 → 𝑄))) logically equivalent to (¬ ((( ¬ (¬𝑃)) ∨ 𝑄) ∨ 𝑅))?
How would you justify your answer if the answer was yes? What if the answer was no?
What are the dimensions required for a truth table of (¬ (¬ (𝑃 ∨ ((¬ 𝑄) → 𝑅))))?
Complete the truth table and use it to construct the full disjunctive normal form of this expression.
COMP1805ABC (Winter 2021) − “Discrete Structures I”
Practice Questions for the Final Exam
Using only the rules of inference and the logical equivalences from class and the notes, show that the
following argument is valid. You may assume that all the premises given are true. Make sure that you include
both the rule and the line number(s) to which that rule is applied.
- ∀𝑥(𝐴(𝑥) ∨ 𝐷(𝑥))
- ∀𝑥(¬𝐴(𝑥) ∨ ¬𝐵(𝑥))
- ∃𝑥(¬𝐶(𝑥) ∧ 𝐵(𝑥))
Conclude: ∃𝑥(¬𝐶(𝑥) ∧ 𝐷(𝑥))
Note this is an example of Question 3 from Quiz 2
For this question about predicate logic, please note that, even though the ‘nonsense’ words are only nouns
and verbs, you do not need to know the meaning of the words being used in order to answer this question.
Consider a universe of discourse that contains (among other things) all farthings. If the predicates S(x), Q(x),
and T(x) represented the assertions x jilled, x quinzeed, and x scrims, respectively, then construct an accurate
translation, using quantified predicates, of the following:
If any farthings jilled then that farthing quinzeed or that farthing did not scrim.
Can you determine if ((((𝑍 ∪ 𝑌) ∪ 𝑋) ∪ (𝑍
𝐶
))) and ((𝑌 ∩ (𝑍 ∖ (𝑋 ∪ 𝑍)))
𝐶
) are equivalent?
n.b., 𝐴 ∖ 𝐵 and 𝐴
𝐶 denote the set difference between A and B and the complement of A, respectively.
COMP1805ABC (Winter 2021) − “Discrete Structures I”
Practice Questions for the Final Exam
Which of the following sets is equivalent to the Universe? Justify your answer.
What type of sequence is 102, 569, 1036, 1503, 1970, 2437?
What about 79, 312, 545, 1011, 1244, 1477?
How can you justify your answers?
What expression, using Sigma notation, represents the sum of the integers from 37 to 211, inclusive?
What is the closed form of this expression?
Consider these adjacency matrices and answer the questions below (for each graph being represented):
How would you perform a breadth-first search starting from a random vertex? A depth-first search?
How would you represent the resultant search trees using an adjacency matrix? An adjacency list?
How many of the vertices in the search trees are cut vertices? Cut edges?
What is the chromatic number of each graph? How can you prove it?
COMP1805ABC (Winter 2021) − “Discrete Structures I”
Practice Questions for the Final Exam
Consider the collection of functions plg(), bar(), foo(), adv(), and wcr(), each of each is associated with an
unspecified operation that has a worst-case time complexity specified below.
The function call “plg()” is an operation with a worst-case time complexity of Θ(𝑛)
The function call “bar()” is an operation with a worst-case time complexity of Θ(𝑛
2
)
The function call “foo()” is an operation with a worst-case time complexity of Θ(𝑛
2
)
The function call “adv()” is an operation with a worst-case time complexity of Θ(𝑛)
The function call “wcr()” is an operation with a worst-case time complexity of Θ(𝑙𝑜𝑔 𝑛)
g = n
while (g > 1):
k = n
while (k > 1):
i = n
while (i > 1):
q = n
while (q > 1):
plg()
q = 1
bar()
i = i – 1
foo()
k = k / 2
c = n^2
while (c > 1):
adv()
c = c – 1
wcr()
g = g – 1
What is the time complexity of this algorithm? (Note this example is taken from Tutorial 6 Quiz)
COMP1805ABC (Winter 2021) − “Discrete Structures I”
Practice Questions for the Final Exam
Consider the following functions:
For what functions 𝑔(𝑥) would each of these functions be O(𝑔(𝑥))? Ω(𝑔(𝑥))? Θ(𝑔(𝑥))?
What witnesses c and k could you use to justify your answers?
For a domain of {′𝑔′, ′ℎ′, ′𝑖′, ′𝑗′, ′𝑘′, ′𝑙′, ′𝑚′, ′𝑛′} and a codomain of {3, 4, 5, 6, 8}, consider the following function:
𝑓(′𝑔′) = 3 𝑓(′ℎ′) = 4 𝑓(′𝑖′) = 8 𝑓(′𝑗′) = 6
𝑓(′𝑘′) = 6 𝑓(′𝑙′) = 3 𝑓(′𝑚′) = 3 𝑓(′𝑛′) = 5
Is this function injective? Surjective? Bijective?
If your answer to any of these is no, what you would need to change to grant it this property?
Consider the following binary relation on the set {0, 1, 2, 3, 4, 5, 6}:
{(0, 1), (0, 3), (1, 2), (1, 4), (2, 1), (2, 4), (2, 6), (3, 1), (3, 2), (3, 5), (4, 0), (4, 4), (4, 6), (5, 0), (5, 2), (5, 6), (6, 1), (6, 6)}
Is this relation reflexive? Symmetric? Transitive?
If your answer to any of these is no, then complete the closure required for a relation with that property.