Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders370

vi. 8 c¤d: c R dIMPLIES NOT.d R c/

vii. 8 c¤d: c R dIFF NOT.d R c/

viii. 8 b;c;d: .b R c ANDc R d/IMPLIESb R d

ix. 8 b;d: Œ 9 c: .b R c ANDc R d/çIMPLIESb R d

x. 8 b;d: b R d IMPLIESŒ 9 c: .b R c ANDc R d/ç

(a)R\IdDD; i.

(b)RR^1

(c)RDR^1

(d)IdDR

(e)RıRR

(f)RRıR

(g)R\R^1 IdD

(h)RR^1

(i)R\IdRDR^1 \IdR

(j)R\R^1 D;

Homework Problems

Problem 9.49.
LetR 1 andR 2 be two equivalence relations on a set,A. Prove or give a counterex-
ample to the claims that the following are also equivalence relations:

(a)R 1 \R 2.

(b)R 1 [R 2.

Problem 9.50.
Prove that for any nonempty setD, there is a unique binary relation onDthat is
both a weak partial order and also an equivalence relation.