2   Matematická logika a důkazy
Jak jsme již poznali, výrokové logice chybí možnost „parametrizace" výroků, což znamená zavedení omezeného a dobře definovaného kontextu pro každé tvrzení, ve kterém pak můžeme už jednotlivé výroky vyhodnocovat podle pravidel výrokové logiky.
Takovou parametrizaci si lze v jednoduché ukázce představit jako proměnnou X, jež třeba nabývá hodnot ze skupiny našich studentů a umožňuje nám hovořit v různých výrocích o stejném nespecifikovaném studentovi X...
Obecně se tak dostáváme na „vyšší úroveň" predikátové logiky.
Stručný přehled lekce
* Vysvětlení kvantifikátorů a zjednodušené střípky predikátové logiky.
* Normální tvar formule, mechanická negace formulí.
* Jak vymýšlet (tvořit) a správně formulovat matematické důkazy.
Petr Hliněný, Fl MU Brno, 2020
1/13
Fl: IB000: Logika a důkazy
2.1   Kvantifikace a predikátová logika
Dříve popsaná výroková logika je velmi omezená faktem, že každý výrok musí být (tzv. absolutně) vyhodnocen jako pravda nebo nepravda.
* Predikátová logika pracuje s predikáty. Predikáty jsou „parametrizované výroky", které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu parametrů. nVýrok. prom. lze chápat jako predikáty bez parametrů.c
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
* x > 3 (parametrem je zde x £ R),c
* 'čísla x a y jsou nesoudělná' (parametry x, y G N),
* obecnejšou predikáty psány P(x,y), kde x, y jsou libovolné parametry.c
Následně pak můžeme psát formule ve stylu (a více viz následující definice)
* (P(x,y) AQ(x,z)) ->R(y,z)t
* (P(x,y)AQ(y,z))->^R(x,z).n
Parametrům predikátů se také říká proměnné, aleje třeba dávat pozor, aby se nepletly s výrokovými proměnnými, jedná se o jiné objekty.
Petr Hliněný, Fl MU Brno, 2020
2/13
Fl: IB000: Logika a důkazy
Syntaxe a sémantika predikátové logiky
Definice: Z predikátů (zahrnují i výrokové proměnné) lze vytvářet predikátové formule pomocí už známých výrokových spojek a takzvaných kvantifikátorů. ^Přesněji, nechť    je formule výrokové či predikátové logiky, pak také
* (všeobecný kvantifikátor) formule Vx . (p a
* (existenční kvantifikátor) formule 3x. (p
jsou formulemi predikátové logiky.
Pro ukázku si uvedeme například predikátovou formuli:
Mx.3y. (x + 2 < y /\Mz.(x + y + z> 2020))
Náš zápis predikátových formulí ve stylu Vx .tp není jediný možný, často se také setkáte se zápisy M x: (p nebo Mx((p). Všechny tyto tři způsoby můžete používat.
Petr Hliněný, Fl MU Brno, 2020
3/13
Fl: IB000: Logika a důkazy
Definice 2.1. Zjednodušená sémantika (význam) predikátové logiky. Uvažujme libovolnou množinu (nebo třídu) IA, zvanou univerzum, a předpokládejme, že každý predikátový parametr (proměnná)       ... má zvolenou hodnotu z U. Vyhodnocení predikátové formule a pak definujeme induktivně takto:
• Každý predikát P(x,y,...) se vyhodnotí (na 0 nebo 1) jako výrok v aktuálním kontextu, tj. vzhledem k aktuálně zvoleným hodnotám svých parametrů x, y,....
• Výrokové spojky jsou vyhodnoceny podle pravidel Definice 1.8.
• Formule tvaru Vx .(p se vyhodnotí jako pravdivá (1), právě když pro každou volbu parametru x £ U je pravdivá formule (p.
• Formule tvaru 3x. (p se vyhodnotí jako pravdivá (1), právě když existuje alespoň jedna volba parametru x £ U, pro kterou je pravdivá formule ip.
Všimněte si, že Definice 2.1 nedává konzistentní návod na vyhodnocení takové predikátové formule, ve které se některá proměnná vyskytuje mimo kvantifikátor.
Fakt: Je-li každá proměnná - parametr predikátu - v dané formuli kvantifikovaná (tj. formule je uzavřená), pak je formule buď pravdivá nebo nepravdivá.
Petr Hliněný, Fl MU Brno, 2020
4/13
Fl: IB000: Logika a důkazy
Příklad 2.2. Ukažme si vyjádření násl. slovních výroků v predikátové logice:
Každé prvočíslo větší než 2 je liché;
Vn \{n G N A Pr(n) A n>2) Li(n)
□
přičemž lze rozepsat Li(n) = 3k G N (n = 2k + 1). □
Každé celé číslo n > 1, které není prvočíslem, je dělitelné nějakým celým číslem y kde n ^ y a y > 1;
Vn [(n E Z An > 1 A-iPr(n)) =>► 3y(y GŽAy > lAn^yAyln)
□
□
Příklad 2.3. Proč na pořadí kvantifikátorů velmi záleží:
Pro každého studenta A v posluchárně platí, že existuje student B v posluchárně takový, že A je kamarád B.
Existuje student B v posluchárně, že pro každého studenta A v posluchárně platí, že A je kamarád B. □
Petr Hliněný, Fl MU Brno, 2020
5/13
Fl: IB000: Logika a důkazy
Konvence zápisu predikátových formulí
• Pokud píšeme více kvantifikátorů za sebou, vynecháváme zbytečně opakované symboly jako       Mx\/y3z. (f ,
nebo dokonce Vx, y, z3s, t ((f) .
• Jsou-li ve formuli (f některé parametry predikátů bez kvantifikace („neuzavřené"), například pak mohou být v zápise zdůrazněny jako parametry samotné formule ip(x, y,...).
Například ip(x, y) = 3z(x < z < y) .
• Další možná modifikace se týká univerza pro hodnoty kvantifikovaných proměnných. Zatímco striktně bychom měli psát Vn(n £ Z n2 > n), často vidíme jiný možný zápis Vn £ Z (n2 > n).
Petr Hliněný, Fl MU Brno, 2020
6/13
Fl: IB000: Logika a důkazy
2.2   Normální tvar logických formulí
Přesný význam tvrzení se zanořenými negacemi je někdy skutečně obtížné pochopitx
„Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad."
Výrokové formule se proto obvykle prezentují v tzv. normálním tvaru, ve kterém se negace zanořených podformulí nevyskytují, formálně:
Definice: Formule (f je v normálním tvaru, pokud se v ní operátor negace aplikuje pouze na výrokové proměnné (případně na predikáty).
• Pro ilustraci, k formuli ~^(A =^> B) je ekvivalentní normální tvar A A -iB,
• k formuli -.(C A (-^4     B)) je ekvivalentní -.C V (-^4 A -.B), □
• k formuli -.((A => B)     C) je ekvivalentní (A    B) A -.Cn
• a pokud důsledně aplikujeme přirozené pravidlo dvojí negace (|= —> —>A <^> A), tak výše napsané tvrzení „... nemám nerad" si převedeme na lépe srozumitelný tvar:
„Nemusím říct, že tě mám nerad."
Petr Hliněný, Fl MU Brno, 2020
7/13
Fl: IB000: Logika a důkazy
Negace formule v normálním tvaru
Použitím následujících neformálních „přepisovacích" pravidel dokážeme převést každou formuli predikátové logiky na normální tvar:
• Je-li (již znegovaná) formule tvaru bude přepsána na ((fA^)x
(f A -i^
Podobně:
((p A ip)
i(f A -i^ V -ľ0
Pro kvantifikátory se pak použije následující intuitivní převod
^       3x. —op
Plný formální popis této metody převodu do normálního tvaru ponecháváme na budoucí Oddíl 5.4.
Petr Hliněný, Fl MU Brno, 2020
8/13
Fl: IB000: Logika a důkazy
->(<£> =^> ip)       ~>        (/? A -ľ0 -i(ip\/ip)        ~>        -k/? A-ľ0
Uvažme výrokovou formuli -i(P V ->(C     ~~^4-)))- Užitím uvedeného
postupu ji upravíme takto: □
->(A -(5 V -.(C -A)))) = A A -.(-.(B V -.(C -A))) = □ AA(SV--(C=>-.A)) =    AA(BV(CA —>(—=□
A A (5 V (CA A))
Obdobně uvažme predikátovou formuli ->(\/x3y-iP(x, y)). Tu užitím našeho postupu upravíme následovně: □
i(Vz3y-iP(z,y))        3a;-i(3y-iP(a;,y)) =□ 3xVy -i(->P(x, y))    =   ž\x\/y P(x,y)
Petr Hliněný, Fl MU Brno, 2020
9/13
Fl: IB000: Logika a důkazy
2.3   Tvoření matematických důkazů
Jak moc formální mají správné matematické důkazy vlastně být?
• Záleží, komu je důkaz určen — konzument musí být schopen „snadno" ověřit korektnost každého tvrzení v důkazu a plně pochopit, z čeho vyplývá.
• Je tedy hlavně na vás zvolit tu správnou úroveň formálnosti zápisu vět i důkazů podle situace.
• Avšak vůbec neplatí, že čím více formálních matematických symbolů v důkazu použijete místo běžného jazyka, tím by byl důkaz přesnější!
A jak na ten správný matematický důkaz máme přijít?
• No. . ., nnalézání matematických důkazů je tvůrčí činnost, která není vůbec snadná a jako taková vyžaduje tvůrčí (přímo „umělecké11) matematické vlohy. I pokud takové vlohy (zatím) v sobě necítíte, snažte se jí alespoň trochu přiučit.
Petr Hliněný, Fl MU Brno, 2020
10/13
Fl: IB000: Logika a důkazy
Dokazovat či vyvracet tvrzení?
Představme si, že našim úkolem je rozhodnout platnost matematického tvrzení. Jak pak matematicky správně zdůvodníme nalezenou odpověď?
• Záleží na odpovědi samotné. .. t
• Pokud je to ANO (platí), prostě podáme důkaz podle uvedených zvyklostí.
• Pokud je odpověď NE, tak naopak podáme důkaz negace daného tvrzení.
Poměrně častým případem je matematická věta T, která tvrdí nějaký závěr pro širokou oblast vstupních možností. Potom je postup následujícím
• Pokud T platí, nezbývá než podat vyčerpávající důkaz platnosti pro všechny vstupy.
• Avšak pokud T je nepravdivá, stačí uhodnout vhodný protipříklad a jen pro něj dokázat, že při platnosti všech předpokladů závěr tvrzení platný není.
Ke slovíčku „stačí" ještě dodáváme, že pro správné matematické vyvrácení nepravdivého tvrzení T protipříklad uvést přímo musíte
(viz pravidlo -i(Vx . (p) ^> 3x . -«p).
Petr Hliněný, Fl MU Brno, 2020
11/13
Fl: IB000: Logika a důkazy
Příklad 2.5. Rozhodněte platnost následujícího tvrzení: Pro všechna reálná x platí
x2 + 3x + 2 > O.n
Důkaz: Standardními algebraickými postupy si můžeme upravit vztah na x + 3x + 2 = {x + 1) • (x + 2) > 0. Co nám tato úprava naznačuje? nNapříklad to, že k porušení daného tvrzení stačí volit x tak, aby jedna ze závorek byla kladná a druhá záporná. To nastane třeba pro x = —|. □
Pro vyvrácení tvrzení nám tedy stačí začít volbou protipříkladu reálného čísla x = —| (není nutno zdůvodňovat, jak jsme jej „uhodli"!) a následně dokázat úpravou
x2 + 3x+2 = (x+l).(x + 2) = (-| + l)-(-| + 2) = = -\<0-°
Dané tvrzení tudíž není platné. Pí
Petr Hliněný, Fl MU Brno, 2020
12/13
Fl: IB000: Logika a důkazy
Konstruktivní a existenční důkazy
Z hlediska praktické využitelnosti je vhodné rozlišovat tyto dvě kategorie důkazů (třebaže z formalně-matematického pohledu mezi nimi kvalitativní rozdíl není).
• Důkaz z Příkladu 1.5 je konstruktivní. Dokázali jsme nejen, že číslo z existuje, ale podali jsme také návod, jak ho pro dané x a y sestrojit.
• Existenční důkaz je takový, kde se prokáže existence nějakého objektu bez toho, aby byl podán použitelný návod na jeho konstrukci.
Příklad 2.6.  Cistě existenčního důkazu.
Věta. Existuje program, který vypíše na obrazovku čísla tažená ve 45. tahu sportky v roce 2020.c
Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2020. Pro každý možný výsledek existuje program, který tento daný výsledek vypíše na obrazovku. Mezi těmito programy je tedy jistě takový, který vypíše právě ten výsledek, který bude ve 45. tahu sportky v roce 2020 skutečně vylosován. q
To je ale podvod, že? nA přece není... Formálně správně to je prostě tak a tečka.
Petr Hliněný, Fl MU Brno, 2020
13/13
Fl: IB000: Logika a důkazy