Topics Covered on Exam Relations definition and graphical view binary and n ary relation inverse composition of a relation associativity of composition reflexive irreflexive symmetric anti symmetric and transitive properties equivalence relations partial ordering relations reflexive symmetric and transitive closures Functions definition and graphical view composition of a function inverse injection surjection and bijection Sections in the book that will be useful Chapter 5 Sections 1 2 6 Chapter 7 Sections 1 4 Also since a relation is simply a set it may be useful to review material on sets from chapter 3 How to study First flip through my notes making sure you understand the examples presented Look at the past couple homework solutions and also look at previous homework questions on this material Practice these problems Finally flip through the book to make sure you understand what is in each of the sections I mentioned above Keep in mind that I may not have covered everything in these sections Format Unlike last time I will actually have some T F and multiple choice matching as well as some short answer However as always I will have a few proofs of the nature that you have seen over the past three or four weeks The key to these proofs is to first understand what the question is asking Once you have determined that apply the pertinent definitions in such a way 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 listed such as R 1 2 2 3 or generally as the following R a b a Z b Z b a 1 Make sure you understand how to interpret both Example R a b a Z b Z c a b 2c where c Z This is read as The set R contains all elements a b such that a and b are positive integers and there exists an integer s such that a b 2c In essence the value of c has little to do with the membership in the set 2 Know how to use the definition of relation function composition Consider the situation where R S and T are all relations over the set A x A For example if we know that x y R S T we can deduce that x z R S and z y T for some element z in A Similarly if x z R S then we know that 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 defintion and a w the next time The problem with using z both times is that all relation function composition says is that there IS some intermediate element not that it is the same for each element in the composition Thus there is a distinct possibility that z and w are NOT equal If we were to call them with the same variable name we would not be taking that into account and may 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 allowed to 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 that relation is b a that same restriction as above on a and b Basically if you have an explicit listing you simply flip all ordered 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 More importantly try to understand what they mean either graphically or logically Remember each of these are properties of a relation not part of a relation or an element Each of these makes a claim that all elements in the relation satisfy a particular property To disprove one of these you must find a single counter example To prove one of these properties you must assume that the if part is true and under that assumption show that the then part logically follows 5 Each of the closures mentioned in homework 4 essentially augment a relation Keep in mind how this works ie the definitions of these Memorize and try to understand what they mean Essentially r R takes the set R and adds whatever it needs to to the set to make it reflexive the same is true of the other two closures 6 Computing mathematical function inverses switch the x and y and solve for y 7 Computing mathematical function compositions remember that f g x and g f x are typically not the same thing 8 Injection Surjection Bijection First memorize these definitions then try to understand what they mean Often times it is easier to gain understanding of these terms in a pictorial sense Remember a bijection is simply both an injection and a surjection Also make sure you know all the extra 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 False b 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 R R False e 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 False i 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 g f 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 R S S R n Let A 1 2 3 The number of possible True 9 relations R that are subsets of AxA is 2 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 are subsets of AxA A 1 2 3 4 If R 1 2 1 3 2 4 3 1 3 2 4 4 and S 1 4 2 1 2 3 3 2 4 1 4 2 then what is R …
View Full Document
Unlocking...