[SOLVED] VE203 Homework 2

Exercise 2.1

Show by induction that every nonempty finite set of real numbers has a smallest element.

Exercise 2.2
What is wrong with the following proof of the “theorem”?

Theorem. Given any positive number a, then for all positive integer n, we have an−1 = 1.
Proof. If n = 1, an−1 = a1−1 = a0 = 1. By induction, assume that the theorem is true for n = 1,2,…,k, then for

n = k + 1,
therefore the theorem is true for all positive integers n.

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

10 11

Input: A[1 . . . n], unsorted array
Output: all the A[i], 1 ≤ i ≤ n in increasing order Function mergeSort(A[1 . . . n]):

if n=1then return A

else

L ← mergeSort(1…⌊n2 ⌋)
R ← mergeSort(⌊ n2 ⌋ + 1 . . . n) return merge(L, R)

end end

Input: X[1…n], Y[1…m], 2 sorted arrays
Output: X ∪ Y sorted with elements in increasing order Function merge(X[1…n], Y[1…m]):

if n=0then return Y

else if m = 0 then return X

else if X[1] < Y [1] then
return X[1] followed by merge(X[2 . . . n], Y )

else
return Y [1] followed by merge(X, Y [2 . . . m])

end end

(k+1)−1 k ak−1 × ak−1 1 × 1
a =a= a(k−1)−1 = 1 =1

Exercise 2.3

Define a nonempty sorted list as either • ⟨x,⟨⟩⟩;or

• ⟨x, ⟨y, L⟩⟩ where x ≤ y and ⟨y, L⟩ is a nonempty sorted list.
Prove by structural induction that in a nonempty sorted list ⟨x, L⟩, every element z in L satisfies z ≥ x.

Exercise 2.4 (4 pts)

Show that for any logical proposition φ using the connectives {¬, ∧, ∨, →}, i.e., wffs, there exists a proposition that is logically equivalent to φ using only

(i) (2 pts) {↓}, where ↓ is the Peirce arrow (NOR), with p ↓ q ⇔ ¬(p ∨ q). (ii) (2 pts) {|}, where | is the Sheffer stroke (NAND), with p | q ⇔ ¬(p ∧ q).

Exercise 2.5

Show by induction that the following two algorithms mergeSort and merge are correct.

Page 1 of 2

Exercise 2.6

Let

m ∼ n :⇔ 2 | (n − m), m, n ∈ Z.

1. (i)  (1 pt) Show that ∼ is an equivalence relation.
2. (ii)  (1 pt) What partition Z2 := Z/ ∼ is induced by ∼?
3. (iii)  (2 pts) Define addition and multiplication on Z2 by the addition and multiplication of class representatives, i.e.,[m] + [n] := [m + n], [m] · [n] := [m · n].

   Show that these operations are well-defined, i.e., independent of the representatives m and n of each class.

4. (iv)  (6 pts) Verify that (Z2 , +, ·) is a field, i.e.,(a) Closure under addition, i.e., ∀m, n ∈ Z2, ∃m + n ∈ Z2;
   (b) Closure under multiplication, i.e., ∀m, n ∈ Z2 , ∃m · n ∈ Z2 ;

   (c) Commutativity of the addition “+”, i.e., m + n = n + m for all m, n ∈ Z2; (d) Commutativity of the multiplication “·”, i.e., m · n = n · m for all m, n ∈ Z2;

   (e) Associativityoftheaddition“+”,i.e.,(m+n)+k=n+(m+k)forallm,n,k∈Z2; (f) Associativity of the multiplication “·”, i.e., (m · n) · k = n · (m · k) for all m, n, k ∈ Z2;

   (g) Distributivity: k·(m+n)=k·m+k·nforallk,m,n∈Z2;
   (h) Existenceofanadditiveidentity,i.e.,∃0∈Z2,∀m∈Z2: 0+m=m+0=m;

   (i) Existence of a multiplicative identity, i.e., ∃1 ∈ Z2, ∀m ∈ Z2: 1 · m = m · 1 = m;

   (j) Existenceofanadditiveinverse,i.e.,∀m∈Z2,∃n∈Z2 suchthatm+n=n+m=0;
   (k) Existenceofamultiplicativeinverse,i.e.,∀m∈Z2,m̸=0,∃n∈Z2 suchthatm·n=n·m=1;

   (l) The additive and multiplicative identity elements are different, i.e., 0 ̸= 1.

Exercise 2.7 (8 pts)

Determine whether the relation R on the set of all integers is reflexive, symmetric and/or transitive, where (x, y) ∈ R iff

(i) x + y = 0 (ii) 2 | (x − y) (iii) xy = 0 (v) x = ±y (vi) x = 2y (vii) xy ≥ 0

Exercise 2.8 (12 pts)

Letf:X→Y beanyfunction.ShowthatforallA,B⊂X,wehave (i) (2pts) f(A∪B)=f(A)∪f(B).

(ii) (2pts) f(A∩B)⊂f(A)∩f(B),whereequalityholdsiff isinjective. (iii) (2pts) f(A)−f(B)⊂f(A−B),whereequalityholdsiff isinjective.

Show that for all C, D ⊂ Y , we have
(iv) (2 pts) f−1(C ∪ D) = f−1(C) ∪ f−1(D).

(v) (2 pts) f−1(C ∩ D) = f−1(C) ∩ f−1(D). (vi) (2 pts) f−1(C − D) = f−1(C) − f−1(D).

(iv) x = 1 or y = 1 (viii) x = 1

Note that the function f−1 : 2Y → 2X has better behavior than f : 2X → 2Y with respect to union, intersection, and complementation. (Note that f : 2X → 2Y is induced by f : X → Y , which is a not uncommmon overloading/abusing of notation.)

Page 2 of 2