Szerkesztő:Gubbubu/Halmazrendszerek geometriája/1

. feladat megoldása|link=Halmazrendszerek geometriája/Feladatok#Diszkrét intervallumok|linkszöveg=Vissza}}

Tartalomjegyzék

Feladatok

- megoldásokkal -

E lapon egy kidolgozottfeladat-gyűjtemény található a Halmazrendszerek geometriája c. könyvhöz.

1. fej. (Halmazrendszerek és hipergráfok)

Diszkrét intervallumok

1. Fejezzük az alábbi halmazokat diszkrét intervallumok és véges sok halmazműveleti jel (unió, metszet, különbség) segítségével (N használata is megengedett):
   1. {2, 3, 4, 5, 6, ...}
   2. {10, 11, 12, ..., 20}
   3. {2, 4, 6, 8, 10, 12}
2. Bizonyítsuk be (pl. mat.-i indukcióval):
   1. 0,n = {x∈N | 0≤x≤n}; azaz hogy tetszőleges x∈N esetén x∈0,n akkor és csak akkor igaz, ha 0≤x≤n;
   2. hogy 0,n⊆0,m akkor és csak akkor teljesül, ha n≤m.

Megoldások:

1. 1. fa.
   1. Egyszerű megoldás: N-0,1
   2. A legegyszerűbb megoldás: 1,20-1,9
   3. Egyszerű megoldások: 1,13-{3,5,7,9,11} de lehet trükközni is: 1,12-2·0,5+1
2. 2. fa.
   1. Az n-re vonatkozó teljes indukcióval bizonyítunk. 1). Ha n=0, akkor x∈0,0 := {0} azt jelenti, x=0, azaz valóban 0≤x≤0. 2). Ha valamely n-re igaz az állítás, hogy „x∈0,n akkor és csak akkor, ha 0≤x≤n”, enek megfelelője n+1-re: „x∈0,n+1 akkor és csak akkor, ha 0≤x≤n+1”, ami ugyanaz, mint „x∈0,n∪{n+1} akkor és csak akkor, ha 0≤x≤n+1”. Ez igaz: Ha - az indukciós feltevést kihasználva - 2a). x∈0,n∪{n+1} = {x∈N | 0≤x≤n}∪{n+1} := A, akkor x∈{x∈N | 0≤x≤n+1} = A, ugyanis ha x az unió első tagjának eleme, azaz 0≤x≤n, akkor n≤n+1 és ≤ tranzitivitása miatt 0≤x≤n+1 is (x≤n és n≤n+1 következménye x≤n+1) ha pedig x az unió második tagjának eleme, azaz x=n+1, ekkor x=n+1≤n+1 miatt igaz 0≤x≤n+1 (≤ ún. reflexív tulajdonsága). 2b). Ha pedig, fordítva, 0≤x≤n+1, akkor vagy x = n+1, ez esetben x∈0,n+1 = 0,n∪{n+1} (az unió második tagjában van az x), vagy pedig x<n+1, azaz x≤n (más lehetőség nincs, a ≤ reláció ún. gyanis ha x az unió első tagjának eleme, azaz 0≤x≤n, akkor n≤n+1 és ≤ trichotom tulajdonsága miatt), és az indukciós feltevést kihasználva ekkor x∈0,n ⊆ 0,n∪{n+1} = 0,n+1, azaz mindkét megvizsgált és minden lehetőséget kimerítő esetben x∈0,n+1.
   2. Az előző tételből következik. x∈0,n = {z | 0≤z≤n}, és x∈0,m = {z | 0≤z≤m}, ha az első halmaz része a másodiknak, akkor az első halmaz „utolsó” eleme, n (is), a másodikba esik, azaz 0≤n≤m, ha fordítva, ez utóbbi egyenlőtlenség teljesül, akkor n a második halmazba esik, és ekkor a ≤ tranzitivitása miatt minden nála kisebb természetes szám is, azaz az egész 0,n halmaz. Q.E.D.

Megoldás: Halmazrendszerek geometriája/1#Diszkrét intervallumok

Sorbarendezések

1. Bizonyítsuk be, hogy véges halmaz minden részhalmaza is véges! (megjegyzés: nem nehéz, de annyira idegölős, favágós jellegű a célzott korosztály számára, hogy valószínűleg halálfejetr kap) Megoldás: Legyen A véges, ekkor létezik olyan n,f hogy A-t f bijektíven képezi 1,n-re. Legyen R⊆A, ekkor van egy legkisebb m, hogy m<n, de f(m) nem eleme R-nak.

Részhalmaz karakterisztikus függvénye

1. Bizonyítsuk, hogy ha egy halmaz hatványhalmazának (részhalmazai halmazának) minden eleméhez hozzárendeljük a halmaz felett értelmezett karakterisztikus függvényét, akkor egy bijektív leképezést kapunk!

Részhalmaz karakterisztikus vektora

1. Írjuk fel az U = {a,b,c,d} halmaz összes részhalmazainak karakterisztikus vektorait, ha a sorbarendezés (d, b, a, c}! Megoldás ...

Hatványhalmaz

1. Ne örülj, lesz.

Hipergráfok

1. Mekkora egy véges U halmaz feletti nem üres hipergráfok száma?
2. Mekkora egy véges U halmaz feletti olyan hipergráfok száma, amelyek nem tartalmazzák élként az üres halmazt? Megoldás: ld. később

Gyakorló feladatok

1. Bizonyítsuk be, hogy egy véges, legalább két elemű U halmazt véve, az olyan U feletti hipergráfok száma, melyek minden éle két elemű, négyzetszám!
2. Bizonyítsuk be, hogy véges, legalább n elemű U halmazt véve, az olyan U feletti hipergráfok száma, melyeknek minden éle n elemű, n-edik hatvány! (megjegyzés: üres hipergráfot is megengedünk).
3. Adjunk képletet egy véges, n elemű U halmaz azon hipergráfjainak számára, melyek minden éle v-elemű (v∈0,n)
4. Legyen az U feletti H hipergráf Boole-vektora b(H), a J hipergráfé pedig b(J). (Milyen) halmazművelettel keletkezik a b^-1(b(H)@b(J)) hipergráf a H,J hipergráfokból, ha @ a modulo 2 összeadás, a szorzás, a kivonás, a minimumképzés, a maximumképzés?
5. Hogyan néz ki egy U feletti hipergráfnak az U hatványhalmazára vonatkozó komplementerének Boole-vektora?

További feladatok

1. Egy, az u 1,2,...,n változókon értelmezett n-változós f logikai függvény hipergráfjának nevezzük az {u_i | i=1,2,...,n} halmaz azon halmazcsaládját, amely U pontosan azon R részhalmazait tartalmazza, melyekre χ(R,u_i)=f(u_i) minden i-re teljesül. Mit jelent a logikai függvény hipergráfjára nézve az, hogy az u₁ változó fiktív (fiktívnek nevezünk egy független függvényváltozót, hogyha a többi változó rögzített értéke mellett értéke bárhogy is változik, a függvényérték állandó marad)?

Nehezebb feladatok

1. Általánosítsuk a Boole-vektor fogalmát végtelen halmazokra! A jólrendezési tétel használata megengedett.

Rendszám

1. Bizonyítsuk be, hogy adott U halmaz felett az O_U,ν(...) leképezés kölcsönösen egyértelmű megfeleltetést létesít az U feletti hipergráfok {U}×℘(℘(U)) halmaza és a ${\mbox{ }}_{\underline {0,2^{2^{n}}-1}}$ diszkrét intervallum között;

Valószínűségszámítást kedvelőknek:

1. Véletlenszerűen választunk két n-edrendű hipergráfot (ugyanabból az U halmazból). Mekkora a valószínűsége, hogy a nagyobb rendszámú hipergráf több elemet fog tartalmazni?
2. Írjuk fel annak az eseménysorozatnak a valószínűségeloszlását (ha lehet, adjunk képletet), hogy egy k rendszámú és n-edrendű hipergráf (n rögzített, k nem) több elemet tartalmaz, mint az összes őt megelőző rendszámú! Készítsünk grafikont!

Számelméletkedvelőknek

1. Feladatok számelméletkedvelőknek:
   1. Válasszunk egy (lehetőleg háromnál nagyobb) n természetes számot, és egy n elemű U halmazt. Hogyan jellemezhetőek szerkezetileg azok az U feletti hipergráfok, amelyekre igaz, hogy rendszámuk többszöröse valamely Fermat-számnak?
   2. Lássuk be, hogy adott U halmaz és ν sorbarendezés mellett a ${\mbox{ }}_{P_{U,\nu }\left({\mathcal {H}}\right):\wp \left(\wp \left(U\right)\right)\to {\underline {1,2^{2^{n}}}};}$ ${\mbox{ }}_{P_{U,\nu }\left({\mathcal {H}}\right)\ :=\ \log _{2}\left(\prod _{k=0}^{2^{|U|}}2^{k}\cdot \chi _{\mathcal {H}}\left(o_{U,\nu }^{-1}\left(\mathbf {k} \right)\right)\right)}$ függvény nem jelent bijektív leképezést!
   3. Mi az értékkészlete a fenti leképezésnek?

---

Eztnetöröldmígametárólnemválaszolnak

Dear Meta User[1]! This edit link doesn't work :

Sectiontitle

---

---

Lap teteje

---