Indukce řeší všeMedved_ 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
To je jak, kdyby ti v analyze dali axiomy realnejch cisel a chteli po tobe pocitat limity :X
Par dotazu pred zkouskou
-
- 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
Osiris
-
- 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
axiomy Robinsonovy a Peanovy aritmetiky mas v prednasce "Predikátová logika 6" http://ktiml.ms.mff.cuni.cz/vyuka/materialy.htmlMedved% 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...
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.
-
- 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
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?
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?
Re: Par dotazu pred zkouskou
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 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.
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.
-
- 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
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
presneji http://www.peklo.unas.cz/logika/peano2.pdf