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.