Szerkesztő:Gubbubu/Halmazrendszerek geometriája/1
Megjelenés
Halmazrendszerek geometriája/1. feladat megoldása |
{{{Szöveg}}}
E lapon egy kidolgozottfeladat-gyűjtemény található a Halmazrendszerek geometriája c. könyvhöz. |
Diszkrét intervallumok
- 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):
- {2, 3, 4, 5, 6, ...}
- {10, 11, 12, ..., 20}
- {2, 4, 6, 8, 10, 12}
- Bizonyítsuk be (pl. mat.-i indukcióval):
- 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;
- hogy 0,n⊆0,m akkor és csak akkor teljesül, ha n≤m.
Megoldások:
- 1. fa.
- Egyszerű megoldás: N-0,1
- A legegyszerűbb megoldás: 1,20-1,9
- Egyszerű megoldások: 1,13-{3,5,7,9,11} de lehet trükközni is: 1,12-2·0,5+1
- 2. fa.
- 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.
- 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
- 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
- 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
- Í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
- Ne örülj, lesz.
Hipergráfok
- Mekkora egy véges U halmaz feletti nem üres hipergráfok száma?
- 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
Boole-vektor
Gyakorló feladatok
[szerkesztés]- 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! [1]
- 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).
- Adjunk képletet egy véges, n elemű U halmaz azon hipergráfjainak számára, melyek minden éle v-elemű (v∈0,n) [2]
- 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?
- Hogyan néz ki egy U feletti hipergráfnak az U hatványhalmazára vonatkozó komplementerének Boole-vektora?
További feladatok
[szerkesztés]- 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 {ui | i=1,2,...,n} halmaz azon halmazcsaládját, amely U pontosan azon R részhalmazait tartalmazza, melyekre χ(R,ui)=f(ui) minden i-re teljesül. Mit jelent a logikai függvény hipergráfjára nézve az, hogy az u1 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
[szerkesztés]- Általánosítsuk a Boole-vektor fogalmát végtelen halmazokra! A jólrendezési tétel használata megengedett.
Rendszám
- Bizonyítsuk be, hogy adott U halmaz felett az OU,ν(...) leképezés kölcsönösen egyértelmű megfeleltetést létesít az U feletti hipergráfok {U}×℘(℘(U)) halmaza és a diszkrét intervallum között;
Valószínűségszámítást kedvelőknek:
[szerkesztés]- 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?
- Í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
[szerkesztés]- Feladatok számelméletkedvelőknek:
- 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?
- Lássuk be, hogy adott U halmaz és ν sorbarendezés mellett a függvény nem jelent bijektív leképezést!
- Mi az értékkészlete a fenti leképezésnek?
Eztnetöröldmígametárólnemválaszolnak
[szerkesztés]Dear Meta User[1]! This edit link doesn't work :