Exam 2 Flashcards
(73 cards)
construct zero-one matrices representing binary relations,
A matrix in which if the binary relation is true = 1, if false = 0 MR = 0 1 1 1 1 0 1 0 1
construct zero-one matrices representing union of binary relations R1 ∪ R2. (Join)
All relations that are in R1 and R2 are true = 1, and the others are 0
construct zero-one matrices representing the intersection of binary relations R1 ∩ R2 (Meet)
All relations that are in R1 that are also in R2 are true = 1, and the others left over in R2 are 0
onstruct zero-one matrices representing the composition of binary relations M1 O M2
Is the zero-one matrix for the composite
of R1 and R2, R2 ◦ R1.
(a, c) is in R2 ◦ R1 if (a, b) ∈ R1 and (b, c) ∈ R2.
Example of composition
Question 1: Let A = {a, b, c}, B = {1,2} and C = {a, b, g} is being three sets and R = {(a, 1), (a, 2), (b, 2), (c, 1)} and S = {(1, a), (2, b), (2, g)} be two relations, find SoR.
Solution:
Here, R is a relation where a goes to 1 and so on. Thus, S o R will be calculated as a goes to 1 and in turn, 1 goes to a, yielding (a, a).
Hence, SoR = {(a, a), (a, b), (a, g), (b, b), (b, g), (c, a)}.
construct zero-one matrices representing the powers of a binary relation R^2
Is the zero one matrice multiplied by itself
ex.
(0∧0)∨(1∧1)∨(1∧1)(0∧1)∨(1∧1)∨(1∧0)(0∧1)∨(1∧0)∨(1∧1)
(1∧0)∨(1∧1)∨(0∧1)(1∧1)∨(1∧1)∨(0∧0)(1∧1)∨(1∧0)∨(0∧1)
(1∧0)∨(0∧1)∨(1∧1)(1∧1)∨(0∧1)∨(1∧0)(1∧1)∨(0∧0)∨(1∧1)
=
1 1 1
1 1 1
1 1 1
Multiplying Matrices
tbf
find the corresponding binary relation to the given zero-one matrix
the y axis on the matrix is the first coordinate, the x axis is the second. If = 1, then those coordinates are in the binary relation
construct directed graphs representing the given binary relations and vice versa
Directed graphs are the graphs that point to one another, if there is a relation (a,b) then a has an arrow pointing to b
Determine whether a relation is reflexive when it is represented as a a zero-one matrix or a directed graph
ZO Matrix: In other words, all elements are equal to 1 on the main diagonal. = 100 010 001
digraph:
When all points have self loops
Determine whether a relation is symmetric when it is represented as a a zero-one matrix or a directed graph
ZO Matrix: Mij = Mji for all i and j. for every (a,b) there must be a (b,a)
digraph:
When there are arrows point going in both directions for all points
Determine whether a relation is antisymmetric when it is represented as a a zero-one matrix or a directed graph
ZO Matrix:
R is antisymmetric if and only
if Mij = 0 or Mji = 0 for all i does not equal j.
Except for self loops, Mij and Mji cannot both equal 1
digraph:
When there are no points in which arrows point in between one another
Determine whether a relation is transitive when it is represented as a a zero-one matrix or a directed graph
ZO Matrix & digraph
Must be able to get from A to D and back to A with A,C & C,D and then D,A
Find reflexive closures of a binary relation
The reflexive closure of a relation R on A is obtained by adding (a, a) to R for each a ∈ A.
Find symmetric closures of a binary relation.
The symmetric closure of R is obtained by adding (b, a) to R for each (a, b) ∈ R.
Find transitive closure of a binary relation using Algorithm 1
Transitive Closure
=MR∗
= MR ∨ MR^2 ∨ MR^3 ∨ M^4
You take the column from the first matrix and figure if its true for all elements of the row of the other matrix
= 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 ∨ 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 ∨ 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 ∨ 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Find transitive closure of a binary relation using Warshall’s algorithm
Add 1 to positons in which paths within the poset use as an interior vertex
ex. W1 = 1 for all paths that use 1 as an interior vertex so if (b,a) and (a,d) exists, add 1 in (b,d) and so on...
Is the given relation an equivalence relation?
is reflexive, symmetric, and transitive.
What is the equivalence class of a set for the given equivalence relation?
The set of all elements that are related to an element
a of A is called the equivalence class of a. The equivalence class of a with respect to R is denoted
by [a]R.
Find the partition of a set when an equivalence relation is given and vice versa
A partition is all the different ways to create subsets that include all elements in a set (nonempty (is not empty), disjoint (contain duplicates of an element) and exhaust (use every element))
Is the given relation a partial order or total order?
Is a partial order if partial order if it is reflexive, antisymmetric, and transitive.
A total order is If S is a poset and every two elements of S are comparable
Find the ordering of given n-tuples according to the given lexicographic order.
(use curvy) < to order things by least to greatest usually
construct Hasse diagram for partial orderings
Construct a digraph representation of the poset (S, 4) so that all edges point up (except the loops)
• Eliminate all loops
• Eliminate all edges that are redundant because of transitivity
• Eliminate the arrows at the ends of edges since everything points up
Find the following from a given poset or a Hasse diagram:
Maximal/minimal elements
Minimal Elements:
The elements at the bottom that have no other elements related to them
Maximal Elements:
The elements that are at the top that are not related to any other elements
Find the following from a given poset or a Hasse diagram:
The greatest/least element if exists
Least Element:
element would have to be a number that relates to all other elements
Greatest Element:
element would have to be a number that all other
elements relate to.