Title: IMA1 (viikko 1) muut

Täydennä seuraavassa päättelyssä jokaisen ekvivalenssin kohdalle käytetty päättelysääntö.

\((\neg p \leftrightarrow q) \Leftrightarrow(p \leftrightarrow \neg q)\)

Todistus.

\(\hphantom{\leftrightarrow} \neg p \leftrightarrow q\)

\(\neg(p \leftrightarrow q) \Leftrightarrow(p \wedge \neg q) \vee(q \wedge \neg p)\)

Todistus.

\(\hphantom{\leftrightarrow} \neg(p \leftrightarrow q)\)

\((p \rightarrow(q \rightarrow r)) \Leftrightarrow((q \wedge p) \rightarrow r)\)

Todistus.

\(\hphantom{\leftrightarrow} p \rightarrow(q \rightarrow r)\)

\((\neg(p \vee(\neg p \wedge \neg q)) \wedge(\neg p \rightarrow r)) \Rightarrow q \vee r\)

Todistus.

\(\hphantom{\leftrightarrow} \neg(p \vee(\neg p \wedge \neg q)) \wedge(\neg p \rightarrow r)\)

\(((p \vee \neg q) \wedge(r \vee \neg p)) \wedge q \Rightarrow r\)

Todistus.

\(\hphantom{\leftrightarrow} ((p \vee \neg q) \wedge(r \vee \neg p)) \wedge q\)

\(\Leftrightarrow(\neg p \rightarrow q) \wedge(q \rightarrow \neg p)\)
\(\Leftrightarrow(\neg \neg p \vee q) \wedge(\neg q \vee \neg p)\)
\(\Leftrightarrow(p \vee q) \wedge(\neg q \vee \neg p)\)
\(\Leftrightarrow(q \vee p) \wedge(\neg p \vee \neg q)\)
\(\Leftrightarrow(\neg \neg q \vee p) \wedge(\neg p \vee \neg q)\)
\(\Leftrightarrow(\neg q \rightarrow p) \wedge(p \rightarrow \neg q)\)
\(\Leftrightarrow(p \rightarrow \neg q) \wedge(\neg q \rightarrow p)\)
\(\Leftrightarrow p \leftrightarrow \neg q\)

\(\Leftrightarrow \neg((p \rightarrow q) \wedge(q \rightarrow p))\)
\(\Leftrightarrow \neg((\neg q \rightarrow \neg p) \wedge(\neg p \rightarrow \neg q))\)
\(\Leftrightarrow \neg((\neg \neg q \vee \neg p) \wedge(\neg \neg p \vee \neg q))\)
\(\Leftrightarrow \neg((q \vee \neg p) \wedge(p \vee \neg q))\)
\(\Leftrightarrow(\neg(q \vee \neg p)) \vee(\neg(p \vee \neg q))\)
\(\Leftrightarrow(\neg q \wedge \neg \neg p) \vee(\neg p \wedge \neg \neg q)\)
\(\Leftrightarrow(\neg q \wedge p) \vee(\neg p \wedge q)\)
\(\Leftrightarrow(\neg p \wedge q) \vee(\neg q \wedge p)\)

\(\Leftrightarrow \neg p \vee(q \rightarrow r)\)
\(\Leftrightarrow(q \rightarrow r) \vee \neg p\)
\(\Leftrightarrow(\neg q \vee r) \vee \neg p\)
\(\Leftrightarrow \neg q \vee(r \vee \neg p)\)
\(\Leftrightarrow \neg q \vee(\neg p \vee r)\)
\(\Leftrightarrow(\neg q \vee \neg p) \vee r\)
\(\Leftrightarrow \neg(q \wedge p) \vee r\)
\(\Leftrightarrow(q \wedge p) \rightarrow r\)

\(\Leftrightarrow(\neg p \wedge \neg(\neg p \wedge \neg q)) \wedge(\neg p \rightarrow r)\)
\(\Leftrightarrow \neg p \wedge(\neg(\neg p \wedge \neg q) \wedge(\neg p \rightarrow r))\)
\(\Leftrightarrow \neg p \wedge(\neg(\neg p \wedge \neg q) \wedge(\neg \neg p \vee r))\)
\(\Leftrightarrow \neg p \wedge((\neg \neg p \vee \neg \neg q) \wedge(\neg \neg p \vee r))\)
\(\Leftrightarrow \neg p \wedge(\neg \neg p \vee(\neg \neg q \wedge r))\)
\(\Leftrightarrow \neg p \wedge(\neg p \rightarrow(\neg \neg q \wedge r))\)
\(\Leftrightarrow \neg p \wedge(\neg p \rightarrow(q \wedge r))\)
\(\Rightarrow q \wedge r\)

\(\Leftrightarrow(p \vee \neg q) \wedge((r \vee \neg p) \wedge q)\)
\(\Leftrightarrow(p \vee \neg q) \wedge((r \vee \neg p) \wedge q)\)
\(\Leftrightarrow(p \vee \neg q) \wedge(q \wedge(r \vee \neg p))\)
\(\Leftrightarrow(q \rightarrow p) \wedge(q \wedge(p \rightarrow r))\)
\(\Leftrightarrow((q \rightarrow p) \wedge q) \wedge(p \rightarrow r)\)
\(\Leftrightarrow(q \wedge(q \rightarrow p)) \wedge(p \rightarrow r)\)
\(\Rightarrow p \wedge(p \rightarrow r)\)
\(\Rightarrow r\)

Valitse jokaiseen kohtaan pudotusvalikosta vastaus ennen kuin painat vastauksen lukitusnappia.

Todista seuraava väite induktiotodistuksella:

\([value]\) on jaollinen luvulla \([value]\) kaikilla luonnollisilla luvuilla \(n\), kun \(n\geq [value]\).

Huom. Väite saattaa päteä pienemmilläkin \(n\):n arvoilla, mutta todistetaan se niin kuin pienin pätevä arvo olisi \(n=[value]\).

Alkuaskel:

Kun \(n=[value]\), on \([value] =\)
joka jaollinen luvulla \([value]\).

Induktio-oletus:

Oletetaan, että on olemassa sellainen \(k\in \mathbb{N}\) , jolle \([value]\) on jaollinen luvulla \([value]\) eli \([value] =\)
(Kirjoita \([value]\):lla jaollisen luvun esitys käyttäen muuttujaa \(m\).)

Induktioaskel:

Kun \(n=k+1\), niin eli \([value]\) \((k+1)^[value]-(k+1)\) \(=[value]\)\(\Big(\)\(\Big)\), missä oikealla puolella suluissa oleva lauseke esittää luonnollista lukua.
(Anna sulkujen sisään muuttujista \(k\) ja \(m\) riippuva mahdollisimman sievennetty muoto. Huomaa, että luvulla \([value]\) kertominen on jo huomioitu sulkujen edessä.)

Todista seuraava väite induktiotodistuksella:

\([value]^n+[value]\) on jaollinen luvulla \([value]\) kaikilla luonnollisilla luvuilla \(n\), kun \(n\geq [value]\).

Huom. Väite saattaa päteä pienemmilläkin \(n\):n arvoilla, mutta todistetaan se niin kuin pienin pätevä arvo olisi \(n=[value]\).

Alkuaskel:

Kun \(n=[value]\), on \([value]^n+[value] =\)
joka jaollinen luvulla \([value]\).

Induktio-oletus:

Oletetaan, että on olemassa sellainen \(k\in \mathbb{N}\) , jolle \([value]^k + [value]\) on jaollinen luvulla \([value]\) eli \([value]^n + [value] =\)
(Kirjoita \([value]\):lla jaollisen luvun esitys käyttäen muuttujaa \(m\).)

Induktioaskel:

Kun \(n=k+1\), niin eli \([value]^{k+1} + [value] = [value](\)\()\), missä oikealla puolella suluissa oleva lauseke esittää luonnollista lukua.
(Anna sulkujen sisään muuttujista \(k\) ja \(m\) riippuva mahdollisimman sievennetty muoto. Huomaa, että luvulla \([value]\) kertominen on jo huomioitu sulkujen edessä.)

Järjestä suoran todistuksen osat oikeaan järjestykseen.

Sijoita luvut 1-7 vastauslaatikoihin ilmaisemaan järjestystä.

Neliö tarkoittaa tulosta, joka saadaan, kun luku kerrotaan itsellään.

Väite: Mikä tahansa pariton kokonaisluku on kahden kokonaisluvun neliön erotus.

Luku \(a\in \mathbb{N}\) on luvun \(b\in \mathbb{N}\) tekijä, jos \(b=ak\) jollekin \(k\in \mathbb{N}\).

Väite: Jos \(a\) on \(b\):n tekijä ja \(b\) on \(c\):n tekijä, niin \(a\) on \(c\):n tekijä.

Yhdistetty luku on luonnollinen luku, joka voidaan jakaa tasan muillakin luvuilla kuin ykkösellä ja itsellään (ts. ei ole alkuluku). Jako menee tasan, jos jakolaskun tulos eli osamäärä on kokonaisluku.

Väite: Luonnollinen luku, jossa on kahden ykkösen välissä \(3n-1\) nollaa (missä \(n\in \mathbb{N}\)), esim. \(1001\), on yhdistetty luku.

Todistus.

Olkoon \(n\in \mathbb{Z}\).
Tällöin \(x=2n+1\) on pariton kokonaisluku.
Kaikki parittomat kokonaisluvut voidaan esittää muodossa \(x\).
Lisäksi, koska \(n\in \mathbb{Z}\), niin \(n+1\in \mathbb{Z}\).
Luvun \(n+1\) neliö on \((n+1)^2=n^2+2n+1\).
Ratkaistaan tästä yhtälöstä \(2n+1= (n+1)^2-n^2\).
Näin ollen pariton kokonaisluku \(x\) on kahden kokonaisluvun neliön erotus.
Olkoon \(a,b,c \in \mathbb{N}\).
Olkoon lisäksi \(a\) luvun \(b\) tekijä ja \(b\) luvun \(c\) tekijä.
Koska \(a\) on \(b\):n tekijä, on olemassa \(k_1\in \mathbb{N}\) siten, että \(b=ak_1\).
Koska \(b\) on \(c\):n tekijä, on olemassa \(k_2\in \mathbb{N}\) siten, että \(c=bk_2\).
Tällöin \(c=bk_2=(ak_1)k_2=a(k_1 k_2)\).
Tässä esityksessä \(k_1\in \mathbb{N}\) ja \(k_2 \in \mathbb{N}\), joten myös \(k=k_1k_2\in \mathbb{N}\).
Näin ollen \(a\) on \(c\):n tekijä.
Olkoon \(n\in \mathbb{N}\) ja \(k=100\cdots 01\in \mathbb{N}\), missä esiintyvien nollien määrä on \(3n-1\).
Kirjoitetaan \(k\) muodossa \(k=10^{3n}+1=(10^n)^3+1^3\).
Käytetään kaavaa \(a^3+b^3=(a+b)(a^2-ab+b^2)\).
Saadaan \(k=10^{3n}+1^3=(10^n+1)(10^{2n}-10^n+1^2)\).
Tässä \(10^n+1\in \mathbb{N}\) ja \(10^{2n}-10^n+1^2\in \mathbb{N}\).
Lisäksi, koska \(n\in\mathbb{N}\), niin \(10^n+1\neq 1\) ja \(10^n+1\neq 10^{3n}+1=k\).
Siis luvulla \(k\) on tekijänä luku \(10^n+1\), joka ei ole \(k\) eikä ykkönen, joten \(k\) on yhdistetty luku.