Matematické Fórum

vilem · 04. 05. 2009 12:16 — Editoval vilem (04. 05. 2009 12:17)

Zdravím

nevěděl by někdo jak na druhý odstavec?

Detailně popište, jak k libovolné formuli ϕ výrokové logiky vytvořit ekvivalentníformuli v konjunktivní normální formě a ekvivalentní formuli v disjunktivní normální formě.
Co nejpřesněji odhadněte, jak maximálně velké mohou být výsledné formule, jestliže původní formule byla velikosti n. Ukažte konkrétní příklady formulí (pro všechny velikosti n),pro které je této maximální velikosti výsledných formulí skutečně dosaženo.

Kondr · 05. 05. 2009 14:52

Stačí do googlu zadat "conjunctive form size"
http://en.wikipedia.org/wiki/Conjunctive_normal_form -- je tam i příklad formule, která konverzí do CNF (česky KNF) naroste exponenciálně. Pokud v té formuli prohodíme "a" za "nebo", dostaneme formuli, která roste exponenciálně převodem do DNF.

vilem · 06. 05. 2009 11:59

Takže chápu li to dobře

převeduli tuto formuli

$http://upload.wikimedia.org/math/8/c/1/8c1b2f895c7a0c6c94d88c472631e402.png$

do KNF

$http://upload.wikimedia.org/math/3/4/e/34e73d3ebc54981bef0b7843b4d2141e.png$

Získám složitost 2 na n. A je pro to nějaké logické vysvětlení proč tomu tak je,neboť z wiki jsme to moc nepochopil.

Kondr · 06. 05. 2009 13:42

To plyne z toho, že "a" a "nebo" se chovají jako * a +, jsou vůči sobě distributivní. Můžeš si to tedy představit jako roznásobování závorek a že to tak dopadne dokázat indukcí. Zbývá ukázat, že výslednou formuli už nezjednodušíme.

jamesr · 10. 05. 2009 17:24

Tady je trošku problém, v zadání není to n popsané, ptal jsem se cvičícího a n má být počet symbolů ve formuli, ne počet podformulí, jak je vysvětleno na té wiki. Nebo se mýlím? Cvičící mi trošku neznačil, že výsledek by mohl být jiný...

Kondr · 10. 05. 2009 18:15

↑ jamesr:Počet symbolů je v našem případě v první formuli m=2n, ve druhé n*2^n=m*2^(m/2-1). Je to exponenciální nárust, ale s menším základem.

jamesr · 11. 05. 2009 11:31 — Editoval jamesr (11. 05. 2009 11:57)

A počítáš jako symboly i logické spojky? Já jsem zplodil nějaký takovýto vztah ((n+1)/2) *2^((n+1)/4) - 1 kde n je počet všech symbolů...zaprvé je to pěkný hnus a za druhé to nefunguje vždy... např. pro formuli (A1*B1*C1) v (A2*B2*C2) .. tady počítám počet symbolu 11 (6písmen+5spojek)

//i když ono to může být správně a prostě pro tu formuli bude velikost menší než maximální odhad
////pokud by to bylo správně asymptotický odhad by bylo O (n*2^n) ??

Kondr · 11. 05. 2009 18:26

↑ Kondr: Jak jsem naznačil, asymptotický odhad by měl být $O(n\cdot \sqrt{2}^n)$ . Jak správně píšeš, je to pro nejhorší případ (v zadání je "jak maximálně velké ..."), realizuje se jen pro speciální typ formulí.

jamesr · 11. 05. 2009 19:07

teď opravdu nechápu, jak se tam vzala odmocnina...

Kondr · 11. 05. 2009 19:53

↑ jamesr:
To je jen jinak zapsané $O(n\cdot 2^{n/2})$ , s tou odmocninou mi to přišlo názornější.

jamesr · 11. 05. 2009 20:23

jezis no jasne, ja jsem idiot :)

Matematické Fórum

#1 04. 05. 2009 12:16 — Editoval vilem (04. 05. 2009 12:17)

Odhad velikost formule

#2 05. 05. 2009 14:52

Re: Odhad velikost formule

#3 06. 05. 2009 11:59

Re: Odhad velikost formule

#4 06. 05. 2009 13:42

Re: Odhad velikost formule

#5 10. 05. 2009 17:24

Re: Odhad velikost formule

#6 10. 05. 2009 18:15

Re: Odhad velikost formule

#7 11. 05. 2009 11:31 — Editoval jamesr (11. 05. 2009 11:57)

Re: Odhad velikost formule

#8 11. 05. 2009 18:26

Re: Odhad velikost formule

#9 11. 05. 2009 19:07

Re: Odhad velikost formule

#10 11. 05. 2009 19:53

Re: Odhad velikost formule

#11 11. 05. 2009 20:23

Re: Odhad velikost formule

Zápatí