1. For each relation described below on the left, indicate in the table to the right which among the listed properties it possesses. (The properties are defined in Section 14.2 of Gries & Schneider and in the Notes on Relations web page.) Each relation is to be understood as being "on" the set A = { a, b, c } (meaning that it is a subset of A × A).
|
R1: { (a,a), (b,b), (c,c), (a,b), (c,b) } R2: { (c,a), (a,b) } R3: { (a,a), (b,b), (c,c) } (i.e., identity relation) R4: ∅ (i.e., empty relation) R5: { (a,b), (b,c), (a,c), (c,a) } R6: { (a,b), (b,a) } |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2. Each part asks you to "show" a binary relation R on the set A = {a,b,c,d}. Perhaps the most effective way of doing that is to draw the directed graph GR whose vertices are labeled by the members of A and that contains the edge (x,y) (i.e., the edge directed from the vertex labeled x to the vertex labeled y) if and only if (x,y) ∈ R (i.e., xRy).
A binary relation R is a set of ordered pairs; hence a "largest" (respectively, "smallest") relation satisfying a specified condition is one having the greatest (respectively, least) possible number of ordered pairs. (Of course, the number of ordered pairs in R corresponds to the number of edges in GR.)
(a) Show a smallest binary relation on A = { a, b, c, d } having as its transitive closure the universal relation on A (i.e., the relation A × A). (By "smallest" is meant having the fewest number of ordered pairs.) In your answer, explicitly state the size (i.e., number of members) of the relation you show.
(b) Show a smallest irreflexive binary relation R on A = { a, b, c, d } such that R2 is the identity relation on A. In your answer, explicitly state the size (i.e., number of members) of the relation you show. Explain why there is no such binary relation on A - { d }.
(c) Show a largest binary relation on A = { a, b, c, d } that is neither symmetric, nor reflexive, nor transitive. (By "largest" is meant having the greatest number of ordered pairs.) In your answer, explicitly state the size (i.e., number of members) of the relation you show.
(d) Show a largest irreflexive binary relation on A = { a, b, c, d } that is the same as its own transitive closure. In your answer, explicitly state the size (i.e., number of members) of the relation you show.
3. Recall these definitions of relation inverse and composition (the latter of which Gries & Schneider call product):
| Inverse: | R-1 = { x,y | (x,y)∈R : (y,x) } |
|---|---|
| Composition/Product: | R∘S = { x,z | (∃y | (x,y)∈R ∧ (y,z)∈S) : (x,z) } |
Consider the binary relations actedIn ⊆ Actor × Movie and directed ⊆ Director × Movie. Using relation inverse and composition/product, express the following relations in terms of actedIn and directed:
(a) wasDirectedBy ⊆ Actor × Director, where (x,y) ∈ wasDirectedBy if and only if x acted in a movie that was directed by y.
(b) actedInSameMovieAs ⊆ Actor × Actor, where (x,y) ∈ actedInSameMovieAs if and only if there is some movie in which both x and y acted.
(c) hadSameDirectorAs ⊆ Actor × Actor, where (x,y) ∈ hadSameDirectorAs if and only if x and y acted in (possibly different) movies directed by the same director. For example, Shaw acted in Jaws and Hanks acted in Saving Private Ryan, both of which were directed by Spielberg. Hence, (Shaw,Hanks) ∈ hadSameDirectorAs.
Simply for purposes of illustration, we can imagine actedIn and Directed relations that look like this:
|
|
|||||||||||||||||||||||||||||||||||||||||||
Of course, your answers should make no mention of any of the example pieces of data in this illustration (e.g., "Hanks", "Jaws", etc.).