211L6Solutions

From Marks Wiki
Revision as of 01:24, 25 August 2006 by Mark (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Exercises

1. For each of the pair of sets A and B below, determine whether A is a subset of B or B is a subset of A or A = B.

  • (a) A = {1, 2}, B = {2, 3, 4}.

A != B

  • (b) A = {a, c}, B = {c, d, a}.

a is a subset of b (proper subset)

  • (c) A = {3, 2, a}, B = {2, 3, a}.

A = B

  • (d) A = {4, 7,−1}, B = {7, 3, 4}.

A != B


2. For any two sets A and B prove the equalities A U A = A and A n B = B n A are true.

  • If x is from a A U A then x is from A and is also x is from A. {x | x is a member of A or x is a member of A}. Thus A U A = A.
  • For any set, if {x | x is a member of A and x is a member of B}, then it follows that x is a member of B and x is a member of A. Thus A n B = B n A.


3. Let A, B, C be sets. Prove that (A U B) U C = A U (B U C) and (A n B) n C = A n (B n C).

  • Let A = {a,b} B = {b,c} C = {c,d}.
    • (A U B) U C = {a,b,c} U {c,d} = {a,b,c,d}
    • A U (B U C) = {a,b} U {b,c,d} = {a,b,c,d}
    • Thus (A U B) U C = A U (B U C)
  • Let A = {a,b} B = {a,c} C = {a,d}.
    • (A n B) n C = {a} n {a,d} = {a}
    • A n (B n C) = {a,b} n {a} = {a}
    • Thus (A n B) n C = A n (B n C)

4. Give examples of sets A and B such that A \ B != B \ A.

let A = {a,b,c} and B = {c,d,e}. Then A\B = {a,b} and B\A = {d,e}

{a,b} does not equal {d,e} and thus A\B is not the same as B\A.


5. Let A and B be sets. Prove or disprove the following equalities:

  • (a) P(A n B) = P(A) n P(B).

e.g.

  • P({a b} n {b c}) = P{(b)} = b
  • P(a b) n P{b c} = {(a,a), (a,b), (b,a), (b,b)} n {(b,b), (b,c), (c,b), (c,c)} = (b,b)

b does not equal (b,b).


  • (b) P(A U B) = P(A) U P(B).
  • P({a} U {a}) = a
  • P({a}) U P({a}) = a

Therefore, in at least one instance this does hold true.

6. Find the cross products A × B, A × A, and A × B × A for the following sets:

  • (a) A = {1, 2}, B = {2, 3, 4}.
    1. A × B = {{1,2},{1,3},{1,4},{2,2},{2,3},{2,4}}
    2. A × A = {{1,1},{1,2},{2,2}}
    3. A × B × A = {{1,2,1},{1,2,2},{1,3,1},{1,3,2},{1,4,1},{1,4,2},{2,2,2},{2,3,2},{2,4,2}}
  • (b) A = N, B = {1, 2}.
    1. A × B = {{N,1},{N,2}}
    2. A × A = {{ N,N },}
    3. A × B × A = {{N,1,N},{N,2,N}}
  • (c) A = {c, d}, B = 0.
    1. A × B = {{c,0},{d,0}}
    2. A × A = {{c,c},{c,d},{d,d}}
    3. A × B × A = {{c,0,c},{c,0,d},{d,0,d}}

7. For sets A, B and C prove A × (B U C) = A × B U A × C.

  • Let A = {a,b} B = {b,c} C = {c,d}.
    • A × (B U C) = A × {b,c,d} = {{a,b},{a,c},{a,d},{b,b},{b,c},{b,d}}
    • A × B U A × C = {{a,b},{a,c},{b,b},{b,c}} U {{a,c},{a,d},{b,c},{b,d}} = {{a,b},{a,c},{a,d},{b,b},{b,c},{b,d}}
    • Thus A × (B U C) = A × B U A × C


8. Consider the set A = {x, y}. List down all unary and binary relations on this set. How many ternary relations are there on this set? How many 4-place relations are there on this set? {x,y,(x,x),(x,y),(y,x),(y,y)} //and empty There are no ternary or 4-place relations.


9. Consider the set A = {a, b, c}. Do the following:

  • (a) Find a relation on A that is symmetric and reflexive but not transitive.

{(a,a),(a,b),(b,b),(b,a),(c,c)}

  • (b) Find a relation on A that is symmetric and transitive but not reflexive.

{(a,b),(b,a),(a,c),(c,a),(b,c),(c,b)}

  • (c) Find a relation on A that is reflexive and transitive but not symmetric.

{(a,a),(a,b),(b,b),(b,c),(c,c),(c,a)}


10. Let R be a binary relation on A. Call a relation R0 the minimal symmetric cover of R if the following are true:

  • (a) R0 is a symmetric relation.
  • (b) R � R0.
  • (c) If S is a symmetric relation containing R then R0 � S.

Design a method that builds the minimal symmetric cover for any given binary relation R.

For all (x,y) which exist in R, if (y,x) does not exist, create it.

11. Let R be a binary relation on A. Call a relation R0 the transitive closure of R if the following are true:

  • (a) R0 is a transitive relation.
  • (b) R � R0.
  • (c) If T is a transitive relation containing R then R0 � T.

Design a method that builds the transitive closure for any given binary relation R.

Wherever (x,y) exist in R and (y,z) exist in R, if there isn't already a path from x,z then create one.


12. Give an example of a symmetric relation which is antisymmetric. R={(1,1),(2,2),(3,3)}


13. Give an example of antisymmetric relation which is symmetric. R={(1,1),(2,2),(3,3)}

Programming exercises

1. Write a program that for input finite sets A and B outputs A [ B.

  • Done

2. Write a program that for input finite sets A and B outputs A \ B.

  • Done

3. Write a program that for input finite sets A and B outputs A \ B.

  • Done

4. Write a program that as input takes a binary relation on a finite set and determines

  • a) if the relation is reflexive;

Done

  • b) if the relation is symmetric;

Done

  • c) if the relation is transitive;
  • d)if the relation is antisymmetric.

Done

5. Write a program that given a finite set A and a binary relation R on A outputs the minimal symmetric cover of R (see Exercise 10).

6. Write a program that given a finite set A and a binary relation R on A outputs the transitive closure of R (See Exercise 11)

Retrieved from "https://wiki.kram.nz/index.php?title=211L6Solutions&oldid=277"