Kapitola 3
Složitější výroky a kvantifikátory

Složitější výroky

Složené výroky nemusí obsahovat jen jedinou spojku, ale mohou být mnohem složitější. I u těchto výroků často potřebujeme odhalit, zda jsou pravdivé. V této kapitole si ukážeme, jak to udělat. Jako doplnění si ukážeme, že některé logické spojky lze nahradit kombinací negace a jiných spojek.

Už v předchozí kapitole jsme si ukázali použití tabulky pravdivostních hodnot. U složitějších výroků ji budeme používat jako nástroj ke zjištění pravdivostního ohodnocení výsledného výroku. Nejdříve si složitý výrok rozdělíme na co nejjednodušší dílčí výroky spojené logickými spojkami. Tyto výroky ohodnotíme, pro jednotlivá ohodnocení budeme analyzovat pravdivostní hodnoty složitějších výroků podle spojek a ty dále spojovat, až nám vznikne ohodnocení celého výroku. Ukažme si postup řešení na následujícím jednoduchém příkladě:


Nejdříve si výrok rozdělíme na dva jednodušší, které jsou spojeny pomocí implikace:


Druhý výrok už se dále dělit nedá, u něj jsme hotovi. Ten první bychom ale mohli ještě dále rozdělit na dva spojené konjunkcí:


Máme rozděleno. Zkusme sestavit tabulku, uděláme to postupně. Nejdříve dosadíme jen samotné výroky A, B a C - všechny možné kombinace jejich pravdivostních ohodnocení. Tabulka by mohla vypadat následovně:
1 0 1
1 1 1
1 0 0
1 1 0
0 0 1
0 1 1
0 0 0
0 1 0

Nyní přidáme negaci výroku A:
1 0 1 0
1 1 1 0
1 0 0 0
1 1 0 0
0 0 1 1
0 1 1 1
0 0 0 1
0 1 0 1

Přidáme konjunkci výroků a , ze současného stavu tabulky už dokážeme zjistit, jaká jsou ohodnocení výroků, které jsou jí spojeny:
1 0 1 0 0
1 1 1 0 0
1 0 0 0 0
1 1 0 0 0
0 0 1 1 0
0 1 1 1 1
0 0 0 1 0
0 1 0 1 1

Na závěr přidáme implikaci a výrok C:
1 0 1 0 0 1
1 1 1 0 0 1
1 0 0 0 0 1
1 1 0 0 0 1
0 0 1 1 0 1
0 1 1 1 1 1
0 0 0 1 0 1
0 1 0 1 1 0

A máme ohodnocení našeho výroku pro jednotlivé pravdivostní hodnoty výroků A, B a C. Vidíme, že náš výrok je nepravdivý jen v jediném případě.

Zkusme ještě jiný výrok:
Opět si ho rozdělíme na dva, tentokrát spojené konjunkcí:



Ty už lze snadno rozdělit na výroky A a B. Opět vyplníme tabulku (nejdříve samotné výroky A, B a implikace "z A plyne B"):
1 1 1
1 0 0
0 1 1
0 0 1

Přidáme implikaci "z B plyne A":
1 1 1 1
1 0 0 1
0 1 1 0
0 0 1 1

A výsledný výrok:
1 1 1 1 1
1 0 0 1 0
0 1 1 0 0
0 0 1 1 1

Zkusme jej pro zajímavost ještě porovnat s ekvivalencí:
1 1 1 1 1 1
1 0 0 1 0 0
0 1 1 0 0 0
0 0 1 1 1 1

Našli jsme vyjádření ekvivalence pomocí konjunkce a dvou implikací, když se podíváme na značení implikace a na značení ekvivalence, zjistíme, že vychází právě z tohoto poznatku. Některé spojky opravdu můžeme vyjádřit pomocí jiných a negace. Později si ukážeme i další případy.

Nyní se podíváme na další výrok:

Zkusme jej opět rozdělit na dva jednodušší spojené implikací:


Vytvoříme tabulku, ta bude nakonec vypadat takto:
1 1 1 1
1 0 1 1
0 1 0 1
0 0 1 1

Náš výrok je pravdivý pro jakékoli ohodnocení výroků A a B. Takové výroky jsou velmi důležité, protože se používají pro odvození nových poznatků z těch, které už známe. Za písmena A a B můžeme dosadit jakékoli výroky, ale výsledek bude vždy pravdivý. Máme pro ně také speciální označení, těmto výrokům říkáme tautologie.

Tautologie mohou samozřejmě být i mnohem složitější. Ukažme si ještě jednu:

Tabulka by vypadala takto:
1 1 0 1 1 1
1 0 0 0 0 1
0 1 1 1 1 1
0 0 1 1 1 1

Máme tu ekvivalenci dvou složitějších výroků, která je zároveň tautologií. To znamená, že spojované výroky jsou ekvivalentní, tedy že jsme našli vyjádření implikace pomocí negace a disjunkce. Jsou-li dva výroky ekvivalentní, potom je jejich spojení pomocí ekvivalence tautologií.

Negace složitějších výroků

Také u složitých výroků musíme být schopni vytvořit jejich negace. Princip není nijak složitý, jeho hlavní myšlenka spočívá opět v rozdělení výroku na menší části. Budeme postupovat "shora", znegujeme "nejvrchnější" spojku a podle toho, jak bude vypadat její negace, budeme pokračovat ke stále jednodušším výrokům. Vezměme si např. vyjádření ekvivalence pomocí konjunkce implikací, na které jsme tu již narazili:


Nejprve znegujeme konjunkci, podle které bychom výrok rozkládali:

Vznikla nám disjunkce dvou negací, zkusíme tedy i tyto negace vyjádřit jinak:

A jsme hotovi. Protože původní výrok byl jiným vyjádřením ekvivalence, je tento výrok vyjádřením negace ekvivalence dvou výroků. Splnili jsme tedy předsevzetí z předchozí kapitoly, kde jsme si provedení negace ekvivalence slíbili.

Na ukázku znegujeme ještě složitější výrok:

Nejprve znegujeme ekvivalenci - o několik řádků výš najdeme, jak její negace vypadá. Nesmíme jen zapomenout, že do negace ekvivalence budeme za výroky dosazovat celé závorky:

Upravíme ještě vnitřní negaci disjunkce (využijeme znalosti, že dvojitá negace dá původní výrok) a implikace:

Nyní si uvědomíme, jak lze jinak přepsat implikaci a zjistíme, že dva složitější výroky spojené disjunkcí jsou vlastně dvě stejné konjunkce, které mají jen prohozené pořadí výroků. U konjunkce ale nezáleží na pořadí spojovaných výroků, takže tuto disjunkci můžeme odebrat a ponechat jen jednu spojovanou část:

Kvantifikátory

V první kapitole jsme si řekli, že např. zápis

není výrokem, protože se v něm vyskytuje proměnná x, u které nevíme, co za ni dosadit. Takové proměnné se říká volná proměnná. Pokud nám u daného tvrzení brání ve vytvoření výroku jen volné proměnné, říká se mu výrokový vzorec. 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 způsobem jako u výroků. Značení výrokových vzorců budeme provádět stejně jako u výroků - velkými písmeny. Ukažme si příklad - budeme mít dva výrokové vzorce:

Spojíme-li je konjunkcí, vyjde nám následující:

Takový zápis bychom přečetli: "x je menší než pět a současně x je větší než nula." Stále nemáme výrok, protože nám vadí volná proměnná, ale také se nezměnilo nic na tom, že se jedná o výrokový vzorec. Můžeme zkusit i negaci výrokového vzorce - třeba toho prvního (mohli bychom negovat ale i celý složený výrokový vzorec):

"Není pravda, že x je menší než pět." Výsledek zcela popírá původní výrokový vzorec - je jeho negací. Proč nenapíšeme, že "x je větší nebo rovno pěti"? Tady musíme být opatrní. To by totiž platilo jen v případě, kdy bychom za x dosazovali pouze čísla. My ale zatím nenáme nijak specifikováno, co můžeme za proměnnou dosadit, a tak raději zůstaneme jen u takto obecné formulace.

Pokud bychom chtěli negovat složitý výrokový vzorec s logickými spojkami, budeme postupovat také stejně jako u výroků - zkusme to s naším spojením:

Při negaci ještě složitějších výrokových vzorců se opět provádí rozklad na menší části a postupné negování.

Aby z výrokového vzorce vznikl výrok, musíme z volné proměnné vytvořit vázanou proměnnou. Právě k tomu slouží kvantifikátory, které napíšeme - spolu s proměnnou, kterou kvantifikujeme - před upravovaný výrokový vzorec.

Jedním ze dvou kvantifikátorů je obecný (někdy se mu též říká velký kvantifikátor), značí se a můžeme ho číst:"Pro každé...". Tento kvantifikátor má následující vliv na pravdivost vytvořeného výroku:

Výsledný výrok je pravdivý právě tehdy, když výrokový vzorec s touto proměnnou je pravdivým výrokem po dosazení libovolné hodnoty, které tato proměnná může nabývat.


Druhým kvantifikátorem je takzvaný existenční (někdy mu říkáme malý), značí se a čteme jej: Existuje.... Jeho vliv na výsledný výrok je samozřejmě odlišný:

Výsledný výrok je pravdivý právě tehdy, když mezi hodnotami, kterých může nabývat vázaná proměnná, existuje alespoň jedna, po jejímž dosazení do výrokového vzorce vznikne pravdivý výrok.


Procesu vázání proměnných se někdy říká kvantifikování proměnných, vzniká nám kvantifikovaný výrok. Ve výrokovém vzorci může být více proměnných, výrok z takového vzorce vyrobíme kvantifikováním všech volných proměnných.

Význam kvantifikátorů si nejlépe ukážeme na příkladech - nejdříve třeba obecný kvantifikátor:

Zápis přečteme: "Pro každé x platí, že x je menší než číslo 5." Takovou formulaci už bychom mohli považovat za výrok. Dříve jsme nevěděli, co za x dosadit, teď ale říkáme, že ať dosadíme cokoliv (to je ono "Pro každé"), bude vztah pořád platit (takový výrok je samozřejmě nepravdivý). Ale nastává nám tu ještě jeden problém. Proměnnou x jsme ničím neomezili, takže za ni můžeme dosadit zcela cokoli - číslo 7, písmeno b, slovo čabajka nebo slona, kterého právě vidíme v ZOO. Zkrátka můžeme za x dosadit jakýkoli objekt. Taková tvrzení se nám pro praktické použití moc hodit nebudou. Proto bývá zvykem omezit proměnnou jen na množinu, ze které ji budeme vybírat - na množinu reálných čísel, na množinu všech trojúhelníků nebo třeba na množinu všech zvířat pražské ZOO. V našem příkladě řekneme, že proměnná x nabývá pouze záporných celočíselných hodnot (výrok pak dokonce bude pravdivý):

Teď bychom zápis přečetli: "Pro každé záporné celé číslo x platí, že x je menší než číslo pět." Mohli bychom začít i slovy: "Pro každé x z množniny záporných celých čísel platí,..."

Stejně tak můžeme použít existenční kvantifikátor, změníme tím ale význam výroku:

Čteme: "Existuje x z množniny záporných celých čísel takové, že x je menší než číslo pět." To je samozřejmě také pravdivý výrok, víme, že tuto vlastnost splňují dokonce všechna záporná čísla (nám by stačilo jedno).

Ukažme si ještě několik dalších příkladů kvantifikovaných výroků:

1) "Pro každý automobil vyrobený v České republice platí, že jej pohání spalovací motor."
To je nepravdivý výrok, protože v České republice se vyrábějí např. i elektromobily. Množinou, na kterou omezujeme proměnnou (v našem případě by proměnnou byl automobil), je množina automobilů vyrobených v České republice.

2) "Existuje automobil vyrobený v České republice takový, že je poháněný spalovacím motorem."
Takto formulovaný výrok je již pravdivý - určitě bychom nějaký takový našli (stačí nám jeden), jeden je na fotografii níže.


Existuje automobil...

3) "Pro každý trojúhleník ABC s pravým úhlem u vrcholu C platí, že obsah čtverce nad stranou AB je roven součtu obsahů čtverců nad stranami AC a BC."
Předchozí věta není nic jiného, než jinak zformulovaná Pythagorova věta, takže výrok je pravdivý.

4) "Pro každý pravoúhlý trojúhelník platí, že obsah čtverce nad přeponou je roven součtu obsahů čtverců nad odvěsnami."
A máme opět pravdivý výrok, opět Pythagorovu větu, v častějším znění. Není zde už ale tolik zřejmé, co je proměnná (pravoúhlý trojúhelník) a co je množina, z níž ji vybíráme (množina pravoúhlých trojúhelníků).

5)
Zápis můžeme přečíst slovy: "Pro každé reálné číslo x platí, že druhá mocnina x je větší než nula."
Výrok je nepravdivý, pokud bychom za x dosadili nulu (což je reálné číslo), nebude tvrzení platit. Kdyby byla použita neostrá nerovnost místo ostré, výrok by platil.

6)
Toto je ukázka kvantifikování složitějšího výrokového vzorce složeného ze dvou pomocí konjunkce. Výrok je pravdivý, říká, že součet i součin přirozeného čísla se sebou samotným je opět přirozeným číslem.

7)
"Pro každé reálné číslo x existuje reálné číslo y takové, že  součet x a y je roven deseti." Výrok je pravdivý, opravdu ke každému reálnému číslu můžeme najít takové reálné číslo tak, aby jejich součet byl deset. Jak už jsme si řekli, v jednom výroku může být více kvantifikovaných proměnných. Musíme si ale dát pozor na pořadí kvantifikátorů. Jejich prohození může změnit význam výroku.

8)
"Existuje reálné číslo y tak, že pro všechna reálná čísla x platí, že součet x a y je deset." Takový výrok je samozřejmě nepravdivý, neexistuje číslo, ke kterému by bylo možné cokoli přičítat a vycházelo by stále číslo deset.

Pokud je ve výroku více kvantifikovaných podmínek, 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 téhož typu. V ostatních případech by došlo ke změně významu výroku! Následující výroky mají shodný význam (a oba jsou nepravdivé - říkají totiž, že součin libovolných dvou reálných čísel je 10):


Vzhledem k tomu, že po svázání všech volných proměnných vznikne z výrokového vzorce výrok, můžeme s takovým výrokem nakládat jako s jakýmkoli jiným, tedy jej spojovat s jinými pomocí logických spojek a také negovat.

Negace kvantifikovaných výroků

S určitou nadsázkou lze říci, že při negování se kvantifikátory převádějí jeden na druhý. My si to ale ukážeme přesněji:

Negace obecného kvantifikátoru
Označíme-li výrokový vzorec A, proměnnou nazveme x a budeme ji vybírat z množiny označené M, můžeme psát:


Obecný kvantifikátor nám říká, že A platí pro všechny hodnoty proměnné x. 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: Existuje hodnota proměnné, pro níž vznikne pravdivý výrok z negace výrokového vzorce. Negace našeho výroku tedy bude:


Negace existenčního kvantifikátoru
Použijeme-li stejné značení, výrok můžeme zapsat takto:

Existenční kvantifikátor říká, že existuje alespoň jedna hodnota proměnné x taková, že z A 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 říci také tak, že pro všechny hodnoty proměnné x vznikne z A nepravdivý výrok, neboli že pro všechny hodnoty, kterých x může nabývat, bude platit negace A:


Více kvantifikátorů
Pokud máme 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, písmena A, B, C, D označují nějaké výrokové vzorce, písmena K, M, N označují množiny:

Při jeho negaci bychom postupovali následovně:

Negace kvantifikátorů u x a y:


Negace konjunkce:


Negace implikace a kvantifikátoru u z:


Negace disjunkce - výsledný výrok:


Další příklady
1) "Pro každé racionální číslo platí, že jej lze zapsat zlomkem."
Pravdivost tohoto výroku vychází přímo z toho, jak se racionální čísla definují. Věta nám na první pohled přesně neříká, co je vlastně proměnná a množina. V následujícím příkladě se to však vysvětlí.

2) "Pro každé x z množiny racionálních čísel platí, že existuje dvojice čísel p z množiny celých čísel a q z množiny přirozených čísel tak, že číslo x lze zapsat jako podíl p a q."
Tatáž věta, ale s přesně popsanými všemi proměnnými a množinami. Která vám zní líp? Zkusme ji znegovat a zapsat oběma způsoby:
"Existuje x z množiny racionálních čísel takové, že pro všechny dvojice čísel p a q z množiny celých čísel podíl p ku q není roven x"
"Existuje racionální číslo, které nelze zapsat zlomkem."

3) "Do každé kružnice lze vepsat pravoúhlý trojúhelník."
Kdo někdy slyšel pojem Thaletova kružnice, ví, že tento výrok je pravdivý. Jak bychom ho znegovali?
"Existuje kružnice, do které nelze vepsat pravoúhlý trojúhelník."


Thales z Milétu

4)
Výrok tvrdí, že odmocnina z přirozeného čísla je opět přirozené číslo. Ale víme, že už odmocnina z čísla dvě je iracionální číslo. Negace výroku by vypadala takto:

Co už bychom měli znát?