Výuka logiky
Úvod
Kapitoly
Nápověda
Testy
Notice: Use of undefined constant nazev - assumed 'nazev' in /srv/beegfs/web/web/kdm/diplomky/moravecdp/uvod-anonym.incl on line 82 Notice: Use of undefined constant nazev - assumed 'nazev' in /srv/beegfs/web/web/kdm/diplomky/moravecdp/uvod-anonym.incl on line 82 Notice: Use of undefined constant nazev - assumed 'nazev' in /srv/beegfs/web/web/kdm/diplomky/moravecdp/uvod-anonym.incl on line 82 Notice: Use of undefined constant nazev - assumed 'nazev' in /srv/beegfs/web/web/kdm/diplomky/moravecdp/uvod-anonym.incl on line 82 Notice: Use of undefined constant nazev - assumed 'nazev' in /srv/beegfs/web/web/kdm/diplomky/moravecdp/uvod-anonym.incl on line 82
NAHORU

Kvantifikátory

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.

Volné a vázané proměnné

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ů:

  1. obecný kvatifikátor (někdy též nazývaný „velký“)
  2. existenční kvantifikátor (někdy též nazývaný „malý“)

Obecný 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ů.

Existenční 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ů)!

Příklady výroků s kvantifikátory

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í:

Škoda 1201
Škoda 1201
  1. Pro každý automobil vyrobený v České republice platí, že jej pohání spalovací motor.
    V této větě je skryt obecný kvantifikátor, i když zde není zapsána jeho značka. Tento výrok říká, že ať vezmeme v úvahu libovolný automobil české výroby, vždy bude poháněn spalovacím motorem. Je to výrok nepravdivý, protože z českých továren již vyjely např. také elektromobily, pod jejichž kapotou bychom spalovací motor hledali marně.
  2. Existuje automobil vyrobený v České republice takový, že je poháněný spalovacím motorem.
    Změna kvatifikátoru změnila také význam věty a z té se stal pravdivý výrok. V této chvíli nám stačí najít jeden automobil české výroby, který bude poháněn spalovacím motorem, abychom mohli výrok prohlásit za pravdivý. Jeden takový vidíme na fotografii vpravo.
  3. Pro každý trojúhelní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.
    Uvedené souvětí je vlastně Pythagorova věta, pouze v neobvyklém znění. Je to tedy pravdivý výrok.
  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 zde je Pythagorova věta ve znění již mnohem častějším. Z této formulace však již není na první pohled zřejmé, co je množina z níž vybíráme hodnoty proměnné (množina všech pravoúhlých trojúhelníků) ani co je sama proměnná (ta se skrývá pod souslovím „pravoúhlý trojúhelník“). Opět jde o pravdivý výrok.
  5. (x): x2 > 0
    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 zde však byla použita neostrá nerovnost, výrok by byl pravdivý.
  6. (x): (x + x)  (x · x)
    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 samým je opět přirozeným číslem, což samozřejmě platí.
  7. 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í (je tedy pravdivý). Věta nám na první pohled přesně neříká, co je vlastně proměnná a co množina, z níž máme hodnoty proměnné vybírat. V následujícím příkladě se to však vysvětlí.
  8. 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.
    V této větě je již zřejmé, co je proměnnou a co množinou hodnot, jichž může proměnná nabývat, přesto zůstává otázkou, která z formulací je srozumitelnější…
  9. (x(y): x + y = 10
    Pro každé reálné číslo x existuje reálné číslo y takové, že součet x a y je roven deseti.“ Tento 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.
  10. (y(x): x + y = 10
    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ý, protože neexistuje číslo, ke kterému by bylo možné cokoli přičítat a vycházelo by stále číslo deset. Změna v pořadí kvantifikátorů zde zřejmě sehrála důležitou roli.

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.

Negace kvantifikovaných výroků

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:

(xM): 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:

(xM): ¬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:

(xM): 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):

(xM): ¬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.

Negace výroků s větším počtem kvantifikátorů

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:

(xM(yN): [(A(x, y B(x))  (zK): (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:

(xM(yN): ¬[(A(x, y B(x))  (zK): (C(x, y, z D(x, z))]

Kvantifikátory jsou prozatím znegovány, nejvyšší spojkou je nyní konjunkce, znegujeme tedy ji:

(xM(yN): [¬(A(x, y B(x))  ¬(zK): (C(x, y, z D(x, z))]

Dále znegujeme implikaci a kvantifikátor u proměnné z:

(xM(yN): [(A(x, y ¬B(x))  (zK): ¬(C(x, y, z D(x, z))]

A negaci dokončíme znegováním disjunkce:

(xM(yN): [(A(x, y ¬B(x))  (zK): (¬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

Shrnutí

Název kvantifikátoru Značení Čtení Negace
Obecný kvantifikátor „Pro každé…“ ¬[(xM): A(x)]  (xM): ¬A(x)
Existenční kvantifikátor „Existuje…“ ¬[(xM): A(x)]  (xM): ¬A(x)

Co už bychom měli znát?