Par dotazu pred zkouskou

Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Par dotazu pred zkouskou

Příspěvek od Osiris »

Medved_ píše:Jasne, myslel jsem to spis tak, ze treba k VL mame dokazanych asi 10 vet + nejake pokrocilejsi nastroje pro dokazovani, takze se pomoci toho da uz leccos vymyslet, navic na tech dukazech vidis zhruba tu techniku, jak na to. Kdezto v Peanove aritmetice toho moc nedokazes, kdyz ti neukazi jak na to. Proste me tenhle predmet sere, tak jsem chtel vyjadrit svoji frustraci, no :D:D

To je jak, kdyby ti v analyze dali axiomy realnejch cisel a chteli po tobe pocitat limity :X
Indukce řeší vše :twisted:
Osiris
Triebenekl
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 5. 2. 2007 20:55
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Par dotazu pred zkouskou

Příspěvek od Triebenekl »

Medved% píše:Jeste takovy trapny dotaz: odkud jste se ucili treba dokazovani v Peanove aritmetice? Ja ve skriptech snad ani nenasel axiomy, natoz tak nejake navody na to, jak dokazovat...
axiomy Robinsonovy a Peanovy aritmetiky mas v prednasce "Predikátová logika 6" http://ktiml.ms.mff.cuni.cz/vyuka/materialy.html

Na tomhle foru je zatim jeden priklad na pouziti schema indukce http://forum.matfyz.info/viewtopic.php?t=1973

Na cvicenich jsme jeste dokazovali asociativitu a komutativitu scitani.
Pro ty, kteri se k tomu na cvikach nedostali to klidne prepisu - napr. tu asocicativitu.

pripomenu nektere axiomy Peanovy aritmetiky:
Q4: x+0 = x
Q5: x+S(y) = S(x+y)
Ind: Ax[0] -> {(Vx)(A -> Ax[S(x)]) -> (Vx)A}

Chceme dokazat (x+y)+z = x+(y+z)
(dokazovali jsme to celkem neformalne)

Nejdriv to dokazeme pro nulu:
(x+y)+0 = x+(y+0)
ted pouzijeme Q4 na pravou i levou stranu a dostaneme:
x+y = x+y
coz plati

Ted udelame indukcni krok
predpokladam, ze plati (x+y)+z = x+(y+z) a chci odvodit (x+y)+S(z) = x+(y+S(z)):
(x+y)+z = x+(y+z)
z axiomu rovnosti pro funkce (R2) a vety o rovnosti dostanu:
S((x+y)+z) = S(x+(y+z))
dale pouziji Q5 na levou stranu
(x+y)+S(z) = S(x+(y+z))
a pouziji dvakrat Q5 na pravou stranu a ziskam:
(x+y)+S(z) = x+(y+S(z))
Naposledy upravil(a) Triebenekl dne 23. 6. 2008 22:17, celkem upraveno 1 x.
Triebenekl
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 5. 2. 2007 20:55
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Par dotazu pred zkouskou

Příspěvek od Triebenekl »

Premyslel jsem, jak z toho meho neformalniho dukazu udelat formalni.
Ve skoro kazdem kroku pouzivam vetu o rovnosti (diky ni muzu cast formule nahradit tim, cemu se to rovna).
Nakonec by se asi sluselo to vsechno dosadit do axiomu indukce a odvodit, ze plati to, co jsme chteli.

nejprve pro nulu:
1) |- x+y = x+y //(R2)
2) |- (x+y)+0 = x+(y+0) //dvakrát(Q4) + Veta o Rovnosti

indukcni krok:
3) |- (x+y)+z = x+(y+z) -> S((x+y)+z) = S(x+(y+z)) //(R2)
4) |- (x+y)+z = x+(y+z) -> (x+y)+S(z) = x+(y+S(z)) //třikrát(Q5) + Veta o Rovnosti
5) |- (Vx) ((x+y)+z = x+(y+z) -> (x+y)+S(z) = x+(y+S(z))) //pravidlo generalizace

"dosazeni" do axiomu indukce:
6) |- ((x+y)+0 = x+(y+0)) -> {(Vx) ((x+y)+z = x+(y+z) -> (x+y)+S(z) = x+(y+S(z))) -> (Vx) ((x+y)+z = x+(y+z))} //axiom indukce pro A=((x+y)+z = x+(y+z))
7) |- (Vx) ((x+y)+z = x+(y+z) -> (x+y)+S(z) = x+(y+S(z))) -> (Vx) ((x+y)+z = x+(y+z)) //MP pro 2) a 6)
8) |- (Vx) ((x+y)+z = x+(y+z)) //MP pro 5) a 7)
9) |- (x+y)+z = x+(y+z) //Veta o Uzaveru

myslite, ze by to takhle proslo u zkousky?
Medved
Admin(ka) level I
Příspěvky: 168
Registrován: 30. 5. 2006 21:18

Re: Par dotazu pred zkouskou

Příspěvek od Medved »

Mno, tak jsem si prosel ten odkazovany material PL6 a bud jsem uplny imbecil, nebo je to tam napsane jak pro ufony, protoze asi tak 95% veci vubec nerozumim, ani tomu jak to navazuje na dalsi latku, ani co to rika, ani jak se pomoci toho pocitaji nejake priklady na zkousce :D Myslim, ze po dlouhe dobe zase napisu neco do ankety...

Jinak diky Triebenklovi za ty dukazy, kdybys chtel napsat jeste komutativitu, tak bych se nezlobil :) Sorry, ze ja moc konstruktivne neprispeju, ale nemam cim :( Ale to co tady pises vypada bez chyby a docela verim tomu, ze to je dobre.
Triebenekl
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 5. 2. 2007 20:55
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Par dotazu pred zkouskou

Příspěvek od Triebenekl »

zjistil jsem, ze komutativita scitani v Peanove aritmetice se tu na foru uz resila a da se najit na http://www.peklo.unas.cz/
presneji http://www.peklo.unas.cz/logika/peano2.pdf
Odpovědět

Zpět na „2007“