Matematické Fórum

jorge · 02. 04. 2009 11:42

Ahoj,
zoufale prosim o pomoc...
mam odevzdat do skoly projektik

do predmetu uvod do teoreticke informatiky...
priznam se..v tehle te casti absolutne plavu... a bohuzel to je ma posledni prekazka k tomu abych mohl jit k statnicim - uz to opakuju :(
jestli by kdokoliv vedel co s tim a mohl nejak poradit, za kazdou trosku budu vdecny, dekuju moc...

Kondr · 18. 04. 2009 11:38 — Editoval Kondr (18. 04. 2009 11:39)

Lemma 1
Každou formuli $\varphi_i$ jde zapsat v jednom ze tří tvarů
* formule tvořená pouze prvky V a logickými spojkami
* formule $\top$
* formule $\bot$

Důkaz: každou formuli lze převést do konjunktní normální formy (KNF).
* Pokud by některá klauzule obsahovala $\top$ , lze tuto klauzuli vyloučit (pokud bychom takto měli vyloučit poslední klauzuli, znamená to, že celá formule je tautologie a lze ji psát jako $\top$
* Pokud by některá klauzule obsahovala $\bot$ spolu s jinými symboly, lze symbol $\bot$ vyloučit
* Pokud by některá klauzule obsahovala pouze $\bot$ , je celá formule nesplnitelná a lze ji psát jako $\bot$
Takto jsme ukázali, že každou formuli, která není tvaru $\bot$ nebo $\top$ , ale jeden z těchto symbolů obsahuje, lze upravit na kratší tvar (který bude stále v KNF). Proto formule převedená na co nejkratší tvar KNF je v jednom ze tří tvarů popsaných v lemmatu.

Připravili jsme si lemma a můžeme jít na důkaz. Ten povedeme sporem. Předpokládejme, že máme takovou formuli $\varphi$ , pro kterou splňující ohodnocení neexistuje a navíc je pro ni ze všech možných takových formulí n nenjmenší možné.

Pokud by nějaká formule $\varphi_i$ byla $\top$ , zvolíme příslušné $x_i=1$ . Ve všech $\varphi_j$ kromě nahradíme $x_i$ symbolem $\top$ (protože $x_i=1$ , nezmění se tím pravdivostní hodnota). Formule
$(x_1\equiv \varphi_1)\wedge(x_2\equiv \varphi_2)\cdots\wedge (x_{i-1}\equiv \varphi_{i-1})\wedge(x_{i+1}\equiv \varphi_{i+1})\cdots\wedge(x_{n}\equiv \varphi_{n})$ je kratší než původní $\varphi$ , takže pro ni existuje splňující přiřazení. Tím ale vytvoříme splňující přiřazení pro $\varphi$ , což je spor.

Nyní předpokládejme, že žádná z formulí $\varphi_i$ není $\top$ a zvolme $x_1=x_2=\cdots=x_n=0$ . Některé formule $\varphi_i$ jsou $\bot$ , pro ně bude $x_i\equiv\varphi_i$ splněno zřejmě. Jiné vzniknou spojkami z prvků V, nicméně tyto spojky pokud mají za oba parametry 0 vrátí vždy 0, proto budou splněny ekvivalence $x_i\equiv\varphi_i$ pro všechna i. Našli jsme tedy splňující ohodnocení a máme spor.

Pokud jde o druhou část, stačí říct, že $x_i\equiv\neg x_i$ je daného tvaru a není splnitelná.

Matematické Fórum

#1 02. 04. 2009 11:42

dukaz splnitelnosti formuli

#2 18. 04. 2009 11:38 — Editoval Kondr (18. 04. 2009 11:39)

Re: dukaz splnitelnosti formuli

Zápatí