Assignments for Math 221, Discrete Structures
J. Stanley Warford April 5, 2013

Assignment 1 1. 2. 3. 4. 5. Study Section 12.2. Do Exercises 12.4(b, e). Do Exercise 12.8.

Math 221, Discrete Structures

Do Exercise 12.9. In your induction case, you should start with (n + 1)2 and use the result from Exercise 12.8. Do Exercise 12.10. i is divisible by 3 means that i = 3k for some integer k. You may use the fact that the sum of two expressions, each one divisible by 3, is also divisible by 3.

1

Assignment 2 1. 2. 3. 4. Study Section 12.5. Do Exercise 12.5. Do Exercise 12.14.

Math 221, Discrete Structures

Prove (12.16.1). There are two base cases, one for n = 1 and one for n = 2. For the induction case, there are two inductive hypotheses–one with n − 1 and one with n. You can assume both of them to prove the case for n + 1. Start with the RHS, use (12.14), then the inductive hypotheses. Prove (12.35a). The base case is n = 1. Prove (12.35b). The base case is n = 1.

5. 6.

1

Assignment 3 1. 2. Study Section 10.1.

Math 221, Discrete Structures

Do Exercise 10.1(a, b, c, d, e, g). For 10.1(d), you will need an implication in the body of a universal quantification. For 10.1(g), it is easiest to translate “It is not the case that” as ¬.

1

Assignment 4 1. Do Exercise 10.1(h, i, j, k, l, m). For 10.1(h) and (l), you will need an implication with the ∈ symbol. For 10.1(m), you will need to quantify with Σ with a body of 1. Do Exercise 10.3.

Math 221, Discrete Structures

2. 3. 4.

Do Exercise 10.5. Give a formal definition for the predicate rev(b, c, n), where b and c are arrays with b being the reverse of c. Do Exercise 10.6(a, b, c, d, e, f, n). Make the same assumption about array b as in Exercise 10.1, namely b[ j..k] is empty if j = k + 1, and j > k + 1 is not allowed. For 10.6(e), assume that n is an integer, and consider only nonnegative exponents.

1

Assignment 5 1.

Math 221, Discrete Structures

Prove (p.5) Postcondition rule. Start with the LHS and use the definition of the Hoare triple. Then use (4.3) Monotonicity of ∧, together with (p.3). Prove (p.8). Start with the RHS. You should find (3.59) and (3.76e) useful. Prove (p.11). Prove (p.13). Prove (p.17a). Let R be an arbitrary postcondition and use (p.6).

2. 3. 4. 5.

1

Assignment 6

Math 221, Discrete Structures

In each of the following exercises, calculate the expression E so that the program meets its specification. Begin each calculation with wp.S.post . Assume bold face upper-case identifiers are rigid variables that cannot appear in the program. 1. 2. 3. 4. 5. int x, y {x = X ∧ x ≤ y} x := E {x = y ∧ X ≤ y} int a, b {true} a, b := a + 1, E {b = a + 1} int i, j {i = j} i, j := i + 1, E {i = j} int a, b, z {b ̸= 0 ∧ z + a ∗ b = C} z, a := z + b, E {z + a ∗ b = C} int a, b, z {a ̸= 0 ∧ even.a ∧ z + a ∗ b = C} a, b := a/2, E {z + a ∗ b = C}

1

Assignment 7

Math 221, Discrete Structures

In the exercises that have class composition with ; , you must use (p.14) before you use (p.18), and (p.18) before you assume any conjunct of the antecedent. 1. Prove that the following three statements swap the values of x and y by showing that the original value of variable x is indeed rigid variable X and the same for y. int x, y,t { ? } t := x; x := y; y := t {x = Y ∧ y = X } In each of the following exercises, calculate the expression E so that the program meets its specification. Begin each calculation with wp.S.post and write the final program with preconditions and postconditions after your calculation. To save writing, you can abbreviate the invariant. For example, in 2. you can define P1: x = (Σ k i ≤ k < n : b[k]) and then use P1 in your proof and the final statement of your program. You must state your definition of P1 in each exercise in which you use this technique. 2. const int n int i, x, b[n] {x = (Σ k i ≤ k < n : b[k]) } i, x := i − 1, E {x = (Σ k i ≤ k < n : b[k]) } const int n int i, x, b[n] {x = (Σ k 0 ≤ k < i : b[k − 1]) } i := i + 1; x := E {x = (Σ k 0 ≤ k < i : b[k − 1]) } const int n int i, x, b[n] {x = (Σ k 0 ≤ k < i : b[k]) } x := E; i := i + 1 {x = (Σ k 0 ≤ k < i : b[k]) }

3.

4.

1

Assignment 8

Math 221, Discrete Structures

In each of the following exercises, prove that the program meets its specification. You may find the following math step useful.

xy = ⟨math trichotomy⟩ x ̸= y
1. int x, y {x > 0 ∧ y > 0 ∧ x ̸= y} if x > y → x := x − y [] x < y → y := y − x. fi {x > 0 ∧ y > 0} This exercise requires you to use the following properties of the greatest common divisor function, gcd:

2.

x > y ⇒ gcd(x − y, y) = gcd(x, y), y > x ⇒ gcd(x, y − x) = gcd(x, y), and gcd(x, y) = gcd(y, x).
For example, suppose you want to prove an implication using the technique of assuming the conjuncts of the antecedent (4.4), and x > y is one of the conjuncts. Then you can assume conjunct x > y in your hint and substitute equals for equals as if gcd(x − y, y) = gcd(x, y) were a theorem. int x, y const int A, B {gcd(x, y) = gcd(A, B) ∧ x ̸= y} if x > y → x := x − y [] x < y → y := y − x fi {gcd(x, y) = gcd(A, B)}

1

Assignment 9 1. Do Exercise 12.42(b).

Math 221, Discrete Structures

1

Assignment 10 1. 2. Study Sections 14.1, 14.2 to page 273.

Math 221, Discrete Structures

Prove (14.2.1) Ordered pair one-point rule. Use nesting (8.20) followed by the one-point rule for a single element (8.14). Use the following as your last step.

P[y := F][x := E] = ⟨Property of textual substitution, provided ¬occurs(‘x, y’, ‘E, F ’)⟩ P[x, y := E, F]

3. 4. 5.

Prove (14.4) Membership. Use the two-variable version of (11.3) with F, x := ⟨x, y⟩, (b, c). Prove (14.5). Prove (14.15.3) Identity lemma. Use (14.5.2) but with dummy renaming so as not to confuse the two different x’s.

1

Assignment 11 1. 2. 3. 4. 5. 6. Study proof of (14.22) in the handouts. Do Exercise 14.18. Prove (14.19a). Prove (14.19d). Prove (14.19e).

Math 221, Discrete Structures

Prove (14.23a). Start with the LHS and prove the (9.8) Lemma with an arbitrary ordered pair. Use the (14.20) version of relation product, not the (14.21) version. The proof is based on (8.15) Distributivity.

1

Assignment 12 1. 2. Study all of Section 14.2, Visualizing relations in the handouts.

Math 221, Discrete Structures

Do Exercise 14.25(b). Start with the ordered pair version of (11.48) and use (9.4a) Trading. You will need (8.20) Nesting and the one-point rule. Do Exercise 14.25(c). Do Exercise 14.25(d). Do Exercises 14.27(a, b, d, f, g, h, i). Show your answers in a table with column headings “reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive” and “yes” or “no” in the body of the table.

3. 4. 5.

1

Assignment 13 1. 2. 3. Study Section 14.3. Do Exercise 14.32. Counterexamples are not necessary.

Math 221, Discrete Structures

For the relationship ρ on on B = {0, 1, 2, 3} defined as ρ = {⟨0, 1⟩, ⟨1, 1⟩, ⟨1, 2⟩, ⟨2, 0⟩, ⟨2, 2⟩, ⟨3, 0⟩}: (a) Find the reflexive closure of ρ . (b) Find the symmetric closure of ρ .

4.

Find the transitive closure of each of the following relations on B = {1, 2, 3, 4}. (a) ρ = {⟨1, 2⟩, ⟨2, 1⟩, ⟨2, 3⟩, ⟨3, 4⟩, ⟨4, 1⟩} (b) ρ = {⟨2, 1⟩, ⟨2, 3⟩, ⟨3, 1⟩, ⟨3, 4⟩, ⟨4, 1⟩, ⟨4, 3⟩}

5.

Which of the following relations are equivalence relations on {0, 1, 2, 3}? For those that are not, state the properties that they lack. (a) {⟨0, 0⟩, ⟨1, 1⟩, ⟨2, 2⟩, ⟨3, 3⟩} (b) {⟨0, 0⟩, ⟨0, 2⟩, ⟨2, 0⟩, ⟨2, 2⟩, ⟨2, 3⟩, ⟨3, 2⟩, ⟨3, 3⟩} (c) {⟨0, 0⟩, ⟨1, 1⟩, ⟨1, 2⟩, ⟨2, 1⟩, ⟨2, 2⟩, ⟨3, 3⟩} (d) {⟨0, 0⟩, ⟨1, 1⟩, ⟨1, 3⟩, ⟨2, 2⟩, ⟨2, 3⟩, ⟨3, 1⟩, ⟨3, 2⟩, ⟨3, 3⟩} (e) {⟨0, 0⟩, ⟨0, 1⟩, ⟨0, 2⟩, ⟨1, 0⟩, ⟨1, 1⟩, ⟨1, 2⟩, ⟨2, 0⟩, ⟨2, 2⟩, ⟨2, 3⟩}

6.

What are the equivalence classes of the following equivalence relations? (a) On {a, b, c, d, e, f }: ρ = {⟨a, a⟩, ⟨a, c⟩, ⟨a, d⟩, ⟨b, b⟩, ⟨b, f ⟩, ⟨c, a⟩, ⟨c, c⟩, ⟨c, d⟩, ⟨d, a⟩, ⟨d, c⟩, ⟨d, d⟩, ⟨e, e⟩, ⟨ f , b⟩, ⟨ f , f ⟩} (b) On the integers 0..9: b ρ c ≡ b − c is a multiple of 3. (c) On N: b ρ c ≡ b − c is a multiple of 2. (d) On Z: b ρ c ≡ b − c is a multiple of 5.

7.

Write the equivalence relation that corresponds to the following partitions of {a, b, c, d, e, f }. (a) {{a, d, e}, {c, f }, {b}} (b) {{a}, {b}, {c}, {d}, {e}, { f }}

1

Assignment 14 1. Do Exercise 14.33, prove the part (b) ⇒ (c) of Theorem (14.35).

Math 221, Discrete Structures

[b] ∩ [c] ̸= 0 ⇒ [b] = [c] /
Assume the antecedent of the above expression and prove the consequent. The antecedent implies that some element is in both [b] and [c]. Call that element z. Thus, we have the assumption z ∈ [b] and z ∈ [c]. So, by (14.34), you can assume z ρ b and z ρ c in your proof. Prove [b] = [c] by proving that x ∈ [b] ≡ x ∈ [c] for an arbitrary element x. The easiest way is to use mutual implication. That is, prove that x ∈ [c] ⇒ x ∈ [b] and x ∈ [b] ⇒ x ∈ [c]. For the first part of the proof, start with the left hand side, x ∈ [c], and use the definition of equivalence class. Pull a rabbit out of the hat using the identity of ∧ and the assumption z ρ c. After a few manipulations based on the properties of an equivalence relation, pull another rabbit out of the hat using the assumption z ρ b. The second part of the proof is identical in form, but starting with the left hand side x ∈ [b]. 2. Do Exercise 14.34, prove the part (c) ⇒ (a) of Theorem (14.35).

[b] = [c] ⇒ b ρ c
Start with the LHS and use Extensionality (11.4) followed immediately by Instantiation (9.13). The key to the proof is your choice of x in (9.13). With the right choice, the proof is simple.

1

Assignment 15 1. 2. Study Section 14.4.

Math 221, Discrete Structures

Prove (14.38.1) Alternate definition of total: A function f on B ×C is total if, for an arbitrary element b: B,

(∃c: C : f .b = c)
The proof is outlined below with the hints supplied and the proof steps for you to fill in.

f is total = ⟨(14.38) Definition of total⟩

=

⟨(14.16) Definition of domain with b: B := a: B⟩

=

⟨(14.37.1) Notation⟩

=

⟨(11.4) Extensionality (set equality) with x := b: B⟩

=

⟨b ∈ B ≡ true, (11.5.1) abbreviation⟩

=

⟨(11.3) Set membership with ‘a’ not in ‘b’⟩

=

⟨(9.20.1) Existential double trading⟩

=

⟨(8.14) One-point rule and textual substitution⟩

=

⟨English terminology (page 163, first paragraph)⟩ For an arbitrary element b: B, (∃c: C : f .b = c)

(continued)

1

Assignment 15 3.

Math 221, Discrete Structures

Prove (14.40). Let g : B → C and f : C → D be total functions. Then the composition f • g of f and g is the total function defined by ( f • g).b = f (g.b). Hint: Because g is total, g.b exists for any b in B. Because f is total, f (g.b) exists for any g.b in C. See the figure below for an example. So, let d be an arbitrary element in the domain of f (g.b), and prove that ( f • g).b = d equivales f (g.b) = d . Start with ( f • g).b = d and use (14.39) then (14.37.1). You should eventually use the one-point rule to get f (g.b) = d .
B C D

g.b

b

f(g.b)

g : B→C

f : C→D

2

Assignment 16 1. Prove (14.53a)

Math 221, Discrete Structures

b is least ⇒ b is minimal.

Start with the antecedent and show that it implies the consequent. Begin with the definition of least (14.51.b). To discover the steps in the proof, work backward on some scratch paper to see the expression that you are heading for. Eventually, you will use (14.48.2) followed by range weakening/strengthening (9.10). Here is the first step to get you started:

b is least = ⟨(14.51b) Definition of least⟩ b ∈ S ∧ (∀c c ∈ S : b ≼ c) = ⟨(9.4.1) Universal double trading⟩
2. 3. Which of the following are posets? For those that are not posets, state the properties that they lack. (a) ⟨Z, =⟩ (b) ⟨Z, ̸=⟩ (c) ⟨Z, ≥⟩ (d) ⟨Z, ⟩ Find two incomparable elements in each of the following posets. (a) ⟨P{0, 1, 2, }, ⊆⟩, where P is the power set. (b) ⟨{1, 2, 4, 6, 8}, |⟩ List the ordered pairs in the poset relations for each of the following Hasse diagrams. c b d d e b d c a g e f

4.

(a) 5.

a

(b)

(c) a

b

c

Draw the Hasse diagram for each partial ordering ⟨S, ρ ⟩. (a) S = {a, b, c}, ρ = {⟨a, a⟩, ⟨b, b⟩, ⟨c, c⟩, ⟨a, b⟩, ⟨b, c⟩, ⟨a, c⟩}. (b) S = {a, b, c, d}, ρ = {⟨a, a⟩, ⟨b, b⟩, ⟨c, c⟩, ⟨d, d⟩, ⟨a, b⟩, ⟨a, c⟩}. (c) S = {0, {a}, {a, b}, {c}, {a, c}, {b}}, ρ = ⊆. /

6.

Answer the following questions for the partial ordering represented by the Hasse diagram. (a) Find the maximal elements. (b) Find the minimal elements. (c) Is there a greatest element? (d) Is there a least element? l m (e) Find all the upper bounds of {a, b, c}. (f) Find the least upper bound of {a, b, c} if it exists. j k (g) Find all the lower bounds of {g, h, j, k, l, m}. g h i (h) Find the greatest lower bound of {g, h, j, k, l, m} if it exists. d e f (i) Find all the lower bounds of {h, j, k, l, m}. a b c (j) Find the greatest lower bound of {h, j, k, l, m} if it exists.

1

Assignment 17

Math 221, Discrete Structures

In the following exercises, display the relations in table format, not in angle bracket ⟨ ⟩ format. 1. 2. Study Section 14.5. (a) (b) (c) (d) (a) (b) (c) (d) 4. Write the first two rows of the relational table ALL defined on page 296. Write the first two rows of the relational table for W here(Title, T heater) in (14.55). Write the first two rows of the relational table for W hen(Title, Month, Day,Year) in (14.55). Write the first two rows of the relational table for Author(Title, Book) in (14.55).

3.

Write the relational table that results from the following queries.

σ (MC, Lyrics = Hammerstein) π (σ (MC, Lyrics = Hammerstein), Title) W here ◃▹ Composer ◃▹ Run (First three rows only) π (W here ◃▹ Composer ◃▹ Run, T heater, Music, Per f s)

(First three rows only)

Write the query to list the title of the musical and the authors of the books and the lyrics for those musicals that were performed on Forty-Sixth St. Do not perform unnecessary joins. (a) Assume the database ALL. (b) Assume the database PABM , MC. (c) Assume the database (14.55) W here,W hen, Author, Run, Lyricist,Composer.

1

Assignment 18 1. Take a break.

Math 221, Discrete Structures

1

Assignment 19 1. 2. 3. Prove that 5n3 + 106 n2 + 100 = Θ (n3 ). Prove that n3 − 9n − 50 = Θ (n3 ). In this problem, lg n = log2 n. (a) (b) (c) (d) (e) 4.

Math 221, Discrete Structures

Graph the functions f (n) = n and f (n) = lg n over the range 0.25 ≤ n ≤ 5. For what values of n is lg n greater than 0? For what values of n is lg n greater than 1? For what values of n is n greater than lg n? Prove that 2n2 2n + n lg n = Θ (n2 2n ). You may use (b), (c), and (d) in your proof.

Answer the following questions. No proof is required. (a) Is 2n+1 = O(2n )? (b) Is 22n = O(2n )?

1

Assignment 20 1. 2. 3. 4. 5. Skim Sections 15.1, 15.2, 15.3. Study 15.4 except Prime Numbers and Congruences. Prove (15.79). Use (4.7.1) Truth implication. Prove (15.96) Symmetry. Prove (15.99) Zero. Use (15.81.1), (8.18), and (3.84a).

Math 221, Discrete Structures

1

Assignment 21 1. 2. Study Sections 16.1, 16.3.

Math 221, Discrete Structures

Prove Step (b), Case 2, in the proof of Euclid’s algorithm we did in class. The program is on page 318 in the text.

1

Assignment 22 1. 2. 3. 4. 5.

Math 221, Discrete Structures

¨ Study Sections 19.1, 19.2 The Konigsberg Bridges Problem.
Do Exercise 16.4. Do Exercise 16.13. Do Exercise 16.22. Do Exercise 16.46.

1

Assignment 23 1. 2. 3. 4. Study Sections 19.3, 19.4, 19.5. Do Exercise 19.4. Do Exercise 19.19. All the graphs must be connected and loop-free.

Math 221, Discrete Structures

Prove (19.4). Use proof by mathematical induction on the number of edges, with a base case of zero edges.

1