Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
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...
Offline
Lemma 1
Každou formuli jde zapsat v jednom ze tří tvarů
* formule tvořená pouze prvky V a logickými spojkami
* formule
* formule
Důkaz: každou formuli lze převést do konjunktní normální formy (KNF).
* Pokud by některá klauzule obsahovala , 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
* Pokud by některá klauzule obsahovala spolu s jinými symboly, lze symbol vyloučit
* Pokud by některá klauzule obsahovala pouze , je celá formule nesplnitelná a lze ji psát jako
Takto jsme ukázali, že každou formuli, která není tvaru nebo , 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 , 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 byla , zvolíme příslušné . Ve všech kromě nahradíme symbolem (protože , nezmění se tím pravdivostní hodnota). Formule
je kratší než původní , takže pro ni existuje splňující přiřazení. Tím ale vytvoříme splňující přiřazení pro , což je spor.
Nyní předpokládejme, že žádná z formulí není a zvolme . Některé formule jsou , pro ně bude 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 pro všechna i. Našli jsme tedy splňující ohodnocení a máme spor.
Pokud jde o druhou část, stačí říct, že je daného tvaru a není splnitelná.
Offline
Stránky: 1