Matematické Fórum

Hotel007

Dobrý den,
jak lze bez použití pravdivostní tabulky dokázat, že je výroková formule tautologií? Mám tu i pár příkladů:
$(P \wedge \neg q)\rightarrow (q\leftrightarrow \neg p)$
$\neg ((p \rightarrow q) \vee r) \leftrightarrow ((p \wedge \neg q)\wedge \neg r)$
$\neg (p \rightarrow (p \wedge w)) \leftrightarrow (p \wedge(\neg p \vee \neg q))$
$(a \rightarrow(b \rightarrow c))\rightarrow ((a \rightarrow b)\rightarrow(a \rightarrow c))$

Pokud najdete někde na internetu tuto problematiku pěkně napsanou, budu vděčný!

ryzskej · 21. 10. 2010 23:25

Dá se to udělat i přes Semantic - tablo..

ryzskej · 21. 10. 2010 23:36

Zkus http://www.cs.vsb.cz/duzi/UvodLogika.html a Přednáška č.3.

Rotter_Martin · 21. 10. 2010 23:46

to, zda je tvrzení tautologie, lze dokázat (jak již podotkl ryzskej) pomocí tabla, a konkrétně pomocí konjunktivního tabla.

vše je popsáno tady

www.cs.vsb.cz/duzi/PresentaceLogika3-06.ppt

konkrétně vše potřebné na straně 15-16

Fauſt · 21. 10. 2010 23:57

Díky větě o úplnosti víme, že tautologie jsou právě formule dokazatelné bez předpokladů, takže krom pravdivostní tabulky můžeš hledat důkaz z axiomů výrokové logiky. Třeba ta poslední formule je přímo axiom, takže je triviálně dokazatelná.

Hotel007 · 24. 10. 2010 19:29

Ok, děkuji již jsem to nadrtil... :)

Dále bych poprosil o kontrolu :

infix>prefix

$((p \vee q) \rightarrow q) \rightarrow ((\neg p \vee (p \leftrightarrow q)) \wedge \neg (\neg p \rightarrow(\neg q \vee p)))$

$pq\vee q \rightarrow p \neg pq \leftrightarrow \vee p \neg q \neg p \vee \rightarrow \neg \wedge \rightarrow$

ještě přidám další příklady na kontrolu během dneška, děkuji za ochotu.... :)

Hotel007 · 24. 10. 2010 20:49

Dokažte správnost závěru:

Pokud mi ujede bus, přijdu pozdě, nepřišel jsem pozdě => neujel mi autobus

$((U \rightarrow P) \wedge \neg p) \rightarrow \neg U$

U pravdivostní tabulky mi vyšlo:

0
0
0
1

to znamená, že závěr není správně, protože premisy nejsou tautologie, je tak?

Hotel007 · 24. 10. 2010 22:11

Negujte:

půjdu do obchodu jen tehdy, když půjdeš ty, nebo Karel.

$O \rightarrow (J \wedge K)$

negace je $O \wedge \neg (\neg J \vee \neg K)$

Půjdu do obchodu a nepůjdeš ty, nebo nepůjde Karel.

Je to tak správně? Pochybuji, ale díky za kontrolu :)

Wotton · 25. 10. 2010 10:02

↑ Hotel007: tady jsi udělal tabulku pouze premis. Abys zjistil, že úsudek je správně (správnost závěru budu považovat za překlep, protože to je nesmysl), tak bys musel udělat tabulku celé implikace, a ta tautologií je. Tudíž i úsudek je platný.

↑ Hotel007: v tomhle máš špatně jak tu negaci měla by být buď $O \wedge(\neg J \vee \neg K)$ nebo $O \wedge \neg (J \wedge K)$ , ale hlavně to máš špatně zformalizovaný. Má to vypadat $O \leftrightarrow (J \wedge K)$

Wotton · 25. 10. 2010 10:19

↑ Hotel007: tohle by mělo být správně;-)

Hotel007 · 25. 10. 2010 10:57

mohu poprosit ještě o vysvětlení toho, jak tedy pomocí té tabulky zjistím správnost úsudku? Co jsem koukal, tak se vždy dělala jen pravdivostní tabulka na premisy... :( děkuji

Wotton · 25. 10. 2010 14:44 — Editoval Wotton (25. 10. 2010 15:21)

Z úsudku si uděláš implikaci tak jak si to udělal předtím

$(u \rightarrow p)$ a $\neg p$ jsou premisy, $\neg u$ je závěr.

Hledaná implikace je pak tak si psal (například takhle, protože je víc možností jak ji udělat), jen si dej pozor na velikost písmenek, protože to mně na chvíli zmátlo $((u \rightarrow p) \wedge \neg p) \rightarrow \neg u$

pokud pro ni uděláš tabulku, tak ti vyjde tautologie právě tehdy když je úsudek platný.

EDIT:

Druhá možnost (a tu jste možná dělali) je, že si uděláš tabulku pro všechny premisy a pro závěr, a podívá se na řádek na kterém jsou všechny premisy pravdivé. Pokud je na všech takových řádcích pravdivý i závěr, tak je úsudek platný.

Matematické Fórum

#1 21. 10. 2010 23:17 — Editoval Hotel007 (21. 10. 2010 23:20)

Výroková logika

#2 21. 10. 2010 23:25

Re: Výroková logika

#3 21. 10. 2010 23:36

Re: Výroková logika

#4 21. 10. 2010 23:46

Re: Výroková logika

#5 21. 10. 2010 23:57

Re: Výroková logika

#6 24. 10. 2010 19:29

Re: Výroková logika

#7 24. 10. 2010 20:49

Re: Výroková logika

#8 24. 10. 2010 22:11

Re: Výroková logika

#9 25. 10. 2010 10:02

Re: Výroková logika

#10 25. 10. 2010 10:19

Re: Výroková logika

#11 25. 10. 2010 10:57

Re: Výroková logika

#12 25. 10. 2010 14:44 — Editoval Wotton (25. 10. 2010 15:21)

Re: Výroková logika

Zápatí