Loogika, hulgad ja tõestus

Mõiste

Loogikas kontrollime, kas järeldus tuleb eeldustest päriselt välja. Hulk on objektide kogum. Tõestus näitab, miks väide kehtib kõigil lubatud juhtudel.

Eeldus: oskad kasutada muutujaid, lihtsaid arvuhulki ja näha, kas näide vastab väitele.

Märgid

• $\in$ tähendab “kuulub hulka”.
• $\subset$ tähendab “on alamhulk”.
• $\Rightarrow$ tähendab “sellest järeldub”.
• $\Leftrightarrow$ tähendab “parajasti siis, kui”.

Implikatsioon

Implikatsioon

$$P\Rightarrow Q$$

tähendab: kui eeldus $P$ kehtib, siis järeldus $Q$ peab kehtima.

Eeldus on lähtekoht; järeldus on see, mida sellest lähtekohast põhjendusega saadakse.

Näide:

Kui arv jagub 4-ga, siis ta jagub 2-ga.

$$4\mid n\Rightarrow 2\mid n.$$

Vastupidine suund ei pruugi kehtida:

$$2\mid n\not\Rightarrow 4\mid n,$$

sest $6$ jagub 2-ga, aga ei jagu 4-ga.

Seega kontrolli alati, kummast eeldusest alustad ja millise järelduseni pead jõudma.

Ekvivalents

Ekvivalents

$$P\Leftrightarrow Q$$

tähendab, et mõlemad suunad kehtivad:

$$P\Rightarrow Q$$

ja

$$Q\Rightarrow P.$$

Näide:

Täisarv $n$ on paarisarv parajasti siis, kui leidub täisarv $k$, nii et

$$n=2k.$$

Siin toimivad mõlemad suunad:

• kui $n$ on paarisarv, saab teda kirjutada kujul $2k$;
• kui $n=2k$, siis $n$ on paarisarv.

Vastunäide

Üldväite ümberlükkamiseks piisab ühest vastunäitest.

Üldväite tõestamiseks peab põhjendus katma kõik lubatud juhud, mitte ainult mõne näite.

Väide: “Kõik paarisarvud jaguvad 4-ga.”

Vastunäide: $6$ on paarisarv, aga $6$ ei jagu 4-ga.

Seega väide on väär.

Näide

Kui arv jagub 4-ga, siis ta jagub 2-ga. Vastupidine väide ei kehti: 6 jagub 2-ga, aga ei jagu 4-ga.

Hulkade näide:

$$\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}.$$

Kui $x\in\mathbb{N}$, siis kindlasti $x\in\mathbb{Z}$. Vastupidine ei kehti: $-3\in\mathbb{Z}$, aga $-3\notin\mathbb{N}$, kui naturaalarvud algavad 1-st.

Tõlgendus: hulkade sisaldumine annab ühe suuna; vastupidist suunda peab eraldi kontrollima.

Tüüpviga

Üks näide võib väite ümber lükata, aga üks näide ei tõesta üldist väidet.

Teine tüüpviga on segada implikatsioon ja ekvivalents. Väide “kui arv jagub 4-ga, siis jagub 2-ga” ei tähenda automaatselt, et “kui arv jagub 2-ga, siis jagub 4-ga”.

Kolmas tüüpviga on kasutada sõna “või” ja mõelda “ja”. Matemaatikas tähendab “$P$ või $Q$” tavaliselt, et vähemalt üks neist kehtib.

Neljas tüüpviga on pidada vastupidist väidet automaatselt tõeseks. Iga implikatsiooni puhul kontrolli eraldi ka vastupidist suunda.

Kui jäid kinni

Korda hulkadesse kuulumise märke ja vahet väitel ning selle vastupidisel väitel. Vaata näitest, kuidas üks vastunäide lükkab üldise väite ümber. Alusta harjutustest 1 ja 2; tõestuse kirjutamise juurde mine siis, kui implikatsiooni suund on selge.

Harjutused

Lihtne kontroll

1. Kas väide “kui $x>5$, siis $x>2$” on tõene?
2. Kas vastupidine väide “kui $x>2$, siis $x>5$” on tõene?

Rakendus

1. Too vastunäide väitele “kõik täisarvud on naturaalarvud”.
2. Selgita, mida tähendab $P\Leftrightarrow Q$.

Mõtlemisülesanne

1. Kas väide “arv on paarisarv parajasti siis, kui ta on kujul $2k$, kus $k$ on täisarv” on ekvivalents?
2. Kas “ei kehti korraga $P$ ja $Q$” tähendab sama mis “ei kehti $P$ ega $Q$”? Põhjenda.
3. Olgu $P$: arv jagub 2-ga ja $Q$: arv jagub 3-ga. Mida tähendab “$P$ või $Q$”? Too näide arvust, mis sobib.

Vastused

1. Jah, sest $x>5$ korral on kindlasti $x>2$.
2. Ei. $x=3$ on vastunäide.
3. Näiteks -1 on täisarv, aga ei ole naturaalarv.
4. Mõlemad suunad kehtivad: $P\Rightarrow Q$ ja $Q\Rightarrow P$.
5. Jah: paarisarvust saab kirjutada $n=2k$ ja iga $2k$ kujuline täisarv on paarisarv.
6. Ei. Kui $P$ on tõene ja $Q$ väär, ei kehti need korraga, kuid väide „kumbki ei kehti” on väär.
7. Arv jagub 2-ga või 3-ga või mõlemaga; matemaatiline "või" lubab ka mõlemat korraga. Näiteks 8 sobib, 9 sobib ja 6 sobib mõlemaga.

Seosed

Loogika on tõestuste, võrratuste, funktsioonide omaduste ja kõrgema matemaatika alus. Järgmine matemaatilise induktsiooni peatükk kasutab loogilist järeldamist lõpmatu hulga väidete tõestamiseks.