Mark: 1 revision(s)

2008-03-08T22:35:28Z

1 revision(s)

← Older revision		Revision as of 22:35, 8 March 2008
(No difference)

Mark at 01:24, 25 August 2006

2006-08-25T01:24:25Z

New page

==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}.'''
*#A × B = {{1,2},{1,3},{1,4},{2,2},{2,3},{2,4}}
*#A × A = {{1,1},{1,2},{2,2}}
*#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}.'''
*#A × B = {{N,1},{N,2}}
*#A × A = {{ N,N },}
*#A × B × A = {{N,1,N},{N,2,N}}
*'''(c) A = {c, d}, B = 0.'''
*#A × B = {{c,0},{d,0}}
*#A × A = {{c,c},{c,d},{d,d}}
*#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)

211L6Solutions - Revision history

Mark: 1 revision(s)

Mark at 01:24, 25 August 2006