Diskreetti matematiikka/Joukko-oppi

Wikikirjastosta

Ongelmia ratkaistaessa täytyy usein käsitellä matemaattisia kohteita. Esimerkiksi jos sinulta kysytään, kuinka paljon on kaksi kertaa kolme, saatat osoittaa kuutosta. Kun esität useita kohteita samalla kertaa, osoitat kohteiden joukkoa. Jos haluat esittää neljä ensimmäistä numeroa, saatat kirjoittaa:

Koska kaikki kolme esitystapaa osoittavat samoihin matemattisiin kohteisiin, ne ovat kaikki sama joukko. Huomaa, että joukot pitävät sisällään vain sen, mihin osoitetaan, ei sitä kuinka monta kertaa johonkin osoitetaan tai että missä järjestyksessä.

Joukkojen suhteet[muokkaa | muokkaa wikitekstiä]

On olemassa monia usein käytettyjä lauseita joukoista:

  • Alkio on joukossa; joukko osoittaa siihen
  • Kaksi joukkoa ovat yhtenevät; molemmat osoittavat samoihin alkioihin
  • Joukko on toisen joukon ylijoukko; se osoittaa kaikkiin toisen joukon alkioihin, ehkä useampaankin
  • Joukko on on toisen joukon aito ylijoukko; se osoittaa kaikkiin toisen joukon alkioihin, mutta aina myös muihin sen lisäksi
  • Osajoukko ja aito osajoukko -suhteet ovat vastakkaiset verrattuna ylijoukko ja aitoylijoukko -suhteisiin

Symboli ⊂ näyttää ja toimii samalla tavalla kuin <. Symbolit ∈ ja < näyttävät samanlaisilta, mutta älä kuitenkaan sekoita niitä keskenään.

Joukko-operaatiot[muokkaa | muokkaa wikitekstiä]

On olemassa monta tapaa yhdistää kaksi joukkoa kolmanneksi joukoksi:

  • Voimme muodostaa yhdistejoukon
  • Voimme muodostaa leikkausjoukon
  • Voimme muodostaa erotusjoukon

∪ symboli näyttää kupilta, joka voi pitää sisällään paljon asioita. ∩ symboli näyttää ylitsevuotavalta kupilta, joka ei pysty pitämään sisällään paljon asioita. Älä sekoita symboleita keskenään.

Joukot omine symboleineen[muokkaa | muokkaa wikitekstiä]

Monia joukkoja käytetään niin usein, että niille on annettu omat erityiset symbolit.

  • Tyhjä joukko ilmaisee, ettemme osoita mihinkään objekteihin; tällainen joukko ei pidä sisällään yhtään objektia
  • Luonnollisten lukujen joukko
  • Kokonaislukujen joukko
  • Murtolukujen joukko
  • Reaalilukujen joukko
  • Kompleksilukujen joukko

Vain silloin kun matemaattinen lause on omalla rivillään, käytämme liitutaulupaksunnosta (). Muutoin käytämme tavallista paksunnosta (N).

Set comprehension[muokkaa | muokkaa wikitekstiä]

Kun esitämme joukon, voimme tehdä sen kirjoittamalla esiin kaikki joukon alkiot. Jos kuitenkin haluamme esittää äärettömän joukon, niin jokaisen alkion kirjoittaminen voi olla hieman ongelmallista. Voimme ratkaista ongelman esittämällä joukon set comprehension muodossa. Joukko esitetään tässä muodossa esitämällä sen mukana sääntö ja suhde indeksijoukkoon I. Se on;

jossa R on x2=0, tai x=3t kokonaisluvulle t. Tällaista sääntöä kutsutaan x:n boolen predikaatiksi, ja voimme lukea lauseen: S on sellainen joukko kaikille x I:ssä, että x:n neliö on nolla.

Esim. parillisten lukujen joukko:

Toisen asteen yhtälön ratkaisujen joukko:

Huomaa, että:

on kokonaan eri joukko!

Venn-diagrammit[muokkaa | muokkaa wikitekstiä]

Venn-diagrammi on joukkojen graafinen esitystapa, jolla pyritään havainnollistamaan joukkoja ja niiden välisiä suhteita.

Leikkaus
A:n ja B:n leikkaus
Yhdiste eli unioni
A:n ja B:n yhdiste
Osajoukko
A on B:n osajoukko


  • Ei päällekkäisyyttä, tai joukon A ja B yhdistejoukko on tyhjä joukko.

Perusjoukot ja komplementit[muokkaa | muokkaa wikitekstiä]

Perusjoukot[muokkaa | muokkaa wikitekstiä]

Kun työskentelemme joukkojen kanssa, on käytännöllistä ajatella toista, laajempaa joukkoa, jota kutsumme perusjoukoksi, ja sitten työskennellä tämän joukon sisällä. Esim. jos käsittelemme joukkoja {-1,0,1} ja {-3,-1,1,3}, niin on käytännöllistä työskennellä joukossa Z. Kun työskentelemme tällaisessa laajemmassa joukossa, kuten Z, sanomme että Z on perusjoukko, ja oletamme kaikkien joukkojen olevan Z:n osajoukkoja.

Merkitsemme perusjoukkoa :lla, kuitenkin on helpompi kirjoittaa vain E.

Komplementit[muokkaa | muokkaa wikitekstiä]

Olkoon joukko A perusjoukon E osajoukko. Määrittelemme A:n komplementin olevan kaikki E:ssä olevat alkiot, jotka eivät ole A:ssa. Toisin sanottuna A:n komplementti on:

A:n komplementti esitetään merkitsemällä , tai .

Harjoituksia[muokkaa | muokkaa wikitekstiä]

Koeta vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

  1. Onko ?
  2. Onko ?
  3. Onko ?
  4. Oikein vai väärin? Jos väärin, anna esimerkki alkiosta, joka kuuluu ensimmäiseen, muttei toiseen joukkoon.
  5. Oikein vai väärin? Jos väärin, anna esimerkki alkiosta, joka kuuluu ensimmäiseen, muttei toiseen joukkoon.
  6. Onko ?
  7. Onko ?
  8. Kirjoita joukon
    viisi alkiota
  9. Kirjoita
    alkiot.
  10. Etsi perusjoukko, siten että nämä joukot ovat sen osajoukkoja:

  1. Kun on annettu, etsi A', siten että .

Vastaukset[muokkaa | muokkaa wikitekstiä]

2. Ei, on irrationaalinen, ei rationaaliluku
4.1. Kyllä.
4.2. Ei. Esimerkiksi 1/2 kuuluu rationaalilukuihin mutta ei kokonaislukuihin.
6. Kyllä.
8. Viisi alkiota ovat esimerkiksi {3,5,7,9,11}.
10.

Muita konsepteja[muokkaa | muokkaa wikitekstiä]

Mainitut ideat eivät ole ainoita, joita kohtaamme joukko-opissa. Näitä keskeisiä aiheita ei välttämättä ole erityisesti painotettu tässä lähtötason kurssissa, mutta on tärkeä osata ne, sillä niitä tarvitaan myöhemmin abstraktissa algebrassa ja muilla aloilla.

Voidaan ohittaa.

Potenssijoukko[muokkaa | muokkaa wikitekstiä]

Joukon S potenssijoukko, merkittynä P(S), on kaikkien S:n osajoukkojen joukko (sisältäen myös itse joukon S). NB: Tyhjä joukko on kaikkien joukkojen osajoukko.

Esim. P({0,1})={{},{0},{1},{0,1}}

Mahtavuus[muokkaa | muokkaa wikitekstiä]

Joukon S mahtavuus, merkittynä |S|, on yksinkertaisesti joukon alkioiden lukumäärä. Eli |{a,b,c,d}|=4, jne. Joukon mahtavuuden ei tarvitse olla äärellinen; joidenkin joukkojen mahtavuus on ääretön.

Potenssijoukon mahtavuus[muokkaa | muokkaa wikitekstiä]

Jos P(S)=T, niin |T|=2|S|.

Harjoituksia[muokkaa | muokkaa wikitekstiä]

Koita vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

  1. |{1,2,3,4,5,6,7,8,9,0}|
  2. |P({1,2,3})|
  3. P({0,1,2})
  4. P({1})
Vastaukset[muokkaa | muokkaa wikitekstiä]
2. 23=8
4. {{},{1}}

Joukkojen identtisyys[muokkaa | muokkaa wikitekstiä]

yhdiste- ja leikkausoperaattoria käyttämällä voimme muodostaa sääntöjä, jotka yksinkertaistavat joukkojen käsittelyä.

Esim.

Kuinka voimme yksinkertaistaa ilmaisua?

Useat seuraavista joukkojen identtisyyksistä ovat samankaltaisia tavallisessa matematiikassa, kuten liitännäisyyslaki, osittelulaki, jne.

Vaihdannaisuus[muokkaa | muokkaa wikitekstiä]

Liitännäisyys[muokkaa | muokkaa wikitekstiä]

Ositeltavuus[muokkaa | muokkaa wikitekstiä]

Identtisyys[muokkaa | muokkaa wikitekstiä]

Idempotenssi[muokkaa | muokkaa wikitekstiä]

Dominointi[muokkaa | muokkaa wikitekstiä]

Kaksoiskomplementti[muokkaa | muokkaa wikitekstiä]

Komplementit yhdisteet ja leikkaukset[muokkaa | muokkaa wikitekstiä]

De Morganin lait[muokkaa | muokkaa wikitekstiä]

Nämä ovat lakeja pikemmin kuin aksioomia, koska voimme todistaa ne toisista aksioomista.

Muista, että yllä olevat kaksi joukkoa A ja B ovat yhtenevät, jos ja .

Todistus.

1)

Otetaan satunnainen alkio . Emme tiedä mitään x:stä, se voi olla numero, funktio tai elefantti. Ainoa asia minkä tiedämme x:stä, on että

joten

koska tätä komplementti tarkoittaa. Siten

and

aukaisemalla yhdiste. Soveltamalla komplementteja uudestaan saamme

and

Lopuksi, jos jotain on kahdessa joukossa, sen täytyy olla niiden yhdisteessä, joten

Joten, otimme minkä tahansa alkion :, niin se on aina , joten määritelmän mukaan


2) :

Toimimme samanlaisella tavalla. Ensiksi, otamme satunnaisen alkion ensimmäisestä joukosta,

Käyttäen tietoamme yhdisteistä, se tarkoittaa

ja

Nyt, käyttäen komplementteja

ja

Jos jokin ei ole A:ssa, eikä B:ssä, se ei voi olla niiden yhdiste, joten

Ja lopulta

Joten, nyt meillä on molemmat ja . Näin todistimme ensimmäisen De Morganin laeista:

Toisen puolen lukija voi todistaa itse harjoituksena.

Joukkojen erotus[muokkaa | muokkaa wikitekstiä]

Joukkojen A ja B erotus on se joukko, johon kuuluvat ne joukon A alkiot jotka eivät kuulu joukkoon B.

Dualisointi[muokkaa | muokkaa wikitekstiä]

Huomaa, että yllä olevista säännöistä sinun ei tarvitse muistaa koko taulukkoa. Itse asiassa sinun tarvitsee muistaa vain puolet taulukosta ja voit vaihtaa ∪:in ∩:iin ja toisinpäin. Näin voi kuitenkin menetellä vain poikkeustapauksissa.

Tämä on tärkeä ominaisuus, ja sanommekin, että jokaista yhdisteitä koskevaa sääntöä vastaa vastaavan leikkaussäännön duaali. Ominaisuutta voidaan käyttää joukkojen indenttisyyslakien muistamiseen.

Dualisointi liittyy Boolen algebran aksioomiin. Katso Diskreetti matematiikka:Boolen algebra.

Harjoituksia[muokkaa | muokkaa wikitekstiä]

Koeta vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

Vastaukset[muokkaa | muokkaa wikitekstiä]

2.
4.

Lisää joukko-operaatioista[muokkaa | muokkaa wikitekstiä]

Kahden joukon erotus[muokkaa | muokkaa wikitekstiä]

Joukko , luetaan A miinus B, sisältää kaikki joukon A alkiot, jotka eivät ole joukon B alkioita. Toisin sanoen:

Erotusta voidaan käyttää äärettömien joukkojen määrittelyssä, esim. kaikkien kokonaislukujen erisuuri kuin nolla joukko voidaan kirjoittaa: . On itsestään selvää, että ja

Suppea merkintä useammalle kuin kahdelle joukolle[muokkaa | muokkaa wikitekstiä]

Jos meillä on joukot , voimme esittää näiden joukkojen yleistetyn yhdisteen tai leikkauksen, ts. jonka voimme kirjoittaa lyhyesti

.

Samalla tavalla leikkauksille kirjoitamme:

.`

Karteesinen tulo[muokkaa | muokkaa wikitekstiä]

Karteesinen tulo on tärkeä konsepti, kun käsittelemme funktioita seuraavassa osiossa. Esittelemme peruskäsitteet ensiksi.

n-tuplat[muokkaa | muokkaa wikitekstiä]

n-tupla on samanlainen kuin joukko, mutta alkioiden järjestys on tärkeä. Kirjoitamme nämä järjestetyt joukot pyöreillä sulkeilla - ( ja ) aaltosulkeiden { ja } sijaan korostaaksemme, että alkiot ovat järjestyksessä. Ajattele pisteitä tasolla - (1,0) ei ole sama kuin (0,1), mutta jos kirjoitamme nämä joukoille varatuilla aaltosulkeilla, ne ovat. Esim.

mutta

Karteesinen tulo[muokkaa | muokkaa wikitekstiä]

Kahden joukon karteesinen tulo on joukko, joka sisältää kaikki kahden joukon alkioista tehdyt tuplat. Kahden joukon A ja B karteesinen tulo ilmaistaan A × B. Se on määritelty:

Ymmärtäminen voi olla helpompaa esimerkeistä:

On selvää, että joukkojen A ja B karteesisen tulon mahtavuus on:

Kahden joukon A ja B karteesinen tulo voidaan muodostaa tekemällä tuplat A:n ja B:n alkioista; Operaation voi kuvitella ruudukon tai taulukon muotoon: jos, esim. A = {0,1} ja B = {2,3}, ruudukko on

×A
01
B2 (0,2)(1,2)
3(0,3)(1,3)

Karteesinen tulo voidaan tuottaa myös useimmilla ohjelmointikielillä soveltaen kahta sisäkkäistä silmukkaa, tai suhteellisesta tietokannasta valitsemalla kahdesta taulukosta ilman, että selvittää mistä.


Harjoituksia[muokkaa | muokkaa wikitekstiä]

Koeta vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

  1. {2,3,4}×{1,3,4}
  2. {0,1}×{0,1}
  3. |{1,2,3}×{0}|
  4. |{1,1}×{2,3,4}|

Vastaukset[muokkaa | muokkaa wikitekstiä]

2. {(0,0),(0,1),(1,0),(1,1)}
4. 6

Russellin antinomia[muokkaa | muokkaa wikitekstiä]

Tarkastellaan luokkaa

Luokan A alkiot ovat joukkoja. Jos siis A olisi joukko, pitäisi A:n olla luokassa A. Mutta toisaalta tämä on ristiriidassa A:n määritelmän kanssa. Siten A on luokka, mutta ei joukko.

Tämän esimerkin avulla nähdään naiivin joukko-opin ja aksiomaattisen joukko-opin ero. Aksiomaattinen joukko-oppi pyrkii määrittelemään käsitteet täsmällisesti, jotta yllä olevan esimerkin kaltaisia paradoksaalisia tilanteita ei pääse syntymään.