Matematické Fórum

Blujacker · 10. 01. 2011 20:00

Ahoj,

připravuju se na zkoušku z logiky a narazil jsem na problém v predikátové logice. Ve výrokové logice sestavím sémantický strom bez problémů, ale jak bych ho mohl sestavit pro predikátovou logiku, když tam jsou navíc kvantifikátory $\forall,\ \exists$ ?

Například pokud bych dokazoval:
Které z následujících tvrzení není tautologickým důsledkem této množiny formulí $(\forall x)(a(x)\ \vee\ b(x)),\ (\exists x)\neg a(x)$
a) $(\exists x)b(x)$
b) $(\exists x)\neg b(x)$
c) $(\forall x)(\neg b(x) \Rightarrow a(x))$
d) $(\forall x)(\neg a(x) \Rightarrow b(x))$

Dokazoval bych to tak, že bych našel negace možností a-d a připojoval bych je na strom. Tam, kde by vznikl spor tam by byl tautologický důsledek. Ale bohužel nevím jak bych ten strom vyjádřil v predikátové logice.

Děkuji

Kondr · 12. 01. 2011 01:36

Otázka zní, která z nich není tautologickým důledkem. Tedy když najdeš realizaci a valuaci takovou, že v ní daná formule neplatí, máš vyhráno.

Wotton · 17. 01. 2011 09:44

↑ Blujacker:

Zdravím,

není to o moc složitější než ve VL.
Když narazíš na obecný kvantifikátor, tak pokračuješ v jedný větvi a napíšeš postupně tolik formulí kolik si v této větvi zatím použil volných proměnných. Tyto volné proměnné postupně dosazuješ za tu proměnnou co je vázána odstraňovaným kvantifikátorem. Pokud si zatím žádnou proměnnou nepoužil, tak si zvolíš nějakou novou.

Pokud odstraňuješ existenční kvantifikátor, tak vytvoříš jednu větev s nějakou dosud nepoužitou volnou proměnnou (opět dosazenou za proměnou vázanou odstraňovaným kvantifikátorem), a pro každou použitou volnou proměnnou další novou větev (tyhle další větve se standardně neučí, ale pak to nefunguje dobře!!!).

Matematické Fórum

#1 10. 01. 2011 20:00

Predikátová logika - sémantické stromy

#2 12. 01. 2011 01:36

Re: Predikátová logika - sémantické stromy

#3 17. 01. 2011 09:44

Re: Predikátová logika - sémantické stromy

Zápatí