Topics Covered on ExamRelations: definition and graphical view, binary and n-aryrelation, inverse, composition of a relation, associativity ofcomposition, reflexive, irreflexive, symmetric, anti-symmetric,and transitive properties, equivalence relations, partialordering relations, reflexive, symmetric, and transitive closuresFunctions: definition and graphical view, composition of afunction, inverse, injection, surjection, and bijection.Sections in the book that will be useful:Chapter 5: Sections 1, 2, 6Chapter 7: Sections 1, 4Also, since a relation is simply a set, it may be useful to reviewmaterial on sets from chapter 3.How to study:First, flip through my notes, making sure you understand theexamples presented. Look at the past couple homeworksolutions, and also look at previous homework questions onthis material. Practice these problems. Finally, flip through thebook to make sure you understand what is in each of thesections I mentioned above. Keep in mind that I may not havecovered everything in these sections.FormatUnlike last time I will actually have some T/F and multiplechoice/matching, as well as some short answer. However, asalways, I will have a few proofs of the nature that you haveseen over the past three or four weeks. The key to these proofsis to first understand what the question is asking. Once youhave determined that, apply the pertinent definitions in such away that you can show the assumptions imply the conclusion.Some specific things to remember:1) A relation can be defined in two ways: either explicitly listedsuch as R = {(1,2), (2,3)} or generally as the following: R = {(a,b) | aZ+ bZ+ b = a + 1}Make sure you understand how to interpret both. Example:R = {(a,b) | aZ+ bZ+ c | a = b + 2c, where cZ}This is read as: “The set R contains all elements (a,b) such thata and b are positive integers and there exists an integer s suchthat a = b + 2c.”In essence, the value of c has little to do with the membershipin the set.2) Know how to use the definition of relation/functioncomposition. Consider the situation where R, S, and T are allrelations over the set A x A. For example, if we know that(x,y)(RS)T, we can deduce that (x,z) RS and (z, y) T,for some element z in A. Similarly, if (x,z) RS, then we knowthat (x,w) R and (w,z) S, for some element w of A. Now why is it that I used a z one time in applying the defintionand a w the next time?The problem with using z both times is that allrelation/function composition says is that there IS someintermediate element, not that it is the same for each elementin the composition. Thus, there is a distinct possibility that zand w are NOT equal. If we were to call them with the samevariable name, we would not be taking that into account, andmay make an error in our proof.So, this brings up the point to realize that all of the formulas,definitions you have are in terms of variables. You are allowedto plug in anything for those variables... as long as the “type”matches so to speak...3) How to compute a relation inverse: If a relation is defined as{(a,b)| some restriction on a and b...} then the inverse of thatrelation is:{(b,a)| that same restriction as above on a and b...}Basically, if you have an explicit listing, you simply flip allordered pairs in the relation around, ie.If R = {(1,2), (2,4)} then R-1 = { (2,1), (4,2) }4) Reflexive, Symmetric, blah, blah,...First of all, memorize each of these definitions. Moreimportantly, try to understand what they mean, eithergraphically or logically. Remember, each of these areproperties of a relation, not part of a relation, or an element.Each of these makes a claim that all elements in the relationsatisfy a particular property. To disprove one of these, youmust find a single counter example.To prove one of these properties, you must assume that the ifpart is true, and under that assumption show that the then partlogically follows.5) Each of the closures mentioned in homework #4 essentiallyaugment a relation. Keep in mind how this works, ie. thedefinitions of these. Memorize and try to understand what theymean. Essentially, r(R) takes the set R and adds whatever itneeds to to the set to make it reflexive, the same is true of theother two closures.6) Computing mathematical function inverses: switch the x andy and solve for y.7) Computing mathematical function compositions: rememberthat f(g(x)) and g(f(x)) are typically not the same thing.8) Injection, Surjection, Bijection: First memorize thesedefinitions, then try to understand what they mean. Oftentimes it is easier to gain understanding of these terms in apictorial sense. Remember a bijection is simply both aninjection and a surjection. Also make sure you know all theextra restrictions placed on a function compared to a relation.1) (15 pts) True/False: Circle the correct answer. Please be clear with your answer!!!(+1 for a correct answer, 0 for no response, and–1 for an incorrect response.)a) All functions are surjective. Falseb) The relation R={(1,3), (2,4), (5,7), (6,8)} True is transitive.c) Let f be a bijection from the finite set A to the True finite set B. |A| =|B|.d) If R is a non-empty relation, then so is RR. Falsee) If a relation R is symmetric, it contains an False even number of elements.f) A partial ordering relation must be True anti-symmetric.g) The total number of edges in a complete False graph with 5 vertices is 15.h) All walks are paths. Falsei) There exists a graph G such that the sum of the False degrees of its vertices is 9.j) If f: A B and g: B C are both injections, True then gf is as well.k) If a relation R is symmetric it can not be False anti-symmetric.l) Let [x] and [y] be equivalence classes in an True equivalence relation. [x]=[y] or [x][y] = .m) For 2 relations R and S that are subsets of AxA, False RS = SRn) Let A={1,2,3}. The number of possible True relations R that are subsets of AxA is 29.o) Let A={1,2,3}. Let R be a relation over AxA False such that R={(1,2),(2,1),(3,2)}. R is a bijection.2) (8 pts) Let R and S be relations that
View Full Document
Unlocking...