Přesné vyjadřování a důkazy

• Tuto část cvičení je možné a často žádoucí kombinovat se Cvičením 0 (s ohledem na to, zda bylo Cvičení 0 před nebo po přednášce)...

• Je potřeba opakovaně rozebrat některé z příkladů z přednášky na důkazy (Lekce 1), případně jiné krátké důkazy (viz volitelné příklady níže). Vysvětlit praktický rozdíl mezi důkazem tvrzení a jeho vyvrácením protipříkladem, což se studentům často plete. Dát si záležet na pochopení rozdílů mezi "rozhodněte, zda", "dokažte" a "vyvraťte (podejte protipříklad)" a co to všechno znamená.
  • Nechť studenti chvíli pracují ve dvojicích, každý si zkusí napsat svůj "důkaz" zadaného jednoduchého tvrzení a poté tímto svým zápisem zkusí přesvědčit souseda (a naopak).
  • Příklady tvrzení k takovému jednoduchému dokazování a logickým hrátkám (ne vše nutně musí být pravdivé, nechybí někde upřesnění?):
    Dřevěná a železná kulička jsou stejně velké, takže ta železná je těžší.
    Pepa je silnější než Tonda a Tonda je silnější než Lojza, takže když Lojza uzvedne kámen, uzvedne ten samý kámen i Pepa.
    Když na semaforu naskočí zelená, auta se hned rozjedou do křižovatky, tedy alespoň pokud před semaforem nečeká zrovna autoškola.
• Příklady na "vyvraťte tvrzení" - zde je třeba hledat a najít jeden co nejkonkrétnější(!) protipříklad. Vůbec není vhodné se snažit postihnout vágně "všechny špatné situace", často je to naopak velkou chybou!
  • Pokud máte rozhodnout, zda "všichni lidé mají vlasy", budete skutečně shánět seznam všech plešatých obyvatel?

Ještě blahé paměti na základní škole nás náš vynikající učitel matematiky důrazně učil, že "matematik je líný dělat zbytečné věci". Přesně to platí i v tomto bodě, prostě to nejjednodušší dostatečné řešení (najít jeden konkrétní protipříklad pro vyvrácení) je zároveň to nejlepší řešení.

Základy matematické logiky

• Pro tento letmý úvod do logiky není dobré začínat se symbolicky zapsanými formulemi, nýbrž co nejvíce setrvat u formulí vyjádřených v běžném jazyce.
  • Které jazykové spojky/konstrukty odpovídají základním logickým spojkám &, |, ->? Jaký je význam?
  • Kdy je přednesené tvrzení splnitelné a kdy se jedná o tautologii (pomůžeme si pravdivostní tabulkou?).
    Například: Pokud dnes svítí slunce, zítra bude pršet.
    Jestliže platí, že když neprší, tak zároveň prší, potom už určitě prší.
    (Poznámka: "zítra bude pršet" není přísně formálně vzato výrokem, neboť v tento okamžik nemůžeme rozhodnout jeho platnost. Záměrně je však použit v této otázce, kde je třeba uvažovat nad všemi možnými pravdivostními hodnotami.)
  • Co třeba takový příklad: Z elementárních výroků "předevčírem pršelo", "včera sněžilo", "dnes je konec světa" sestavte tautologii v přirozeném jazyce. Pohrejte si s ní, ať vypadá hezky a košatě, zkuste ji pak také znegovat.
    Bude výsledná negace splnitelnou formulí?
  • Pro zadanou jednoduchou formální výrokovou formuli sestavte smysluplnou větu s touto logickou strukturou;
    například !A->!B, (A&B)->C, A->(B|C), či složitější (A->B)->C, A->(B->C).
• Z formálních výrokových formulí probrat práci s nim a pravdivostní tabulky, dopsání formule k předvyplněné tabulce, vyjádření formule pouze pomocí implikace a negace. Mechanická negace formule.
  • Jsou nebo nejsou následující dvě formule ekvivalentní: !X -> [ (Z|X) & !(Y|Z) ] ,  X | [ (!Y->Z) & !(Y|Z) ]  Napsali jste si k nim pravdivostní tabulku?
  • ...
  • Demonstrace potřeby mechanické negace složitého výroku pro účely důkazu sporem.
• Je třeba vysvětlit skutečně do hraničních detailů význam implikace, tj. ne pouze pravdivostní tabulku, ale skutečný logický význam v matematických tvrzeních. Jaký má význam implikace z nepravdivých (sporných) předpokladů?
  • Řekl, že když ho naštvu, dostanu facku, ale já jsem k němu byl slušný a stejně mi dal facku. Lhář!?
  • Je-li n přirozené a zároveň n<0, tak n=0.5. (Proč? Přece 0.5 není přirozené ani záporné... Aha, a proč tedy ne n=1.5?)

Ze základů predikátové logiky se stručně uvádí pouze na intuitivní úrovni kvantifikátory (existenční a všeobecný) a jak se s nimi pracuje - v jednoduchých situacích a na jednoduchých příkladech.

• Proč jsou kvantifikátory v matematickém usuzování potřebné? Například
  "Každý člověk je smrtelný; Sókratés je člověk, je tedy smrtelný" - kde se zde využívá kvantifikátor a jak?
• Další jednoduché příklady:
  V každé řadě sedí student, který má brýle. Existuje řada, ve které má každý student brýle. Existuje řada, ve které nemá žádný student brýle.
  Každý student má v učebně kamaráda (kde jsou zde přesně kvantifikátory?).
• Upozorňujeme, že nelze zaměnit existenční kvantifikátor za univerzální, ale ani naopak.
  Obzvláště zrádné je časté přesvědčení studentů, že ze všeobecného kvantifikátoru "vyplývá" existenční - NE! Všichni studenti v učebně mají červené svetry, a tudíž existuje v učebně student s červeným svetrem. Ale co když tam žádný student není?
• Obecně nelze prohazovat pořadí kvantifikátorů - rozdíl si dobře uvědomíme třeba na následujícím příkladu:
  1. Pro každého studenta A v posluchárně existuje osoba B taková, že B je partnerem/partnerkou A.
  2. Existuje osoba B taková, že B je partnerem/partnerkou každého studenta A v posluchárně (tj. všech najednou).