Discrete Structures: For each of the following relations, determine whether it i

Question

Discrete Structures:

For each of the following relations, determine whether it is reflexive, anti-reflexive, symmetric, anti-symmetric, or transitive. Note that it may be possible for a relation to satisfy more than one property in each category – think carefully about the definitions! Briefly explain your answers for each one.

a. The domain is all CPUs. For any CPUs x and y, xRy if x has a higher clock speed than y.

b. The domain is all people. For any people x and y, xRy if x and y are friends. Assume that everyone is his/her own friend, and that if A considers B a friend then B feels the same way about A.

Explanation / Answer

hi,
lets first define all the properties,
1.Reflexive:if every element of X is related to itself
2. Anti-reflexive:where no element is related to itself
3. Symmetric, if it holds for all a and b in X that a is related to b if and only if b is related to a
4.Anti-symmetric:where the only way a can be related to b and b be related to a is if a = b
5.Transitive:if whenever an element a is related to an element b and b is related to an element c then a is also related to c
Now,
B.given xRy if x and y are friends,
Reflexive:since given everyone is his/her own friend, TRUE
Anti-reflexive: :FALSE, since reflexive
Symmetric:Given if A, B is in relation, i.e A considers B as friend then B also feels the same, i,e B,A also exists
Anti-symmetric:FALSE, since A,B and B,A exists even where A!=B
Transitive: if x,y belong to R i.e X is friend of Y and y,z belong to R i.e Y is friend of Z, then since Y is friend of Z and Y is also friend of X, X is a friend of Z, hence true
A. given For any CPUs x and y, xRy if x has a higher clock speed than y.
Reflexive: No, because the clock speef of any CPU is not greater than clock speed of itself
Anti-reflexive: Yes, since no element is related to itself,
Symmetric:False, since if x and y are related, then speed of x>speed of y, which means y,x cannot satisfy.
Anti-symmetric:True, no pair satisfies x and y and y and x, even when x==y
Transitive: if x,y belong to R i.e speed of X>speed of Y, and y,z belong to R i.e. speed of Y>speed of Z, then since
speed of X> speed of Y >speed of Z, x,z satisfies the relation.

Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.