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) x y (y < x),   b) x y (y > x).

Vastaus

---

Tehtävä 8

Olkoot x ja reaalilukuja. Ovatko seuraavat propositiot tosia:

a)  ( > 0)  (x1) (|x - 1| < ),   b)  (x1)  ( > 0) (|x - 1| < ) ?

Vastaus

---

Tehtävä 9

Funktion f : ( = reaaliluvut) jatkuvuus määritellään ehdolla

( > 0)  (x )  ( > 0)  (y ) (|y - x| < |f(y) - f(x)| < ).

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

( > 0)  ( > 0)  (x )  (y ) (|y - x| < |f(y) - f(x)| < ).

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 n² 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 | 280/n },   B = { 2n+1 | n },   C = { x | 0 < x < 10 } = ]0, 10[.

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

Vastaus

---

Tehtävä 14

Todista:

a)	A B A B = B A B = A,
b)	A B A C A B C,
c)	A C B C A B C,
d)	A B A C B CC.

---

Tehtävä 15

Todista joukko-opilliset de Morganin lait. Piirrä kuviot.

---

Tehtävä 16

Olkoot A ja B joukkoja. Todista:

(A B) B = (A B) B B = Ø.

---

Tehtävä 17

Olkoot A, B ja C saman perusjoukon osajoukkoja. Todista identiteetit

a)	(A B) C = A (B C),
b)	A (B C) = (A B) (A C),
c)	(A B) (A C) = A (B C),
d)	(A B) (A C) = A (B C)

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

---

Tehtävä 18

Olkoon kaikkien kokonaislukujen joukko. Todista: a) { 3n + 2 | n } = { 3n - 7 | n }, b) { 7n + 3 | n } = { 7n - 32 | n }.

---

Tehtävä 19

Sievennä joukko-opilliset lausekkeet

a) [-1 + , 1 - ],   b) ] - , [.

---

Tehtävä 20

Olkoon

A = { (x, y) | (x - cos )² + (y - sin )² < 4 }

xy-tason joukko. Millainen joukko on

A ?

Vastaus

---

Tehtävä 21

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

---

Tehtävä 22

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

---

Tehtävä 23

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

---

1.4 Kuvaus

Tehtävä 24

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

f(x) = .

Vastaus

---

Tehtävä 25

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

f(x) = .

Vastaus

---

Tehtävä 26

Määritellään funktio f : 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 : määritellään ehdoilla

Millainen funktio on kyseessä?

---

Tehtävä 28

Miten reaalimuuttujan x funktion

f(x) =

(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 - x³)/(x² - 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) = x² + 1 ja h(x) = 1 - x² yhdistetyt kuvaukset hogof, gohof ja hofog.

---

Tehtävä 31

Olkoot f(x) = x - 2, g(x) = 2x + 3 ja h(x) = x² + x. Muodosta yhdistetyt funktiot fo go h ja hogof.

---

Tehtävä 32

Olkoot f : ja g : reaalimuuttujan reaaliarvoisia funktioita, f(x) = , g(x) = x² + 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)	k3 = n2(n + 1)2,   n ,
b)	k22k = (n2 - 2n + 3) 2n+1 - 6,   n ,
c)	1 . 3 + 3 . 5 + . . . + (2n - 1)(2n + 1) = (4n2 + 6n - 1),   n ,
d)	+ + . . . + = ,   n = 2, 3, . . . ,
e)	(1 + )1(1 + )2. . . (1 + )n = ,   n .

---

Tehtävä 36

Luvut x_n, n , määritellään siten, että x₁ = 1 ja x_n+1 = x_n + 2 + 1, n = 1, 2, 3, . . . . Osoita induktiota käyttäen, että kaikki luvut x_n ovat kokonaislukuja.

---

Tehtävä 37

Olkoon x ± 1. Todista induktiolla

= + ,   n = 0, 1, 2, . . . .

---

Tehtävä 38

Laske seuraavat summat ja tulot:

a) k 2^k,   b) jk,   c) 3^k.

Vastaus

---

Tehtävä 39

Tutki, montako a_ijk-termiä on kolminkertaisessa summassa

a_ijk

ja laske summa, kun a_ijk = 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 < . 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 < ja joukon B alkioiden lukumäärä #B = n < . Osoita, että erilaisia funktioita A B on n^m 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 - S(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,
AC: 1.5,  AD: 1,  BD: 0.5,  CD: 1,
ACD: 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 ovat yhtä mahtavia.

---