These questions are about partial orderings. In both questions, lower-case lette
ID: 3198238 • Letter: T
Question
These questions are about partial orderings. In both questions, lower-case letters a, b, c, etc. represent arbitrary distinct objects.
1. (10 points.) Is the relation represented by the set S a partial ordering?
S = { (a, a), (b, b), (c, a), (c, c), (c, d), (d, c), (d, d) }
If S is a partial ordering, then explain why. If S is not a partial ordering, then state what properties of partial orderings it does not have. Also, if S does not have a property, then show a counterexample.
2. (10 points.) Suppose that the relation R is a partial ordering, so x R y means that x precedes y in the ordering. Also suppose that we know the following facts about R.
a
R
c
e
R
h
c
R
g
h
R
f
g
R
d
b
R
h
d
R
f
i
R
b
g
R
e
i
R
e
Show a total ordering ? that is compatible with what we know about the partial ordering R.
a
R
c
e
R
h
c
R
g
h
R
f
g
R
d
b
R
h
d
R
f
i
R
b
g
R
e
i
R
e
Explanation / Answer
Hi,
Its against chegg policy to post multiple questions as one, please post the other one as a separate question
1.
Given realtion is S = { (a, a), (b, b), (c, a), (c, c), (c, d), (d, c), (d, d) }
Now, A relation R on a set S is called a partial ordering if it is reflexive, antisymmetric and transitive
lets check for all 3
a. reflexive - a relation R is reflexive if every element of the set is related to itself
since (a,a),(b,b),(c,c) and (d,d) exist, S is reflexive
b. R is anti-symmetric if for all a and b in the set
if R(a,b) and R(b,a), then a = b,
in S since we have both (c,d) and (d,c) and also c!=d which means S is NOT anti-symmetric and therefore NOT a partial ordering
Thumps up if this was helpful, otherwise let me know in comments
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.