Szerkesztő:Gubbubu/Halmazrendszerek geometriája/1

A Wikikönyvekből, a szabad elektronikus könyvtárból.
 Halmazrendszerek geometriája/1. feladat megoldása 
[Halmazrendszerek geometriája/Feladatok#Diszkrét intervallumok Halmazrendszerek geometriája/Feladatok#Diszkrét intervallumok ]
{{{Szöveg}}}



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)[szerkesztés]

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 = {xN | 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,n0,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} = {xN | 0≤x≤n}∪{n+1} := A, akkor x∈{xN | 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,n0,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
Boole-vektor


Gyakorló feladatok[szerkesztés]
  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! [1]
  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) [2]
  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[szerkesztés]
  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 {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]
  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 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]
  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[szerkesztés]
  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 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[szerkesztés]

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

Sectiontitle[szerkesztés]



Lap teteje

  1. Gráfelméleti nyelven: Legalább két elemű halmaz felett mindig négyzetszámnyi sok gráf található.
  2. Ezek az ún. n-edrendű v-uniform hipergráfok.