Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

#1 02. 04. 2009 11:42

jorge
Zelenáč
Příspěvky: 1
Reputace:   0 
 

dukaz splnitelnosti formuli

Ahoj,
zoufale prosim o pomoc...
mam odevzdat do skoly projektik
http://www.chlivek.com/UTI.jpg
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...

Offline

 

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

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4247
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
 

Re: dukaz splnitelnosti formuli

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á.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech