Title: Ekvivalenssitodistukset

Q: Joukkojen osoittaminen samaksi on itse asiassa eräänlainen ekvivalenssitodistus eli ”jos ja vain jos”-tyyppinen todistus. Ekvivalenssitodistuksia käsitellään laajemmin kurssimateriaalin luvussa 3.3. Ryhdy tutustumaan tuohon lukuun vastatessasi seuraavan tehtävän kysymyksiin.

Tarkastelleen väitettä "\( (a+b)^2=a^2+b^2\), jos ja vain jos \(a=0\) tai \(b=0\)".

Täydennä väitteen ekvivalenssitodistuksen rakenne. Osa todistuksesta puuttuu tarkoituksella.

Todistetaan ensimmäinen suunta ("\( \Rightarrow \)").

[...]

                \( \vdots \)

[...]

Todistetaan toinen suunta ("\(\Leftarrow\)").

[...]

                \( \vdots \)

[...]
A: Oletetaan, että (a + b)² = a² + b².; Siis a = 0 tai b = 0.; Oletetaan, että a = 0 tai b = 0.; Siis (a + b)² = a² + b².
If right: Vastauksesi on oikein.
If partly right: Vastauksesi on osittain oikein.
If wrong: Vastauksesi on väärin.
Feedback: Todistetaan ensimmäinen suunta ("\( \Rightarrow \)"). Oletetaan, että \( (a+b)^2=a^2+b^2\). \( \vdots \) Siis \(a=0\) tai \(b=0\). Todistetaan toinen suunta ("\(\Leftarrow\)"). Oletetaan, että \(a=0\) tai \(b=0\). \( \vdots \) Siis \((a+b)^2=a^2+b^2\).

Q: Olkoon \(n \in \mathbb{Z}\). Täydennä todistus väitteelle "\(n\) on parillinen, jos ja vain jos \(n^2\) on jaollinen luvulla \(4\)".

Todistus. Oletetaan, että [...]. Tällöin [...] jollakin \(k \in \mathbb{Z}\). Nähdään, että \(n^2\) = [...], missä [...] \(\in \mathbb{Z}\). Siis [...].

Oletetaan sitten, että [...]. Tästä seuraa, että [...]. Osoitetaan, että myös [...].
Tehdään vastaoletus, että \(n\) on pariton. Nyt \(n\) = [...] jollakin \(m \in \mathbb{Z}\). Tällöin \(n^2\) = [...] = [...] = [...] eli [...].
Päädyttiin ristiriitaan, joten alkuperäinen väite on tosi. Siis [...].
A: n on parillinen; n = 2k; (2k)² = 4k²; k²; n² on jaollinen luvulla 4; n² on jaollinen luvulla 4; n² on parillinen; n on parillinen; 2m + 1; (2m+1)²; 4m² + 4m + 1; 2(2m² + 2m) + 1; n² on pariton; n on parillinen
If right: Vastauksesi on oikein.
If partly right: Vastauksesi on osittain oikein.
If wrong: Vastauksesi on väärin.
Feedback: Todistus. Oletetaan ensin, että \(n\) on parillinen. Tällöin \(n = 2k\) jollakin \(k \in \mathbb{Z}\). Nähdään, että \(n^2 = (2k)^2 = 4k^2\), missä \(k^2 \in \mathbb{Z}\). Siis \(n^2\) on jaollinen neljällä. Oletetaan sitten, että \(n^2\) on jaollinen neljällä. Tästä seuraa, että \(n^2\) on parillinen. Osoitetaan, että myös \(n\) on parillinen. Tehdään vastaoletus, että \(n\) on pariton. Nyt \(n = 2m + 1\) jollakin \(m \in \mathbb{Z}\). Tällöin \(n^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1\) eli \(n^2\) on pariton. Päädyttiin ristiriitaan, joten alkuperäinen väite on tosi. Siis \(n\) on parillinen.

Q: Olkoon \(a \in \mathbb{R} \), ja olkoot \(A = \{ (x,y) \in \mathbb{R}^2 \mid x^2-2x-y<a^2-2a\}\) ja \(B = \{(x,y) \in \mathbb{R}^2 \mid y<0 \} \).

Tutkitaan väitettä "\(A \cap B = \emptyset\), jos ja vain jos \(a=1\)".

a) Minkä tyyppinen todistus on rakennettava?

[...]

b) Mikä seuraavista kuvaa parhaiten todistuksen rakennetta?
[...]

c) Pystytäänkö johtopäätökseen etenemään oletusten avulla vai pitäisikö kokeilla epäsuoraa todistusta?
[...]
A: ekvivalenssitodistus; Todistuksessa on kaksi osaa. Ensimmäisessä osassa lähdetään oletuksesta \(A \cap B = \emptyset\), ja päädytään johtopäätökseen \(a=1\). Toisessa osassa taas lähdetään oletuksesta \(a=1\), ja päädytään johtopäätökseen \(A \cap B = \emptyset\).; Epäsuora todistus helpottaa tehtävän ratkaisua.
Gap 1 offers: ekvivalenssitodistus; implikaatiotodistus; induktiotodistus; ristiriitatodistus; kontrapositiotodistus
Gap 2 offers: Todistuksessa on kaksi osaa. Ensimmäisessä osassa lähdetään oletuksesta \(A \cap B = \emptyset\), ja päädytään johtopäätökseen \(a=1\). Toisessa osassa taas lähdetään oletuksesta \(a=1\), ja päädytään johtopäätökseen \(A \cap B = \emptyset\).; Todistuksessa on yksi osa. Lähdetään oletuksesta \(A \cap B = \emptyset\), ja päädytään johtopäätökseen \(a=1\).; Todistuksessa on yksi osa. Lähdetään oletuksesta \(a=1\), ja päädytään johtopäätökseen \(A \cap B = \emptyset\).; Todistuksessa on kaksi osaa. Ensin tehdään alkuaskel ja sitten induktioaskel, minkä jälkeen väite seuraa induktioperiaatteesta.; Todistuksessa on kaksi osaa. Ensimmäisessä osassa lähdetään oletuksesta \(x \in A \cap B\), ja päädytään johtopäätökseen \(A \cap B = \emptyset\). Toisessa osassa taas lähdetään oletuksesta \(A \cap B = \emptyset\), ja päädytään johtopäätökseen \(a=1\).
Gap 3 offers: Epäsuora todistus helpottaa tehtävän ratkaisua.; Epäsuora todistus ei helpota tehtävän ratkaisua.
Feedback: a) Minkä tyyppinen todistus on rakennettava? ekvivalenssitodistus b) Mikä seuraavista kuvaa parhaiten todistuksen rakennetta? Todistuksessa on kaksi osaa. Ensimmäisessä osassa lähdetään oletuksesta \(A \cap B = \emptyset\), ja päädytään johtopäätökseen \(a=1\). Toisessa osassa taas lähdetään oletuksesta \(a=1\), ja päädytään johtopäätökseen \(A \cap B = \emptyset\). c) Pystytäänkö johtopäätökseen etenemään oletusten avulla vai pitäisikö kokeilla epäsuoraa todistusta? Epäsuora todistus helpottaa tehtävän ratkaisua. Joukon osoittaminen tyhjäksi on usein hankalaa suoralla todistustekniikalla. Vastaavasti oletuksesta, että jokin joukko on tyhjä, voi olla vaikeaa päästä eteenpäin.

Oletetaan, että \(x \in \mathbb{R}\). Halutaan osoittaa, että \((x^2-1)(3x+2) = 0\), jos ja vain jos \(x \in \{-1, - \frac{2}{3}, 1\}\). Kyseessä on ekvivalenssitodistus. Ovatko seuraavat väittämät oikein vai väärin?

a) Ekvivalenssitodistus koostuu kahdesta implikaatiotodistuksesta.

b) Todistuksessa oletetaan, että \((x^2-1)(3x+2) = 0\).

c) Todistuksessa oletetaan, että \(x \in \{-1, - \frac{2}{3}, 1\}\).

d) Jos yhtälöstä \((x^2-1)(3x+2) = 0\) seuraa yhtälö \(x = 1\), niin tästä voidaan päätellä, että luku \(1\) toteuttaa yhtälön.

e) Jos tehtävän väite on tosi, niin \(x = 2\) on eräs yhtälön ratkaisuista.

f) Todistuksessa tulee näyttää, että \(x = -1\) on yhtälön ratkaisu.
Feedback: a) Oikein. Väite "P jos ja vain jos Q" todistetaan näyttämällä "jos P, niin Q" ja "jos Q, niin P". b) Oikein. Tämä on toisen implikaatiotodistuksen oletus. c) Oikein. Tämä on toisen implikaatiotodistuksen oletus. d) Väärin. Kyseinen päättely osoittaa, että \(x = 1\) on yksi mahdollinen ratkaisu yhtälölle. Tämän jälkeen tulee vielä sijoittaa se yhtälön vasemmalle puolelle ja tarkistaa, että vasen puoli on \(0\). e) Väärin. Väite sanoo, että yhtälö toteutuu täsmälleen silloin, kun \(x = -1, x = - \frac{2}{3}\) tai \(x = 1\). f) Oikein. Tämä on osa implikaatiotodistusta "jos \(x \in \{-1, - \frac{2}{3}, 1\}\), niin \((x^2-1)(3x+2) = 0\)".