Matematické Fórum

kitchima

No, mam dokazat tieto pravidla absorbcie:

p v (p ^ q) <=> p

p ^ (p v q) <=> p

Viem, ze pre absorbciu sa pouzivaju tieto pravidla: a+a=a
a*a=a
a+ab=a
a* (a+b)=a

Ten prvy priklad je p+pq=p a ten druhy priklad je vlastne p*(p+q)=p. Vsak?
Ale neviem to nejak sformulovat, aby to bol dokaz. Pomoze mi s tym niekto prosim?
Lebo neviem ci to ma nieco spolocne s dokazom, ale ak si spravim pravdivostnu tabulku, vyjdu mi obe tautologie...
Dakujem

kitchima · 27. 10. 2009 18:49

↑ kitchima:

Prosiiiiiiiiiiiiiiiiiiiiiim. potrebujem to surne na zajtra

kitchima · 28. 10. 2009 09:31

↑ kitchima:

Tak nikto nevie poradit? Dakujem

zdenek1 · 28. 10. 2009 10:08

↑ kitchima:
Nevím co stačí jako důkaz. Tohle je tautologie a dá se dokázat pravdivostní tabulkou.

kitchima · 28. 10. 2009 10:38

↑ zdenek1:

nie, tabulka nestaci. preto neviem ako to zapisat inak, ale dik aspon za snahu :)

Pavel · 29. 10. 2009 11:40 — Editoval Pavel (29. 10. 2009 12:34)

Použiju následující tautologie:

$1.\ (A\Leftrightarrow B)\Leftrightarrow[(A\Rightarrow B)\wedge(B\Rightarrow A)]$ .
$2.\ (A\Rightarrow B)\Leftrightarrow(\neg A\vee B)$ .
$3.\ (A\vee \neg A)\Leftrightarrow{\mathbb 1}$ - ${\mathbb 1}$ - vždy pravdivý výrok
$4.\ ({\mathbb 1}\vee A)\Leftrightarrow{\mathbb 1}$
$5.\ ({\mathbb 1}\wedge A)\Leftrightarrow A$
$6.\ [\neg(A\vee B)]\Leftrightarrow (\neg A\wedge\neg B)$
$7.\ [(A\wedge B)\vee C]\Leftrightarrow [(A\vee C)\wedge(B\vee C)]$
$8.\ [\neg(A\wedge B)]\Leftrightarrow (\neg A\vee\neg B)$

A pomocí řetězce logicky ekvivalentních formulí ukážu, že $p\vee(p\wedge q)\Leftrightarrow p$ je tautologie.

$[p\vee(p\wedge q)\Leftrightarrow p]\Leftrightarrow{\text(ad 1)}\{[p\vee(p\wedge q)\Rightarrow p]\wedge[p\Rightarrow p\vee(p\wedge q)]\}\Leftrightarrow{\text{(ad 2)}}\{\{\neg[p\vee(p\wedge q)]\vee p\}\wedge[\neg p\vee p\vee(p\wedge q)]\}\nl \Leftrightarrow{\text{(ad 3)}}\{\{\neg[p\vee(p\wedge q)]\vee p\}\wedge[{\mathbb 1}\vee(p\wedge q)]\}\Leftrightarrow{\text{(ad 4)}}\{\{\neg[p\vee(p\wedge q)]\vee p\}\wedge{\mathbb 1}\}\Leftrightarrow{\text{(ad 5)}}\{\neg[p\vee(p\wedge q)]\vee p\}\nl \Leftrightarrow{\text{(ad 6)}}\{[\neg p\wedge\neg(p\wedge q)]\vee p\}\Leftrightarrow{\text{(ad 7)}}\{[\neg p\vee p]\wedge[\neg(p\wedge q)\vee p]\}\Leftrightarrow{\text{(ad 3)}}\{{\mathbb 1}\wedge[\neg(p\wedge q)\vee p]\}\Leftrightarrow{\text{(ad 5)}}[\neg(p\wedge q)\vee p]\nl \Leftrightarrow{\text{(ad 8)}}(\neg p\vee \neg q\vee p)\Leftrightarrow{\text{(ad 3)}}({\mathbb 1}\vee \neg q)\Leftrightarrow{\text{(ad 4)}}{\mathbb 1}$

Tudíž formule $p\vee(p\wedge q)\Leftrightarrow p$ je tautologie.