6.042 Exam 1

October 18, 2000

Name: Tutorial Leader: DO NOT WRITE IN THIS SPACE

Problem 1:  / 30
Problem 2:  / 25
Problem 3:  / 15
Problem 4:  / 8
Problem 5:  / 32
Problem 6:  / 30
Problem 7:  / 40
Problem 8:  / 20
Total:  / 200

Problem 1 [30 points] Predicates and Quantifiers

Use the following propositions where the universe of discourse is the set of all natural numbers:

P (n) : n is a perfect square
Q(n) :  n is prime
R(n, m) :  n < m
S(n, m) :  n divides m
T (n, m) :  n = m

Express each of the following statements using quantifiers, logical connectives, and the propositions listed above, along with variables and integers.

(a) (5 points) 4 is a perfect square and 4 is greater than 1.

(b) (5 points) There is a natural number that divides all natural numbers.

(c) (5 points) Two natural numbers are equal exactly when neither is less than the other.

(d) (5 points) A natural number n that is greater than 1 is prime exactly when the only positive natural number less than n that divides n is 1.

(e) (5 points) A natural number n is a perfect square only if there is a positive natural number (strictly) between 1 and n that divides n.

(f) (5 points) Given only the statements (a)-(e) above and the standard rules of propositional and quantifier reasoning, can you conclude that 4 is not prime? If not, state a fact you can use together with the statements (a)-(e) to conclude that 4 is not prime (your fact should not mention the number 4). If so, just list which of the statements (a)-(e) above are necessary.

Problem 2 [25 points] Relations For each relation listed in parts (a) through (e) circle all terms listed that apply to it.

(a) (5 points) A = {a, b}, R = {(a, a), (a, b)}.

(b) (5 points) aRb whenever a and b are students and either a = b or a has a GPA greater than or equal to that of b. (You may assume that all students have different GPAs).

(c) (5 points) aRb whenever a and b are real numbers and a = b^{x} for some rational number x.

(d) (5 points) aRb whenever a and b are rational numbers and ab is an integer.

(e) (5 points) aRb whenever a and b are integers such that there is a positive integer k such that 3^{k}|a and 3^{k}|b and 3^{k+1} |̸a and 3^{k+1} |̸b.

Problem 3 [15 points] Directed Graphs Recall that a tournament graph is a directed graph in which between any two different nodes a and b there is an edge either from a to b or from b to a but not both, and there are no other edges in the graph. For each of the following, answer true or false and give a brief justification of your answer.

(a) (5 points) There is no tournament graph on 4 nodes with an Euler circuit.

(b) (5 points) There is no tournament graph on 5 nodes with an Euler circuit.

(c) (5 points) There is no tournament graph on 225 nodes with an Euler circuit.

Problem 4 [8 points] Structured Reasoning

For this proof, fill in the predicate and quantifier rules used for each step denoted with a *, and say which statements they are based on.

Given: ∀x∃y[Q(x, y) ∨ R(x, y)] Prove: ∀x[∃yQ(x, y) ∨ ∃yR(x, y)] Proof:

1. Let x_{0} be arbitrary.

2. ∃y[Q(x_{0}, y) ∨ R(x_{0}, y)] Universal Instantiation, from Given

3. Q(x_{0}, y_{0}) ∨ R(x_{0}, y_{0}) Existential Instantiation, from 2.

4. ∃yQ(x_{0}, y) ∨ ∃yR(x_{0}, y) :

4.1. case i: Assume Q(x_{0}, y_{0}). *4.1.1. ∃yQ(x_{0}, y) \underline{Existential Generalization, from 4.1} *4.1.2. ∃yQ(x_{0}, y) ∨ ∃yR(x_{0}, y) \underline{Addition, from 4.1.1}

4.2. case ii: Assume R(x_{0}, y_{0}). 4.2.1. ∃yR(x_{0}, y) 4.2.2. ∃yQ(x_{0}, y) ∨ ∃yR(x_{0}, y)

*4.3. QED ∃yQ(x_{0}, y) ∨ ∃yR(x_{0}, y) \underline{Proof by cases from 3, 4.1.2, and 4.2.2} *5. QED ∀x[∃yQ(x, y) ∨ ∃yR(x, y)] \underline{Universal Generalization, from 1 and 4.3} Problem 5 [32 points] Proof Comprehension

For each of the following proofs, determine whether it is valid or invalid. If it is valid, say so. If it is invalid, what about the proof is incorrect? (NOTE: If you say a proof is valid, feel free to give some explanation for why you think that proof is valid. This may give you some partial credit if you are incorrect.)

(a) (8 points)

Theorem: 2 = 1. Proof:

1. Assume 2 = 1.

2. x^{2} + 2 = x^{2} + 1.

3. 2xdx = 2xdx. (differentiating both sides)

4. 2 = 2 (dividing both sides by xdx)

5. Therefore, 2 = 1 (QED)

(b) (8 points)

Theorem: All rational numbers x greater than or equal to 1 are such that x ≤ 2^{x}. Proof: Let P (n) be the statement “n ≤ 2^{n}.”

1. We know that 1 ≤ 2^{1} = 2. Therefore, P (1).

2. Assume P (n) where n ≥ 1.

3. Then, n ≤ 2^{n}

4. Adding 1 to both sides, we get n + 1 ≤ 2^{n} + 1

5. Substituting that 1 ≤ n, we get n + 1 ≤ 2^{n} + n.

6. Substituting from step 3 into the RHS of step 5, we get n + 1 ≤ 2^{n} + 2^{n}

7. Simplifying, we get n + 1 ≤ 2^{n+1}.

8. Thus, P (n + 1). Therefore, by induction, ∀nP (n).

(c) (8 points)

Theorem: If G is a finite graph with positive integer-weighted edges that has a spanning tree, it has a minimal spanning tree (a spanning tree T such that the sum of the weights of the edges in T is as small as it could be for any spanning tree).

Proof: Every spanning tree of G has a total weight w which is non-negative integer. Therefore, the set of possible total weights of spanning trees is a subset of the non-negative integers. By the well-ordering property, since there is a spanning tree, there must be a least weight of a spanning tree, and therefore there must be a spanning tree that has that weight. Thus, there is a minimal spanning tree.

(d) (8 points)

Theorem: There are infinitely many prime numbers.

Proof: Let S be the set of all prime numbers. Now let k = 1 + ∏_{p∈S} p. Note that k is not divisible by any p in S since the remainder when dividing by p would be 1. Furthermore, notice that if p is any element of S then k = 1 + ∏_{q∈S} q ≥ 1 + p > p. But this is a contradiction. Therefore, there must be infinitely many prime numbers.

Problem 6 [30 points] Hamiltonian Circuits

In this problem you will prove that for any positive integer n, any 2n by 2n grid graph has a Hamiltonian circuit.

An n by m grid graph is made up of vertices described as pairs of integers (x, y) where 0 ≤ x < n and 0 ≤ y < m. There is an edge between two vertices if their x-coordinates differ by 1 or if their y-coordinates differ by 1 but NOT if both differ by 1.

So, for example, there would be edges between the vertices (2, 3) and (3, 3) but not between (2, 3) and (3, 2).

(a) (4 points) Draw a 4 by 4 grid graph. Label vertices (1, 3), (2, 2), and (2, 3).

(b) (10 points) Prove that the chromatic number of any m by n grid graph is 2 (for m, n > 1).

(c) (16 points) Prove by induction that any 2n by 2n grid graph has a Hamiltonian circuit for n ≥ 1. (Other proof methods will not get credit) Note: this question does not have anything to do with the question in part (b).

Problem 7 [40 points] State Machines and Invariants

Consider the following algorithm, that, given a number, produces the prime factorization of that number. The prime factorization of a number is a list of all primes that divide that number, where primes may be listed multiple times if they divide the number multiple times. The product of all the numbers in the list should be equal to the original number.

Assume that Append (List, i) takes a list and adds the element i to the beginning of it. Assume that () refers to the list with no elements.

FactorPrime (n ∈ ℕ):

1. i := 2.

2. List := ().

3. m := n.

4. IF m = 1 THEN FactorPrime(n): = List.

5. IF i|m THEN Append (List, i). m := m/i.

ELSE

i := i + 1.

6. Go to step 4.

(a) (10 points) Represent this algorithm as a state machine.

(b) (10 points) Using an invariant, prove that if the algorithm ever gets to the point where m = 1, then the list is a factorization (not necessarily a prime factorization) of its input n.

(c) (10 points) Prove that the list never contains any numbers that are not prime.

(d) (10 points) Prove that this algorithm always terminates. 13 Problem 8 [20 points] Bags and Stacks

This problem involves two labeled state machines, called Bag and Stack, each of which keeps track of a collection of integers. A “client” can interact with each using requests and responses. Both support the same kinds of operations: insert and get, though the operations behave a little differently in the two machines.

Bag maintains a “bag” of integers, which is like a set of integers except it allows repeats. Written out in detail:

Bag Labeled State Machine:

Q: B, a bag of integers req, either insert(x), get, or null resp, either OK , an integer, error, or null

Q_{0}: B is the empty bag, req = resp = null

L: Input: insert(x), get Internal: perform(insert(x)),perform(get) Output: respond(r)

δ: insert(x):

Can occur: Anytime

Effect: if req = null then req := insert(x) get:

Can occur: Anytime

Effect: if req = null then req := get perform(insert):

Can occur if: req = insert(x) Effect: add x to B; resp :=OK

perform(get):

Can occur if: req = get

Effect:

if B is nonempty then choose any element x in B and remove one copy from B; resp := x else resp := error

respond(r):

Can occur if: resp = r, r ≠ null Effect: req := null; resp := null The other machine, Stack, differs from Bag only in its state and the perform transitions:

Stack Labeled State Machine:

Q: S, a sequence of integers req, resp, as for Bag

Q_{0}: S is the empty sequence, req = resp = null

δ: perform(insert):

Can occur if: req = insert(x)

Effect: S = xS, where xS is the concatenation of x and S;

resp :=OK

perform(get):

Can occur if: req = get

Effect:

if S is nonempty then resp := head(S) (the first element of S); S := tail(S) (all but the first element)

else resp := error

For this problem, you need give only a trace or an abstraction relation that works to justify your answer. If you give an abstraction relation, you do not have to prove it is correct.

(a) (10 points) Does Stack implement Bag? If your answer is yes, then give an abstraction relation. If it is no, then give an example of a trace of Stack that is not a trace of Bag.

(b) (10 points) Does Bag implement Stack? If so, give an abstraction relation. If not, give a trace of Bag that is not a trace of Stack.