DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK. Rendezett halmaz. (a, b) R a R b 1. Reflexív 2. Antiszimmetrikus 3

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


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):


3

BMF


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:


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


5

BMF


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:


6

BMF


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


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)}


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.


9

BMF


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.


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}


INF(C) = a

11

DISZKRÉT MATEMATIKA RENDEZETT HALMAZOKKAL KAPCSOLATOS PÉLDÁK. Rendezett halmaz. (a, b) R a R b 1. Reflexív 2. Antiszimmetrikus 3

Recommend Documents