Sok tényező, köztük. Egyenértékűségi relációk

Legyen R bináris reláció egy X halmazon. Egy R relációt hívunk fényvisszaverő ha (x, x) Î R minden x Î X esetén; szimmetrikus - ha (x, y) Î R azt jelenti, hogy (y, x) Î R; a 23-as tranzitív szám a 24-es változatnak felel meg, ha (x, y) Î R és (y, z) Î R azt jelenti, hogy (x, z) Î R.

1. példa

Azt mondjuk, hogy x Î X van közös y Î X elemmel ha a halmaz
x Ç y nem üres. Egy közös kapcsolat reflexív és szimmetrikus lesz, de nem tranzitív.

Egyenértékűségi reláció X-en reflexív, tranzitív és szimmetrikus relációnak nevezzük. Könnyen belátható, hogy R Í X ´ X akkor és csak akkor ekvivalencia reláció, ha a zárványok megtörténnek:

Id X Í R (reflexivitás),

R -1 Í R (szimmetria),

R ° R Í R (tranzitivitás).

Valójában ez a három feltétel egyenértékű a következőkkel:

Id X Í R, R -1 = R, R ° R = R.

Szakítással egy X halmazt páronként diszjunkt részhalmazok A halmazának nevezzük a Í X úgy, hogy UA = X. Minden A partícióhoz társíthatunk egy ekvivalencia relációt az X-hez, x ~ y beállítással, ha x és y valamilyen a Î elemei. A.

Minden X-en lévő ~ ekvivalencia relációhoz tartozik egy A partíció, amelynek elemei részhalmazok, amelyek mindegyike a ~ relációban lévőkből áll. Ezeket a részhalmazokat ún ekvivalencia osztályok ... Ezt az A partíciót az X halmaz faktorhalmazának nevezzük a ~ vonatkozásában, és a következővel jelöljük: X / ~.

Határozzuk meg a ~ arányt a w természetes számok halmazán, x ~ y beállítással, ha az x és y 3-mal való elosztása utáni maradékok egyenlőek egymással. Ekkor w / ~ három ekvivalenciaosztályból áll, amelyek megfelelnek a 0, 1 és 2 maradékoknak.

Rendelési viszony

Egy X halmazon lévő R bináris relációt hívunk antiszimmetrikus ha x R y és y R x-ből következik: x = y. Egy X halmazon lévő R bináris relációt hívunk rendi hozzáállás ha reflexív, antiszimmetrikus és tranzitív. Könnyen belátható, hogy ez egyenértékű a következő feltételek teljesítésével:

1) Id X Í R (reflexivitás),

2) R Ç R -1 (antiszimmetria),

3) R ° R Í R (tranzitivitás).

Egy X halmazból és egy X-en lévő R sorrendi relációból álló rendezett párt (X, R) hívunk részben megrendelt készlet .

1. példa

Legyen X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) ), (1, 3), (2, 2), (3, 3)).

Mivel R teljesíti az 1-3 feltételt, ezért (X, R) egy részben rendezett halmaz. Az x = 2, y = 3 elemekre sem x R y, sem y R x nem igaz. Az ilyen elemeket ún egyedülálló ... Általában a sorrendi összefüggést £ jelöli. A fenti példában 0 £ 1 és 2 £ 2, de nem igaz, hogy 2 £ 3.

2. példa

Legyen< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

Egy részlegesen rendezett halmaz (X, £) x, y Î X elemeit hívjuk meg hasonló ha x £ y vagy y £ x.

Egy részlegesen rendezett halmazt (X, £) hívunk lineárisan rendezett vagy lánc ha bármely két eleme összehasonlítható. A 2. példa halmaza lineárisan lesz rendezve, de az 1. példából nem.

Egy részlegesen rendezett halmaz (X, £) A Í X részhalmazát hívjuk meg felülről határolt ha létezik olyan x Î X elem, hogy £ x minden Î A-ra. Egy x Î X elemet hívunk a legnagyobb X-ben, ha y £ x minden y Î X-re. Egy x Î X elemet akkor nevezünk maximálisnak, ha az x-en kívül nincs más y Î X elem, amelyre x £ y. Az 1. példában a 2. és 3. elem lesz a legnagyobb, de nem a legnagyobb. Hasonlóképpen, alsó határ részhalmazok, legkisebb és legkisebb elemek. Az 1. példában a 0 elem lesz a legkisebb és a legkisebb is. A 2. példában a 0 is rendelkezik ezekkel a tulajdonságokkal, de (w, £) nem rendelkezik sem a legnagyobb, sem a maximális elemmel.

Legyen (X, £) egy részlegesen rendezett halmaz, A Í X egy részhalmaz. Egy A-n lévő reláció, amely a, b Î A elemek (a, b) párjaiból áll, amelyekre a £ b, sorrendi reláció lesz A-n. Ezt a relációt ugyanaz a szimbólum jelöli: £. Így (A, £) egy részben rendezett halmaz. Ha lineárisan rendezett, akkor azt mondjuk, hogy A - lánc in (X, £).

A maximalitás elve

Egyes matematikai állítások nem bizonyíthatók a választás axiómája nélkül. Ezek a kijelentések állítólag azok a választás axiómájától függ vagy érvényesek a ZFC elméletben , a gyakorlatban a választási axióma helyett a bizonyításhoz általában vagy a Zermelo-axiómát, vagy a Kuratowski-Zorn-lemmát, vagy a választási axiómával egyenértékű bármely más állítást használjuk.

Lemma Kuratovsky-Zorn. Ha minden lánc egy részben megrendelt készletben(X, £) felülről határolt, majd be x van legalább egy maximális elem.

Ez a lemma ekvivalens a választási axiómával, ezért axiómának is felfogható.

Tétel.Bármilyen részben megrendelt készlethez(X, £) van egy relációt tartalmazó reláció£ és átalakul x lineárisan rendezett halmazba.

Bizonyíték... A £ relációt tartalmazó összes rendbeli reláció halmazát az Í befogadási reláció rendezi. Mivel a rendi viszonyok láncának uniója egy sorrendi reláció, ezért a Kuratowski-Zorn lemma szerint létezik olyan R maximális reláció, amelyre x £ y x R y-t jelenti. Bizonyítsuk be, hogy R egy X-et lineárisan rendező reláció Tegyük fel az ellenkezőjét: legyen olyan a, b Î X, hogy sem (a, b), sem (b, a) nem tartozik R-hez.

R ¢ = R È ((x, y): x Ra és b R y).

Ezt úgy kapjuk meg, hogy R-hez adunk egy (a, b) és (x, y) párokat, amelyeket hozzá kell adni R ¢-hez abból a feltételből, hogy R ¢ egy sorrendi reláció. Könnyen belátható, hogy R ¢ reflexív, antiszimmetrikus és tranzitív. R Ì R ¢-t kapunk, ami ellentmond R maximalitásának, ezért R a kívánt lineáris sorrendű reláció.

Egy lineárisan rendezett X halmazt akkor nevezünk jól rendezettnek, ha minden nem üres A Í X részhalmaza tartalmazza a legkevesebb a Î A elemet. A Kuratowski-Zorn lemma és a választási axióma szintén ekvivalens a következő állítással:

Axióma Zermelo. Minden halmazhoz van egy sorrendi reláció, amely jól rendezett halmazzá változtatja.

Például a természetes számok w halmaza jól rendezett. Az induktivitás elvét a következőképpen foglaljuk össze:

Transzfinit indukció. Ha(X, £) Jól rendezett halmaz, és F (x) elemeinek tulajdonsága,érvényes a legkisebb x 0 Î X elemre, és úgy, hogy ha F (y) igaz minden y-ra < z следует истинность F(z), то F (x) mindenkire igaz x Î X .

Itt y< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.

Teljesítmény fogalma

Legyen f: X à Y és g: Y à Z beállított leképezések. Mivel f és g relációk, összetételük g ° f (x) = g (f (x)). Ha h: Z à T halmazok térképe, akkor h ° (g ° f) = (h ° g) ° f. Az Id X és Id Y összefüggések függvények, ezért az Id Y ° f = f ° Id x = f összetétel határozza meg. X = Y esetén f 2 = f ° f, f 3 = f 2 ° f,…, f n + 1 = f n ° f.

Az f: X àY leképezést hívjuk injekcióval ha f (x 1) ¹ f (x 2) az X halmaz bármely x 1 ¹ x 2 elemére. Az f leképezést nevezzük szurjektálás ha minden y ÎY esetén van olyan x Î X, hogy f (x) = y. Ha f egyben szurjektív és injekció is, akkor f-et hívjuk bijekció ... Könnyen belátható, hogy f akkor és csak akkor bijekció, ha az f -1 Í Y ´ X inverz reláció függvény.

Azt fogjuk mondani, hogy az egyenlőség | X | = | Y | ha bijekció van X és Y között. Tegye | X | £ | Y | ha van injekció f: X à Y.

Cantor-Schroeder-Bernstein tétel. Ha X | £ | Y | és|I | £ | X | , azután X | = | I |.

Bizonyíték... Hipotézis szerint léteznek f: X à Y és g: Y à X injekciók. Legyen A = g ¢¢ Y = Img az Y halmaz képe a g leképezéshez képest. Azután

(X \ A) Ç (gf) ¢¢ (X \ A) = Æ,

(gf) ¢¢ (X \ A) Ç (gf) 2 ¢¢ (X \ A) = Æ,…,

(gf) n ¢¢ (X \ A) Ç (gf) n + 1 ¢¢ (X \ A) = Æ,…

Tekintsük a j leképezést: X à A definíció szerint j (x) = gf (x) for

x Î (X \ A) È (gf) ¢¢ (X \ A) È (gf) 2 ¢¢ (X \ A) È…, és j (x) = x egyébként. Könnyen belátható, hogy j bijekció. Az X és Y közötti kívánt bijekció g -1 ° j lesz.

Kántor antinómiája

Feltesszük | X |< |Y|, если |X| £ |Y| и не существует биекции между X и Y.

Kántor-tétel. Bármely X, | X | halmazhoz< |P(X)|, где P(X) – множество всех подмножеств множества X.

Halmazelmélet. Alapfogalmak

A halmazelmélet a modern matematika alapvető definíciója. Georg Cantor készítette az 1860-as években. Azt írta: "Sokan sok, egészében elképzelhető." A halmaz fogalma a matematika alapvető, meghatározatlan fogalmai közé tartozik. Nem csapódik le más, egyszerűbb fogalmakra. Ezért nem definiálható, hanem csak magyarázható. A halmaz tehát az intuíciónk vagy gondolataink által világosan megkülönböztethető tárgyak egy egésszé egyesítése; néhány közös tulajdonság által meghatározott objektum gyűjteménye.

Például,

1. Sok voronyezsi lakos

2. A sík pontjainak halmaza

3. A természetes számok halmaza ℕ stb.

A halmazokat általában nagy latin betűkkel jelölik ( A, B, C stb.). Az adott halmazt alkotó objektumokat elemeinek nevezzük. A halmaz elemeit kis latin betűkkel jelöljük ( a, b, c stb.). Ha NS- állítsa be, majd rögzítse х∈Х azt jelenti, hogy NS a halmaz eleme NS vagy mi NS a készlethez tartozik NSés a bejegyzés x∉X azt az elemet NS nem tartozik a készlethez NS... Például legyen ℕ a természetes számok halmaza. Azután 5 ℕ , a 0,5∉ℕ .

Ha a készlet Y halmaz elemeiből áll NS akkor azt mondják Y a halmaz egy részhalmaza NSés jelöljük Y⊂X(vagy Y⊆X). Például az egész számok halmaza ℤ a racionális számok részhalmaza ℚ .

Ha két szettre NSés Y két zárvány egyszerre megy végbe X Yés I X, azaz NS a halmaz egy részhalmaza Yés Y a halmaz egy részhalmaza NS, majd a készletek NSés Y azonos elemekből állnak. Ilyen készletek NSés Y egyenlőnek nevezzük és írjuk: X = Y.

Az üres halmaz kifejezést gyakran használják - Ø - elemet nem tartalmazó halmaz. Ez bármely halmaz részhalmaza.

A következő módszerek használhatók halmazok leírására.

Halmazok meghatározásának módszerei

1. Tárgyak felsorolása. Csak véges halmazokhoz használatos.

Például, X = (x1, x2, x3 ... x n)... Y jelölés ={1, 4, 7, 5} azt jelenti, hogy a halmaz négy számból áll 1, 4, 7, 5 .

2. A halmaz elemei jellemző tulajdonságának feltüntetése.

Ehhez be van állítva egy bizonyos tulajdonság R, amely lehetővé teszi egy elem halmazhoz való tartozásának meghatározását. Ez a módszer sokoldalúbb.

X = (x: P (x))

(sok NS olyan elemekből áll NS amelyre az ingatlan elégedett P (x)).

Egy üres halmaz a tulajdonságainak megadásával adható meg: Ø = (x: x ≠ x)

Lehetőség van új halmazok létrehozására a már megadottak felhasználásával, halmazokon végzett műveletekkel.

Műveletek beállítása

1. Az unió (összeg) olyan halmaz, amely mindazon elemekből áll, amelyek mindegyike legalább egy halmazhoz tartozik. A vagy V.

A∪ B = (x: x A vagy x B).

2. A metszéspont (szorzat) olyan halmaz, amely minden elemből áll, amelyek mindegyike egyidejűleg halmazként tartozik. Aés sok V.

A∩B = (x: x A és x B).

3. A halmazok különbsége Aés V halmaznak nevezzük, amely a halmazhoz tartozó összes elemből áll Aés nem tartoznak a halmazhoz V.

A \ B = (x: x A és x B)

4. Ha A A halmaz egy részhalmaza V... Azt a sokaságot B\A a halmaz komplementerének nevezzük A sokaknak Vés jelöljük A'.

5. Két halmaz szimmetrikus különbsége a halmaz А∆В = (А \ В) (B \ A)

N- az összes természetes szám halmaza;
Z- az összes egész szám halmaza;
K- az összes racionális szám halmaza;
R- az összes valós szám halmaza;
C- az összes komplex szám halmaza;
Z 0- az összes nem negatív egész szám halmaza.

A halmazokon végzett műveletek tulajdonságai:

1.A B = B A (kommutatív unió)

2.A B = B A (metszéspont kommutativitás)

3. A (B C) = (A V) C (szakszervezeti asszociativitás)

4.A (V C) = (A V) C (asszociatív metszéspont)

5.A (V C) = (A V) (A C) (1 eloszlási törvény)

6.A (V C) = (A V) (A C) (2. eloszlási törvény)

7.A Ø = A

8.A U = U

9.A Ø= Ø

10.A U = A

11. (A B) '= A' B' (de Morgan törvénye)

12. (A B) '= A' B' (de Morgan törvénye)

13.A (A B) = A (abszorpciós törvény)

14.A (A B) = A (abszorpciós törvény)

Bizonyítsuk be a 11-es tulajdonságot. (A B) '= A' V'

Az egyenlő halmazok definíciója szerint két zárványt kell bizonyítanunk 1) (A B) „⊂A” V';

2) A' В'⊂ (А V)".

Az első szerepeltetés bizonyításához vegyünk egy tetszőleges elemet х∈ (А B) '= X \ (A∪B). Ez azt jelenti х∈Х, х∉ А∪В... Ebből következik tehát x∉Aés x∉B, ezért х∈Х \ Аés х∈Х \ В, ami azt jelenti х∈А'∩В '... És így, (A B) „⊂A” V'

Ezzel szemben, ha х∈А V', azután NS egyszerre tartozik a halmazokhoz A ', B', ami azt jelenti x∉Aés x∉B... Ebből következik, hogy x∉ A V, ezért х∈ (А V)"... Ennélfogva, A' В'⊂ (А V)".

Így, (A B) '= A' V'

A két elemből álló halmazt, amelyben az elemek sorrendje meg van határozva, rendezett párnak nevezzük. Írásához zárójeleket használnak. (x 1, x 2)- egy kételemű halmaz, amelyben x 1 az első elem, x 2 pedig a második elem. Párok (x 1, x 2)és (x 2, x 1), ahol x 1 ≠ x 2 különbözőnek tekintendők.

Az n elemből álló halmazt, amelyben az elemek sorrendje definiálva van, n elemből álló rendezett halmaznak nevezzük.

Descartes szorzat - tetszőleges halmaz X 1, X 2, ..., X n n elemből álló rendezett halmazok, ahol x 1 X 1, x 2 X 2, ..., x n X n

X 1 X n

Ha a készletek X 1, X 2, ..., X n mérkőzés (X 1 = X 2 =… = X n), akkor a terméküket jelöljük X n.

Például, ℝ 2 - valós számok rendezett párjainak halmaza.

Egyenértékűségi relációk. Tényezőkészletek

Ehhez a halmazhoz néhány részhalmaz halmazát figyelembe véve új halmazokat hozhat létre. Ebben az esetben általában nem részhalmazok halmazáról beszélünk, hanem egy családról vagy részhalmazok osztályáról.

Számos kérdés foglalkozik egy adott halmaz ilyen részhalmazainak osztályával A amelyek nem metszik egymást, és amelyek egyesülése egybeesik A... Ha az adott halmaz A páronként diszjunkt részhalmazainak uniójaként ábrázolható, akkor azt szokás mondani, hogy A osztályokra bontva. Az osztályokra bontás valamilyen jellemző alapján történik.

Legyen NS Nem egy üres halmaz, akkor bármely részhalmaz R a munkából NS NS bináris relációnak nevezzük a halmazon NS... Ha egy pár (x, y) benne van R, x elemet relációnak mondjuk R val vel nál nél.

Például kapcsolat x = y, x≥y bináris relációk a halmazon ℝ.

Bináris reláció R forgatáson NS ekvivalenciarelációnak nevezzük, ha:

1. (x, x) R; NS X (a reflexivitás tulajdonsága)

2. (x, y) R => (y, x) R (szimmetria tulajdonság)

3. (x, y) R, (y, z) R, majd (x, z) R (tranzitivitási tulajdonság)

Ha egy pár (x, y) ekvivalencia relációba léptek, akkor x-et és y-t ekvivalensnek nevezzük (x ~ y).

1.Hagyd ℤ - egész számok halmaza, m≥1- egész szám. Definiáljunk egy ekvivalencia relációt R tovább ℤ szóval azt n ~ k, ha n-k osztva m... Vizsgáljuk meg, hogy az adott reláción teljesülnek-e a tulajdonságok.

1. Reflexivitás.

Bárkinek n∈ℤ ℤ oly módon, hogy (p, p) ∈R

p-p = 0... Mivel 0∈ ℤ , azután (p, p) ∈ℤ.

2. Szimmetria.

Tól től (n, k) ∈R ebből következik, hogy van ilyen p∈ ℤ, mit n-k = mp;

k-n = m (-p), -p∈ ℤ, ennélfogva (k, n) ∈R.

3. Tranzitivitás.

Attól, hogy (n, k) ∈R, (k, q) ∈R ebből következik, hogy vannak ilyenek 1. oés р 2 ∈ ℤ, mit n-k = olvadáspont 1és k-q = olvadáspont 2... Ezeket a kifejezéseket hozzáadva azt kapjuk n-q = m (p 1 + p 2), p 1 + p 2 = p, p∈ ℤ... Ezért (n, q) ∈ ℤ.

2. Tekintsük a készletet NS a tér vagy sík összes irányított szegmense . =(A, B)... Bemutatjuk az ekvivalencia relációt R tovább NS.

A matematikai elemzés a matematikának egy olyan ága, amely a függvények tanulmányozásával foglalkozik az infinitezimális függvény gondolata alapján.

A matematikai elemzés alapfogalmai az érték, halmaz, függvény, infinitezimális függvény, határérték, derivált, integrál.

Nagysága nevezzük mindazt, ami számmal mérhető és kifejezhető.

Sok néhány elem halmazának nevezzük, amelyeket valamilyen közös tulajdonság egyesít. Egy halmaz elemei lehetnek számok, figurák, tárgyak, fogalmak stb.

A halmazokat nagybetűkkel, az elemeket kisbetűkkel a többszörösek jelölik. A készletelemek göndör kapcsos zárójelekbe vannak zárva.

Ha elem x a készlethez tartozik x akkor írj x∈NS (∈ - tartozik).
Ha az A halmaz része a B halmaznak, akkor írjon A ⊂ B (⊂ - tartalmaz).

Egy halmaz kétféleképpen adható meg: felsorolással és egy meghatározó tulajdonság használatával.

Például a következő halmazokat felsorolás határozza meg:

• A = (1,2,3,5,7) - számok halmaza
• X = (x 1, x 2, ..., x n) - néhány x 1, x 2, ..., x n elem halmaza
• N = (1,2, ..., n) - természetes számok halmaza
• Z = (0, ± 1, ± 2, ..., ± n) - az egész számok halmaza

A halmaz (-∞; + ∞) meghívásra kerül számsor, és tetszőleges szám ennek az egyenesnek a pontja. Legyen a egy tetszőleges pont a számegyenesen, δ pedig egy pozitív szám. Az intervallumot (a-δ; a + δ) nevezzük δ-a pont szomszédsága.

Egy X halmaz fent (lent) korlátos, ha van olyan c szám, amelyre bármely x ∈ X esetén fennáll az x≤с (x≥c) egyenlőtlenség. Ebben az esetben a c számot hívják felső (alsó) él halmaz X. A fent és lent is korlátos halmazt hívjuk korlátozott... Egy halmaz felső (alsó) határai közül a legkisebb (legnagyobb) ún pontos felső (alsó) él ezt a készletet.

Alapvető számkészletek

N	(1,2,3, ..., n) Az összes halmaza
Z	(0, ± 1, ± 2, ± 3, ...) A halmaz egész számok. Az egész számok halmaza sok természetes számot tartalmaz.
K	Sok racionális számok. Az egész számok mellett vannak törtek is. A tört az alak kifejezése, ahol p- egész szám, q- természetes. A tizedes törteket úgy is fel lehet írni. Például: 0,25 = 25/100 = 1/4. Az egész számokat úgy is fel lehet írni. Például törtként „egy” nevezővel: 2 = 2/1. Így bármely racionális szám felírható tizedes törtként – természetesen vagy végtelen periodikusként.
R	Sok minden közül valós számok. Az irracionális számok végtelen nem periódusos törtek. Ezek tartalmazzák: Együtt két halmaz (racionális és irracionális számok) - valós (vagy valós) számok halmazát alkotják.

Ha a halmaz nem tartalmaz elemet, akkor meghívásra kerül üres készletés rögzítik Ø .

A logikai szimbolológia elemei

∀x jelölés: |x |<2 → x 2 < 4 означает: для каждого x такого, что |x|<2, выполняется неравенство x 2 < 4.

Quantor

A kvantorokat gyakran használják matematikai kifejezések írásakor.

Kvantifikátor egy logikai szimbólum, amely a következő elemeket jellemzi mennyiségi szempontból.

• ∀- általánosság kvantor, a „mindenkire”, „bármelyikre” szavak helyett használatos.
• ∃- egzisztenciális kvantor, a „létezik”, „van” szavak helyett használatos. A ∃ ! karakterek kombinációja is használatos, amely csak egy van beolvasva.

Műveletek beállítása

Kettő Az A és B halmaz egyenlő(A = B), ha azonos elemekből állnak.
Például, ha A = (1,2,3,4), B = (3,1,4,2), akkor A = B.

Konszolidáció (összeg) Az A és B halmazt A ∪ B halmaznak nevezzük, amelynek elemei ezen halmazok legalább egyikéhez tartoznak.
Például, ha A = (1,2,4), B = (3,4,5,6), akkor A ∪ B = (1,2,3,4,5,6)

kereszteződés (termék) az A és B halmazt A ∩ B halmaznak nevezzük, melynek elemei mind az A, mind a B halmazhoz tartoznak.
Például, ha A = (1,2,4), B = (3,4,5,2), akkor A ∩ B = (2,4)

Különbség az A és B halmazt AB halmaznak nevezzük, melynek elemei az A halmazhoz tartoznak, de nem tartoznak a B halmazhoz.
Például, ha A = (1,2,3,4), B = (3,4,5), akkor AB = (1,2)

Szimmetrikus különbség az A és B halmazt A Δ B halmaznak nevezzük, amely az AB és BA halmazok különbségeinek uniója, azaz A Δ B = (AB) ∪ (BA).
Például, ha A = (1,2,3,4), B = (3,4,5,6), akkor A Δ B = (1,2) ∪ (5,6) = (1,2, 5, 6)

A halmazokon végzett műveletek tulajdonságai

Permutációs tulajdonságok

A ∪ B = B ∪ A
A ∩ B = B ∩ A

Kombinációs tulajdonság

(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Megszámlálható és megszámlálhatatlan halmazok

Bármely két A és B halmaz összehasonlításához megfeleltetést hozunk létre elemeik között.

Ha ez a megfeleltetés egy az egyhez, akkor a halmazokat ekvivalensnek vagy ekvivalensnek nevezzük, A B vagy B A.

1. példa

A BC láb és az ABC háromszög AC befogópontjainak halmaza egyenlő erősségű.

Ha a hozzáállás R a következő tulajdonságokkal rendelkezik: reflexív szimmetrikus tranzitív, azaz. egy ekvivalencia reláció (~ vagy ≡ vagy E) a halmazon M , akkor az ekvivalenciaosztályok halmazát a halmaz faktorhalmazának nevezzük M az egyenértékűség tekintetében R és jelöltük ÚR

A halmaz elemeinek van egy részhalmaza M egyenértékű x hívott ekvivalencia osztály.

A hányadoshalmaz definíciójából következik, hogy a Boole-féle részhalmaza: .

A függvényt hívják azonosításaés a következőképpen van meghatározva:

Tétel. Tényezőalgebra F n / ~ izomorf a Boole-függvények algebrájával B n

Bizonyíték.

A keresett izomorfizmus ξ : F n / ~ → B n értéket a következő szabály határozza meg: ekvivalencia osztály ~(φ) a függvény illeszkedik f φ , amelynek a halmazból tetszőleges képletű igazságtáblázata van ~(φ) ... Mivel a különböző igazságtáblázatok különböző ekvivalenciaosztályoknak felelnek meg, a leképezés ξ injektív, és mivel bármely Boole-függvényhez f tól től Fogadó van egy képlet, amely a függvényt reprezentálja f, a leképezést ξ szürjektív. Műveletek mentése, 0, 1, amikor megjelenik ξ közvetlenül ellenőrizve. CHTD.

Az egyes függvények funkcionális teljességére vonatkozó tétel szerint, amelyek nem állandók 0 , valami SDNF-nek felel meg ψ osztályhoz tartozó ~ (φ) = ξ -1 (f) függvényt reprezentáló képletek f ... A probléma az osztályban való tartózkodással adódik ~(φ) diszjunktív normálforma, amely a legegyszerűbb szerkezetű.

Munka vége -

Ez a téma a következő részhez tartozik:

Előadások a diszkrét matematika tudományágáról

Moszkvai Állami Építőmérnöki Egyetem .. Vezetésgazdaságtani és Információs Rendszerek Intézet az Építőiparban .. IEUIS ..

Ha további anyagra van szüksége ebben a témában, vagy nem találta meg, amit keresett, javasoljuk, hogy használja a keresést munkáink között:

Mit csinálunk a kapott anyaggal:

Ha ez az anyag hasznosnak bizonyult az Ön számára, elmentheti az oldalára a közösségi hálózatokon:

Csipog

Az összes téma ebben a részben:

Diszkrét matematika tantárgy
A diszkrét (véges, véges) matematika a matematikának a diszkrét struktúrák tulajdonságait vizsgáló ága, míg a klasszikus (folytonos) matematika az objektumok tulajdonságait.

Izomorfizmus
Az algebrai műveleteket tanulmányozó tudományt algebrának nevezik. Ez a koncepció konkretizálódik és elmélyül a kurzus tanulmányozása során. Az algebrát csak az a kérdés érdekli, hogy HOGYAN cselekedjünk

Feladatok
1. Bizonyítsuk be, hogy egy izomorf térkép mindig izotóniás, és ennek fordítva nem igaz. 2. Írja le csoportját a halmazok nyelvén. 3. Írd le a tömegek nyelvén azokat a tárgyakat, amelyek

A halmaz és a halmaz elemei
A jelenleg létező halmazelméletek a fogalmi alap és a logikai eszközök paradigmatikájában (nézetrendszerében) különböznek egymástól. Tehát példaként felhozhatunk két ellentétet

Véges és végtelen halmazok
Miből áll egy készlet, pl. a halmazt alkotó objektumokat elemeinek nevezzük. A készlet elemei különböznek és különböznek egymástól. Ahogy a fenti példából is látható

A készlet kardinalitása
Egy véges halmaz számossága megegyezik az elemeinek számával. Például az n számosságú A halmaz B (A) univerzumának számossága

A1A2A3 | +… + | A1A2A3 | +… + | A1A2An | +… + | Аn-2An-1An | + (-1) n-1 | A1A2A3 ... An |
Egy véges A halmaz k számosságú, ha ekvivalens az 1 .. k szegmenssel ;:

Részhalmaz, saját részhalmaz
A halmaz fogalmának bevezetése után felmerül a probléma, hogy a meglévő halmazokból új halmazokat hozzunk létre, vagyis a halmazokra vonatkozó műveleteket határozzuk meg. Állítsa be az M ",

Jelentős halmazelméletek szimbolikus nyelve
A tantárgy tanulmányozása során különbséget teszünk a halmazelmélet tárgynyelve és a metanyelv között, amelynek segítségével a tárgynyelvet tanulmányozzuk. A halmazelmélet nyelvén relációst értünk

Bizonyíték
A B halmaz végtelen, ami azt jelenti

Elemek hozzáadása és eltávolítása
Ha A egy halmaz, és x egy elem, akkor az elem

Limitált készletek. Határok felállítása
Legyen adott egy f (x) numerikus függvény valamelyik X halmazon. Az f (x) függvény felső korlátja (határa) egy ilyen szám

Pontos felső (alsó) korlát
Az E összes felső határának halmazát Еs jelöli, minden alsó határt Еi. Abban az esetben

A halmaz pontos felső (alsó) határa
Ha egy z elem az E halmaz és az összes felső határának Es halmaz metszetébe tartozik (illetve az alsó r

A felső és alsó határok alapvető tulajdonságai
Legyen X egy részben rendezett halmaz. 1. Ha, akkor

A pluralitás attribúciós szempontból
Az aggregált nézőpont, ellentétben az attribúcióval, logikailag inkonzisztens abban az értelemben, hogy olyan paradoxonokhoz vezet, mint Russell és Cantor (lásd alább). Az attribútum keretein belül t

Szerkezet
Egy részlegesen rendezett X halmazt struktúrának nevezünk, ha tartalmaz bármilyen kételemű halmazt

Fedő és elválasztó készletek
Az A halmaz egy partíciója egy Аi család

Bináris kapcsolat
Egy n hosszúságú sorozatot, amelynek tagjai a1, .... ann, jelöljük (a1, .... a)

A bináris kapcsolatok tulajdonságai
Az R bináris reláció a Ho halmazon a következő tulajdonságokkal rendelkezik: (a) reflexív, ha хRх

Háromoldalú kapcsolatok
XY derékszögű termék

N-áris kapcsolatok
A két X, Y halmaz derékszögű szorzatával analóg módon megszerkeszthető egy X derékszögű szorzat

Leképezések
A leképezések a halmaz elemei közötti kapcsolatok némelyike. A kapcsolatok legegyszerűbb példái az x tagsági kapcsolatok

Levelezés
Egy Descartes-szorzat S részhalmazát az Mi halmazok elemeinek n-áris megfelelésének nevezzük. Formálisan

Funkció
A diszkrét matematika minden szakasza a függvény fogalmán alapul. Legyen X-

Egy függvény ábrázolása relációk szempontjából
Az f bináris relációt függvénynek nevezzük, ha -ból és

Injekció, szurjekció, bijekció
A "leképezés" kifejezés használatakor különbséget kell tenni az XvY leképezés és az X-Y-leképezés között.

Inverz függvény
Tetszőleges esetén határozza meg

Részben rendelt készletek
Egy S halmazt részlegesen rendezettnek (PN) nevezünk, ha reflexív, tranzitív és antiszimmetrikus bináris parciális sorrendű relációt adunk meg.

A halmaz ábrázolásának minimalizálása
E törvények felhasználásával vizsgáljuk meg az M halmaz reprezentációjának minimalizálásának problémáját a műveletek segítségével

Permutációk
Adott egy A halmaz. Legyen A egy véges halmaz, amely n elemből áll A = (a1, a2, ..., a

Permutációk ismétlésekkel
Legyenek az A halmaznak azonos (ismétlődő) elemei. Permutáció a kompozíció ismétlésével (n1, n2, ..., nk

Szállás
k (1≤k≤n) hosszúságú sorok, amelyek az A n elemű halmaz különböző elemeiből állnak (a sorok eggyel különböznek

Elhelyezések ismétlésekkel
Legyenek az A halmaznak azonos (ismétlődő) elemei. Elhelyezések n elem ismétlődésével k néven

Rendezett elhelyezés
n objektumot helyezünk el m dobozba úgy, hogy minden doboz egy sorozatot tartalmazzon, és ne a benne elhelyezett objektumok halmazát, mint korábban. Kettő

Kombinációk
Egy m elemű A halmazból alkossunk egy n hosszúságú rendezett halmazt, melynek elemei azonos elrendezések

Kombinációk ismétlésekkel
A kapott képletek csak akkor érvényesek, ha az A halmaz nem tartalmaz azonos elemeket. Legyen n típusú elem, és közülük egy sor

Metódusgeneráló függvények
Ez a módszer a kombinatorikus számok felsorolására és a kombinatorikus azonosságok megállapítására szolgál. A kiindulópont a szekvencia (ai) kombinátor

Algebrai rendszer
Az A algebrai rendszer egy ‹M, O, R› gyűjtemény, melynek első komponense M egy nemüres halmaz, a második O komponens a halmaz.

Lezárás és algebrák
Egy részhalmazt a φ if művelet tekintetében zártnak nevezünk

Algebrák egy bináris művelettel
Adjunk meg egy bináris műveletet az M halmazon. Tekintsük az általa generált algebrákat, de először vegyük figyelembe a bináris műveletek néhány tulajdonságát. Bináris o

Groupoid
A forma algebra<М, f2>csoportoidnak nevezzük. Ha f2 olyan művelet, mint a szorzás (

Egész számok modulo m
Adott egy egész számokból álló gyűrű ... Emlékeztessünk. Algebra<М,

Egyezések
Egybevágóság az A = algebrán (Σ - az algebra aláírása csak funkcionális szimbólumokból áll) ilyen ekvivalencia relációnak nevezzük.

A gráfelmélet elemei
A grafikonok matematikai objektumok. A gráfelméletet olyan területeken alkalmazzák, mint a fizika, kémia, kommunikációelmélet, számítógépes tervezés, elektrotechnika, gépészet, építészet, kutatás

Grafikon, csúcs, él
Irányítatlan gráfon (vagy röviden gráfon) egy ilyen tetszőleges G = párt értünk , mit

Levelezés
A G irányított gráf másik, gyakrabban használt leírása az X csúcsok egy halmazának és egy Г megfelelésnek a meghatározása, amely

Irányítatlan gráf
Ha az éleknek nincs orientációja, akkor a gráfot irányítatlannak nevezzük (iránytalan duplikált vagy nem orientált

Incidens, vegyes grafikon
Ha az e élnek (u, v) vagy alakja van<и, v>, akkor azt mondjuk, hogy az e él esik a ver-be

Fordított egyezés
Mivel ez olyan csúcsok halmaza

Gráfizomorfizmus
Két grafikon G1 = és G2 = izomorfak (G

Útvonalorientált útvonal
Az irányított gráf útvonala (vagy irányított útvonala) olyan ívsorozat, amelyben

Szomszédos ívek, szomszédos csúcsok, csúcsfokozat
ívek a = (xi, xj), xi ≠ xj, közös végpontokkal, n

Kapcsolódás
Egy gráf két csúcsát összekapcsoltnak nevezzük, ha van egy egyszerű lánc, amely összeköti őket. Egy gráfot összefüggőnek nevezünk, ha minden csúcsa össze van kötve. Tétel.

Súlyozott ívgrafikon
A G = (N, A) gráfot súlyozottnak nevezzük, ha egy l: A → R függvény van definiálva az A ívek halmazán,

Erős kapcsolódási mátrix
Erősen összefüggő mátrix: tegyen 1-et az átlóra; töltse ki az X1 sort - ha a csúcs elérhető X1-ről és X1-ről d

fák
A fák nemcsak azért fontosak, mert különféle tudásterületeken alkalmazzák őket, hanem magában a gráfelméletben betöltött különleges helyzetük miatt is. Ez utóbbi a fa szerkezetének rendkívüli egyszerűségének köszönhető

Minden nem triviális fának van legalább két lelógó csúcsa
Bizonyítás Tekintsünk egy G fát (V, E). A fa egy összefüggő gráf, ezért

Tétel
Egy szabad fa középpontja egy csúcsból vagy két szomszédos csúcsból áll: Z (G) = 0 & k (G) = 1 → C (G) = K1

Orientált, rendezett és bináris fák
Az orientált (rendezett) fák hierarchikus kapcsolatok absztrakciói, amelyek nagyon gyakoriak mind a gyakorlati életben, mind a matematikában és a programozásban. Fa (orient

Bizonyíték
1. Minden ív egy csomópontba tartozik. A 9.2.1 definíció 2. pontjából a következőket kapjuk: v

Rendezett fák
A T1, ..., Tk halmazok egy sorrend ekvivalens definíciójában részfák. Ha a T1 részfák relatív sorrendje, ...,

Bináris fák
A bináris (vagy bináris) fa a csomópontok véges halmaza, amely vagy üres, vagy egy gyökérből és két diszjunkt bináris fából áll – a bal és a jobb oldalon. Bináris fa nem jav

Ingyenes kilátás a fákra
A fák ábrázolásához ugyanazokat a technikákat használhatja, mint az általános gráfok ábrázolásakor – szomszédsági és előfordulási mátrixok, szomszédsági listák és egyebek. De a d speciális tulajdonságait felhasználva

Vége a
Indoklás A Prüfer-kód valóban egy ingyenes faábrázolás. Ennek ellenőrzésére megmutatjuk, hogy ha T "fa

Bináris fa ábrázolása
Bármely szabad fa orientálható úgy, hogy az egyik csomópontot gyökérnek jelöljük ki. Bármely rendelési fa tetszőlegesen megrendelhető. A rendezett rend egy csomópontjának (testvéreinek) leszármazottai számára a rokon

Alapvető logikai függvények
Jelöljük E2 = (0, 1) - két számból álló halmazt. A 0 és 1 számok alapvetőek a diszkrét matracban

Boole-függvény
Az x1, x2,…, xn argumentumból álló logikai függvény egy f függvény a halmaz n-edik hatványából

Kételemű Boole-algebra
Tekintsük a Bo = (0,1) halmazt, és definiáljunk rajta műveleteket az ist táblázatok szerint

Logikai függvénytáblázatok
Egy n változóból álló logikai függvény adható meg egy két oszlopból és 2n sorból álló táblázattal. Az első oszlop felsorolja a B összes halmazát

F5 - ismételje meg az y-t
f6 - modulo 2 összege f7

A műveletek sorrendje
Ha egy összetett kifejezésben nincs zárójel, akkor a műveleteket a következő sorrendben kell végrehajtani: konjunkció, diszjunkció, implikáció, ekvivalencia, tagadás. Elrendezési egyezmények Shannon első tétele
Az eredeti φ képlettel egyenértékű SDNF és SKNF megtalálásának problémájának megoldásához először figyelembe vesszük az f (x1, x2) Boole-függvény kiterjesztését

Shannon második tétele
A kettősség elve alapján a Boole-algebrákra a következő tétel igaz: 6.4.3. (második Shannon-tétel). Bármely f logikai függvény (x1, x2, ...

Funkcionális teljesség
Tétel (a funkcionális teljességről). Bármely f logikai függvényhez létezik egy φ képlet, amely az f függvényt reprezentálja

Algoritmus az sdnf megtalálásához
Az SDNF megtalálásához ezt a képletet először DNF-re kell redukálni, majd a kötőszavait az egység összetevőivé kell átalakítani a következő műveletekkel: a) ha a kötőszó tartalmaz néhány

Quine módszere
Tekintsük Quine módszerét egy adott Boole-függvényt reprezentáló MDNF megkeresésére. Határozzuk meg a következő három műveletet: - teljes ragasztási művelet -

Logikai függvények kanonikus ábrázolása
A logikai (képlet-) függvények kanonikus formái olyan kifejezések, amelyek egy szabványos logikai formulával rendelkeznek, így egyedileg reprezentálnak egy logikai függvényt. Az algebrákban

Boole-függvényrendszerek
Legyen adott f (g1, g2, ..., gm) és g1 (x1, x2, ..., xn), g2 (x1) logikai függvények

Zhegalkin alapon
Példa Tekintsük a rendszert. Teljes, mivel a szabványos alapból származó bármely függvény keresztül fejeződik ki

Post tétele
Post tétele szükséges és elégséges feltételeket támaszt egy Boole-függvényrendszer teljességéhez. (E.L. bejegyzés A matematikai logika kétértékű interaktív rendszerei. - Annals of Math. Stu

Bizonyíték
Szükség. Ellentmondás útján. Hadd u

Zhegalkin algebra
A modulo 2 összeg, a konjunkció, valamint a 0 és 1 állandók funkcionálisan teljes rendszert alkotnak, azaz. alkotnak egy algebrát - a Zhegalkin-algebrát. A =

Propozíciós logika
A matematikai logika a természetes nyelv szintaxisának (forma) és szemantikájának (tartalmának) alapfogalmait tanulmányozza. Tekintsük a matematikai logika három fő kutatási területét – a logikát

Predikátum meghatározása
Legyenek X1, X2, ..., Xn tetszőleges változók. Ezeket a változókat tárgyváltozóknak nevezzük. Hagyja, hogy a változók halmaza Ön

Predikátumok alkalmazása az algebrában
Tekintsük azokat a predikátumokat, amelyekben csak egy változó szabad, amelyeket x-szel jelölünk, és tárgyaljuk a predikátumok használatát az algebrában. Tipikus példa

Boole predikátum algebra
Mivel a logikai műveletek alkalmazhatók predikátumokra, a Boole-algebra alaptörvényei érvényesek rájuk. Tétel. (A logikai műveletek tulajdonságai predikátumokra). Mn

F↔G = (F → G) (G → F), F → G = nem FG
2. Használja a törvényt ne F = F, de Morgan törvényei: nem (F

Predikátumok számítása
A predikátumszámítást elsőrendű elméleteknek is nevezik. Az állítmányszámításban, akárcsak a propozíciószámításban, az első helyen az eldönthetőség problémája áll.

Követés és egyenértékűség
A Q2 állításforma a Q1 állításformából következik, ha a Q1 → Q2 implikáció valódi magasra változik

Elfogadott megnevezések
Szimbólumok "nem több, mint rend". Ha összehasonlítjuk két f (n) és g (n) függvény növekedési sebességét (nemnegatív értékekkel), a következők nagyon kényelmesek

Meta megjelölések
Szimbólumok Tartalom Példa VAGY

Tényező beállítása

Készletek.

A részleges sorrendű reláció egy x halmazon egy bináris reláció, amely antiszimmetrikus, reflexív és tranzitív, és jelölése
párként:

A bináris attitűdöt toleranciának nevezzük, ha reflexív és szimmetrikus.

A bináris relációt kvázi-rendnek nevezzük, ha irreflexív, antiszimmetrikus és tranzitív (előrendelés).

A bináris relációt szigorú sorrendnek nevezzük, ha reflexív és tranzitív.

Egy enáris algebrai művelet egy M halmazon függvény

- unáris működés;

- bináris művelet;

- hármas működés.

Bináris algebrai művelet -

- művelet, amely az M halmazból minden egyes rendezett párhoz hozzárendeli az M halmaz valamely elemét.

Tulajdonságok:

1) cserélhetőség:

2) asszociativitás:

Semleges elem

M értéket állít be egy bináris algebrai művelethez

Az elem neve:

• 
  Tényező sokaság- ennek ekvivalenciaosztályainak halmaza sokaság... A részleges rendelés bekapcsolva a sokaság x-et bináris relációnak nevezzük...


• 
  Következő kérdés. " Tényező sokaság. Tényező sokaság- összesített. Multiplikatív és additív formák.


• 
  Tényező sokaság- összesített.
  Sok- bizonyos és különböző tárgyak egymás közötti halmaza, amelyek összességében elképzelhetők.


• 
  A multiplikatív függvény - és ... további részletek." Tényező sokaság. Tényező sokaság- ennek ekvivalenciaosztályainak halmaza sokaság.


• 
  A valóságban a gyártási folyamat bonyolultabb, terméke a felhasználás eredménye sokaság tényezőket.


• 
  A vezetői döntések minősége attól függ sokaság tényezőket, amelyek közül a legjelentősebb az n.


• 
  A tőkebevonási döntések optimalizálása kutatási folyamat sokaság tényezőket befolyásolja a várt eredményeket...