Mathematical Techniques for Computer Science (COMP11120)
Class notes
Lecture Notes on Notions for Partial Orders (COMP11120)
7 views 0 purchase
Course
Mathematical Techniques for Computer Science (COMP11120)
Institution
The University Of Manchester (UOM)
Deepen your understanding of partial orders with these comprehensive lecture notes for COMP11120. Covering key concepts such as posets, Hasse diagrams, and order properties, these notes provide clear explanations and illustrative examples to help you grasp the foundational elements of partial order...
Mathematical Techniques for Computer Science (COMP11120)
All documents for this subject (9)
Seller
Follow
jpxoi
Content preview
Notions for Partial Orders
Maximal and Minimal Elements
An element p of a
poset (P ) ,
is a maximal element of P if and only if for all Example : The binary relation R' on set S where R =
[(V v) , ,
(V , W) , (w , v) , (W , W) , (W , ),
(X , z) , (X w) , (2 y) , (y z)]
pleP have p 1 p' then
, , ,
we
p =
p
For a maximal element of a
poset there cannot be another element above it (because any
& maximal
element above has to be equal to it) v
.
Vi elements
E w W
An element Y
*
p of a
poset (P 2) ,
is a minimal element of P if and only if it is the
case that for all pleP we have p' up then p =
pl
Z
A minimal element cannot have another element below it. 8y < *
X
minimal
A poset have than maximal minimal element.
can more one or
elements
Greatest and Least Element
An element of poset (P 2) is the greatest
p a
,
element of P if and only if it is the Example : The binary relation R' on set S where R =
((V v) , ,
(V , W) , (w , v) , (W , Wh , (W , ),
z) , (X w) , (2 y) , (y z)]
case that for all plep we have p'Xp (X , , , ,
maximal
An element p of a
poset (P 2) ,
is the least element of P if and only if it is the
v
elements
Least : none as we can't
case that for all pleP we have pap compare X with 2
Y W
Greatest : none as we can't
Compare y , v, and 2
.
minimal
Z
X elements
Bitstrings Example : Consider the relation 1 over bitstrings b = mom,me of length 3 for
mo ,
m
, ma e [0 13 ,
i . .
e
b
/000 , 001, 010
,
011 , 100
,
101 , 110 , 1113
Let mom , me momims if and
only if mosmo and m
, m ! and
m2 < m2
111 masimal
011 101 110
Least : 000
001 018 100
Greatest : 111
000 minimal
Upper and Lower Bounds
Let S be a subset of a poset (P, ) Example Consider
: poset (P , 1) for ,
P = Su ,
V
,
W
, , y, 23 given below .
An element Find all the bounds for the set S
p of P is an
upper bound for S if and only if for all pleS if we have p'XP .
upper .
An element of P is lower bound S if only if for all pleS if have pXP! V S UB
p a
for and we
[x] * V, w
, Y
Note that in both cases
p doesn't have to be an element of S Y
W U
(x 2) ,
v
,
w
(w ,
x
, z] v
,
w
X 2
Sy ,
W,
v} v
V S LB
Sy V3
,
7,
y
Y
W U
sw uy , Z
X
& Y W3
,
X 2 Ey w
, , v3 none !
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jpxoi. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.58. You're not tied to anything after your purchase.
