dalsi priklad zo skusky.. 02

[hydrant]

Tak mam aj ja nejake skuskove priklady co neviem...
Verim, ze sa najde niekto, kto to vyriesi

1) Ax[t] <-> (Vx)(x=t -> A)

2) Je predikatova logika uplna? (nestaci ano nie, ale nejaky dokaz)

3) Ktora z mnozin je splnitelna? Najdite jej model. napr. {((A->B)->B)}
je mi jasne ze A aj B moze mat hodnotu 1 a formula je splnena, lenze ako zapisem jej model? Vo vyrokovej logike je model ohodnotenie premennych, ja ziadne premenne nevidim:( mam tam napisat v(A) = v(B) = 1 ?? (to v je s ciarkou nad sebou) podla mna to nie je uplne spravne pretoze model podla definicie je nieco ine

4) Prevedte formulu Ado disjunktivnej normalnej formy.... ok to je lahke, ale co ked je tam potom podotazka:
a) kolko je dosledkov A?
b) kolko je kompletnych rozsireni teorie A?

Budem vdacny za vsetky hinty... tak piste, piste, piste. Ja sa odvdacim mojimi mudrostami, ak nejake najdem. THX

[MyS]

1) viz skripta str. 70
2) proc by nebyla, mame vetu o uplnosti
3) jestli to chces v predikatovce, tak chapej B jako B(x), tedy jako predikat

[Dawe]

1) viz skripta str70 kde?
2) Tohle jsem tak nějak pochopil, ale nejsem si vším jistej. Bezesporná znamená, že mám formuli, která z toho nejde dokázat? Jako třeba (A & non A) ? Ten zbytek z tý věty je mi jasnej.
3)dosadit třeba za A: x<y ... a pak asi ještě něco za x a y.
4) To nechápu, asi jsem tam ještě nedočet...

[MyS]

No, mimo pdfek ma stepanek na strance i PL.PS. a tam, na konci kapitolky "PL s rovnosti".
Jo, taky tu bezespornost tak chapu. Nebo je to ekvivalentni tomu, ze ta teorie ma model, tj. je splnitelna.

[Dawe]

Dík za info, ale já to nemůžu rozbalit, takže zůstanu u slidů a je to...

[MyS]

skripta

[hydrant]

1) viz skripta str. 70
2) proc by nebyla, mame vetu o uplnosti
3) jestli to chces v predikatovce, tak chapej B jako B(x), tedy jako predikat

1) Za tie skripta vdaka.
2) No, bohuzial to tam nevidim. Veta o uplnosti tvrdi:
i) ak je A formule jazyka L, potom plati T|-A prave ked T|=A
ii) teoria T je bezesporna, prave ked ma model

Lenze podla definicie:
Teoria T je uplna ak je bezesporna, a pre kazdu formulu plati bud T|-A alebo T|-(nA)
Takze mne sa zda, ze to nie je zrovna to iste, ak sa mylim vysvetlite mi to prosim

3) ano to dava zmysel, tak ale ako napisem model? M = <{1}, B={}, A={1}> ak chcem aby B malo ohodnotenie 0, a A malo ohodnotenie 1? Potom este prepisem formule teorie z ((A->B)->B) na (A(x)->B(x))->B(x)
je tak?

4) Co ta styrka? To tam zajtra urcite dostaneme... necital to niekto v skriptach? Ja som presiel iba slajdy.

[jaruch]

a to co ako je to kompletne rozsirenie a dosledky?

[hydrant]

a to co ako je to kompletne rozsirenie a dosledky?

no keby som to vedel tak sa tu nepytam... v slajdoch som definiciu nenasiel

[macbeth]

je to v tych skriptach asi od strany 100 o nejakych rozsireniach, ale hlava mi to nejak uz nepobrala...

[Tuetschek]

2) No, bohuzial to tam nevidim. Veta o uplnosti tvrdi:
i) ak je A formule jazyka L, potom plati T|-A prave ked T|=A
ii) teoria T je bezesporna, prave ked ma model

Lenze podla definicie:
Teoria T je uplna ak je bezesporna, a pre kazdu formulu plati bud T|-A alebo T|-(nA)
Takze mne sa zda, ze to nie je zrovna to iste, ak sa mylim vysvetlite mi to prosim

Me se taky zda ze z toho primo neplyne ze PL je uplna ... napadlo mi takovy zverstvo - dokazat "oblibenou" indukci podle slozitosti uzavrene formule primo z definice uplne teorie ze je pro kazde A bud A nebo ¬A dokazatelna:

Pro A tvaru (∀x)B nebo (∃x)B, kde je B atomicka formule by to melo byt dany,
pro A tvaru (∀x)¬B nebo (∃x)¬B, vim-li ze je dokazatelny bud ¬B nebo B se da prevyst podle prenexni operace
na dokazatelnost ¬(∃x)B, resp. ¬(∀x)B,
pro A tvaru (∀x)(B -> C) nebo (∃x)(B -> C) by melo jit z dalsi prenexni operace previst na (B -> (Qx)C), B a C jsou jednodussi nez A, C je uzavrena a B je podle vety o uzaveru dokazatelna <-> je dokazatelny uzaver B...

Myslite nekdo ze by se to dalo dokazat takhle, ze to neni uplne scestny?

[MyS]

A co treba takhle:
-PL (axiomy) maji model (libovolny) -> PL je bezesporna
- Vezmu T=axiomy PL a Con(T) je taky bezesporna mnozina. Tu rozsirim na maximalni bezespornou. Pak plati, ze bud Con(T)|-T nebo Con(T)|-nT. Kdyby tam byly obe, je to spor s bezespornosti. Kdyby zadna, je to spor s maximalitou.

[dr.Bik]

Predikatova logika neni uplna.

Pokud by byla uplna, tak pro kazdou formuli A bud |-A, nebo |-nA

Vezmu formuli (je to PL s rovnosti) x=0
V interpretaci, kde za mnozinu individui vezmu {0} je tato formule pravdiva, ale jsou samozrejme i takove interpretace, kde neplati.
Potom ani jedna z formuli neni v PL dokazatelna

(stejne tak by slo vzit treba formuli 1+1=0, v Z_3 neplati, ale v Z_2 jo)

Kdyztak PL.PS okolo strany 88

[jaruch]

a je nejaky rozdiel medzi tym, ci je PL uplna a ci jej formalny system PL uplny? bo v skriptach sa pise, ze formalny system PL je uplny.

[MyS]

Vezmu formuli (je to PL s rovnosti) x=0

Ale pozor, musis vzit UZAVRENOU formuli (def. uplny teorie)...