Materiály:
Riešenie úlohy 7
Pre každý z uvedených výrokov nájdite taký príklad množiny \(M\) a výrokových foriem \(a(t)\), \(b(t)\) a \(c(t)\) definovaných na množine \(M\), aby po ich dosadení do výroku sme dostali pravdivý / nepravdivý výrok.
Podúloha a)
\[ [(\exists x \in M : a(x)) \wedge (\exists y \in M : b(y))] \implies [\forall z \in M : (a(z) \implies b(z))] \]Pravda
Výrok bude pravdivý práve vtedy keď záver implikácie platí alebo predpoklad implikácie neplatí. Keď sa pozrieme bližšie — kedy bude záver pravdivý?
\[ \forall z \in M : (a(z) \implies b(z)) ~ ~ ~ ~ (1)\]Môžeme skúsiť dve možnosti:
- \(M = \emptyset\). Potom \( (1) \) platí podľa toho, že \(\forall x \in \emptyset: P(x)\) je pravdivý výrok pre ľubovoľné \(P\).
- \(M \neq \emptyset\). Nech napríklad \(M = \{1,2\}\). Podľa \((1)\) platí \(a(1) \implies b(1)\) a \(a(2) \implies b(2)\). Tak nech \(a(1) = 1, b(1) = 1, a(2) = 1, b(2) = 1\). Skúste overiť, že naozaj potom \( (1) \), a teda aj celý výrok platí.
Nepravda
Výrok bude nepravdivý práve vtedy keď záver implikácie neplatí a zároveň predpoklad implikácie platí. Keď sa pozrieme bližšie — kedy bude záver nepravdivý?
\[ \forall z \in M : (a(z) \implies b(z))\]Práve vtedy keď negácia bude pravdivou.
\[\neg \forall z \in M : (a(z) \implies b(z))\]\[\exists z \in M : (a(z) \wedge \neg b(z))\]
Nech teda pomenujme si tento prvok \(1 \in M\), a teda \(a(1)=1\) a \(b(1) = 0\).
Kedy bude predpoklad pravdivý?
\[ (\exists x \in M : a(x)) \wedge (\exists y \in M : b(y)) \]Práve vtedy keď platí \(\exists x \in M : a(x)\) a zároveň \(\exists y \in M : b(y)\). O prvom výroku vieme že platí keďže \(a(1)=1\), a nech teda \(2 \in M\) je také aby platilo \(b(2)\). Všimneme si, že naozaj potrebujeme nový prvok \(2\), keďže \(b(1)=0\).
Zdá sa, že sme použili všetky podmienky, ale stále nezistili hodnotu \(a(2)\). To by mohlo znamenáť, že tento výrok môže mať ľubovoľnú pravdivostnú hodnotu. Skúste zistiť, že naozaj v oboch prípadoch:
- \(M = \{1,2\};~ a(1)=1, a(2) = 1, b(1)=0, b(2)=1\)
- \(M = \{1,2\};~ a(1)=1, a(2) = 0, b(1)=0, b(2)=1\)
dostaneme, že pôvodné tvrdenie neplatí.
Podúloha b)
\[ \{ \forall x \in M: [a(x) \implies ( \exists y \in M: b(y) ) ] \} \implies [\forall x \in M: (a(x) \implies b(x))] \]Skúsme rovnaký postup ako v podúlohe vyššie.
Pravda
Výrok bude pravdivý práve vtedy keď záver implikácie platí alebo predpoklad implikácie neplatí. Keď sa pozrieme bližšie — kedy bude záver pravdivý?
\[ \forall x \in M: (a(x) \implies b(x)) ~ ~ ~ ~ (1)\]Môžeme skúsiť dve možnosti:
- \(M = \emptyset\). Potom \( (1) \) platí podľa toho, že \(\forall x \in \emptyset: P(x)\) je pravdivý výrok pre ľubovoľné \(P\).
- \(M \neq \emptyset\). Nech napríklad \(M = \{1,2\}\). Podľa \((1)\) platí \(a(1) \implies b(1)\) a \(a(2) \implies b(2)\). Tak nech \(a(1) = 1, b(1) = 1, a(2) = 1, b(2) = 1\). Skúste overiť, že naozaj potom \( (1) \), a teda aj celý výrok platí.
Tu ale by sme mohli skúsiť aj iné možnosti, napríklad:
\( M = \{1\} \). Podľa \((1)\) platí \(a(1) \implies b(1)\), tak nech \(a(1) = 0, b(1) = 0\).
Alternatívny postup
Ako iný spôsob riešenia, mohli by sme zvoliť postup hľadania toho, kedy bude nepravdivý predpoklad implikácie.
\[ \{ \forall x \in M: [a(x) \implies ( \exists y \in M: b(y) ) ] \} \]Kedy bude tento výrok nepravdivý? Práve vtedy keď negácia bude pravdivá.
\[ \{ \exists x \in M: [a(x) \wedge ( \forall y \in M: \neg b(y) ) ] \} \]Z tadialto ľahko vidime, že existuje \( x \), že \( a(x) = 1\), a pre všetky \(y \in M \) \(b(y) = 0\). Tak nech \( M = \{ 1 , 2 \} \), a \(a(1) = 1 \), \( b(1) = 0, b(2) = 0 \), a, keďže hodnota \(a(2)\) nie je špecifikovaná žiadnými podmienkami, tak nech \(a(2) = 0 \).
Skontrolujte, že naozaj potom predpoklad neplatí, a teda platí celý pôvodný výrok.
Nepravda
\[ \{ \forall x \in M: [a(x) \implies ( \exists y \in M: b(y) ) ] \} \implies [\forall x \in M: (a(x) \implies b(x))] \]Výrok bude nepravdivý práve vtedy keď záver implikácie neplatí a zároveň predpoklad implikácie platí. Keď sa pozrieme bližšie — kedy bude záver nepravdivý?
\[ \forall x \in M: (a(x) \implies b(x)) \]Práve vtedy keď negácia bude pravdivou.
\[\neg \forall x \in M: (a(x) \implies b(x)) \]\[\exists x \in M : (a(x) \wedge \neg b(x)) \]
Nech teda \(1 \in M \) a \(a(1) = 1\) a \(b(1) = 0\).
Kedy bude predpoklad pravdivý?
\[\{ \forall x \in M: [a(x) \implies ( \exists y \in M: b(y) ) ] \} \]Vidime, že výrok musí platiť pre všetky \(x \in M\), a predpoklad implikácie je \(a(x)\). Čiže oplatilo by sa pozrieť, ako bude vyzerať výrok pre \(x=1\) (totiž to, keď musí byť pravdivý pre všetky hodnoty v \(M\), tak aj pre \(x = 1\) musí platiť).
\[[a(1) \implies ( \exists y \in M: b(y) ) ]\]Čo vieme zjednodúšiť ako:
\[( \exists y \in M: b(y) ).\]Teraz vieme, že musí existovať prvok \(y \in M\) taký, aby platilo \(b(y)\). Nemôže to byť prvok \(1\) – preňho sme už definovali \(b(0)=0\). Tak nech \(2\in M\), a \(b(2)=1\).
Zdá sa, že sme použili všetky podmienky, ale stále nezistili hodnotu \(a(2)\). To by mohlo znamenáť, že tento výrok môže mať ľubovoľnú pravdivostnú hodnotu. Skúste zistiť, že naozaj v oboch prípadoch:
- \(M = \{1,2\};~ a(1)=1, a(2) = 1, b(1)=0, b(2)=1\)
- \(M = \{1,2\};~ a(1)=1, a(2) = 0, b(1)=0, b(2)=1\)
dostaneme, že pôvodné tvrdenie neplatí.