Diskreetti matematiikka, syksy 2010
Harjoitus 7 (4.-5.11., to 16-18 M107, pe 12-14 M107)
  1. Olkoot (E, £ ) ja (F, \preceq) epätyhjiä järjestettyjä joukkoja. Määritellään joukossa E×F relaatio L seuraavasti:
    2. [ (x,y) L (x¢,y¢) ]    Û     [ (x < x¢) Ú((x = x¢) Ù(y \preceq y¢))  ]
    Osoita, että L on osittainen järjestys joukossa E×F.
    Kyseessä on nk. leksikografinen järjestys eli aakkosjärjestys.
    Jos järjestykset £ ja \preceq ovat täydellisiä, niin onko myös L täydellinen järjestys?
  2. Osoita, että "olla yhtä mahtava kuin" on ekvivalenssirelaatio minkä tahansa perusjoukon potenssijoukossa.

    3. Onko relaatio "olla korkeintaan yhtä mahtava kuin" puolestaan osittainen järjestys? Jos ei, niin miten siitä saataisiin sellainen?
  3. Muodosta bijektio
    4. a) joukkojen N ja Z
    b) joukkojen N ja Q
    välille. Tämä todistaa kyseiset joukot yhtämahtaviksi.
    Vihje. a) Ajattele joukkoja lukusuoralla.
    b) Asettele (positiiviset) rationaaliluvut (päättymättömään) taulukkomuotoon (Cantor).
  4. Olkoot A ja B Í X. Ilmoita joukkojen A ja B karakterististen funktioiden avulla
    5. a) joukon A\B karakteristinen funktio.
    b) joukon (A\B)È(B\A) karakteristinen funktio.
  5. Yliopiston ylioppilaskunnan syyskekkerit pidettiin vanhempien ihmisten suosiossa olevassa tanssipaikassa. Yhteensä paikalla oli 100 osallistujaa, joista 60 oli miehiä ja loput naisia. Osallistujista alle kolmekymppisiä oli 30, joista 10 miehiä. Lisäksi tiedetään, että osallistujista vain 40 oli opiskelijoita, näistä 20 oli miehiä, 15 alle kolmekymppisiä ja 5 alle kolmekymppisiä miehiä. Kuinka monta osallistujista oli
    6. a) yli kolmekymppisiä naisia?
    b) yli kolmekymppisiä ei-opiskelijanaisia?
  6. Kuinka monessa luvuista 1000, 1001, ¼ , 9999 on peräkkäin kaksi samaa numeroa?
  7. Todista: Jos #X = n, niin X voidaan jakaa kahdeksi ekvivalenssiluokaksi 2n-1 - 1 eri tavalla.
    8. Vihje: Induktiotodistus joukon alkiomäärän suhteen.

File translated from TEX by TTH, version 3.80.
On 27 Oct 2010, 11:58.