Seuraava lukuSisällysluettelo

1 Logiikan ja joukko-opin alkeet

1.1 Logiikkaa

Tehtävä 1
Osoita totuusarvotauluja käyttäen, että implikaatio p ==> q voidaan kirjoittaa muotoon ¬p  \/ q, ts. että propositio (p ==> q) <==> (¬p  \/ q) on identtisesti tosi.


Tehtävä 2
Todista totuusarvotauluja käyttäen loogiset de Morganin lait:   a) ¬(p  \/ q) <==> (¬p  /\ ¬q),   b) ¬(p  /\ q) <==> (¬p  \/ ¬q).


Tehtävä 3
Todista totuusarvotaulua käyttäen konjunktiivinen distributiivisuus: [p  /\ (q  \/ r)] <==> [(p  /\ q)  \/ (p  /\ r)].


Tehtävä 4
Lausu propositiot p  /\ q ja p  \/ q käyttäen yksinomaan negaatiota ja implikaatiota (mutta ei konjunktiota tai disjunktiota).

Vastaus


Tehtävä 5
Looginen NAND-operaatio p|q määritellään totuusarvotaululla

  p   q   p|q

  1   1   0
  1   0   1
  0   1   1
  0   0   1

Osoita:   a) p|p <==> ¬p,   b) (p|p)|(q|q) <==> p  \/ q,   c) (p|q)|(p|q) <==> p  /\ q.


Tehtävä 6
Mitkä seuraavista reaalilukua x koskevista väittämistä ovat tosia, mitkä eivät?

a) 2x > 3 ==> x > 2,   b) 3x < 4 ==> x < 1  \/ 2x < 3,   c) ¬(x > 1 <==> x > 0  /\ x > 1).

Vastaus


Tehtävä 7
Olkoot x ja y reaalilukuja, x > 0, y > 0. Ovatko seuraavat väittämät tosia?

a)  A x  E y (y < x),   b)  E x  A y (y > x).

Vastaus


Tehtävä 8
Olkoot x ja e reaalilukuja. Ovatko seuraavat propositiot tosia:

a)  A (e > 0)  E (x/=1) (|x - 1| < e),   b)  E (x/=1)  A (e > 0) (|x - 1| < e) ?

Vastaus


Tehtävä 9
Funktion f : R --> R (R = reaaliluvut) jatkuvuus määritellään ehdolla

 A (e > 0)  A (x  (- R)  E (d > 0)  A (y  (- R) (|y - x| < d ===> |f(y) - f(x)| < e).

Ns. tasainen jatkuvuus taas määritellään ehdolla

 A (e > 0)  E (d > 0)  A (x  (- R)  A (y  (- R) (|y - x| < d ===> |f(y) - f(x)| < e).

Selosta, mikä ero näillä käsitteillä on.


1.2 Matemaattisesta todistamisesta

Tehtävä 10
Osoita totuusarvotauluja käyttäen propositiot

[p  /\ (p ==> q)] ==> q  ja  [p  /\ (¬q ==> ¬p)] ==> q

tautologioiksi. Millaisia matemaattisia todistustapoja nämä säännöt vastaavat?


Tehtävä 11
Olkoon n luonnollinen luku. Todista: n on parillinen, jos ja vain jos n2 on parillinen. Selosta todistuksen looginen rakenne.


Tehtävä 12
Tarkoittakoon a jotakuta teekkaria ja olkoon p propositio ’a  (- Ø’ (Ø on tyhjä joukko). Olkoon q propositio ’a on vihreäsilmäinen leijona’. Onko propositio p ==> q tosi vai epätosi? Jos propositio on tosi, niin seuraako tästä, että kaikki teekkarit ovat leijonia?


1.3 Joukko-oppia

Tehtävä 13
Olkoon

A = { n  (- N | 280/n  (- N },   B = { 2n+1 | n  (- N },   C = { x  (- R | 0 < x < 10 } = ]0, 10[.

Määritä   a) A  /~\ B,   b) A  /~\ C,   c) B  /~\ C,   d) A  U C,   e) (A  U B)  /~\ C,   f) (B  U C)  /~\ A.

Vastaus


Tehtävä 14
Todista:

a)  A < B <====> A  U B = B <====> A  /~\ B = A,
b)  A < B  /\ A < C <====> A < B  /~\ C,
c)  A < C  /\ B < C <====> A  U B < C,
d)  A < B <====> A  /~\ C < B  /~\ C A C.


Tehtävä 15
Todista joukko-opilliset de Morganin lait. Piirrä kuviot.


Tehtävä 16
Olkoot A ja B joukkoja. Todista:

(A  /~\ CB)  U B = (A  U B)  /~\ CB <====> B = Ø.


Tehtävä 17
Olkoot A, B ja C saman perusjoukon osajoukkoja. Todista identiteetit

a)  (A  /~\ CB)  /~\ CC = A  /~\ C(B  U C),
b)  A  /~\ (B  /~\ CC) = (A  /~\ B)  /~\ C(A  /~\ C),
c)  (A  /~\ CB)  U (A  /~\ CC) = A  /~\ C(B  /~\ C),
d)  (A  /~\ CB)  /~\ (A  /~\ CC) = A  /~\ C(B  U C)

1o tutkimalla mielivaltaisen alkion x kuulumista oikean ja vasemman puolen joukkoihin, 2o soveltamalla joukkoalgebran laskusääntöjä. Piirrä kuviot joukoista.


Tehtävä 18
Olkoon Z kaikkien kokonaislukujen joukko. Todista: a) { 3n + 2 | n  (- Z } = { 3n - 7 | n  (- Z }, b) { 7n + 3 | n  (- Z } = { 7n - 32 | n  (- Z }.


Tehtävä 19
Sievennä joukko-opilliset lausekkeet

a)  U  oo 

k=1[-1 + 1k, 1 - 1k],   b)  oo  /~\ 

k=1] - 1k, 1k[.


Tehtävä 20
Olkoon

Af = { (x, y) | (x - cos f)2 + (y - sin f)2 < 4 }

xy-tason joukko. Millainen joukko on

   /~\ 

f (- [0,2p]Af ?

Vastaus


Tehtävä 21
Olkoot A, B ja C saman perusjoukon joukkoja. Todista, että (A  U B) × C = (A × C)  U (B × C).


Tehtävä 22
Olkoot reaaliluku x relaatiossa R reaalilukuun y, jos x < 1/y. Millainen karteesisen tulon R × R osajoukko relaatio R on?


Tehtävä 23
Olkoot luonnolliset luvut n ja m relaatiossa P toisiinsa, jos n2 + m2 on luonnollisen luvun neliö. Piirrä kuva relaatiosta P karteesisen tulon N × N osajoukkona; tarkastele arvoja n,  m < 20.


1.4 Kuvaus

Tehtävä 24
Etsi mahdollisimman laaja lähtöjoukko reaalimuuttujan x reaaliarvoiselle funktiolle

f(x) =  V~ -----------------
  x(x2 - 1)(x2 - 4).

Vastaus


Tehtävä 25
Määritä mahdollisimman laaja lähtöjoukko ja vastaava arvojoukko reaalimuuttujan x reaaliarvoiselle funktiolle

f(x) =  V~ ------
  x---1-
    x.

Vastaus


Tehtävä 26
Määritellään funktio f : R --> R asettamalla f(x) = |(x + 1)(x - 3)|. Laske välin [1, 4] kuva ja välin [1, 4] alkukuva.

Vastaus


Tehtävä 27
Funktio f : N --> N määritellään ehdoilla

{
  f (n) = n - 10,  kun  n > 100,

  f (n) = f(f(n + 11)),  kun  1 < n < 100.

Millainen funktio on kyseessä?


Tehtävä 28
Miten reaalimuuttujan x funktion

f(x) = 3x + 5
-------
x - 7

(mahdollisimman laajat) lähtö- ja maalijoukko on valittava, jotta funktio olisi bijektio? Määritä käänteisfunktion lauseke. Piirrä sekä funktion että sen käänteisfunktion kuvaaja samaan koordinaatistoon.


Tehtävä 29
Reaalimuuttujan reaaliarvoinen funktio f määritellään lausekkeella f(x) = (1 - x3)/(x2 - 1). Määritä funktiolle mahdollisimman laaja lähtöjoukko ja tätä vastaava arvojoukko. Piirrä funktion kuvaaja. Rajoita lähtöjoukkoa siten, että funktiolle saadaan käänteisfunktio. Mikä on vastaava arvojoukko? Määritä käänteisfunktion lauseke ja piirrä kuvaaja.


Tehtävä 30
Muodosta reaalimuuttujan reaaliarvoisista funktioista f(x) = sin x, g(x) = x2 + 1 ja h(x) = 1 - x2 yhdistetyt kuvaukset hogof, gohof ja hofog.


Tehtävä 31
Olkoot f(x) = x - 2, g(x) = 2x + 3 ja h(x) = x2 + x. Muodosta yhdistetyt funktiot fo go h ja hogof.


Tehtävä 32
Olkoot f : R --> R ja g : R --> R reaalimuuttujan reaaliarvoisia funktioita, f(x) =  V~ 2-
x+1, g(x) = x2 + 1. Muodosta yhdistetyt funktiot fof, fog, gof, gog.


1.5 Luonnolliset luvut

Tehtävä 33
Olkoon A = {1, 2, 3}. Tutki, mitkä Peanon aksioomat A toteuttaa, kun seuraajafunktio s määritellään seuraavasti:   a) s(1) = 2, s(2) = 3;   b) s(1) = 2, s(2) = 3, s(3) = 1;   c) s(1) = 2, s(2) = 3, s(3) = 2.

Vastaus


Tehtävä 34
Mitkä Peanon aksioomat tyhjä joukko toteuttaa?


Tehtävä 35
Todista induktiolla

a)   n
 sum 

 k=1k3 = 1-
4n2(n + 1)2,   n  (- N,
b)   sum n

 k=1k22k = (n2 - 2n + 3) 2n+1 - 6,   n  (- N,
c)  1 . 3 + 3 . 5 + . . . + (2n - 1)(2n + 1) = n-
3(4n2 + 6n - 1),   n  (- N,
d)   1
----
1 .2 +  1
----
2 .3 + . . . +     1
---------
(n - 1)n = n - 1
------
  n,   n = 2, 3, . . . ,
e)  (1 + 1-
1)1(1 + 1-
2)2. . . (1 + 1-
n)n = (n-+-1)n-
   n!,   n  (- N.


Tehtävä 36
Luvut xn, n  (- N, määritellään siten, että x1 = 1 ja xn+1 = xn + 2  ---
 V~  xn + 1, n = 1, 2, 3, . . . . Osoita induktiota käyttäen, että kaikki luvut xn ovat kokonaislukuja.


Tehtävä 37
Olkoon x/= ± 1. Todista induktiolla

 sum n

k=0  2k
-----k-
1 + x2 =   1
------
x - 1 +    2n+1
------n+1
1 - x2,   n = 0, 1, 2, . . . .


Tehtävä 38
Laske seuraavat summat ja tulot:

a)  5
 sum 

k=0k 2k,   b)  3
 sum 

k=1  4
 sum 

 j=0jk,   c)    prod 

k0 p<akr<ill1in0en3k.

Vastaus


Tehtävä 39
Tutki, montako aijk-termiä on kolminkertaisessa summassa

 sum 4

i=1 sum i

j=1 sum j

k=1aijk

ja laske summa, kun aijk = ijk.

Vastaus


1.6 Lukumäärän laskemisesta

Tehtävä 40
Muodosta joukkojen a) {a, b}, b) {a, b, c} kaikki osajoukot. Montako näitä on?


Tehtävä 41
Montako erilaista viiden kortin sarjaa voidaan korttipakasta vetää, kun a) kiinnitetään, b) ei kiinnitetä huomiota korttien järjestykseen?


Tehtävä 42
Neljä punaista, kolme vihreää ja kaksi sinistä palloa asetetaan jonoon. Kuinka monta erinäköistä jonoa saadaan, kun samanväriset pallot ovat keskenään identtisiä?


Tehtävä 43
Kuinka monta erilaista henkilötunnusta on (Suomessa) periaatteessa olemassa? Tunnuksen muoto on ppkkvv-nnnr, missä on aluksi syntymäpäivä (ppkkvv), sitten juokseva numero (nnn) ja lopuksi tarkistusmerkki (r). Tarkistusmerkki määräytyy jakolaskun ppkkvvnnn/31 jakojäännöksestä. Rajoitutaan tarkastelemaan sadan vuoden jaksoa ja oletetaan, että karkausvuosia tähän jaksoon mahtuu 25.


Tehtävä 44
Olkoon joukon A alkioiden lukumäärä #A = m <  oo . Kuinka monta erilaista p (p < m) alkion osajoukkoa joukon A alkioista voidaan muodostaa? Entä osajonoa? (Joukon alkiot ovat aina keskenään eri suuria, ts. jokainen alkio mainitaan vain kerran; jonossa sama alkio voi esiintyä useita kertoja.)


Tehtävä 45
Olkoon joukon A alkioiden lukumäärä #A = m <  oo ja joukon B alkioiden lukumäärä #B = n <  oo . Osoita, että erilaisia funktioita A --> B on nm kappaletta.


Tehtävä 46
Olkoot A ja B äärellisiä joukkoja, #A = m, #B = n. Olkoon S(m, n) surjektioiden A --> B lukumäärä. Osoita, että tälle pätee

S(m, 1) = 1,
S(m, n) = nm - n sum - 1


 k=1(  )
 n
 kS(m, k),   n = 2, 3, . . . .


Tehtävä 47
Laske edellisessä tehtävässä esitettyjen kaavojen avulla surjektioiden määrä S(m, n), kun 1 < m < 4, 1 < n < 4. Mieti, voidaanko tulos saada jollakin muulla tavalla, kun   a) m = n,   b) m < n.


Tehtävä 48
Teekkari saattoi 1970-luvun puolivälissä suorittaa jopa kuusi matematiikan kurssia — kutsuttakoon näitä seuraavassa nimillä A, B, C, D, E, F — joissa oli yhteisiä osia. Kullakin kurssilla oli suorituspistearvonsa (vastaa nykyisiä opintoviikkoja) ja kurssien yhteislaajuuden selvittämiseksi määriteltiin myös kurssien kaksittaisille, kolmittaisille jne. leikkauksille suorituspistearvot. Nämä olivat seuraavat:
A: 3.5,  B: 2,  C: 3,  D: 3.5,  E: 7.5,  F: 5.5,
A /~\ C: 1.5,  A /~\ D: 1,  B /~\ D: 0.5,  C /~\ D: 1,
A /~\ C /~\ D: 1.
Muiden kombinaatioiden leikkaukset olivat tyhjiä. Montako suorituspistettä sai teekkari, joka oli suorittanut kaikki kuusi kurssia?


Tehtävä 49
Laitumella on lauma nautakarjaa. Laumassa on 83 täysin ruskeata eläintä, 77 sarvipäätä, 36 sukupuoleltaan sonnia, 22 ruskeata sarvipäätä, 15 ruskeata sonnia, 25 sarvipäistä sonnia ja 7 ruskeata sarvipäistä sonnia. Muunlaisia eläimiä ei laumassa ole. Kuinka monta eläintä laumassa on kaikkiaan?

Vastaus


Tehtävä 50
Osoita, että rationaalilukuja on yhtä paljon kuin luonnollisia lukuja, ts. että rationaalilukujen ja luonnollisten lukujen joukot ovat yhtä mahtavia.


Tehtävä 51
Osoita, että avoimella välillä ]0, 1[ on reaalilukuja yhtä paljon kuin koko reaalilukujoukossa, ts. että väli ]0, 1[ ja reaalilukujoukko R ovat yhtä mahtavia.


Seuraava lukuSisällysluettelo