Diskreetti matematiikka, syksy 2010
Harjoitus 4 (7.-8.10., to 16-18 M107, pe 12-14 M107)
Tiistaina 5.10. ei liikuntapäivän takia ole luentoa.
 


  1. Olkoon X = {a, b, c, d, e} ja Y = {1, 2, 3, 4, 5}. Mitkä seuraavista relaatioista ovat funktioita, mitkä niistä injektioita, surjektioita, bijektioita? Määritä bijektioiden käänteiskuvaukset.
    2. a)  F : = {(a,4),(b,1),(c,3),(d,1),(e,3),(e,4)} 
    b)  G : = {(a,2),(b,1),(c,3),(d,5),(e,4)} 
    c)  H : = {(a,5),(b,2),(c,3),(e,4)} 
    d)  I : = {(a,5),(b,1),(c,3),(d,1),(e,4)} 
  2. Olkoon f : X ® Y kuvaus, A1, A2 Í X ja B1, B2 Í Y. Osoita, että
    3. a) f(A1 ÇA2) Í f(A1) Ç f(A2),
    b) f-1(B1 È B2) = f-1(B1) È f-1(B2).
    Voiko kohdassa a) inkluusio olla aito?
  3. Olkoon F: X ® Y injektio ja G: F(X) ® X surjektio. Mitä arvelet ilmauksesta G °F, siis mitä ominaisuuksia sillä on?
  4. Olkoon n Î N. Osoita, että minkä tahansa n+1:n luonnollisen luvun joukossa on ainakin kaksi, joiden erotus on jaollinen luvulla n.
  5. Oletetaan, että ihmisten välinen tuttavuus on molemminpuolista. Osoita, että jokaisessa n ³ 2 henkilön joukossa on ainakin kaksi, joilla on yhtä monta tuttavaa.
  6. Osoita, että relaatio R Í X×X on transitiivinen jos ja vain jos R ° R Í R.
  7. Olkoon X äärellinen joukko ja R Í X×X. Miten sen matriisista näkee, onko relaatio
    8. a) refleksiivinen
    b) symmetrinen
    c) antisymmetrinen
    d) transitiivinen
    e) täysi
    f) R-1° R refleksiivinen?
  8. Olkoon relaation R matriisi
    9. MR =  æ
    ç
    ç
    ç
    ç
    ç
    è
    1 
    0 
    1 
    0 
    0 
    1 
    0 
    0 
    1 
    1 
    1 
    0 
    0 
    0 
    1 
    1
    		ö
    ÷
    ÷
    ÷
    ÷
    ÷
    ø    		 .
    Onko relaatio
    a) refleksiivinen
    b) symmetrinen
    c) antisymmetrinen
    d) transitiivinen
    e) täysi
    f) R-1° R refleksiivinen?

File translated from TEX by TTH, version 3.80.
On 29 Sep 2010, 11:24.