Matematická tvrzení je výhodné zapisovat ve zkrácené formě pomocí symboliky predikátové logiky. Podrobněji bude tato oblast matematiky probrána v předmětu Diskrétní matematika a logika ( BI-DML)50. Díky využití tohoto přístupu vynikne logická struktura tvrzení, která by jinak mohla čtenáři zůstat skryta za větami přirozeného (v našem případě českého) jazyka. Na tomto místě pouze stručně shrneme základy, které jsou čtenáři již jistě známy.
Ihned učiňme jednu motivační a vysvětlující poznámku. Řada studentů má k formálním zápisům jistý odpor. Ten je nutné překonat. Uvědomte si, že přesná formulace matematických tvrzení pouze přirozeným českým jazykem je velice „křehká“ a náchylná na dezinterpretaci. Obranou proti tomu je velmi podrobný slovní popis, čímž ovšem text ztrácí na čitelnosti. Tento přístup se používal ve středověku, od té doby jsme se již posunuli. Formální zápis odstraňuje neurčitost, řada problémů tím následně odpadá.
Je také vhodné si uvědomit, že libovolný programovací jazyk je ve své podstatě vysoce formalizovaný zápis jistých instrukcí. Budoucím programátorům by formálně přesné vyjadřování mělo být blízké. Překladač vás vytrestá za sebemenší chybičku, matematika je v tomto směru přeci jen malinko shovívavější!
Výrok je tvrzení, o kterém lze v principu jednoznačně rozhodnout, zda je či není pravdivé. Výroky značíme velkými písmeny $A, \ B, \ C, \ldots$ Často narazíme na výroky závisející na parametru $x$, tzv. predikáty, které značíme dle očekávání $A(x)$. Pro různá $x$ tak dostáváme různé výroky $A(x)$. Uveďme alespoň dva příklady.
Nechť $x$ probíhá množinu všech obyvatel planety Země. Symbolem $A(x)$ označme výrok „$x$ je muž“. Označuje-li $a$ autora tohoto textu, pak je výrok $A(a)$ pravdivý.
Nechť $x$ probíhá množinu všech celých čísel. Symbolem $B(x)$ označme výrok „$x$ je sudé číslo“. Pravdivými výroky pak jsou například $B(2)$, či $B(4)$, ale $B(99)$ pravdivý není.
Připomeňme čtyři základní výrokové spojky (operace), pomocí nichž z daných výroků sestavujeme složitější. K dispozici máme:
$\neg A$, negace, $A$ není pravdivé,
$A \wedge B$, konjunkce, platí $A$ a zároveň $B$,
$A \vee B$, disjunkce, platí $A$ nebo51 $B$,
$A \Rightarrow B$, implikace, $A$ implikuje $B$, případně z $A$ plyne $B$,
$A \Leftrightarrow B$, ekvivalence, $A$ je ekvivalentní s $B$, případně $A$ platí právě tehdy když $B$.
V závislosti na pravdivostním ohodnocení prvotních výroků $A$ a $B$ jsou pravdivostní hodnoty výroků $\neg A$, $A \wedge B$, $A \vee B$, $A \Rightarrow B$ a $A \Leftrightarrow B$ dány následující tabulkou (symbol $1$ standardně označuje pravdivost a $0$ nepravdivost).
| \(A\) | \(B\) | \(\neg A\) | \(A \wedge B\) | \(A \vee B\) | \(A \Rightarrow B\) | \(A \Leftrightarrow B\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Abychom mohli kvantifikovat proměnné vyskytující se ve výrokových formulích, zavádíme tři kvantifikátory:
$\forall$, obecný kvantifikátor, pro všechna, pro každé,
$\exists$, existenční kvantifikátor, existuje, pro nějaké,
$\exists!$, $\exists_1$, existuje právě jedno.
Pokud proměnná $x$ probíhá všechna reálná čísla, píšeme $\forall x \in \R$. Podobně pokud chceme vyjádřit existenci celého čísla $k$, píšeme $\exists k \in \Z$. Pro větší přehlednost kvantifikátory v zápisu formule oddělujeme závorkami. Předveďme si názornou ukázku.
Přirozené číslo $p$ je prvočíslo, právě když každé přirozené $k$ dělící $p$ je rovno $1$ nebo $p$. Zapsáno pomocí kvantifikátorů a výrokových spojek odpovídá tomuto tvrzení formule
zde používáme označení $k|p$ pro predikát „$k$ dělí $p$“.
Podmínku v definici omezenosti množiny $A \subset \mathbb{R}$ shora bychom mohli ekvivalentně vyjádřit následující formulí
Známá Goldbachova hypotéza patří mezi jednoduchá matematická tvrzení, která jsou numericky ozkoušena pro milióny případů, ale důkaz jejich případné pravdivosti doposud není znám. Tato hypotéza tvrdí, že každé sudé přirozené číslo větší než $2$ lze vyjádřit jako součet dvou prvočísel, například
Označíme $P$ množinu všech prvočísel a $2\N$ množinu všech sudých přirozených čísel, pak Goldbachovu hypotézu lze vyjádřit formulí
Na závěr této podkapitoly ozřejmíme ještě jeden obrat často používaný (nejen) v matematické literatuře, a sice vysvětlíme význam „nutné“, „postačující“ a „nutné a postačující“ podmínky. Platí-li tvrzení $A \Rightarrow B$, pak o $A$ mluvíme jako o postačující podmínce pro $B$ a o $B$ mluvíme jako o nutné podmínce pro $A$.
Důvod k tomuto názvosloví by měl být očividný. Platí-li tvrzení $A \Rightarrow B$ a víme-li, že $A$ je pravdivé, pak platí i $B$! Platnost $A$ tedy stačí pro to, aby platilo $B$. Naopak, pokud je tvrzení $A \Rightarrow B$ pravdivé a víme, že $B$ je nepravdivé, potom $A$ je nepravdivé. Tj. aby vůbec $A$ mohlo být pravdivé, tak $B$ musí být nutně pravdivé.
Konečně, je-li jisté tvrzení nutnou a postačující podmínkou pro $A$, pak je ekvivalentní $A$.
Nutnou podmínkou pro přijetí studenta na FIT ČVUT je podání přihlášky na FIT ČVUT. Podání přihlášky na FIT ČVUT ale není postačující podmínkou pro přijetí na FIT ČVUT.
Je sudost přirozeného čísla postačující pro jeho neprvočíselnost?
Není. Číslo $2$ je sudé a je prvočíslem.
Množinu $A\subset\mathbb{R}$ nazýváme omezenou shora (resp. zdola), právě když existuje konstanta $K\in\mathbb{R}$ taková, že pro každé $x\in A$ platí $x < K$ (resp. $x > K$). Množinu $A\subset\mathbb{R}$ nazýváme omezenou, právě když je omezená shora i zdola zároveň.