COMPSCI 250 Introduction to Computation First Midterm Fall 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMPSCI 250
Introduction to Computation
First Midterm Fall 2021
Question 1 (20): Blaze has a set T = {a, d, m, o} of chew toys, consisting of an Antler, a Dinosaur, a Marrowbone, and an Octopus.
Every morning Blaze chooses one or more of her toys to play with while waiting for her walk. Let W = {Mon, Tue, Wed, Thu} to a particular set of weekdays, and define the predicate
C : T × W so that C(x, y) means “Blaze chooses toy x on weekday y”.
Translate each statement as according to the directions:
● (a, 2) (to English) (Statement I) C(a, Wed) · C(o, Wed)
Solution: Blaze chose the Antler or the Octopus on Wednesday, but not both.
● (b, 3) (to symbols) (Statement II) If Blaze chose the Antler on either Tuesday or Wednes-
day, then she also chose the Octopus on Wednesday.
Solution: (C(a, Tue) v C(a, Wed)) → C(o, Wed)
● (c, 3) (to English) (Statement III) (C(a, Wed) v C(o, Tue)) → (-C(a, Tue)A -C(o, Tue)) Solution: If Blaze chose either the Antler on Wednesday or the Octopus on Tuesday, then she did not choose either the Antler on Wednesday or the Octopus on Tuesday.
● (d, 2) (to symbols) (Statement IV) Blaze chose the Dinosaur on each day of the week. Solution: Vy : C(d, y). Alternatively, C(d, Mon) A C(d, Tue) A C(d, Wed) A C(d, Thu) .
● (e, 3) (to English) (Statement V) Vx : ay : C(x, y)
Solution: Every toy was chosen on at least one day of the week.
● (f, 3) (to symbols) (Statement VI) The Marrowbone was chosen on Thursday and on no other days of the week.
Solution: Vy : C(m, y) 4 (x = Thu) . Alternatively, -C(m, Mon) A -C(m, Tue) A -C(m, Wed) A C(m, Thu) .
● (g, 4) (to English) (Statement VII) au : av : Vw : C(w, Thu) → [(u = w) v (v = w)] Solution: Blaze chose no more than two toys on Thursday. Alternatively, there exists two toys u and v such that every toy chosen on Thursday was either u or v .
Question 2 (30): These questions use the definitions, predicates, and premises on the supplemen- tary sheet.
● (a, 10) Given only that Statements I, II and III are true, determine the truth values of the four propositions p = C(a, Tue), q = C(a, Wed), r = C(o, Tue), and s = C(o, Wed). You may use a truth table or a deductive sequence proof. (Hint: Exactly one of the four propositions is true. I intended for there to be only one solution, but there are two. You need to find both, one of which is consistent with the hint.) Solution:
If we assume r, then we can derive q v r by Joining and get -r by Modus Ponens on III and then Separation. This is a contradiction, so r must be false.
If we assume q, we derive -s from I, by the definition of · and also derive s from II, using Joining to get p vq and then Modus Ponens. This is a contradiction, so q is false, and then we know that s is true by I.
Once we know that s is true and that q and r are false, all three statements I, II, and III are satisfied whether p is either true or false. Statement I does not involve p, Statement II is trivially true because s is true, and Statement II is vacuously because q and r are both false. So there are two solutions to this problem, and the one where p is false also satisfies the hint.
● (b, 20) Assuming that Statements I-VII are all true, prove that Blaze chose the Antler on Monday. (You may want to quote consequences of I-III from part (a) of this question.) You may use either English or symbols, but make it clear each time you use a quantifier proof rule. (Use the hint from 2a for this problem, so that you use the solution
to 2a that is consistent with that.)
Solution:
Specifying V to a, we get aw : C(a, w). Let w be the day on which the Antler was chosen. The conclusion from Question 2 part (a) (with the hint) tells us that Blaze did not choose the Antler on either Tuesday or Wednesday, so w must there for be either Monday or Thursday.
Using Instantiation on VII, let u and v be two toys such that C(z, Thu) → [(u = z)v(v = z)]. By Specification on IV to Thursday, we know C(d, Thu). By Specification on VI to Thursday, we get C(m, Thu) 4 (Thu = Thu), which implies C(m, Thu). So u and v must d and m, in either order, and it follows that C(a, Thu) is false and so C(a, Mon) is true.
Question 3 (20): The following are ten true/false questions, with no explanation needed or wanted, no partial credit for wrong answers, and no penalty for guessing. Some of them use the sets, relations, and functions defined on the supplemental sheet, but you should assume the truth of Statements I-VII only if explicitly told to.
● (a) Assuming that Statements I-VII in Question 1 are all true, we cannot determine whether Blaze chose the Octopus on Monday.
Solution: TRUE. We know she chose the Octopus at least once, but we know she chose it on Wednesday and not Tuesday. The statements can be consistent with her also choosing it on Monday, or with her not choosing it.
● (b) Let R be a relation from a set A to a set B. Then R is a one-to-one function if and only if for any element a of A, there exists at most one element b of B such that R(a, b) is true.
Solution: FALSE. The correct definition would be that for any b, there exists at most one a.
● (c) f0f = 1.
Solution: FALSE. The empty set has no elements, so its size is 0. If we instead said “f{0}f”, the size would be 1 .
● (d) If p is any prime number, and “!” is the factorial function, then p! + 1 must be a prime number.
Solution: FALSE. p = 5 is a counterexample, since 5! + 1 = 121 = 11 × 11 .
● (e) If R is an equivalence relation on a set A, and x and y are any elements of A, then if [x] [y], then [x] n [y] = 0.
Solution: TRUE. This was proved as part of the Partition Theorem.
● (f) {0} C {a}, where a is a string.
Solution: FALSE. While the empty set itself is a subset of any set, the set containing empty set is only a subset of another set if the latter also contains the empty set as a member.
● (g) It is not the case that every surjection (onto function) has an inverse function. Solution: TRUE. It has an inverse if and only if it is also an injection, and many surjections are not injections.
● (h) If A and B are sets, and A C B, then A n B = 0 and A u B = B must both be true. Solution: FALSE. The second statement is only true if A and B are disjoint, but the second statement is always true.
● (i) The statement “If I am arguing, then you paid” is the contrapositive of the statement “If I am not arguing, then you did not pay”.
Solution: FALSE. This is the inverse, not the contrapositive.
● (j) Let Σ be the set {a, b} and let Σ* be the set of all finite strings over Σ. Define the relation R C Σ* × Σ* such that R(u, v) means “u is either a prefix of v or a suffix of v , or both”. Then R is not a partial order.
Solution: TRUE. R is not transitive. a is a prefix of ab, and ab is a suffix of bab, but a is neither a prefix nor a suffix of bab .
Question 4 (30+5): Here are some straightforward number theory questions.
● (a, 5) Show the steps of the Euclidean Algorithm to determine the natural g that is the greatest common divisor of 726 and 1463.
Solution: 1463%726 = 11, 726%11 = 0, so the GCD is 11 .
● (b, 5) Give complete factorizations of 726 and 1463. (The solution of part (a) should save you some calculation.)
Solution: 72 = 11 × 66 = 2 × 3 × 11 × 11, 1463 = 11 × 133 = 11 × 7 × 19 .
● (c, 10) Let y and z be any two positive naturals. Let a be the greatest common divisor
of y and z. Prove that y/a has a multiplicative inverse modulo z/a and that z/a has an inverse modulo y/a. Describe how you would compute these two inverses.
Solution: This follows from the Inverse Theorem if we know that y/a and z/a are relatively prime. (We know that they are integers because a divides both y and z.) Suppose that some natural b were a common divisor of y/a and z and b > 1 . Then ba would be a common divisor of y and z, but this ba would be larger than the alleged greatest common divisor, a contradiction. So no such b exists, and y/a and z/a are relatively prime.
● (d, 10) Let g be the greatest common divisor found in part (a). Find the inverse of 726/g modulo 1463/g and the inverse of 1463/g modulo 726/g, making clear which is which. Solution: We want the inverse of 66 modulo 133 and the inverse of 133 modulo 66 . The Euclidean Algorithm gives us 133 - 2 × 66 = 1 on the first nontrivial step. We write 133 = 1 × 133 + 0 × 66, 66 = 0 × 133 + 1 × 66, and 1 × 133 - 2 × 66. The inverse of 66 modulo 133 is -2, and the inverse of 133 modulo 66 is just 1 .
● (e, 5XC) Let D be the division relation, so that for any two naturals D(a, b) means “a divides b, or equivalently b%a = 0”. Let S be the set {x : D(x, 726)v D(x, 1463)}. Draw a Hasse diagram for the set S using the relation D .
Solution:
726 / | \
66 242 363
/ | X X |
6 22 33 121
| X X | / \
2 3 11
1
1463 / |
77 209 | X
11 7
\
133
X |
19
The X’s, represent two crossing lines in the Hasse diagram. For example, 2 has lines upward to 6 and 22, 3 has lines upward to 6 and 33, and 11 has lines upward to 22, 33, 121, and 77. There are lines from 1 to all five primes on the next level.
2022-02-12