Až doposud jsme si u výroků připouštěli jediný neznámý prvek, a to výrokové proměnné. Říkali jsme si, že tvrzení typu „x < 5“ nemůžeme považovat za výrok. V této kapitole si ukážeme nástroje, které nám umožní i taková tvrzení zpřesnit tak, aby se z nich staly výroky.
Pokud se v tvrzení objevuje proměnná, u níž nevíme, co za ni dosadit (např. proměnná x z tvrzení „x < 5“), říkáme jí volná proměnná. Jestliže nám u nějakého tvrzení brání pouze volné proměnné v tom, abychom jej označili jako výrok, říkáme tomuto tvrzení výrokový vzorec. Tvrzení „x < 5“ je tedy výrokovým vzorcem. Výrokové vzorce sice nejsou výroky, ale lze je spojovat pomocí logických spojek, dokonce i negovat a vyjde nám opět výrokový vzorec. Obě tyto činnosti se provádí téměř shodným způsobem jako u výroků. Značení výrokových vzorců budeme provádět podobně jako u výroků – velkými písmeny, do závorky ještě přidáme proměnnou, která nám „zabraňuje“ v tom, abychom daný výrokový vzorec označili za výrok. Výrokový vzorec „x < 5“ bychom tak mohli označit A(x). Pokud by se ve výrokovém vzorci takových proměnných objevilo víc, vypíšeme je do závorky všechny. Výrokový vzorec „x < 5 ∧ y < 5“ bychom mohli označit např. B(x, y).
Pro nás v tuto chvíli ale není důležité, jak se operuje s výrokovými vzorci. Spíše bychom se měli věnovat způsobu, jak z nich vytvořit „pravé“ výroky.
Aby z výrokového vzorce vznikl výrok, musíme z každé volné proměnné vytvořit vázanou proměnnou. Vázaná proměnná sice stále zůstavá proměnnou, ale je u ní dodán dostatek informací, aby pro dané tvrzení mělo smysl zabývat se jeho pravdivostí, a tedy abychom je mohli nazvat výrokem.
Vzpomeňme, co bylo problémem u tvrzení „x < 5“. Nevíme, co za x dosadit. Můžeme za něj dosadit např. číslo −4, ale také třeba autobus jedoucí po ulici nebo ježka, který právě dupe pod okny. Nikde není řečeno, co za x dosadit. Co když zkusíme tvrzení upřesnit tím, že řekneme, že x má být nějaké číslo. Čísel je mnoho druhů, řekněme tedy, že x je nějaké reálné číslo, což můžeme zapsat např. takto: „x < 5, x∈ℝ“
Nyní již z tvrzení víme, že za x se má dosazovat nějaké reálné číslo. Stal se z něj výrok? Ne! Když budeme rozhodovat o jeho pravdivosti, stále nevíme, jaké konkrétní číslo dosadit. Když dosadíme číslo 7, bude tvrzení nepravdivé, když dosadíme číslo ¾, bude pravdivé. Které z těchto dvou čísel si máme vybrat? Nebo máme uvažovat obě? Nebo snad všechna reálná čísla? Nic takového z tvrzení nezjistíme. Když však přidáme kvantifikátory, tuto informaci dostaneme.
Rozlišujeme dva typy kvantifikátorů:
Začněme s obecným kvantifikátorem. Jeho značka je ∀, čteme jej jako „pro každé…“. Pomocí tohoto kvantifikátoru bychom z tvrzení „x < 5, x∈ℝ“ mohli vytvořit výrok, který říká:
„Pro každé reálné číslo x platí, že x < 5.“
Pomocí značky kvantifikátoru lze výrok zapsat takto (kvantifikátor píšeme před výrokový vzorec, do závorky k němu uvádíme proměnnou, jíž se týká – tj. kterou tzv. váže):
∀(x∈ℝ): x < 5
Tentokrát se již skutečně jedná o výrok, který je nepravdivý (existují i reálná čísla větší než 5 a také číslo 5 je reálné číslo). Výrok by byl pravdivý pouze v případě, kdy by uváděná vlastnost (tedy být menší než pět) platila pro každé reálné číslo. Pokud existuje alespoň jedno reálné číslo, které danou vlastnost nesplňuje, pak je výrok nepravdivý (a zde je takových čísel dokonce nekonečně mnoho). Pokud se odtrhneme od našeho příkladu a zobecníme vše, co jsme si o obecném kvantifikátoru řekli, získáme definici pravdivosti výroku s obecným kvantifikátorem:
Obsahuje-li výrok proměnnou vázanou obecným kvantifikátorem, je pravdivý, pouze platí-li následující: Pokud za zmíněnou proměnnou do výrokového vzorce (vzniklého z výroku odebráním kvantifikátoru) dosadíme libovolnou hodnotu, jíž může tato proměnná nabývat, získáme vždy pravdivý výrok.
Neboli obráceně: Pokud existuje alespoň jedna přípustná hodnota vázané proměnné (přípustnou hodnotou se myslí hodnota z vhodné množiny – v našem příkladě z množiny reálných čísel), po jejímž dosazení do výrokového vzorce vznikne nepravdivý výrok, je i celý výrok s kvantifikátorem nepravdivý. V našem příkladu tedy stačí najít jediné reálné číslo, pro nějž vznikne nepravdivý výrok. Budeme-li uvažovat např. číslo 8, pak získáme výrok „8 < 5“. A ten je jistě nepravdivý, tedy i celý výrok s kvantifikátorem je nepravdivý, což jsme zjistili již dříve pomocí „selského rozumu“.
Pokud stále není obecný kvantifikátor jasný, není důvod k panice, o několik odstavců níže si ukážeme ještě některé příklady. Nejdříve se však podívejme na druhý z kvantifikátorů.
Značkou existenčního kvantifikátoru je symbol ∃ a čteme jej „existuje…“ nebo „existuje alespoň jedno…“. Zatímco obecný kvantifikátor naznačuje, že vlastnost (vztah apod.) uváděná ve výrokovém vzorci musí platit pro všechny přípustné hodnoty jím vázané proměnné, exitenční kvatifikátor nám umožňuje říci, že tato vlastnost platí alespoň pro jednu přípustnou hodnotu. Neboli:
Obsahuje-li výrok proměnnou vázanou existenčním kvantifikátorem, je pravdivý pouze platí-li následující: Existuje alespoň jedna přípustná hodnota zmíněné proměnné, po jejímž dosazení do výrokového vzorce (vzniklého z výroku odebráním kvantifikátoru) získáme pravdivý výrok.
Tedy, má-li být výrok s existenčním kvantifikátorem naopak nepravdivý, nesmí z výrokového vzorce (vzniklého odebráním kvantifikátoru) vzejít pravdivý výrok pro žádnou přípustnou hodnotu vázané proměnné. Pokud existuje byť jen jediná hodnota, se kterou by pravdivý výrok vznikl, bude i celý výrok s kvantifikátorem pravdivý.
Použijme již známý příklad výrokového vzorce, tentokrát však budeme volnou proměnnou vázat pomocí existenčního kvantifikátoru:
∃(x∈ℝ): x < 5
Takový výrok bychom mohli přečíst následovně: „Existuje reálné číslo x takové, že je menší než pět.“ Je tento výrok pravdivý? Ano, takové číslo totiž určitě existuje, vezměme třeba číslo 1. To je jistě číslo reálné, takže je to přípustná hodnota proměnné x. Zároveň je také menší než pět, neboli po jeho dosazení do výrokového vzorce získáme výrok „1 < 5“, což je samozřejmě výrok pravdivý. Tím jsme splnili definici pravdivosti výroku s existenčním kvatifikátorem – tento výrok je pravdivý. Všimněme si, že ze stejného výrokového vzorce jsme pomocí dvou různých kvantifikátorů vytvořili dva výroky s odlišnou pravdivostní hodnotou.
Nyní, než se podíváme na konkrétní příklady, na kterých si kvantifikátory pro lepší objasnění ukážeme, zbývá uvést několik dodatků. První se týká názvosloví: Procesu vázání volných proměnných se někdy říká kvantifikování proměnných, vzniká jím kvantifikovaný výrok. Dále bychom si měli uvědomit, že výrokový vzorec nemusí obsahovat pouze jedinou volnou proměnnou (např. „x > y“). Obsahuje-li výrokový vzorec více volných proměnných, je pro vytvoření výroku nutné kvantifikovat všechny tyto proměnné (výrok bude obsahovat více kvantifikátorů)!
Zatím jsme si kvantifikátory ukázali jen na „ryze matematickém“ příkladu, avšak ve skutečnosti je můžeme najít i v jiných tvrzeních. Na následujících řádcích si ukážeme několik příkladů z obou oblastí:
V příkladech 9 a 10 jsme narazili na zajímavý problém záměny kvantifikátorů u výroků s více kvantifikovanými proměnnými. Je možné někdy měnit pořadí kvantifikátorů? Pokud je ve výroku více kvantifikovaných proměnných, můžeme měnit pořadí kvantifikátorů s proměnnými před výrokovým vzorcem pouze v případě, že kvantifikátory jsou stejného typu a následují těsně za sebou, popř. jsou-li mezi nimi další kvantifikátory také téhož typu. V ostatních případech by došlo ke změně významu výroku (a tím často také ke změně jeho pravdivostní hodnoty)! To jsme si ukázali právě na příkladech 9 a 10. Nyní si ještě ukažme příklad situace, kdy kvantifikátory můžeme zaměnit. Oba následující výroky mají stejné pravdivostní ohodnocení (a také stejný význam).
∀(y∈ℝ) ∀(x∈ℝ): x + y = 10
∀(x∈ℝ) ∀(y∈ℝ): x + y = 10
Připomeňme na závěr, že jelikož se po kvantifikování volných proměnných z výrokového vzorce stane výrok, můžeme s ním nakládat jako s jakýmkoli jiným výrokem, tj. spojovat jej logickými spojkami s jinými výroky, negovat, apod.
Na negace výroků s kvatifikátory jsme již trochu narazili ve chvíli, kdy jsme si kvantifikátory zaváděli a říkali si, za jakých podmínek kvantifikovaný výrok platí a kdy naopak neplatí. Přesto se na ně podívejme přesněji.
Nejprve si ukažme negaci výroku s obecným kvantifikátorem. Označíme-li výrokový vzorec A(x) a proměnnou x budeme vybírat z množiny označené M, můžeme psát:
∀(x∈M): A(x)
Tento symbolický zápis označuje, že pro každé x z množiny M platí vztah uvedený ve výrokovém vzorci A(x). V podstatě označuje zápis libovolného výroku s obecným kvantifikátorem. My jej využijeme k snadnému zápisu negace takového výroku.
Obecný kvantifikátor nám říká, že A(x) platí pro všechny hodnoty proměnné x. Jak z něj utvoříme negaci? K tomu, aby výrok nebyl pravdivý, stačí, abychom nalezli jednu hodnotu dané proměnné, která po dosazení do výrokového vzorce způsobí vznik nepravdivého výroku. Neboli, musí existovat hodnota proměnné, pro níž vznikne pravdivý výrok z negace výrokového vzorce. Předchozí věta zapsaná symbolicky je na následujícím řádku:
∃(x∈M): ¬A(x)
Ukažme si tento poznatek opět na konkrétním příkladu – uvažujme výrok:
„Pro každé přirozené číslo x platí, že je dělitelné sedmi.“
Toto je samozřejmě nepravdivý výrok, jeho negaci lze formulovat následovně:
„Existuje přirozené číslo x takové, že není dělitelné sedmi.“
Přejděme k negaci výroků s existenčním kvantifikátorem. Použijeme opět symbolický zápis:
∃(x∈M): A(x)
Pak existenční kvantifikátor říká, že existuje alespoň jedna hodnota proměnné x taková, že z A(x) po jejím dosazením vznikne pravdivý výrok. Chceme-li výrok znegovat, musíme říci, že žádná taková hodnota neexistuje. To můžeme formulovat také tak, že pro všechny hodnoty proměnné x vznikne z A(x) nepravdivý výrok, neboli že pro všechny hodnoty, kterých x může nabývat, bude vždy platit negace A(x):
∀(x∈M): ¬A(x)
Můžeme opět uvést příklad:
„Existuje přirozené číslo x takové, že je dělitelné dvěma.“
Negaci tohoto pravdivého výroku můžeme zapsat takto:
„Pro každé přirozené číslo x platí, že není dělitelné dvěma.“
Pokud je před výrokovým vzorcem více kvantifikátorů, změníme při negování všechny tyto kvantifikátory na opačné a potom provedeme negaci výrokového vzorce. Pokud je výrok složen z více kvantifikovaných výroků, postupujeme při negaci opět stejně jako dříve – výrok rozdělíme podle spojky na dva jednodušší, znegujeme spojku a podle výsledku negace spojky upravujeme dílčí výroky.
Uvažujme následující výrok:
∀(x∈M) ∃(y∈N): [(A(x, y) ⇒ B(x)) ∧ ∀(z∈K): (C(x, y, z) ∨ D(x, z))]
Na tomto výroku si ukážeme postup negace složitějších výroků s kvantifikátory. Nejprve znegujeme kvantifikátory u proměnných x a y:
∃(x∈M) ∀(y∈N): ¬[(A(x, y) ⇒ B(x)) ∧ ∀(z∈K): (C(x, y, z) ∨ D(x, z))]
Kvantifikátory jsou prozatím znegovány, nejvyšší spojkou je nyní konjunkce, znegujeme tedy ji:
∃(x∈M) ∀(y∈N): [¬(A(x, y) ⇒ B(x)) ∨ ¬∀(z∈K): (C(x, y, z) ∨ D(x, z))]
Dále znegujeme implikaci a kvantifikátor u proměnné z:
∃(x∈M) ∀(y∈N): [(A(x, y) ∧ ¬B(x)) ∨ ∃(z∈K): ¬(C(x, y, z) ∨ D(x, z))]
A negaci dokončíme znegováním disjunkce:
∃(x∈M) ∀(y∈N): [(A(x, y) ∧ ¬B(x)) ∨ ∃(z∈K): (¬C(x, y, z) ∧ ¬D(x, z))]
Na závěr této kapitoly si ještě řekneme, že existuje také způsob, jakým se v matematice zapisuje, že existuje právě jeden prvek dané množiny, který splňuje určitou vlastnost. Používají se pro to slova „právě jeden“ a značí se vykřičníkem (společně s existenčním kvantifikátorem). Chceme-li např. zapsat, že existuje jen a pouze jedno přirozené číslo menší než dvě, můžeme tak učinit takto:
∃!(x∈ℕ): x < 2
| Název kvantifikátoru | Značení | Čtení | Negace |
|---|---|---|---|
| Obecný kvantifikátor | ∀ | „Pro každé…“ | ¬[∀(x∈M): A(x)] ⇔ ∃(x∈M): ¬A(x) |
| Existenční kvantifikátor | ∃ | „Existuje…“ | ¬[∃(x∈M): A(x)] ⇔ ∀(x∈M): ¬A(x) |