BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK
Rendezett halmaz R ⊆ A x A rendezési reláció A-n, ha R (a, b) ∈ R ≡ a R b 1. Reflexív 2. Antiszimmetrikus 3. Tranzitív Másképpen: aRb for (a, b) ∈ R. 1. ∀a ∈ A aRa 2. ∀a,b ∈ A (aRb ∩ bRa ⇒ a = b 3. ∀a,b,c ∈ A (aRb ∩ bRc ⇒ aRc Lehet használni a szokásos a ≤ b jelet is R-re Ha R rendezés az A-n, akkor (A, R) rendezett halmaz Ha minden elempár benne van R-ben, akkor a rendezés teljes, ha nem mindeygik van benne, vagyis nem mindegyik hasonlítható össze, akkor parciális (részleges) a rendezés. Teljes a rendezés, ha: ∀a, b (a R b ∨ b R a). HESSE diagramm: (a, a) ∈ R →, vagy ahova mutat a nyíl, azt az elemet feljebb rajzoljuk.Ekkor nem kell nyíl, csak vonal. Ez a diagramm a rendezés rövidített jelölése is. A definíció szerint: (1)
∀a (a R a).
DIAGRAMMban: minden elembőkl indulna egy hurok. Ezeket NEM ábrázoljuk, hiszne tudjuk. Helyette csak az elemeket rejzoljuk le.
©Bércesné Novák Ágnes
1
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK Ha (a, b) ∈R, akkor rajzolunk egy vnalat a-ból b-be, és b-t feljebb rajzoljuk:
DIAGRAMM 6
3. ∀abc (a R b ∧b R c ⇒ a R c) Ez lenne, helyette:
DIAGRAMM ≡ ≡
Vagyis azokat a párokat, amelyek a tranzitivitással (is) kaphatók, nem kötjük vonallal össze:
≡ w
©Bércesné Novák Ágnes
2
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK Példa: A = {a, b, 1, 2, 3}. Adjon meg A-n négy különböző (parciális) rendezést
(A1≤1)
(A1≤2)
(A1≤3)
(A1≤4)
A fenti ábrák alapján adja meg a rendezést párokkal. Például (A1≤1) a következőképpen adható meg: (a,a)∈ ≤1 , (b,b)∈ ≤1 , (1,1)∈ ≤1, (2,2)∈ ≤1, (3, 3)∈ ≤1 (a,1)∈ ≤1, (b,2) ∈ ≤1, (b, 3) ∈ ≤1 vagy: (a≤11, b ∈ ≤12, b ∈ ≤13 ........ Írja ide a rendezés ily módon való megadását a többi esetben is: (A1≤2):
(A1≤3):
(A1≤4):
©Bércesné Novák Ágnes
3
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK
A = {1, 2, 3, 4}. xRy akkor és csak akkor ha x ≤ y (A, ≤ )
DIAGRAMM 2
“≤” a szokásos rendezés: DIAGRAMM3
R = {(1, 2), (3, 3), (4, 4), (1, 1), (2, 2)} van megadva a DIAGRAMM 2-ben Egy halmazon (parciális) rendezést megadni annyit jelent, hogy egy reflexív, antiszimmetrikus, tranzitív relációt adunk meg. Ez az ábrával egyszerűbb, hiszen a megengedett jelekkel a reláció “kijön”. Rendezést megadni ≡ diagrammot rajzolni Példa: A = {1, 2, 3, 4, 5, 6, 7, 8} nRm vagyis n ≤ m akkor és csak akkor, ha n | m
n|m: ∃ k ∈ Z (m = k•n) Volt előadáson:
©Bércesné Novák Ágnes
4
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK Reflexív : nRn
n|n , mert n = 1* n k = 1
Antiszimmetrikus: nRm és mRn, akkor n=m n|m
∩
→
m|n
n=m
∃ k1∈ Z m = k1 * n
∩
∃ k2 ∈ Z
m = k 1 * k2 * m
k 1, k ∈ Z
k1 = k 2 = 1
k1 = k2 = -1
or
m=n
n = k2 * m
m = -n n = -m n=m
n=m Tranzitív: ∃t
n|m∩m|k⇒n|k k = t•n
m = k1n ∩ k = k2 m k = t * n k = k 2 • k 1• n
t = k1 * k2
(A, | ), (P(A), ⊆)
További példák: (A, R), itt R lehet a |
reflexív,antiszimetrikus, tranzitív
©Bércesné Novák Ágnes
5
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK
A RENDEZETT HALMAZ SPECIÁLIS ELEMEI: MAXIMÁLIS, MINIMÁLIS, LEGNAGYOBB, LEGKISEBB
a0 ∈ A a LEGKISEBB (A, ≤) ha ∀a ∈ A (a0 ≤ a) Példa: A = {1, 2, 3, 4, 5}, n ≤ m ha n | m HESSE DIAGRAMM 1≤m
mnden m ∈ A-ra 1 A LEGKISEBB ELEM (A, ≤)-ban.
LEGKISEBB azt jelenti, hogy legalul van és össze van kötve minden elemmel. HA pl. A-t megváltoztatjuk: A = {1, 2, 3, 4}, akkor nincsen legkisebb és nincsen legnagyobb elem.
≤ = {(1, 1), (1, 2), (3, 3), (4, 4)}
DEF.: A LEGNAGYOBB ( A, ≤) – ban, ha ∀a∈A (a ≤ a0), a0 ∈ A Felül szerepel, és össze van kötve mindegyik elemmel, (N, ≤) DIAGRAMM: 0 a legkisebb, de nincsen legnagyobb:
©Bércesné Novák Ágnes
6
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK
Példa: Adjon meg egy olyan rendezést, amelyben 5 a legnagyobb elem, és nincsen legkisebb elem.
Def.: a0 MAXIMÁLIS (A, ≤ ) –ban, ha (a0∈A) ¬∃a∈A(a ≠ a0 ∩ a0 ≤ a) Max (A, ≤) azokat az elemeket jelenti, amelyek felett nincsen elem. Példa: MAX: 4, 3, 5
Feladat: A fenti (def. felettii) két példában jelölje be a maximális elemeket. Def.: ©Bércesné Novák Ágnes
7
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK
MINIMÁLIS elem (A, ≤)-ban a0 ∈ A MINIMÁLIS, ha ¬∃a∈ A (a ≠ a0 ∩ a ≤ a0) Példa: Adjon meg olyan rendezést az A = {1, 2, 3, 4, 5, 6}halmazon, hogy 3 MAX eleme és 4 MIN eleme legyen: Egy megoldás: MAX : 6, 1, 2 MIN : 6, 1, 4, 5
Másik megoldás: MAX : 5, 6, 1 Melyek a minimálisak?
Feladat: Melyek az alábbi , 1, 2, 3, 4, számhalmazon megadott rendezésben a legnagyobb, legkisebb, minimális, maximális elemek? R = {(1, 2), (1, 3), (2, 3), (4, 3)} ∪ {(x,x)}
©Bércesné Novák Ágnes
8
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK Példa: Nincsen legnagyobb, nincsen legkisebb elem, de van 5 MIN és 10 MAX.
Feladat: Adjon meg egy rendezést úgy a természetes számokon, hogy 10 MAX és 5 minimális elem legyen!
Feladat : Adjon meg egy rendezést úgy a természetes számokon, hogy X db MAX és legyen legkisebb elem!
Feladat: Adjon meg egy rendezéset úgy a természetes számokon, hogy egyetlen MAX elem legyen, de ne legyen legnagyobb elem.
©Bércesné Novák Ágnes
9
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK
Tételek: (A, ≤) : Ha van legkisebb és legnagyobb elem, ezek egyértelműek. Ha A végtelen, lehetséges, hogy egyetlen maximális eleme van, de nincsen léegnagyobb. (MIN, nincsen legkisebb, hasonlóan). HA A véges, és van egyértelmű MAX és MIN elem, akkor.......
Minden rendezett halmazban a legnagyobb elem egyben... és a legkisebb elem egyben ... Def.:(A, ≤) B ⊆ A X0∈A alsó (felső x0) korlátja a B-nek az X0, ha ∀b ∈ B (X0 ≤ (x0≥)b) Példa:
A = {1 2 3 4 5 6 7} B = {5, 3, 4}
Felső: nincs, mert MINDEGYIK b ∈ B felett kellene állnia (összekötve!) Alsó: minden b ∈ B. alatt(összekötve!): 3, 1. 3∈B 1 ∉ B. Példa: (2, ≤) ahol ≤ a szokásos rendezés. Felsö: Alsó:
Példa olyan rendezett halmazra, amelyben semmelyik egynél több elemű halmaznak nincsen felső és alsó korlátja.
©Bércesné Novák Ágnes
10
BMF
NIK DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK Def.: legkisebb felső/SUP, legnagyobb alsó korlát/INF Példa: a B halmaz felső korlátjai: 7, 8, 9 SUP{B} = 7 Alsó korlátok: 4, 3, 2, 1 INF {B} = 4 E
B nincsen SUP, I NF C felső korlátai: f, h, t, z (a reflexivitás miatt kell f-et is belevenni) SUP( C) = f C alsó korlátai: {a}
©Bércesné Novák Ágnes
INF(C) = a
11