Matematické Fórum

Blujacker · 06. 11. 2011 20:31

Zdravím,

mám problém s predikátovou logikou. V zadání je věta a mým úkolem je zjistit, jestli třetí věta vyplývá z prvních dvou. Mnoho takovýchto problému se dá řešit selským rozumem, ale rád bych věděl, jestli existuje řešení i pomocí matematického zápisu.

Zadání: Některé vysoké stromy jsou mrtvé. Všechno vysoké je černé. Proto vše černé je mrtvé.

Pokusil jsem se věty přepsat:
Být strom: $S(x)$
Být vysoký: $V(x)$
Být mrtvý: $M(x)$
Být černý: $C(x)$
1) Některé vysoké stromy jsou mrtvé = $\exists x(V(S(x))\wedge M(x))$
2) Všechno vysoké je černé = $\forall y(V(y)\wedge C(y))$
3) Vše černé je mrtvé = $\forall z(C(z)\wedge M(z))$

$\exists x(V(S(x))\wedge M(x)) \wedge \forall x(V(x)\wedge C(x)) \Rightarrow\forall x(C(x)\wedge M(x))$

Jak to mohu upravit, abych mohl jasně říci, zda třetí věta vyplývá z prvních dvou?

Děkuji

zdenek1 · 06. 11. 2011 20:49

↑ Blujacker:
No ale ona nevyplývá.

((:-)) · 06. 11. 2011 20:53 — Editoval ((:-)) (06. 11. 2011 20:57)

↑ zdenek1:

Zadávateľ to možno vie - je to dosť logické...

Myslím, že by chcel vedieť, akým formálnym postupom môže prísť k správnej odpovedi.

Pripomína mi to Raymonda Smyllyana ... :-)

Ale na takúto formalizáciu nemám...

halogan · 06. 11. 2011 20:56

$\forall y(V(y)\wedge C(y))$

Tohle by znamenalo, že všechno je vysoké a černé. Bude tam jiný logický operátor.

Stejně tak u

$\forall z(C(z)\wedge M(z))$ .

---

$\exists x(V(S(x))\wedge M(x))$

Tady nebude to zanoření. Funkce S ti vrací 1 nebo 0, což nemůžeš předat Véčku. A taky je tu ten problém se spojkou.

Blujacker

↑ zdenek1:
To zrovna vím, potřebuju to formálně dokázat :-)

↑ halogan:

$(\exists x((V(x) \wedge S(x)) \Rightarrow M(x)) \wedge \forall x(V(x) \Rightarrow C(x))) \Rightarrow(\forall x(C(x) \Rightarrow M(x)))$

Ale jak to tedy mohu dokázat?

zdenek1 · 06. 11. 2011 21:20

↑ Blujacker:
ten první výrok bude
$\exists x[S(x)\wedge V(x)\wedge M(x)]$

důkaz zatím nemám

halogan · 06. 11. 2011 21:23

Tak ty víš, že tahle implikace neplatí.

Stačí tedy najít takové x, pro které předpoklad bude platit a závěr nikoliv.

Aby neplatil závěr, stačí najít takové x, že C(x) je pravda, ale M(x) není.

zdenek1 · 06. 11. 2011 22:07

↑ Blujacker:
chceme ukázat, že formule
$\{\exists x [S(x)\wedge V(x)\wedge M(x)] \wedge \forall x[V(x)\Rightarrow C(x)]\}\Rightarrow \forall x[C(x)\Rightarrow M(x)]$
je tautologie
podle zadání existuje prvek $a$ tak, že
$S(a)\wedge V(a)\wedge M(a)$
druhá formule platí pro každé $x$ , takže platí i pro prvek $b\neq a$ (nutný předpoklad je, že tento prvek existuje. Pokud by neexistoval, pak je úsudek platný)
$V(b)\Rightarrow C(b)$
a třetí formule také platí pro každé $x$ , takže platí i pro $b$
Musí tedy platit
$\{[S(a)\wedge V(a)\wedge M(a)]\wedge[V(b)\Rightarrow C(b)]\}\Rightarrow[C(b)\Rightarrow M(b)]$
tato formule by měla být tautologie, což evidentně není, snadno se o tom přesvědčíš volbou pravdivostních hodnot: $S(a)=V(a)=M(a)=1$ , $V(b)=C(b)=1$ , $M(b)=0$

Takže úsudek neplatí