Matematická logika

Portál středoškolské matematiky

Úlohy k procvičení

Dokažte základní vztahy pro sudá a lichá čísla, tj. že platí: Součet (a také rozdíl a součin) každých dvou sudých čísel je číslo sudé, součet (a také rozdíl) každých dvou lichých čísel je číslo sudé a že součin dvou lichých čísel je číslo liché.

Dokážeme přímo, stačí si zapsat sudá čísla ve tvaru 2\(k\), lichá čísla ve tvaru (2\(k\) + 1), kde \(k\) je nějaké přirozené číslo (popř. nula). Ukažme např. že součet každých dvou lichých čísel \(a\) a \(b\) je sudé číslo:

Nechť je \(a\) = 2\(k\) + 1 a \(b\) = 2\(s\) + 1, kde \(k\),\(s\)\(\in\)\(\mathbb{N}\)\(_0\). Pak můžeme psát:

\(a\) + \(b\) = (2\(k\) + 1) + (2\(s\) + 1) = 2\(k\) + 2\(s\) + 2 = 2(\(k\) + \(s\) + 1)

Došli jsme k výrazu, který je jistě dělitelný dvěma a tedy sudý, věta je dokázána. Ostatní věty z tohoto cvičení bychom dokazovali analogicky.
Dokažte: \(\forall (p, q \in \mathbb{R}^+)\): ½ · (\(p\) + \(q\)) ≥ \(\sqrt{p · q}\).

Dokážeme přímo. Rozbor:

½ · (\(p\) + \(q\)) ≥ \(\sqrt{p · q}\)
\(p\) + \(q\) ≥ 2\(\sqrt{p · q}\)
\(p\) + \(q\) − 2\(\sqrt{p · q}\) ≥ 0
(\(\sqrt{p}\))\(^2\) − 2\(\sqrt{p}\) · \(\sqrt{q}\) + (\(\sqrt{q}\))\(^2\) ≥ 0
(\(\sqrt{p}\) − \(\sqrt{q}\))\(^2\) ≥ 0

Poslední řádek rozboru je zcela jistě pravdivý výrok pro každá dvě kladná reálná čísla \(p\) a \(q\), vlastní důkaz provedeme otočením postupu rozboru (což můžeme udělat díky tomu, že jsme provádli pouze ekvivalentní úpravy).
Dokažte: \(\forall (r \in \mathbb{R})\): sin \(r\) + cos \(r\) ≠ 1,5.

Dokážeme sporem. Předpokládejme, že existuje \(r\)\(\in\)\(\mathbb{R}\) takové, že sin \(r\) + cos \(r\) = 1,5. Pak můžeme psát:

sin \(r\) + cos \(r\) = 1,5
(sin \(r\) + cos \(r\))\(^2\) = (1,5)\(^2\)
(sin \(r\))\(^2\) + 2 · sin \(r\) · cos \(r\) + (cos \(r\))\(^2\) = 2,25
1 + 2 · sin \(r\) · cos \(r\) = 2,25
2 · sin \(r\) · cos \(r\) = 1,25
sin 2\(r\) = 1,25

My však víme, že sinus reálného čísla nemůže být větší než 1. Dostáváme spor.
Dokažte: \(\forall (a \in \mathbb{N})\): 3\(\mid\)\(a\) \(\Leftrightarrow\) [3\(∤\)(\(a\)\(^3\) + 1) \(\wedge\) 3\(∤\)(\(a\)\(^3\) + 2)].

Věta je formulována jako ekvivalence. Musíme tedy dokázat implikace „oběma směry“. Nejprve dokážeme, větu:

\(\forall (a \in \mathbb{N})\): 3\(\mid\)\(a\) \(\Rightarrow\) [3\(∤\)(\(a\)\(^3\) + 1) \(\wedge\) 3\(∤\)(\(a\)\(^3\) + 2)]

Tuto implikaci dokážeme přímo. Jestliže 3\(\mid\)\(a\), pak existuje přirozené \(k\) tak, že \(a\) = 3\(k\). Nyní zkusme (3\(k\)) dosadit za \(a\) do výrazů (\(a\)\(^3\) + 1) a (\(a\)\(^3\) + 2):

(3\(k\))\(^3\) + 1 = 27\(k\)\(^3\) + 1 = 3\(r\) + 1, kde \(r\) = 9\(k\)\(^3\)
(3\(k\))\(^3\) + 2 = 27\(k\)\(^3\) + 2 = 3\(s\) + 2, kde \(s\) = 9\(k\)\(^3\)

V obou případech jsme došli k číslu, které evidentně není dělitelné třemi, čímž jsme tuto implikaci dokázali.

Nyní dokažme implikaci obrácenou, tj.:

\(\forall (a \in \mathbb{N})\): [3\(∤\)(\(a\)\(^3\) + 1) \(\wedge\) 3\(∤\)(\(a\)\(^3\) + 2)] \(\Rightarrow\) 3\(\mid\)\(a\)

Tuto implikaci budeme dokazovat nepřímo, pomocí implikace obměněné. Vytvořme tedy obměněnou implikaci:

\(\forall (a \in \mathbb{N})\): 3\(∤\)\(a\) \(\Rightarrow\) [3\(\mid\)(\(a\)\(^3\) + 1) \(\vee\) 3\(\mid\)(\(a\)\(^3\) + 2)]

Vyjdeme z předpokladu, že \(a\) není dělitelné třemi. Pak je toto \(a\) buď ve tvaru (3\(k\) + 1) nebo (3\(k\) + 2), kde \(k\) je nějaké přirozené číslo nebo nula. Je také dobré si uvědomit, že „pravá strana“ implikace má tvar disjunkce, stačí nám tedy dokázat pravdivost jen jednoho z jí spojovaných výroků.

Nejprve předpokládejme, že \(a\) = 3\(k\) + 1 a zkusme tento výraz dosadit do výrazu (\(a\)\(^3\) + 2):

(\(k\) + 1)\(^3\) + 2 = 27\(k\)\(^3\) + 27\(k\)\(^2\) + 9\(k\) + 1 + 2 = 3(9\(k\)\(^3\) + 9\(k\)\(^2\) + 3\(k\) + 1)

Vidíme, že je-li \(a\) = 3\(k\) + 1, pak číslo (\(a\)\(^3\) + 2) je dělitelné třemi.

Stejným způsobem se dokáže, že je-li \(a\) = 3\(k\) + 2, pak číslo (\(a\)\(^3\) + 1) je dělitelné třemi. Díky tomu, že na „pravé straně“ implikace máme disjunkci, nemusíme již dokazovat, zda je pro \(a\) = 3\(k\) + 1 číslo (\(a\)\(^3\) + 1) dělitelné třemi a zda je pro \(a\) = 3\(k\) + 2 číslo (\(a\)\(^3\) + 2) (ani by se nám to dokázat nepovedlo).

Dokázali jsme implikace „oběma směry“, věta je tak dokázána.
Dokažte: \(\forall (x \in \mathbb{R})\): \(x\)\(^2\)/(1 + \(x\)\(^4\)) ≤ ½.

Dokážeme přímo. Rozbor:

\(x\)\(^2\)/(1 + \(x\)\(^4\)) ≤ ½
2\(x\)\(^2\) ≤ 1 + \(x\)\(^4\)
0 ≤ 1 − 2\(x\)\(^2\) + \(x\)\(^4\)
0 ≤ (1 − \(x\)\(^2\))

Poslední řádek rozboru je zcela jistě pravdivý výrok pro libovolné reálné \(x\), protože druhá mocnina reálného čísla je vždy číslo nezáporné. Vlastní důkaz provedeme otočením postupu rozboru (opět jsme prováděli pouze ekvivalentní úpravy, a tak tuto metodu můžeme použít).
Dokažte: \(\forall (m \in \mathbb{N})\): 2\(∤\)(\(m\)\(^3\) − 6\(m\) + 2\(m\) − 10) \(\Rightarrow\) 2\(∤\)\(m\).

Použijeme důkaz obměněnou implikací, budeme tedy dokazovat větu:

\(\forall (m \in \mathbb{N})\): 2\(\mid\)\(m\) \(\Rightarrow\) 2\(\mid\)(\(m\)\(^3\) − 6\(m\) + 2\(m\) − 10)

Číslo \(m\) je sudé, tedy \(m\) = 2\(k\), kde \(k\) je nějaké přirozené číslo. Pak:

\(m\)\(^3\) − 6\(m\) + 2\(m\) − 10 = 8\(k\)\(^3\) − 72\(k\)\(^2\) + 4\(k\) − 10 = 2 · (4\(k\)\(^3\) − 36\(k\)\(^2\) + 2\(k\) − 5)

Číslo (\(m\)\(^3\) − 6\(m\) + 2\(m\) − 10) je tedy také sudé, čímž je věta dokázána.
Dokažte: \(\forall (x \in \mathbb{R})\): 4 cos \(x\) + cos 2\(x\) ≥ −3.

Využijeme přímého důkazu, nejprve provedeme rozbor:

4 cos \(x\) + cos 2\(x\) ≥ −3
4 cos \(x\) + cos\(^2\) \(x\) − sin\(^2\) \(x\) ≥ −3
4 cos \(x\) + cos\(^2\) \(x\) − (1 − cos\(^2\) \(x\)) ≥ −3
2 + 4 cos \(x\) + 2 cos\(^2\) \(x\) ≥ 0
1 + 2 cos \(x\) + cos\(^2\) \(x\) ≥ 0
(1 + cos \(x\))\(^2\) ≥ 0

Výraz na posledním řádku platí pro všechna reálná čísla, vlastní důkaz získáme otočením postupu rozboru (opět jsme prováděli pouze ekvivalentní úpravy, díky čemuž můžeme postup otočit).
Dokažte: \(\forall (n \in \mathbb{N})\): 2\(∤\)\(n\) \(\Leftrightarrow\) 2\(∤\)\(n\)\(^2\).

Jde o ekvivalenci, je tedy nutné dokázat dvě implikace. Implikaci \(\forall (n \in \mathbb{N})\): 2\(∤\)\(n\) \(\Rightarrow\) 2\(∤\)\(n\)\(^2\) dokážeme přímo, pro důkaz implikace opačným směrem využijeme metodu obměněné implikace. Postupujeme obdobně jako v Příkladu 9.
Dokažte, že platí: \(\sqrt{11 + \sqrt{10}}\) < 1 + \(\sqrt{11 − \sqrt{10}}\).

Ekvivalentními úpravami dojdeme k pravdivému výroku 41 < 44, postup je analogický jako v Příkladu 1.
Dokažte sporem větu z Příkladu 13, tj. \(\forall (n \in \mathbb{N})\): 2\(\mid\)(\(n\)\(^3\) + 11\(n\)).

Máme přímo určeno, jakým typem důkazu máme tvrzení dokázat. Budeme tedy předpokládat, že platí negace dané věty a využijeme poznatku, že číslo \(n\) je buď sudé, nebo liché. Vlastní důkaz bude analogický jako v Příkladu 6, kde jsme dokazovali velmi podobné tvrzení.
Dokažte matematickou indukcí větu z Příkladu 6, tj. \(\forall (n \in \mathbb{N})\): 2\(\mid\)(\(n\)\(^3\) − 11\(n\)).

Máme přímo určeno, jakým typem důkazu máme tvrzení dokázat. Důkaz provedeme obdobně jako v Příkladu 13.
Dokažte: \(\forall (m \in \mathbb{N})\): 3\(\mid\)(\(m\)\(^2\) + 1) \(\Rightarrow\) 6\(∤\)\(m\).

Použijeme důkaz obměněnou implikací. Obměněná implikace \(\forall (m \in \mathbb{N})\): 6\(\mid\)\(m\) \(\Rightarrow\) 3\(∤\)(\(m\)\(^2\) + 1) se nám bude mnohem lépe dokazovat (budeme moci vycházet z poznatku 6\(\mid\)\(m\)).

Předpokládejme tedy, že 6\(\mid\)\(m\). Pak \(m\) = 6\(k\), kde \(k\)\(\in\)\(\mathbb{N}\). Pak platí:

\(m\)\(^2\) + 11\(m\) = (6\(k\))\(^2\) + 1 = 36\(k\)\(^2\) + 1

Dále můžeme říci, že (12\(k\)\(^2\)) je nějaké přirozené číslo \(r\). Pak \(m\)\(^3\) + 11\(m\) = 36\(k\)\(^2\) + 1 = 3\(r\) + 1, což je jistě číslo, které není dělitelné třemi. Dokázali jsme obměněnou implikaci a tedy i původní větu.
Dokažte: \(\forall (n \in \mathbb{N})\): 1 + 3 + 5 + … + (2\(n\) − 1) = \(n\)\(^2\).

Tuto větu budeme dokazovat matematickou indukcí. Pro číslo jedna věta platí: 2 · 1 − 1 = 1\(^2\).

V indukčním kroku předpokládáme, že tvrzení platí pro nějaké přirozené \(k\), tedy platí 1 + 3 + 5 + … + (2\(k\) − 1) = \(k\)\(^2\). S tímto předpokladem se podívejme na situaci pro (\(k\) + 1):

1 + 3 + 5 + … + [2(\(k\) + 1) − 1] = 1 + 3 + 5 + … + (2\(k\) − 1) + [2(\(k\) + 1) − 1] = \(k\)\(^2\) + (2\(k\) + 2 − + 1) = \(k\)\(^2\) + 2\(k\) + 1 = (\(k\) + 1)\(^2\)

Modrou barvou je opět naznačeno použití předpokladu. Ukázali jsme, že při jeho platnosti věta platí i pro (\(k\) + 1). Důkaz matematickou indukcí je hotov.
Dokažte: \(\forall (n \in \mathbb{N})\): 5\(\mid\)(\(n\)\(^5\) + 4\(n\)) .

Použijeme matematickou indukci. Pro číslo 1 tvrzení platí: 1\(^5\) + 4 · 1 = 5, což je jistě dělitelné pěti.

Nyní předpokládejme, že pro nějaké přirozené \(k\) platí 5\(\mid\)(\(k\)\(^5\) + 4\(k\)), a podívejme se, jak bude vztah vypadat pro (\(k\) + 1):

(\(k\) + 1)\(^5\) + 4(\(k\) + 1) = \(k\)\(^5\) + 5\(k\)\(^4\) + 10\(k\)\(^3\) + 10\(k\)\(^2\) + 5\(k\) + 1 + 4(\(k\) + 1) = \(k\)\(^5\) + 5\(k\)\(^4\) + 10\(k\)\(^3\) + 10\(k\)\(^2\) + 5\(k\) + 1 + 4\(k\) + 4 =
= \(k\)\(^5\) + 4\(k\) + 5\(k\)\(^4\) + 10\(k\)\(^3\) + 10\(k\)\(^2\) + 5\(k\) + 5

Předpokládali jsme, že 5\(\mid\)(\(k\)\(^5\) + 4\(k\)), takže víme, že (\(k\)\(^5\) + 4\(k\)) je dělitelné pěti. Z výrazu, ke kterému jsme došli, nám tak zbývá 5\(k\)\(^4\) + 10\(k\)\(^3\) + 10\(k\)\(^2\) + 5\(k\) + 5, což je jistě také číslo dělitelné pěti (můžeme číslo pět vytknout). Věta platí i pro (\(k\) + 1). Důkaz je dokončen.