Title: Implikaatiotodistukset

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: Joukko-opilliset todistukset perustuvat yleensä alkiotarkasteluun. Tällöin joukko-operaatiot muuntuvat alkioita koskeviksi väitteiksi, joita yhdistellään loogisilla konnektiiveilla. Todistuksissa käytetään luonnollista kieltä, mutta niitä voi mallintaa symbolisella logiikalla. Tässä tehtävässä tutkitaan joukko-operaatioiden ja alkioväitteiden välistä yhteyttä.

Olkoot \(A, B\) ja \(C\) joukkoja ja \(x\) jokin alkio. Merkitään propositiosymbolilla \(p_1\) lausetta \(x \in A\), propositiosymbolilla \(p_2\) lausetta \(x \in B\) ja propositiosymbolilla \(p_3\) lausetta \(x \in C\).

Ilmaise seuraavat propositiolauseet alkiota \(x\) koskevina väitteinä ilman loogisia konnektiiveja.

a) \(p_1 \land p_2\)

[...][...]

b) \((p_1 \land \neg p_2) \lor p_3\)

[...]\((\) [...] \()\)[...][...]

c) \((p_1 \lor p_2) \land \neg (p_2 \lor p_3)\)

[...]\((\) [...] \()\)[...]\((\) [...] \()\)

d) \(\neg p_1 \lor p_2\)

[...][...]
Also offered: ∩
A: x ∈; A ∩ B; x ∈; A \ B; ∪; C; x ∈; A ∪ B; \; B ∪ C; x ∉; A \ B
Feedback: a) \(x \in A \cap B\) b) \(x \in (A \setminus B) \cup C\) c) \(x \in (A \cup B) \setminus (B \cup C)\) d) \(x \notin A \setminus B\). Huomaa, että propositiolause \(\neg p_1 \lor p_2\) on ekvivalentti propositiolauseen \(\neg (p_1 \land \neg p_2)\) kanssa.

Q: Täydennä todistus väitteelle \((A \setminus B) \cap C \subset A \setminus (B \cap C)\).

Todistus. Oletetaan, että [...].
Leikkauksen määritelmän nojalla [...].
Koska [...], niin erotuksen määritelmän nojalla [...].
Koska [...], niin leikkauksen määritelmän nojalla [...].
Koska [...], niin erotuksen määritelmän nojalla [...].
Siis [...] \(\subset\) [...].
A: x ∈ (A \ B) ∩ C; x ∈ A \ B ja x ∈ C; x ∈ A \ B; x ∈ A ja x ∉ B; x ∉ B; x ∉ B ∩ C; x ∈ A ja x ∉ B ∩ C; x ∈ A \ (B ∩ C); (A \ B) ∩ C; A \ (B ∩ C)
Feedback: Todistus. Oletetaan, että \(x \in (A \setminus B) \cap C\). Leikkauksen määritelmän nojalla \(x \in A \setminus B\) ja \(x \in C\). Koska \(x \in A \setminus B\), niin erotuksen määritelmän nojalla \(x \in A\) ja \(x \notin B\). Koska \(x \notin B\), niin leikkauksen määritelmän nojalla \(x \notin B \cap C\). Koska \(x \in A\) ja \(x \notin B \cap C\), niin erotuksen määritelmän nojalla \(x \in A \setminus (B \cap C)\). Siis \((A \setminus B) \cap C \subset A \setminus (B \cap C)\).

Q: Induktiotodistus on keskeinen työväline matematiikassa. Sen avulla voidaan todistaa väitteitä kaikille luonnollisille luvuille. Hieman muunnellen sitä voi käyttää lukujen sijaan todistamaan asioita myös esimerkiksi kaikille propositiolauseille (logiikassa) tai vaikkapa kaikille binääripuille (tietojenkäsittelytieteessä). Aloitetaan induktiotodistuksen harjoittelu summakaavan todistamisella. Voit ottaa mallia esimerkistä 4.1.2.

Tarkoituksena on todistaa induktiolla, että

\( \sum \limits_{i=0}^{n} (3i-2) = \frac{(n+1)(3n-4)}{2} \)

kaikilla luonnollisilla luvuilla \(n\).

Laita induktiotodistuksen vaiheet oikeaan järjestykseen.

[...] Tässä vaiheessa näytettäisiin, että väite pätee luvulla \(n=0\).

[...] Tässä vaiheessa tehtäisiin ensin [...], eli oletettaisiin väitteen pätevän jollain \(k \in \mathbb{N}\). Tämän jälkeen näytettäisiin, että tällöin väite pätee myös luvulla \(k+1\).

[...] Lopuksi todettaisiin, että edellisen perusteella väite pätee [...] nojalla kaikilla \(n \in \mathbb{N}\).
A: Alkuaskel:; Induktioaskel:; induktio-oletus; Johtopäätös:; induktioperiaatteen
Feedback: Alkuaskel: Tässä vaiheessa näytettäisiin, että väite pätee luvulla \(n=0\). Induktioaskel: Tässä vaiheessa tehtäisiin ensin induktio-oletus, eli oletettaisiin väitteen pätevän jollain \(k \in \mathbb{N}\). Tämän jälkeen näytettäisiin, että tällöin väite pätee myös luvulla \(k+1\). Johtopäätös: Lopuksi todettaisiin, että edellisen perusteella väite pätee induktioperiaatteen nojalla kaikilla \(n \in \mathbb{N}\).

Q: Todistetaan väite "jos \(A \cap B = B\), niin \(A \cup B = A\)". Aseta todistuksen eri vaiheet järjestykseen.

[...]

Osoitetaan ensin, että \(A \cup B \subset A\).

[...]

[...]

[...]

[...]

[...]

[...]

Osoitetaan sitten, että \(A \subset A \cup B\).

[...]

[...]

[...]

[...]
A: Oletetaan, että A ∩ B = B.; Oletetaan, että x ∈ A ∪ B.; Yhdisteen määritelmän nojalla x ∈ A tai x ∈ B.; Tapaus 1: Jos x ∈ A, väite pätee.; Tapaus 2: Jos x ∈ B, niin oletuksen mukaan x ∈ A ∩ B.; Koska x ∈ A ∩ B, niin x ∈ A ja väite pätee.; On osoitettu, että A ∪ B ⊂ A.; Oletetaan, että x ∈ A.; Yhdisteen määritelmän nojalla x ∈ A ∪ B.; On osoitettu, että A ⊂ A ∪ B.; Koska A ∪ B ⊂ A ja A ⊂ A ∪ B, niin A ∪ B = A.
Feedback: Todistus. Oletetaan, että \(A \cap B = B\). Halutaan osoittaa, että tällöin \(A \cup B = A\). Osoitetaan ensin, että \(A \cup B \subset A\). Oletetaan, että \(x \in A \cup B\). Yhdisteen määritelmän nojalla \(x \in A\) tai \(x \in B\). Tutkitaan tapaukset: 1. Jos \(x \in A\), väite pätee. 2. Jos \(x \in B\), niin oletuksen \(A \cap B = B\) nojalla \(x \in A \cap B\). Siis \(x \in A\). On osoitettu, että \(A \cup B \subset A\). Osoitetaan sitten, että \(A \subset A \cup B\). Oletetaan, että \(x \in A\). Yhdisteen määritelmän nojalla \(x \in A \cup B\). On osoitettu, että \(A \subset A \cup B\). Siis \(A \cup B = A\).

Q: Oletetaan, että \(A, B\) ja \(C\) ovat joukkoja ja \(B \neq \emptyset\). Pyrkimyksenä on osoittaa, että jos \(A \times B \subset B \times C\), niin \(A  \subset C\).

Laita todistuksen vaiheet oikeaan järjestykseen.

Todistus

[...]

[...]

[...]

           \( \vdots \)

[...]

Väite on todistettu.
Also offered: Oletetaan, että A ⊂ C.; Oletetaan, että (a, b) ∈ A × B.; Näytetään, että A × B ⊂ B × C.; Siis (a, b) ∈ B × C.
A: Oletetaan, että A × B ⊂ B × C.; Näytetään, että A ⊂ C.; Oletetaan, että a ∈ A.; Siis a ∈ C.
Feedback: Todistus Oletetaan, että \(A \times B \subset B \times C\). Näytetään, että \(A \subset C\). Oletetaan, että \(a \in A\). \( \vdots \) Siis \(a \in C\). Väite on todistettu.