Title: Logiikka / todistaminen

\(\)

Alla on "todistettu" väite: . Minkä välivaiheen johto on virheellinen?

Virhe tapahtuu kun väitetään, että aikaisemmista tuloksista ja oletuksista seuraa rivillä oleva väite.
Feedback: Malliratkaisu: Virhe tehdään kun väitetään, että epäyhtälöstä \( ([value]+[value])^2 \geq 4\cdot [value]\cdot [value] \) seuraa \( ([value]+[value]) \geq 2\cdot \sqrt{[value]\cdot [value]} \) koska \([value]+[value]\) voi olla negatiivinen ja oikea johtopäätös on \( \left|[value]+[value]\right | \geq 2\cdot \sqrt{[value]\cdot [value]}. \) Virhe tehdään kun väitetään, että kaavasta \( [value]+[value] \neq [value] \) seuraa \( ([value]-[value])\cdot([value]+[value])\neq ([value]-[value])\cdot [value] \) koska näin on ainoastaan kun \([value]\neq [value]\) ja muuten tulos on \(0=0\). Virhe tehdään kun väitetään, että kaavasta \( [value]^2 = [value]\cdot [value] \) seuraa \( [value]= [value] \) koska tässä jaetaan luvulla \(0=x\). Virhe tehdään kun väitetään, että epäyhtälöstä \( [value] < [value] \) seuraa \( [value]\cdot \log_{[value]}\left(\frac 1{[value]}\right) < [value]\cdot \log_{[value]}\left (\frac 1{[value]}\right) \) koska tässä kerrotaan negatiivisella luvulla \(\log_{[value]}\left (\frac 1{[value]}\right)\) jolloin epäyhtälön suunta vaihtuu. Virhe tehdään kun väitetään, että epäyhtälöstä \( [value] > [value] \) seuraa \( [value]\cdot\log_{[value]}\left (\frac 1{[value]}\right) > [value]\cdot \log_{[value]}\left (\frac 1{[value]}\right) \) koska tässä kerrotaan negatiivisella luvulla \(\log_{[value]}\left (\frac 1{[value]}\right)\) jolloin epäyhtälön suunta vaihtuu.

Tässä tehtävässä todistetaan lause käyttäen aksiomeja ja tehtävänä on määrittää mikä on perustelu jokaiselle askeleelle.

Seuraavat päättelysäännöt ovat käytettävissä (mutta muitakin vaihtoehtoja on olemassa) ja esimerkiksi sääntö a sanoo, että jos on tosi ja on tosi niin silloin on tosi. Huomaa, että lauseena \(x\) voidaan käyttää myös lausetta \(\Not q\) jolloin lauseesta \(\Not x\) tulee lause \(\Not(\Not q)=q\) ja lauseen \(x\Or y\) paikalla voidaan käyttää lausetta \(y\Or x\) sekä lauseen \(x\And y\) paikalla lausetta \(y\And x\).

Todistus on seuraavanlainen ja nyt sinun pitää antaa perustelut, eli kirjoita päättelysäännön kirjain ja niiden jo todistettujen tai oletettujen lauseiden numerot, joita päättelysäännössä käytetään. Esimerkiksi \(a12\) tai \(a,1,2\) tai \(12a\) jos sääntöä \(a\) sovelletaan lauseisiin \(1\) ja \(2\).

\(\)

Mitkä seuraavista implikaatioista ovat tosia ja mitkä epätosia?
Feedback: \(\) Malliratkaisu: Koska joten implikaatio on . Koska joten implikaatio on . Koska joten implikaatio on .

Tässä tehtävänä on osoittaa, että \([value]^{n+2} + [value]^{2\cdot n+1}\) on jaollinen luvulla \([value]\) kaikilla \(n\geq 0\) (eli kaikilla \(n\in \mathbb N_0\) on olemassa \(m\in \mathbb Z\) siten, että \([value]^{n+2} + [value]^{2\cdot n+1}= m\cdot [value]\)).

Tällaisessa tapauksessa on luonnollista (ainakin yrittää) käyttää induktiopäättelyä ja väite \(P(n)\), joka meidän pitää osoittaa oikeaksi on siis \[ P(n):\quad [value]^{n+2} + [value]^{2\cdot n+1}= m_n\cdot [value], \quad m_n\in \mathbb Z. \]
Ensin tarkistamme että \(P(0)\) on tosi ja toteamme, että
\( [value]^{0+2} + [value]^{2\cdot 0+1}=~\)\(\cdot [value]\)

Seuraavaksi tarkistamme, että implikaatio \(P(k)\to P(k+1)\) on tosi, eli oletamme, että \(k\geq 0\), \(P(k)\) on tosi ja osoitamme, että silloin \(P(k+1)\) on myös tosi.

Jos induktiopäättelystä todella on hyötyä (siis verrattuna siihen, että suoraan osoitamme, että \(P(n)\) on tosi kaikilla \(n\geq 0\)) meidän pitää käyttää hyväksi oletusta, että \(P(k)\) on tosi ja siitä syystä kirjoitamme (missä käytämme hyväksi tulosta \([value]^2-[value]=[value]\))
\([value]^{(k+1)+2} + [value]^{2\cdot (k+1)+1} = [value]^{k+3}+ [value]^{2\cdot k+3} = \)
\(~\cdot \Bigl( [value]^{k+2}+ [value]^{2\cdot k+1}\Bigr ) +~\) \(~ \cdot [value]\).
(Kirjoita potenssi \(a^b\) muodossa a^b ja käytä sulkuja ja *-merkkiä tarvittaessa.)

Induktio-oletuksen \(P(k)\) nojalla on olemassa kokonaisluku \(m\) siten, että \([value]^{k+2}+ [value]^{2\cdot k+1}= m\cdot [value]\) joten voimme päätellä, että
\([value]^{(k+1)+2} + [value]^{2\cdot (k+1)+1} =~\) \(~ \cdot [value]\)
Näin ollen myös väite \(P(k+1)\) pätee ja induktioperiaatteen nojalla seuraa, että väite \(P(n)\) on tosi kaikilla \(n\geq 0\).

Selvitä, onko lause tosi vai epätosi:

\( \begin{align*} & \textbf{(a) } \exists\, x\in[1,[value]]:\ [value] \qquad \textbf{(b) } \forall\, x\in\mathbb{R}:\ x^2-2x+1=0\\ & \textbf{(c) } \exists\, x\in\mathbb{R}:\ x^2-2x+1=0 \quad \textbf{(d) } \forall\, x\in\mathbb{N}\ \exists\,y\in\mathbb{R}:\ \frac{y}{x}=3 \end{align*} \)

Tässä merkintä \( \mathbb{N} \) tarkoittaa kokonaislukuja lähtien luvusta \( 1:  1, 2, 3 \ldots \)

\( \textbf{(a)} \) \( \quad \) \( \textbf{(b)} \)

\( \textbf{(c)} \) \( \quad \) \( \textbf{(d)} \)
Feedback: Mallivastaus: \( \textbf{(a)} \) [value]. Suomeksi väite tarkoittaa: Väliltä \([1,[value]]\) löytyy reaaliluku, joka on aidosti [value] kuin [value]. Huomaamme, että tämä väite on [value] kaikilla \(x\in [1,[value]]\), eli väite on /* tosi */ [value]. \( \textbf{(b)} \) Epätosi. Väite ei ole tosi, valitsemalla esimerkiksi \(x=0\). \( \textbf{(c)} \) Tosi. Yhtälön ratkaisuiksi saadaan \[ x=\frac{2\pm\sqrt{(-2)^2-4\cdot 1\cdot 1}}{2}=1. \] Eli nähdään, että löytyy \(x=1\in\mathbb{R}\), jolla polynomi saa arvon \(0\). Näin ollen väite on tosi. \( \textbf{(d)} \) Tosi. Koska \(x\) on luonnollinen luku (eli \(1,2,3,....\)), niin erityisesti \(x\neq 0\) ja jakolasku \(y/x\) on aina hyvin määritelty. Jos \(x\):ää kohden valitaan \(y=3x\in\mathbb{R}\), nähdään, että yhtälö toteutuu \[ \frac{y}{x}=\frac{3x}{x}=3, \] ja väite on tosi.

Osoita totuustaulutarkastelun avulla:

\(\textbf{(a)}\) Osittelulaki: \( p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r) \). Ts. osoita, että \(p \lor (q \land r)\) ja \((p \lor q) \land (p \lor r) \) ovat loogisesti ekvivalentteja.

\(\textbf{(b)}\) Suora todistus: \( p \land (p \to q) \Rightarrow q.\)

Vihje: Kannattaa ratkaista tehtävä ensin paperilla ja sijoittaa sitten puuttuvat alkiot STACKiin.

\(\textbf{(a)}\) Täytä allaolevaan totuustauluun puuttuvat alkiot (siis x:llä merkityt). Alkiot ovat joko nollia tai ykkösiä.

\(\begin{array}{c|c|c|c|c|c|c|c|c} p & q & r & q \land r & p \lor q & p \lor r & p \lor (q \land r) & (p \lor q) \land (p \lor r) \quad (* & p \lor (q \land r) \leftrightarrow (p \lor q) \land (p \lor r) \quad (*** \\ \hline 1 & 1 & 1 & x & x & x & x & x & x \\ 1 & 1 & 0 & x & x & x & x & x & x \\ 1 & 0 & 1 & x & x & x & x & x & x \\ 1 & 0 & 0 & x & x & x & x & x & x \\ 0 & 1 & 1 & x & x & x & x & x & x \\ 0 & 1 & 0 & x & x & x & x & x & x \\ 0 & 0 & 1 & x & x & x & x & x & x \\ 0 & 0 & 0 & x & x & x & x & x & x \\ \end{array}\)

Allaolevassa taulukossa on tilan puutteen vuoksi kaksi viimeistä saraketta merkitty yhdellä ja kolmella tähdellä. Katso ylläolevasta taulukosta, mitä niiden kohdalla kuuluu olla.

\(\quad p \quad | \quad q \quad | \quad r \quad\) | \( \quad q \land r \quad \, \) | \(p \lor q \) | \( p \lor r \) | \(p \lor (q \land r) \) | \( * \) | \(*** \)
\(\quad 1 \quad | \quad 1 \quad | \quad 1 \quad\) |
\(\quad 1 \quad | \quad 1 \quad | \quad 0 \quad\)
\(\quad 1 \quad | \quad 0 \quad | \quad 1 \quad\)
\(\quad 1 \quad | \quad 0 \quad | \quad 0 \quad\)
\(\quad 0 \quad | \quad 1 \quad | \quad 1 \quad\)
\(\quad 0 \quad | \quad 1 \quad | \quad 0 \quad\)
\(\quad 0 \quad | \quad 0 \quad | \quad 1 \quad\)
\(\quad 0 \quad | \quad 0 \quad | \quad 0 \quad\)

\(\textbf{(b)}\) Täytä allaolevan totuustaulun puuttuvat alkiot. Alkiot ovat joko nollia tai ykkösiä.

\(\quad p \quad | \quad q \quad\) | \(\quad \quad p \to q \quad \quad\) | \(p \land (p \to q) \quad \) | \(p \land (p \to q) \Rightarrow q \)
\(1 \quad | \quad 1\) |
\(1 \quad | \quad 0\)
\(0 \quad | \quad 1\)
\(0 \quad | \quad 0\)
Feedback: Mallivastaus. \(\textbf{(a)}\) \( \begin{array}{c|c|c|c|c|c|c|c|c} p & q & r & q \land r & p \lor q & p \lor r & p \lor (q \land r) & (p \lor q) \land (p \lor r) & p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r) \\\hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array}\) \( \textbf{(b)} \) \( \begin{array}{c|c|c|c|c|c} p & q & p \to q & p \land (p \to q) & p \land (p \to q) \Rightarrow q \\\hline 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ \end{array} \)

Täydennä lauseen \(A\) totuustaulukko. Kirjoita jokaiseen vastausruutuun joko 1 (tosi) tai 0 (epätosi).

\(A\colon [value]\)

\(\ p\ \) | \(\ q\ \) | \(\ [value]\ \) | \(\ [value]\ \) | \(\ [value]\ \) | \(\ [value]\ \) | \(\ A\ \)
1 | 1 |  |  |  |  |
1 | 0 |  |  |  |  |
0 | 1 |  |  |  |  |
0 | 0 |  |  |  |  |

Onko \(A\) tautologia?

Syötä jokaiseen vastausruutuun vastaus ja valitse viimeisen kysymyksen vastaus ennen kuin painat vastauksen lukitusnappia, muuten tarkastus ei toimi.