Matematické Fórum

ocas123

Zdravím, mám takový problém - upravovat logické formule umím pomocí tabulek, ale chtějí po nás umět upravovat i pomocí ekvivalentních úprav (tzn. používání pravidel distributivní, asociativní, komutativní, dvojité negace, de Morganovy, idempotence, neutrality, agresivity, vyloučení třetího).
Abych trochu ujasnil:
//forum.matweb.cz/upload3/img/2019-08/36132_Bez%2Bn%25C3%25A1zvu.png

Třeba toto mám upravit právě pomocí ekvivalentních úprav, tak jako bych třeba upravoval lomené výrazy. Problém je ten, že si s tím moc nevím rady. Instinktivně bych prostě použil de Morganův zákon (první závorka z leva by se změnila na: $(\bar{x} \wedge \bar{y})$ a tuto závorku "roznásobil" s tím $\bar{x}$ . Ale jak dál?
Třeba netuším, co bych dělal s tím $(\bar{y} \Rightarrow 1)$

To samé třeba tady:
//forum.matweb.cz/upload3/img/2019-08/36447_Bez%2Bn%25C3%25A1zvu.png

Ztrácím se u $(x\wedge 1)...$ Kde vzali tu jedničku?

Davisek

↑ ocas123: Zdravím, upravením je myšleno zjednodušení?

Předpokládejme že $\alpha, \beta$ jsou formule.
Např. lze použit že $\alpha \rightarrow \beta \equiv \neg \alpha \vee \beta$ .

Takže v prvním případě, $\neg y \rightarrow 1 \equiv \neg\neg y \vee 1 \equiv y \vee 1 \equiv 1$ .

Je důležité si uvědomit, že $\alpha \vee 1 \equiv 1$ , $\alpha \vee 0 \equiv \alpha$ , $\alpha \wedge 1 \equiv \alpha$ , $\alpha \wedge 0 \equiv 0$ .

ocas123 · 26. 08. 2019 19:53

$(\bar{x} \wedge \bar{y})$ Ano, upravením je myšleno zjednodušení.

A ano, máš pravdu s tou ekvivalentní úpravou u té závorky s implikací, moje chyba, že mě to nenapadlo. O tom, že $(x\Rightarrow y)$ lze upravit na $(\neg x\vee y)$ vím, ale jsem tupej a nedošlo mi to. Jinak ten poslední řádek, co jsi napsal - o tom vím - to jsou právě ty zákony neutrality a agresivity. Tu poslední závorku tedy upravím na 1, dostanu:

$\neg x \wedge \neg(x \vee y) \vee (y \vee x) \wedge 1$

Ale nějak si nevím rady, co teď. Můžu využít ten de Morganův zákon a druhou závorku upravit na $(\bar{x} \wedge \bar{y})$ , potom bych to roznásobil s tím $\neg x$ a dostal
$(\neg x \wedge x) \vee (\neg x\wedge y)...$

Zde vidím, že $(\neg x \wedge x)$ mohu ekvivalentními úpravami zjednodušit na 0. Je to možné, nebo jsem vedle?

Davisek · 26. 08. 2019 20:25

↑ ocas123: Ano, je to možné.

ocas123 · 26. 08. 2019 20:43

Ok. Tak mi teď vychází:
$0 \vee (\neg x\wedge y) \vee (y\vee x) \wedge 1$
Asi takto:
$0 \vee (\neg x\wedge y) = (\neg x \wedge y)$
$(y\vee x) \wedge 1 = (y \vee x)$
A:
$(\neg x\wedge y) \vee (y \vee x)$

Co teď? Nenapadá mě, co bych s tím už udělal.

Davisek · 26. 08. 2019 20:59

↑ ocas123: Distributivní zákon.

ocas123 · 26. 08. 2019 22:39

$(\neg x\wedge y) \vee (y \vee x) = (\neg x \vee x) \vee y$
Může být takto? Vyjde 1?

Davisek

↑ ocas123: Asi přesně nevíš co znamená distributivní zákon:

$(\alpha \vee (\beta \wedge \gamma)) \equiv (\alpha \vee \beta) \wedge (\alpha \vee \gamma)$ a
$(\alpha \wedge (\beta \vee \gamma)) \equiv (\alpha \wedge \beta) \vee (\alpha \wedge \gamma)$ .

Tedy to tvoje "roznasobení" a "vytýkaní" je součást distributivního zákona a zaleží jestli jestli jdeš zleva do prava nebo naopak,

To co jsi napsal ty je špatně. Zkus si pravdivostní tabulku a uvidíš (takto si klidně můžeš kontrolovat každý krok pokud si nejsi jistý). Po aplikaci dostaneme:
$(\neg x\wedge y) \vee (y \vee x) \equiv (\neg x \vee (y \vee x)) \wedge (y \vee (y \vee x)) \equiv \cdots$ .

ocas123 · 27. 08. 2019 13:40

No dobře, teď mě napadá leda použít asociativní zákon.
$(\neg x \vee (y \vee x)) \wedge (y \vee (y \vee x)) \equiv (y \vee (\neg x \vee x)) \wedge (x \vee (y \vee y))$

Pokud je tohle dobře, podle tohohle zákona:
//forum.matweb.cz/upload3/img/2019-08/05670_Pozn%25C3%25A1mka%2B2019-08-27%2B133417.png

Měl bych dostat:
$(y \vee (\neg x \vee x)) \wedge (x \vee (y \vee y)) \equiv (y\vee 1) \wedge (x \vee y)$

Je to tak, nebo jsem zas vedle?

Davisek · 27. 08. 2019 14:13

↑ ocas123: Ano, ještě $(y \vee 1) \wedge (x \vee y) \equiv x \vee y$ .

Pomocí pravdivostní tabulky si můžeš zkontrolovat, že formule $x \vee y$ je ekvivalentní k originální formuli.

ocas123 · 27. 08. 2019 14:17

Tak ti moc děkuji, jdu si najít pár příkladů a jedu mechanický dril. :D
Bez těchto ujasnění bych ztracený.

Matematické Fórum

#1 26. 08. 2019 18:19 — Editoval ocas123 (26. 08. 2019 18:24)

Úprava výrokových formulí

#2 26. 08. 2019 19:11 — Editoval Davisek (26. 08. 2019 19:12)

Re: Úprava výrokových formulí

#3 26. 08. 2019 19:53

Re: Úprava výrokových formulí

#4 26. 08. 2019 20:25

Re: Úprava výrokových formulí

#5 26. 08. 2019 20:33 Příspěvek uživatele ocas123 byl skryt uživatelem ocas123. Důvod: preklep

#6 26. 08. 2019 20:43

Re: Úprava výrokových formulí

#7 26. 08. 2019 20:59

Re: Úprava výrokových formulí

#8 26. 08. 2019 22:39

Re: Úprava výrokových formulí

#9 27. 08. 2019 09:33 — Editoval Davisek (27. 08. 2019 10:55)

Re: Úprava výrokových formulí

#10 27. 08. 2019 13:40

Re: Úprava výrokových formulí

#11 27. 08. 2019 14:13

Re: Úprava výrokových formulí

#12 27. 08. 2019 14:17

Re: Úprava výrokových formulí

Zápatí