Title: Epäsuora todistaminen

Feedback shared by this category's questions, if right: Vastauksesi on oikein.
Feedback shared by this category's questions, if partly right: Vastauksesi on osittain oikein.
Feedback shared by this category's questions, if wrong: Vastauksesi on väärin.

Q: Oletetaan, että \(n\) on jokin kokonaisluku. Tarkastellaan väitettä "jos \(3n+2\) on pariton, niin \(n\) on pariton".

Laita väitteen kontrapositiotodistuksen vaiheet järjestykseen.

Todistus

[...]

[...]

[...], missä [...].

[...]

Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.
Also offered: Oletetaan, että n on pariton.; Oletetaan, että 3n+2 on pariton.; Oletetaan, että 3n+2 on parillinen.; Tällöin n=2k+1 jollain k ∈ ℤ.; Tällöin 3n+2=2k jollain k ∈ ℤ.; Tällöin 3n+2=2k+1 jollain k ∈ ℤ.; Nyt 3n+2=6k+5=2(3k+2)+1; 3k+2 on kokonaisluku; Siten 3n+2 on pariton.; Siten n on parillinen.; Siten n on pariton.
A: Oletetaan, että n on parillinen.; Tällöin n=2k jollain k ∈ ℤ.; Nyt 3n+2=6k+2=2(3k+1); 3k+1 on kokonaisluku; Siten 3n+2 on parillinen.
Feedback: Todistus Oletetaan, että \(n\) on parillinen. Tällöin \(n=2k\) jollain \(k \in \mathbb{Z}\). Nyt \(3n+2=6k+2=2(3k+1)\), missä \(3k+1\) on kokonaisluku. Siten \(3n+2\) on parillinen. Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.

Q: Oletetaan, että \(A, B\) ja \(C\) ovat joukkoja. Tarkastellaan väitettä "jos \(A \cap C \subset B\), niin \( (A \setminus B) \cap C = \emptyset \).

Laita väitteen kontrapositiotodistuksen vaiheet järjestykseen.

Todistus

[...]

[...]

[...]

[...]

[...]

[...]

[...]

Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.
Also offered: Oletetaan, että x ∈ (A∖B)∩C.; Oletetaan, että A∩C ⊂ B.; Siten (A∖B)∩C = ∅.
A: Oletetaan, että (A∖B)∩C ≠ ∅.; Tällöin on olemassa x ∈ (A∖B)∩C.; Nyt x ∈ A∖B ja x ∈ C.; Koska x ∈ A ja x ∈ C, niin x ∈ A∩C, ja; lisäksi nähdään, että x ∉ B.; Nyt siis x ∉ B, mutta x ∈ A∩C.; Siten A∩C ⊂ B ei päde.
Feedback: Todistus Oletetaan, että \( ( A \setminus B) \cap C \neq \emptyset\). Tällöin on olemassa \(x \in ( A \setminus B) \cap C\). Nyt \(x \in A \setminus B\) ja \(x \in C\). Edelleen \(x \in A\), mutta \(x \notin B\). Koska \(x \in A\) ja \(x \in C\), niin \(x \in A \cap C\). Nyt siis \(x \notin B\), mutta \(x \in A \cap C\). Siten \(A \cap C \subset B\) ei päde. Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.

Q: Pyritään todistamaan, että jos \(A \times B = \emptyset\), niin \(A = \emptyset\) tai \(B = \emptyset\).

Täydennä todistus.

Todistus

Tehdään kontrapostiotodistus. Väitteen kontrapositio on, että jos [...], niin [...].

Oletetaan siis, että [...]. Tällöin on olemassa [...] ja [...]. Nyt [...], joten [...].

Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.
Also offered: A ≠ ∅ tai B ≠ ∅; A = ∅ tai B = ∅; A × B = ∅
A: A ≠ ∅ ja B ≠ ∅; A × B ≠ ∅; A ≠ ∅ ja B ≠ ∅; a ∈ A; b ∈ B; (a, b) ∈ A × B; A × B ≠ ∅
Feedback: Todistus Tehdään kontrapostiotodistus. Väitteen kontrapositio on, että jos \(A \neq \emptyset\) ja \(B \neq \emptyset\), niin \(A \times B = \emptyset\). Oletetaan siis, että \(A\neq \emptyset\) ja \(B \neq \emptyset\). Tällöin on olemassa \(a \in A\) ja \(b \in B\). Nyt \( (a,b) \in A \times B\), joten \(A \times B \neq \emptyset\). Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.

Q: Pyritään todistamaan, että jos \(A = \emptyset\) tai \(B = \emptyset\), niin \(A \times B = \emptyset\).

Täydennä todistus.

Todistus

Tehdään kontrapositiotodistus. Väitteen kontrapositio on, että jos [...], niin [...].

Oletetaan siis, että [...]. Tällöin on olemassa [...]. Nyt [...], joten [...].

Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.
Also offered: A × B = ∅; A ≠ ∅ tai B ≠ ∅; A = ∅ tai B = ∅
A: A × B ≠ ∅; A ≠ ∅ ja B ≠ ∅; A × B ≠ ∅; (a, b) ∈ A × B; a ∈ A ja b ∈ B; A ≠ ∅ ja B ≠ ∅
Feedback: Todistus Tehdään kontrapositiotodistus. Väitteen kontrapositio on, että jos \(A \times B \neq \emptyset\), niin \(A \neq \emptyset\) ja \(B \neq \emptyset\). Oletetaan siis, että \(A \times B \neq \emptyset\). Tällöin on olemassa \( (a,b) \in A \times B\). Nyt \(a \in A\) ja \(b \in B\), joten \(A \neq \emptyset\) ja \(B \neq \emptyset\). Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.

Q: Tarkastellaan suorakulmaista kolmiota, jonka kateettien pituudet ovat \(a\) ja \(b\) ja hypotenuusan pituus \(c\). Tarkoitus on osoittaa, että \(a+b>c\).

Täydennä väitteen ristiriitatodistus.

Todistus

Tehdään vastaoletus: [...].

Korottamalla epäyhtälö [...] potenssiin saadaan [...].

Koska [...], niin \(a^2+2ab+b^2 >a^2+b^2\). Näin ollen \(c^2 >\)[...], mikä on ristiriidassa Pythagoraan lauseen kanssa, jonka mukaan [...].

Koska [...] päädyttiin ristiriitaan, alkuperäisen väitteen täytyy päteä.
Also offered: a + b < c; kolmanteen; a² + b² ≤ c²; a² + b² < c²; Pythagoraan lauseesta; a² + b² ≠ c²; a² + 2ab + b² < c²; a² + 2ab + b²
A: a + b ≤ c; toiseen; a² + 2ab + b² ≤ c²; 2ab > 0; a² + b²; a² + b² = c²; vastaoletuksesta
Feedback: Todistus Tehdään vastaoletus: \(a+b \leq c\). Korottamalla epäyhtälö toiseen potenssiin saadaan \(a^2+2ab+b^2 \leq c^2\). Koska \(2ab>0\), niin \(a^2+2ab+b^2>a^2+b^2\). Näin ollen \(c^2>a^2+b^2\), mikä on ristiriidassa Pythagoraan lauseen kanssa, jonka mukaan \(a^2+b^2=c^2\). Koska vastaoletuksesta päädyttiin ristiriitaan, alkuperäisen väitteen täytyy päteä.

Q: Kontrapositiotodistus on esimerkki epäsuorasta todistustekniikasta. Sitä käytetään implikaatioväitteiden todistamiseen, kun implikaatiota on vaikea lähestyä suoraan. Tavallisesti näin käy silloin, kun ”jos”-väitettä on vaikea käyttää oletuksena. Kontrapositiotodistuksessa lähdetäänkin ”niin”-väitteen kieltämisestä. Tutustu kontrapositiotodistukseen kurssimateriaalin luvun 3.4 avulla ja tee sen jälkeen seuraava tehtävä.

Oletetaan, että \(n\) on jokin kokonaisluku. Tarkastellaan väitettä "jos \(5n+4\) on pariton, niin \(n\) on pariton". Täydennä väitteen kontrapositiotodistuksen rakenne. (Todistuksesta puuttuu tarkoituksella osa.)

Todistus
Oletetaan, että [...]  on [...].
Tällöin [...] jollain \(k \in \mathbb{Z} \).

                       \( \vdots \)

Siten [...]  on [...].
Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee.

Pohdi lisäksi:
Miksi kontrapositiotodistus on pätevä keino todistaa alkuperäinen väite?
A: n; parillinen; n=2k; 5n+4; parillinen
Gap 1 offers: n; 5n+4
Gap 2 offers: parillinen; pariton
Gap 3 offers: 5n+4=2k; n=2k; 5n+4=2k+1; n=2k+1
Gap 4 offers: n; 5n+4
Gap 5 offers: parillinen; pariton
Feedback: Todistus Oletetaan, että n on parillinen. Tällöin n=2k jollain \(k \in \mathbb{Z} \). \( \vdots \) Siten 5n+4 on parillinen. Näin on todistettu väitteen kontrapositio, joten myös alkuperäinen väite pätee. Kontrapositio soveltuu vain implikaatioväitteiden (eli "jos..., niin..."-tyyppisten väitteiden) todistamiseen. Kontrapositiotodistus on loogisesti pätevä todistuskeino, koska alkuperäinen väite ja sen kontrapositio ovat keskenään loogisesti ekvivalentteja. Kontrapositiotodistusta on usein kannattavaa harkita muun muassa silloin, kun "jos"-osassa oleva lauseke on monimutkaisempi kuin "niin"-osassa oleva lauseke. Esimerkiksi tässä tilanteessa "jos"-osassa oleva lauseke on \(5n+4\), kun taas "niin"-osassa on pelkkä \(n\).

Q: Valitse paras ilmaus siten, että todistus on looginen ja noudattaa hyvää matemaattista kirjoitustapaa.

Osoitetaan kaikille \(m,n \in \mathbb{Z}\) väite "jos \(mn\) ja \(m + n\) ovat parillisia, niin \(m\) ja \(n\) ovat kumpikin parillisia".

Todistus. [...] väitteen kontrapositio "jos ainakin toinen luvuista \(m\) ja \(n\) on pariton, niin \(mn\) on pariton tai \(m+n\) on pariton".

[...] \(m\) on pariton. [...] \(m = 2k + 1\) [...] \(k \in \mathbb{Z}\). Koska \(n\) voi olla parillinen tai pariton, niin on tutkittava tapaukset erikseen.

1. [...] \(n\) on parillinen. Nyt \(n = \) [...] [...] \(l \in \mathbb{Z}\). Laskemalla nähdään, että \(m + n = 2k + 1 + 2l = 2(k+l) + 1\), [...] \(k+l \in \mathbb{Z}\). Siis \(m+n\) on pariton.
2. [...] \(n\) on pariton. Nyt \(n = \) [...] [...] \(l \in \mathbb{Z}\). Laskemalla nähdään, että \(mn = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1\), [...] \(2kl+k+l \in \mathbb{Z}\). Siis \(mn\) on pariton.

Molemmissa tapauksissa [...]. Olemme nyt [...] väitteen kontraposition, joten väite pätee.

Huomaa, että olisimme alussa voineet yhtä hyvin olettaa, että \(n\) on pariton.
A: Todistetaan; Oletetaan, että; Tällöin; jollakin; Oletetaan, että; 2l; jollakin; missä; Oletetaan, että; 2l + 1; jollakin; missä; m+n tai mn on pariton; osoittaneet
Gap 1 offers: Oletetaan; Todistetaan
Gap 2 offers: Oletetaan, että; Tiedetään, että; Päätellään, että
Gap 3 offers: Oletetaan, että; Osoitetaan, että; Tällöin
Gap 4 offers: kun; jos; jollakin; kaikilla
Gap 5 offers: Oletetaan, että; Osoitetaan, että; Tiedetään, että
Gap 6 offers: 2l; 2l + 1
Gap 7 offers: kun; jos; jollakin; kaikilla
Gap 8 offers: kun; missä; jos
Gap 9 offers: Oletetaan, että; Osoitetaan, että; Tiedetään, että
Gap 10 offers: 2l; 2l + 1
Gap 11 offers: kun; jos; jollakin; kaikilla
Gap 12 offers: kun; missä; jos
Gap 13 offers: m+n ja mn ovat parittomia; m+n tai mn on pariton
Gap 14 offers: olettaneet; osoittaneet; muodostaneet
Feedback: Todistus. Todistetaan väitteen kontrapositio "jos ainakin toinen luvuista \(m\) ja \(n\) on pariton, niin \(mn\) on pariton tai \(m+n\) on pariton". Oletetaan, että \(m\) on pariton. Tällöin \(m = 2k + 1\) jollakin \(k \in \mathbb{Z}\). Koska \(n\) voi olla parillinen tai pariton, niin on tutkittava tapaukset erikseen. 1. Oletetaan, että \(n\) on parillinen. Nyt \(n = 2l\) jollakin \(l \in \mathbb{Z}\). Laskemalla nähdään, että \(m + n = 2k + 1 + 2l = 2(k+l) + 1\), missä \(k+l \in \mathbb{Z}\). Siis \(m+n\) on pariton. 2. Oletetaan, että \(n\) on pariton. Nyt \(n = 2l + 1\) jollakin \(l \in \mathbb{Z}\). Laskemalla nähdään, että \(mn = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1\), missä \(2kl+k+l \in \mathbb{Z}\). Siis \(mn\) on pariton. Molemmissa tapauksissa \(m+n\) tai \(mn\) on pariton. Olemme nyt osoittaneet väitteen kontraposition, joten väite pätee. Huomaa, että olisimme alussa voineet yhtä hyvin olettaa, että \(n\) on pariton.

Q: Valitse paras vaihtoehto niin, että todistus on looginen ja noudattaa hyvää matemaattista kirjoitustapaa. Tarkasteltava väite on "jos \(\frac{1}{x}\) on irrationaaliluku, niin \(x\) on irrationaaliluku".

Todistus. [...] väitteen kontrapositio, joka on "jos \(x\) on rationaaliluku, niin \(\frac{1}{x}\) on rationaaliluku".

[...] \(x \in \mathbb{Q}\). [...] \(x = \frac{n}{k}\) [...] \(n, k \in \mathbb{Z}\).

Nähdään, että (Valitse mielekkäin esitysjärjestys allaolevista.) [...]

     a) \(\frac{k}{n} = \left(\frac{n}{k}\right)^{-1} = x^{-1} = \frac{1}{x}\)

     b) \(\left(\frac{n}{k}\right)^{-1} = \frac{k}{n} = x^{-1} = \frac{1}{x}\)

     c) \(\frac{1}{x} = x^{-1} = \left(\frac{n}{k}\right)^{-1} = \frac{k}{n}\)

     d) \(x^{-1} = \left(\frac{n}{k}\right)^{-1} = \frac{1}{x} = \frac{k}{n}\)

[...] \(k, n \in \mathbb{Z}\). Näin ollen \(\frac{1}{x} \in \mathbb{Q}\), mikä [...].
A: Todistetaan; Oletetaan, että; Tällöin; joillakin; c); missä; oli osoitettava
Gap 1 offers: Oletetaan; Todistetaan
Gap 2 offers: Oletetaan, että; Tiedetään, että; Osoitetaan, että
Gap 3 offers: Oletetaan myös, että; Tällöin; Osoitetaan, että
Gap 4 offers: joillakin; kun; jos; mielivaltaisilla
Gap 5 offers: a); b); c); d)
Gap 6 offers: missä; kun; mielivaltaisilla; kaikilla
Gap 7 offers: oltiin oletettu; on ristiriita; oli osoitettava
Feedback: Todistus. Todistetaan väitteen kontrapositio, joka on "jos \(x\) on rationaaliluku, niin \(\frac{1}{x}\) on rationaaliluku". Oletetaan, että \(x \in \mathbb{Q}\). Tällöin \(x = \frac{n}{k}\) joillakin \(n, k \in \mathbb{Z}\). Nähdään, että \(\frac{1}{x} = x^{-1} = \left(\frac{n}{k}\right)^{-1} = \frac{k}{n}\), missä \(k, n \in \mathbb{Z}\). Näin ollen \(\frac{1}{x} \in \mathbb{Q}\), mikä oli osoitettava.

Q: Väitteen "jos \(n^3\) on pariton, niin \(n\) on pariton" kontrapositio on

[...]

Väitteen "jos \(x>0\), niin \(x^3-2x^2+x \geq 0 \)" kontrapositio on

[...]

Väitteen "jos aurinko paistaa, niin linnut laulavat ja kukaan ei ole surullinen" kontrapositio on

[...]
A: "jos \(n\) on parillinen, niin \(n^3\) on parillinen".; "jos \(x^3-2x^2+x < 0\), niin \(x \leq 0\)".; "jos linnut eivät laula tai joku on surullinen, niin aurinko ei paista".
Gap 1 offers: "jos \(n\) on parillinen, niin \(n^3\) on parillinen".; "jos \(n\) on pariton, niin \(n^3\) on pariton".; "jos \(n^3\) on parillinen, niin \(n\) on parillinen".
Gap 2 offers: "jos \(x^3-2x^2+x < 0\), niin \(x \leq 0\)".; "jos \(x^3-2x^2+x \leq 0\), niin \(x < 0\)".; "jos \(x<0\), niin \(x^3-2x^2+x \leq 0\)".
Gap 3 offers: "jos linnut eivät laula tai joku on surullinen, niin aurinko ei paista".; "jos linnut eivät laula ja kaikki ovat surullisia, niin aurinko ei paista".; "jos aurinko ei paista, niin linnut eivät laula ja kaikki ovat surullisia".
Feedback: Väitteen "jos \(n^3\) on pariton, niin \(n\) on pariton" kontrapositio on "jos \(n\) on parillinen, niin \(n^3\) on parillinen". Väitteen "jos \(x>0\), niin \(x^3-2x^2+x \geq 0 \)" kontrapositio on "jos \(x^3-2x^2+x < 0\), niin \(x \leq 0\)". Väitteen "jos aurinko paistaa, niin linnut laulavat ja kukaan ei ole surullinen" kontrapositio on "jos linnut eivät laula tai joku on surullinen, niin aurinko ei paista".