Tautológie s implikáciami

[Martin Sleziak]

Zistite či výrok $(p \Rightarrow r \land q) \Leftrightarrow [(p \Rightarrow r) \land (p\Rightarrow q)]$ je tautológia.

Najprv napíšem jedno riešenie z písomky hlavne kvôli tomu, aby som ukázal, aká je v ňom chyba.

Ľavá strana $p\Rightarrow (r\land q) \equiv 0$ práve vtedy, keď $p\equiv 1$ a $r\land r\equiv 1$, teda pre tieto tri možnosti:
I. $p\equiv 1$, $r\equiv 1$, $q\equiv 0$
II. $p\equiv 1$, $r\equiv 0$, $q\equiv 1$
III. $p\equiv 1$, $r\equiv 0$, $q\equiv 0$

Dosadíme tieto tri prípady do pravej strany.
(Nebudem tu odpisovať časť s overením.)
Vo všetkých troch prípadoch vyšla nula, teda zadaná ekvivalencia je tautológia.

Toto nie je správny argument - vlastne je takto overené iba implikácia jedným smerom.
Ukázali ste, že ak je vľavo nula, tak je nula aj vpravo.
Treba skontrolovať, či toto sú naozaj všetky prípady, kedy vpravo dostaneme nulu.

[Martin Sleziak]

Zistite či výrok $(p \land q \Rightarrow r) \Leftrightarrow [(p \Rightarrow r) \lor (q\Rightarrow r)]$ je tautológia.

Toto riešenie, ktoré sa vyskytlo v písomke, sem píšem preto, že sa mi páčilo. Základná idea je opätovné prepísanie implikácie do iného tvaru a potom použitie známych vlastností logických spojok a negácie.

Vieme, že $(a\Rightarrow b) \Leftrightarrow (\neg a \lor b)$

ĽS: $(p \land q \Rightarrow r) \Leftrightarrow
[\neg (p \land q) \lor r] \Leftrightarrow
[(\neg p \lor \neg q) \lor r] \Leftrightarrow
(\neg p \lor \neg q \lor r)
$

PS: $(p \Rightarrow r) \lor (q\Rightarrow r) \Leftrightarrow
[(\neg p \lor r) \lor (\neg q\lor r)] \Leftrightarrow
(\neg p \lor \neg q \lor r \lor r)\Leftrightarrow
(\neg p \lor \neg q \lor r)
$

ĽS $\Leftrightarrow$ PS

[Martin Sleziak]

A len tak pre zaujímavosť možnosť celkom iného pohľadu.

Ak sa pozrieme na tabuľky pravdivostných hodnôt a ak sa na true a false pozeráme na ako na čísla, tak

• $p\Rightarrow q$ je pravdivé práve vtedy, keď $p\le q$.
• Hodnota $p\land q$ je vlastne $\min(p,q)$.
• Hodnota $p\lor q$ je $\max(p,q)$.

Ak sa takto pozrieme na tautológie z písomky:
$(p \Rightarrow r \land q) \Leftrightarrow [(p \Rightarrow r) \land (p\Rightarrow q)]$
$(p \land q \Rightarrow r) \Leftrightarrow [(p \Rightarrow r) \lor (q\Rightarrow r)]$
Vlastne je to to isté ako skontrolovať, že pre $p,q,r\in\{0,1\}$
\begin{gather*}
p\le \min(r,q) \text{ platí práve vtedy, keď } p\le r \text{ a }p\le q\\
\min(p,q)\le r \text{ platí práve vtedy, keď } p\le r \text{ alebo }p\le q
\end{gather*}

[Martin Sleziak]

Nejaké tautológie s implikáciami sa objavili aj na písomke.

Zistite či výrok $[(p\Rightarrow q)\land(q\Rightarrow r)]\Rightarrow (p\Rightarrow r)$ je tautológia.

Dá sa to riešiť tabuľkou.

Takisto sa dá použiť metóda ktorú som spomenul vyššie: Vieme, že pre reálne čísla z $p\le q$ a $q\le r$ vyplýva $p\le r$.

Ak by sme to chceli riešiť bez tabuľky, tak napríklad takto:
Aby výrok neplatil, tak ľavá strana implikácie musí byť pravdivá a pravé nepravdivá.
Ak chceme aby $p\Rightarrow q$ bola nepravdivá, tak potrebujeme $p\equiv 1$ a $r\equiv 0$.
Ak sa teraz pozrieme na ľavú stranu a chceme aby bola pravdivá, tak by sme potrebovali aby platilo $1\Rightarrow q$ aj $q\Rightarrow 0$.
Prvé je možné iba pre $q\equiv1$, druhé iba pre $q\equiv0$.
Čiže sa nedá nájsť možnosť, kde by to nefungovalo.

Zistite či výrok $(p\Rightarrow r)\Rightarrow [(p\Rightarrow q)\lor(q\Rightarrow r)]$ je tautológia.

Tu ste si mohli zjednodušiť život ak ste si všimli, že už $(p\Rightarrow q)\lor(q\Rightarrow r)$ je tautológia. A teda čokoľvek pridám na ľavú stranu implikácie pred tento výrok, dostanem tautológiu.

Môžeme si ukázať inú možnosť ako overiť, že výrok $(p\Rightarrow q)\lor(q\Rightarrow r)$ je tautológia než vypĺňaním tabuľky.
Skúsme ho znegovať a všimnúť si, že dostaneme výrok, ktorý nemôže platiť.
Ak negujeme $P\equiv [(p\Rightarrow q)\lor(q\Rightarrow r)]$ tak dostaneme
\begin{align*}
\neg P
&\Leftrightarrow \neg [(p\Rightarrow q)\lor(q\Rightarrow r)]\\
&\Leftrightarrow [\neg (p\Rightarrow q)\land \neg(q\Rightarrow r)] \\
&\Leftrightarrow [(p\land \neg q)\land (q\land \neg r)]
\end{align*}
Ak sa pozrieme na posledný výrok, tak vidíme, že tam máme súčasne $q$ aj $\neg q$. Čiže takýto výrok neplatí nikdy. A jeho negácia - čo je presne pôvodný výrok - bude platiť vždy a je to tautológia.