Exam 1 Solutions

October 24, 2000

Problem 1 [30 points] Predicates and Quantifiers

(a) (5 points) P (4) ∧ R(1, 4)

(b) (5 points) ∃n∀mS(n, m)

(c) (5 points) ∀n∀mT (n, m) ↔ ¬R(n, m) ∧ ¬R(m, n)

(d) (5 points) ∀nQ(n) ↔ [∀mR(0, m) ∧ R(m, n) ∧ S(m, n) → T (m, 1)]

(e) (5 points) ∀nP (n) → [∃mR(0, m) ∧ R(1, m) ∧ R(m, n) ∧ S(m, n)]

(f) (5 points) Yes, using parts (a), (c), (d), and (e).

Grading: Parts (a) through (e):

-4 points for using the symbols =, |, <, >, ≤, or ≥ -3 points for mistranslating but in a way that still defines the same true property

(ie, they define part (d) in terms of ¬T instead of R) -2 points for a correct translation but with one letter accidentally misplaced

(ie, an S instead of an R) -2 points for the incorrect order (ie, R(x, 1) instead of R(1, x)). -1 point for forgetting the ∀ in parts (c), (d), or (e). -2 points for other quantifier errors. -1 point for each implication direction mistake (ie, using a ← instead of a →

or a → instead of a ↔) -1 point for leaving out the R(0, x) in parts (d) or (e).

Part (f):

-4 points if they say no, but with a general fact that would be useful. -2 points if they say no, with a general fact that would be useful, but in fact the way

they translated the other parts, they need it. -2 points for saying yes but forgetting to list part (a) as required. -1 point for saying yes and including part (b) or not including parts

(c), (d), or (e): (-1 point per mistake).

Problem 2 [25 points] Relations

(a) (5 points) Antisymmetric, Transitive (b) (5 points) Partial Order, Total Order (c) (5 points) None of These

(d) (5 points) None of These

(e) (5 points) Equivalence Relation Grading:

-1 points for each property they circle that should not be circled.

-4 points for not circling the property that should be circled, if there’s only one. -2 points for not circling a property that should be circled, if there are two. -5 points if they didn’t circle anything. -5 points if they circled “none of these” and something else.

Problem 3 [15 points] Directed Graphs

(a) (5 points) The claim is true.

In a tournament graph on 4 nodes, every node will have an odd number of edges, so the degree of every node is odd. By the theorem from class, it won’t have an Euler circuit.

(b) (5 points) The claim is false.

An example is the graph on five nodes a, b, c, d, e where there are edges are (a, b), (b, c), (c, d), (d, e), (e, a), (a, c), (c, e), (e, b), (b, d), (d, a). The edges in this order give an Euler circuit.

(c) (5 points) The claim is false.

The complete graph on 225 nodes has an Euler circuit, since every node has degree 224, which is even. Since an Euler circuit contains every edge, all we have to do to construct a 225-node tournament graph with an Euler circuit is take the Euler circuit on K_{225} and choose a direction, then include every edge in our 225-node tournament graph in the direction it appears in the Euler circuit. This will be a tournament graph, since every two nodes are connected and every edge is directed.

Grading:

-5 if they don’t answer yes/no or true/false, or if they answer wrong.

-4 if they answer correctly but give no justification.

-3 if they answer correctly but give incorrect justification. -2 if they answer correctly but give incomplete justification. -1 if they answer correctly and give a graph for justification but they give no

explaination that it works: They could show the Euler circuit, or they could say that all nodes have equal in degree and out degree. Just a graph is insufficient.

-1 if they answer correctly but miss a minor point in their justification.

Problem 4 [8 points] Structured Reasoning

4.1.1: Existential Generalization, from 4.1.

4.1.2: Addition, from 4.1.1.

4.3: Proof by cases from 3, 4.1.2, and 4.2.2.

5: Universal Generalization, from 1 and 4.

Grading: Each of the blanks is worth 2 points.

-1 if they get the reason wrong

-1 if they don’t list the right statements the deduction relies on. On step 5, DO take off a point if they only miss the “1”. It’s necessary that the x_{0} be arbitrary to perform a UG. On step 4.1.2, don’t take off a point if they say “Law of Domination” instead of addition. If they say something general like “rules of predicate logic,” this is okay, but if they list an incorrect rule, it’s not.

Problem 5 [32 points] Proof Comprehension

For this question, if they explain what’s wrong with a proof but never say it’s invalid, that’s fine as long as their explanation makes it clear they think it’s invalid. If they seem wishywashy about it, give no credit for saying it’s valid or invalid correctly: only give partial credit on the explanation.

If they say a proof is valid and explain why they think so this can be used as partial credit.

(a) (8 points) This proof, obviously, is invalid. The theorem assumes P and proves TRUE; this is a fallacious argument, since P could be false yet P →TRUE could still be true.

Validity/Invalidity:

4 points for saying it is invalid. Explanation:

4 points for calling this the fallacy of affirming the conclusion

4 points for calling this the converse fallacy

4 points for saying something like “Proving P →TRUE doesn’t prove P.” 3 points for saying that differentiating can’t be reversed. 0 points for anything else, especially if they claim we divided by 0.

(b) (8 points) The proof is invalid. Induction generalizes over the natural numbers, not over the rationals.

Validity/Invalidity:

4 points for saying it is invalid. Explanation:

4 points for talking about induction not applying to the rationals. 2 points for having this idea but being inept about expressing it. -1 point for getting the right reason but giving other “reasons” which are

incorrect (for each other reason).

(c) (8 points) This proof is valid. If they say it is invalid they may get *some* partial credit...

Validity/Invalidity:

8 points for saying it is valid. Explanation:

2 points for saying it is invalid and mentioning minor points the theorem leaves out, such as: - Proving the weight of a spanning tree is an integer

- Proving the well-ordering property of the natural numbers 2 points for any other reasonable nitpick. 0 points for saying it can’t be valid because it’s not formal.

(d) (8 points) This proof is invalid. It would be valid if the assumption that the set S is finite was not omitted. As it is, there is no contradiction, since k is not necessarily a number.

Validity/Invalidity:

4 points for saying it is invalid. Explanation:

4 points for saying anything to the effect of: we need to assume that S is finite. 4 points for arguing there is no contradiction since k is not necessarily a number. 2 points for arguing they didn’t prove k was prime.

Other:

6 points if they say it is valid and that the assumption that S is finite is implicit. 4 points if they say it is valid and that it’s just like the proof we gave in lecture.

Problem 6 [30 points] Hamiltonian Circuits

(a) (4 points) A 4 by 4 grid graph looks like it has 9 cells, not 16. The labeled points should be the middle two on the top row [(1, 3) and (2, 3)] and the point below the further of these to the right [(2,2)].

Grading:

-3 points for drawing a 5 by 5 grid graph but labeling the points correctly

(in a 5 by 5 graph, these points would be internal). -4 points for drawing a 5 by 5 grid graph and labeling the points on the outside. -1 point if they label points as if the bottom left were (1, 1) instead of (0, 0). -1 point if they don’t orient the graph in the standard way. The bottom left should

be (0, 0) and the points should be on the top. If they are oriented consistenly but not in this manner, apply this penalty.

-1 point for each vertex they label incorrectly.

-1 point if they label any of the vertices ambiguously enough that you really can’t tell if they got the label right.

(b) (10 points)

Grading: Use normal proof standards. The following is the breakdown of important points they must cover:

1 point: proving that 1 color would not suffice

6 points: providing a 2-coloring of the m by n grid graph

3 points: explaining why their 2-coloring is valid. If they give a good picture that in your opinion makes it clear why the 2-coloring would work for any size grid graph, give them credit for explaining correctly. However, if they draw a picture without being clear about the pattern, this is insufficient. Also, if they don’t draw a general m by n picture but rather give an example, some explanation is needed to back this up.

(c) (16 points) Give 0 points partial credit for ANY argument that doesn’t resemble induction. If they set up their argument as an inductive one (ie, base case and inductive step) but in their inductive step they don’t call on the inductive assumption but just prove P (n + 1) directly, give them 6 points off: this is actually induction but it’s not a proof in the spirit of induction (if someone does this, just use normal proof standards for the grading instead of what is listed below).

Grading: Use normal proof standards. The following is the breakdown of important points they must cover:

2 points for setting up their proposition correctly (even if they’re not explicit about this). 4 points for the base case: they should give a *little* explanation, not just draw a graph

(though a directed version of the 2x2 grid graph would suffice.) 2 points for breaking down the 2(n + 1) by 2(n + 1) grid graph into a

2n by 2n grid graph plus some remaining area. 6 points for giving a Hamiltonian circuit based on the circuit in the 2n by 2n graph. 2 points for correctly dealing with any issues about the direction

to follow the smaller circuit in.

Problem 7 [40 points] State Machines and Invariants

(a) (10 points)

Grading: The following is a breakdown of the points:

4 points for the set of states. States must include m, i, and List.

2 points for the start state.

4 points for the transitions. Take off 1 point if they never mention about what happens if m = 1.

(b) (10 points)

Grading: Use normal proof standards. The following is a breakdown of the points:

3 points for giving a correct invariant and clearly stating it.

1 point for the base case.

2 points for correctly arguing each of the two types of transitions. 2 points for arguing that if m = 1 the list is a factorization of n.

(c) (10 points)

Grading: Use normal proof standards. The following is a breakdown of the points:

3 points for giving a correct invariant and clearly stating it.

1 point for the base case.

2 points for correctly arguing each of the two types of transitions. 2 points for arguing that if m = 1 the list is a factorization of n.

This problem is a little more tricky. They will probably need to give a stronger invariant than that the list never contains any non-prime numbers, because proving that i is prime when we insert it requires some more information. If they deal with this point by arguing it loosely in the case where i is added to the list, and don’t strengthen their invariant, give them a maximum of 2 points on their invariant and 1 point on that case (so the total penalty is 2 points).

(d) (10 points) Prove that this algorithm always terminates.

Grading: Use normal proof standards. If they use the termination theorem, take off:

1 point if their function isn’t always ≥ 0.

1 point if they never argue m is always an integer (which will probably be necessary to prove their termination function is an integer 6 points if they never argue why their termination function is always ≥ 0,

but they state it.

Problem 8 [20 points] Bags and Stacks

(a) (10 points)

Grading:

5 points for saying yes.

5 points for the abstraction relation.

For this problem, it is okay for them to define the abstraction relation loosely as long as they define the important part well (ie, the part that associates the sequence to the multiset.

(b) (10 points)

Grading:

5 points for saying no.

4 points for giving a sequence of inputs for a correct trace. 1 points for providing the outputs of the trace.