Matematiikan perusteita kieliteknologian opiskelijoille

Tehtäviä - Algebraa

  1. Määrittele relaatio aito osajoukko mahdollisimman monella eri tavalla.
  2. Päteekö refleksiivisyys, antisymmetrisyys ja transitiivisuus aito osajoukko -relaatiolle?
  3. Symmetrinen erotus
    Joukkojen A ja B symmetrinen erotus A+B on joukko, jonka alkiot kuuluvat joko A:han tai B:hen, muttei molempiin. Piirrä symmetristä erotusta kuvaava Venn-diagrammi. Miten määrittelisit symmetrisen erotuksen? Entä miten esittäisit sen muiden joukko-opin operaatioiden avulla? Keksitkö useampia esityksiä? Osoita ne yhtäpitäviksi.
  4. Komplementti
    a) Muodosta joukon { x >= 6 } komplementti perusjoukon N suhteen.
    b) Muodosta joukon { 2 <= x < 4 } komplementti perusjoukon R+ suhteen.
  5. Grellingin paradoksi
    Sanoja, jotka kuvaavat oikein itseään, kutsutaan autoloogisiksi, Esimerkkejä autoloogisista sanoista olisivat 'suomea' ja 'lyhyt'. Sanoja, jotka eivät kuvaa oikein itseään, kutsutaan heteroloogisiksi. Esimerkkejä tällaisista olisivat 'ruotsia' ja 'pitkä'. Onko sana 'heterolooginen' autolooginen vai heterolooginen? Voitko verrata Grellingin paradoksia johonkin toiseen tunnettuun paradoksiin?
  6. Lauseiden ja kielten mahtavuus
    Käytettävissä on äärellinen määrä merkkejä (aakkoset) M. Lause L on äärellisen pituinen jono joukon M merkkejä. Onko kaikkien mahdollisten lauseiden lukumäärä numeroituva vai ylinumeroituva? Kieli K koostuu siihen kuuluvista mahdollisista lauseista. Onko kaikkien mahdollisten kielten lukumäärä numeroituva vai ylinumeroituva?
  7. Tutki relaatioiden L ('lapsi'), J ('jälkeläinen'), S ('sukulainen'), A ('asuu samassa ruokakunnassa') ja V ('vähintään yhtä vanha') omiaisuuksia. Selvitä erityisesti relaation refleksiivisyys, irrefleksiivisyys, symmetrisyys, anisymmetrisyys, transitiivisuus ja vertailullisuus. Perustele ja esitä tulokset vaikka taulukossa. Ovatko kaikki kohdat ongelmattomia?