DU2 - LS 2017/18

[Martin Sleziak]

Pár vecí týkajúcich sa d.ú. č.2: http://msleziak.com/vyuka/2017/temno/du02.pdf

Nejaké staršie komentáre sa dajú nájsť tu: http://msleziak.com/forum/viewtopic.php?t=1053

Zopakujem to čo som hovoril na prednáške - teraz na pár príkladoch ste si mali možnosť rozmyslieť si, či pri takýchto tvrdeniach viete prísť na to či platia alebo nie.
V budúcnosti sa už budem tváriť, že si takéto veci rozmyslieť viete - a budeme ich používať bez zdôvodnenia.
Každopádne hlavne v prípadoch, že ste tvrdili že tvrdenie neplatí a v skutočnosti platí (alebo obrátene, že sa vám podarilo nájsť kontrapríklad na platné tvrdenie) by nebolo zlé si rozmyslieť, kde je vo vašich úvahách chyba.

Poznámky k odovzdaným riešeniam

V jednom zo zadaní sa vyskytovali výroky podobné ako $(\forall x) (p\land Q(x))$.
Dôležité je tu to, že pravdivosť/nepravdivosť $p$ nezávisí od $x$. Viacerí z vás ste sa pozreli na konkrétne príklady, boli to však také, kde to či váš výrok bol pravdivý záviselo od $x$.

Okrem toho sa mi v niektorých odovzdaných úlohách nepozdávalo to, že ste si ich rozmysleli na príkladoch, ktoré nepokrývali všetky možnosti.
Skúsim vysvetliť detailnejšie - povedzme, že súčasťou výroku o ktorom uvažujeme je
$$(\forall x)(P(x)\Rightarrow Q(x)).$$
Ak si to skúsim predstaviť na (síce naivnom ale možno stále užitočnom) príklade s lúkou a kvietkami, tak si môžem zvoliť výroky "kvet je modrý" a "kvet je jedovatý". Takto môžem uvažovať o rôznych možnostiach pre uvedený výrok. Na niektorej lúke môžu byť všetky modré kvety jedovaté (uvedený výrok platí). Na inej lúke môže byť kvet, ktorý je modrý a nie je jedovatý (teda ten výrok neplatí).
Ak si však zvolím $P(x)=$"$x$ je párne" a $Q(x)=$"$x$ je prvočíslo", tak je to síce príklad o ktorom môžem uvažovať, ale ak budem uvažovať iba o ňom, tak tým nepreskúmam všetky možnosti. (Napríklad $(\forall x)(P(x)\Rightarrow Q(x))$ je tu určite nepravdivé.)

[Martin Sleziak]

Treba pri negovaní výrokov s kvantifikátormi pamätať na to, že sa menia kvantifikátory.
Viacerí ste as pozerali na to, čo sa stane ak niektorý výrok (niektorá časť zadanej implikácie či ekvivalencie) neplatí.
Napríklad ak máte výrok $p\lor (\exists x)Q(x)$, tak jeho negáciou dostanete $$\neg p\land (\forall x)\neg Q(x).$$
Ak ste ho znegovali ako $\neg p\land (\exists x)\neg Q(x)$, tak to nie je správne.

[Martin Sleziak]

Skúsim napísať niečo k jednému možnému zdôvodneniu ekvivalencií v prvej úlohe.
Pozrime sa napríklad na to, či platí:
$$p\land (\forall x) Q(x) \Leftrightarrow (\forall x) (p\land Q(x)).$$

Zopakujem to čo som písal vyššie: Dôležité je uvedomiť si, čo znamená $p$ a čo znamená $Q(x)$.
Ako $p$ sme označili nejaký výrok - t.j. je to niečo, čo je pravda alebo nepravda.
Označenie $Q(x)$ znamená niečo trochu iné. Tu sa dajú za $x$ dosadzovať rôzne veci - a keď nejaké $x$ dosadíme, tak dostaneme výrok (t.j. niečo, čo je buď pravda alebo nepravda).

Skúsme sa teraz pozrieť na zdôvodnenie, že uvedená ekvivalencia platí.
Zvlášť rozoberme dva prípady.

A. Čo sa stane ak $p$ je nepravdivý výrok?
Vtedy ľavá strana neplatí.
Čo vieme povedať o pravej strane? Výrok $p\land Q(x)$ je určite nepravda (bez ohľadu na to, či $Q(x)$ je pravda alebo nepravda).
A teda aj celá pravá strana je nepravdivá - lebo za $(\forall x)$ nasleduje tvrdenie, ktoré je určite nepravdivé (pre ľubovoľnú voľbu premennej $x$).
V tomto prípade teda ekvivalencia platí.

B. Čo sa stane ak $p$ je pravdivý výrok?
Vtedy $p\land (\forall x) Q(x) \Leftrightarrow (\forall x) Q(x)$. (To je jasné z toho, ako funguje konjunkcia.)
Treba si rozmyslieť, či v tomto prípade je aj pravá strana ekvivalentná s týmto výrokom.
Keďže sa pozeráme na prípad, keď $p$ je pravdivé, tak výrok $p\land Q(x)$ a $Q(x)$ sú ekvivalentné. T.j. nič sa nezmení ak jeden z nich nahradíme druhým.
Teda (v prípade, že $p\equiv 1$) je aj pravá strana ekvivalentná s $(\forall x) Q(x)$.
Vidíme, že obe strany sú naozaj ekvivalentné.