The exercises referred to by number come from pages 21-22 of the Gries & Schneider textbook.
1. Do Exercise 1.2, parts (b) through (f). The answer to (a) is b+2. Don't forget that textual substitution has higher precedence than any other operator.
2. Do Exercise 1.3, parts (b) through (f). The answer to (a) is y*x + 2 .
3. Do Exercise 1.6. Specifically, show two different instantiations of Inference Rule Substitution (1.1)
E[v:=F] |
in each case taking E to be the theorem x<y ∨ x≥y and v to be the list of variables x,y. (So all that is left for you is to instantiate F in two different ways. Make sure that at least one of them involves compound expressions.)
4. Let F be the formal system whose set of well-formed formulas (wff's) includes precisely those strings of the form xΔyΔz, where each of x, y, and z is a string composed of ∗'s and whose axioms and inference rules are as follows:
| Axiom | R1 | R2 |
|---|---|---|
A wff is, in other words, any string containing zero or more *'s and exactly two Δ's. The wff that includes no *'s is accepted, without proof, as a theorem.
Rule 1 says, informally, that if we take a theorem and insert one * at the beginning and two at the end, what we get is another theorem.
Rule 2 says, informally, that if we take a theorem and remove one * from both the left and right ends, and add one * in the region lying between the two Δ's, what we get is another theorem.
As an example, here is a proof of ∗Δ∗∗Δ∗∗∗∗, which we can also write as ∗Δ∗2Δ∗4, using the convention that, for any natural number r, ∗r stands for a string of ∗'s of length r.
| (1) | ΔΔ | (axiom) |
|---|---|---|
| (2) | ∗ΔΔ∗2 | (R1[u,v,w := λ, λ, λ] applied to (1)) |
| (3) | Δ∗Δ∗ | (R2[u,v,w := λ, λ, ∗] applied to (2)) |
| (4) | ∗Δ∗Δ∗3 | (R1[u,v,w := λ,∗,∗] applied to (3)) |
| (5) | ∗2Δ∗Δ∗5 | (R1[u,v,w := ∗,∗,∗3] applied to (4)) |
| (6) | ∗Δ∗2Δ∗4 | (R2[u,v,w := ∗,∗,∗4] applied to (5)) |
Note that λ refers to the empty string.
(a) Show a proof of ∗Δ∗3Δ∗5
(b) Argue for the following claim:
For every pair of natural numbers k and m, ∗kΔ∗mΔ∗2k+m is a theorem.
Suggested Approach: Provide informal instructions (i.e., an algorithm) for writing a proof of ∗kΔ∗mΔ∗2k+m that would work for all possible choices of the values of k and m.
(c) Argue for the following claim:
If ∗kΔ∗mΔ∗n is a theorem, then 2k+m = n.
Suggested approach: Explain why it must be that every line of every proof is such that the wff on that line satisfies the stated condition. For one-line proofs, this is easy. For multiple-line proofs, you need only argue that the wff on the last line satisfies the stated condition, under the assumption that the wff's on all previous lines do.