Discrete Mathematics Answers

Determine whether function f : Z × Z → Z is onto if (i) f(m,n)=2m−n

(ii) f(m,n)=m+n+1

Show that the relation R consisting of all pairs(x, y) such that x and y are bit

strings of length three or more that agree in their first three bits is an

equivalence relation on the set of all bit strings of length three or more.

Which of these relations on the set of all functions from Z to Z are equivalence

relations? Determine the properties of an equivalence relation that the others

lack.

a) {(f, g) | f (1) = g(1)}

b) {(f, g) | f (0) = g(0) or f (1) = g(1)}

c) {(f, g) | f (x) − g(x) = 1 for all x ∈ Z}

d) {(f, g) | for some C ∈ Z, for all x ∈ Z, f (x) − g(x) = C}

e) {(f, g) | f (0) = g(1) and f (1) = g(0)

Represent each of these relations on {1, 2, 3} with a matrix (with the elements

of this set listed in increasing order).

a) {(1, 1), (1, 2), (1, 3)}

b) {(1, 2), (2, 1), (2, 2), (3, 3)}

c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}

d) {(1, 3), (3, 1)}

Let R1 and R2 be the “congruent modulo 3” and the “congruent modulo 4”

relations, respectively, on the set of integers. That is, R1 = {(a, b) | a ≡ b (mod

3)} and R2 = {(a, b) | a ≡ b (mod 4)}. Find

a) R1 ∪ R2 b) R1 ∩ R2 c) R1 − R2 d) R2 − R1 e) R1 ⊕ R2

Determine whether the relation R on the set of all integers

is reflexive, symmetric, antisymmetric, and/or transitive,

where (x, y) ∈ R if and only if

a) x ≠ y. b) xy ≥ 1.

c) x = y + 1 or x = y − 1.

d) x ≡ y (mod 7). e) x is a multiple of y.

f ) x and y are both negative or both nonnegative.

g) x = y2. h) x ≥ y2

Determine whether the relation R on the set of all

Web pages is reflexive, symmetric, antisymmetric, and/or

transitive, where (a, b) ∈ R if and only if

a) everyone who has visited Web page a has also visited

Web page b.

b) there are no common links found on both Web

page a and Web page b.

c) there is at least one common link on Web page a and

Web page b.

d) there is a Web page that includes links to both Web

page a and Web page b.

For each of these relations on the set {1, 2, 3, 4}, decide

whether it is reflexive, whether it is symmetric, whether

it is antisymmetric, and whether it is transitive.

a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}

b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

c) {(2, 4), (4, 2)}

d) {(1, 2), (2, 3), (3, 4)}

e) {(1, 1), (2, 2), (3, 3),(4, 4)}

f ) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}

Show that A ⊕ B = (A ∪ B) - (A ∩ B).

List the ordered pairs in the relation R from

A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3}, where (a, b) ∈ R

if and only if

a) a = b. b) a + b = 4.

c) a > b. d) a ∣ b.

e) gcd(a, b) = 1. f ) lcm(a, b) = 2.