Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Matematicka logika, predikatska logika, nekoliko pitanja

[es] :: Matematika :: Matematicka logika, predikatska logika, nekoliko pitanja

[ Pregleda: 6310 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

cozi

Član broj: 6066
Poruke: 221
91.150.107.*



+111 Profil

icon Matematicka logika, predikatska logika, nekoliko pitanja23.01.2009. u 11:54 - pre 126 meseci
Koliko je meni poznato, u opstem slucaju ne postoji efektivan postupak, algoritam, za utvrdjivanje da li je neka recenica valjana formula.

Sada, interesuje me na koji nacin da utvrdim da li je neka formula valjana, tj. kada dobijem, recimo, sledece dve formule:

∃x∀y(Fx⇔Fy)
¬∃y∀x(Pxy⇒Pyx)

Zatim, kada utvrdim da nisu valjane formule koji su sledeci koraci, tj. koji su postupci do kontra modela.

Molio bih za sto pragmaticnije odgovore, izbegao bih neku teorisko produbljivanje; vise me interesuje da neko ko zna da uradi ova dva zadatka sto jednostavnije objasni kako ih radi.
Hvala.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8271
*.dynamic.sbb.rs.



+2636 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja23.01.2009. u 13:49 - pre 126 meseci
Oma ti kazem, postoji algoritam takav da:

1. Ako je ulazna fomula valjana, on staje u konacnom broju koraka sa porukom "Formula je valjana".
2. Ako formula nije valjana onda ili staje u konacnom broju koraka sa porukom "Formula nije valjana" ili se nikada ne zaustavlja.

Dakle, valjanost je uvek dokaziva standardnim postupkom, ali je nevaljanost tvrdji orah i otuda predikatski racun nije odluciv.

Za prvu formulu kontramodel je bilo koja relacija F koja nije ni puna ni prazna, a za drugu imas vise mogucnosti:

1. Puna relacija.
2. Prazna relacija.

kao i razne druge.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

cozi

Član broj: 6066
Poruke: 221
93.86.51.*



+111 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja23.01.2009. u 14:45 - pre 126 meseci
Posto vidim, sto bi se reklo, da se razumes u temu, zamolio bih te za dodatna objasnjenja; druge ES-ovce takodje.

Bicu malo konkretniji:
Dakle, na ispitu, cesto, nije dat argument u prirodnom jeziku, vec samo formula, tacnije vise formula od kojih su neke valjane, a druge ne.
E, sad: obicno radim pod pretpostavkom da je formula valjana, primenjujem pravila predikatskog racuna i ako ne mogu da resim (dokazem) zakljucim da nije valjana...
Problem je sto se cesto zanesem, pa pretpostavim ili precrtam nesto, sto ne mogu (po pravilima) ili najcesce izvucem kvantifikator ∃ iznad recimo Fx...
Drugi nacin: pretpostavim da formula nije valjana uradim valuaciju ( nisam siguran da li je odgovarajuci termin za sledece) :

recimo: ¬∃y∀x(Pxy⇒Pyx)
...........0.........1...1.1
.....................0......1
.....................0......0

odredim domen D={a,b} zatim P={(ab), (ba)} i kontra model bi bio ¬¬∃y∀x(Pxy⇒Pyx) tj. ∃y∀x(Pxy⇒Pyx)
Problem je sto u komplikovanijim formulama pogubim se u ovim 0i1 i cesto gresim, tj. ne odredim pravilno skup P{} ili F{}...

Zato me interesuje koji je najbolji nacin da otkrijem da li je recimo sledeca formula valjana :

∃x(Fx^Gx)⇒(∃xFx^∀yGy) ili malo slozenija formula ∃x(∃yFy⇒Gx)⇒∀x(∃yFy⇒Gx)

Zamolio bih te ili ako neko drugi zna, da uradi ovaj zadatak/e, da vidim postupak;
posto dosta toga se secam, a dosta sam zaboravio, pa smatram da bi na taj nacin najbolje shvatio sta i kako...
Hvala.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8271
195.222.97.*



+2636 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja24.01.2009. u 17:27 - pre 126 meseci
Pretpostavimo da formula nije valjana. Tada postoji model u kome je ona netačna. U tom modelu je formula tačna, a formula netačna. Znači, postoji konstanta takva da važi i . Obzirom da je formula tačna, a formula netačna, onda formula netačna, pa postoji neko tako da nije . Kontradikciju nismo izveli, pa bi bilo logično pretpostaviti da formuls nije valjana. Sledeći dobijeni opis modela nalazimo model sa domenom u kome važi , i ne važi . Istinitosnu vrednost za izaberi kako hoćeš i dobio si kontramodel.

Probaj ti da uradiš drugi zadatak, a ja ću da ga prekontrolišem.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

cozi

Član broj: 6066
Poruke: 221
77.46.193.*



+111 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja25.01.2009. u 11:40 - pre 126 meseci
Sada mi je dosta jasnije, hvala ti mnogo.

Dakle, zapisano kako od nas ocekuju na ispitu, D={a,b} F={a,b} G={a} a kontra model bi glasio : ∃x(Fx^Gx)⇒¬(∃xFx^∀yGy)

∃x(∃yFy⇒Gx)⇒∀x(∃yFy⇒Gx)
Pretpostavimo da formula ∃x(∃yFy⇒Gx)⇒∀x(∃yFy⇒Gx) nije valjana; tada postoji model u kome je ona netacna. U tom modelu formula ∃x(∃yFy⇒Gx) je tacna, a formula ∀x(∃yFy⇒Gx) netacna, znaci postoji konstate a, b takve da je tacno Fb, Ga. Posto je tacna formula ∃yFy a formula ∀x(∃yFy⇒Gx) onda formula Fx netacna ( ili formula ∀xFx ? ) sada nije mi jasno da li postoji neko b tako da niije Gb i da li je to kontradiktorno sa prvom pretpostavkom ili postoji neko c tako da ne vazi Gc(mada mislim da nema potrebe za c, jer nema promenljive z ili vec)?
Ja bih uradio: Postoji neko b tako da nije Gb, pa mozemo zakluciti da formula nije valjana. Dakle model ima domen D={a,b} u kome vazi Fb, Ga i ne vazi Gb istinosna vrednost Fa mogu da izaberem ( i ovo mi nije bas jasno imamo li uopste Fa)

Dakle : D={a,b} F={a,b} G={a} kontramodel : ∃x(∃yFy⇒Gx)⇒¬∀x(∃yFy⇒Gx)


∀xFxx⇒∀x∀y(Fxy⇒Fyx)
Pretpostavimo da formula ∀xFxx⇒∀x∀y(Fxy⇒Fyx) nije valjana; tada postoji model u kome je ona netacna. U tom modelu ∀xFxx je tacna, a formula ∀x∀y(Fxy⇒Fyx) netacna, znaci postoji konstata a takva da je tacno Faa. Onda postoje neko a,b tako da nije Fba, istinosnu vrednost Fab mogu da izaberem. Model ima domen D={a,b} F={ (a,a) , (a,b) } kontra model ∀xFxx⇒¬∀x∀y(Fxy⇒Fyx)

 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8271
195.222.97.*



+2636 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja25.01.2009. u 12:25 - pre 126 meseci
Citat:
cozi: Dakle, zapisano kako od nas ocekuju na ispitu, D={a,b} F={a,b} G={a} a kontra model bi glasio : ∃x(Fx^Gx)⇒¬(∃xFx^∀yGy)


Pardon, kontramodel je ovo prvo (D={a,b} F={a,b} G={a}).

Citat:
cozi: Pretpostavimo da formula ∃x(∃yFy⇒Gx)⇒∀x(∃yFy⇒Gx) nije valjana; tada postoji model u kome je ona netacna. U tom modelu formula ∃x(∃yFy⇒Gx) je tacna, a formula ∀x(∃yFy⇒Gx) netacna, znaci postoji konstate a, b takve da je tacno Fb, Ga.


Pardon, postoje konstante a,b td. je ∃yFy⇒Ga tačno i ∃yFy⇒Gb netačno. Ovo drugo znači da je ∃yFy tačno i Gb netačno. Iz ∃yFy i ∃yFy⇒Ga sledi Ga, a iz ∃yFy da postoji konstanta c takva da je Fc. Znači, jedan od kontramodela je D={a,b,c}, F={c}, G={a}, ali postoje i drugi.

Citat:
cozi: Pretpostavimo da formula ∀xFxx⇒∀x∀y(Fxy⇒Fyx) nije valjana; tada postoji model u kome je ona netacna. U tom modelu ∀xFxx je tacna, a formula ∀x∀y(Fxy⇒Fyx) netacna, znaci postoji konstata a takva da je tacno Faa.


Pardon, Fxx važi za svako x, a postoje konstante a,b takve da je Fab⇒Fba netačno, tj. da važi Fab i ne važi Fba. Pošto Fxx važi za svako x, pa samim tim važi i Faa i Fbb, jedan od kontramodela je D={a,b}, F={(a,a),(a,b),(b,b)}.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

cozi

Član broj: 6066
Poruke: 221
77.46.193.*



+111 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja25.01.2009. u 20:21 - pre 126 meseci
Citat:
Pardon, postoje konstante a,b td. je ∃yFy⇒Ga tačno i ∃yFy⇒Gb netačno. Ovo drugo znači da je ∃yFy tačno i Gb netačno. Iz ∃yFy i ∃yFy⇒Ga sledi Ga, a iz ∃yFy da postoji konstanta c takva da je Fc. Znači, jedan od kontramodela je D={a,b,c}, F={c}, G={a}, ali postoje i drugi.


Da li bi jedan od kontramodela mogao biti: D={a,b} F={a} G={0}

Nadam se da sada ne gresim mnogo, ako te ne mrzi da pogledas.

∃x(Fx^Gx)⇒(∃xFx^∀yGy) D={a,b} F={a,b} G={a}

∀x(FxVGx)⇒(∀FxV∀xGx) D={a,b} F={a} G={0}

¬∃x(Fx^Gx)⇒∃(Fx^Gx) D={a,b} F={a} G={0}

∃yFx(Fx<->Fy) D={a,b} F={0}

∀x(Fx⇒Gx)⇒∃x(Fx^Gx) D={a,b} F={a,b} G={a}

Hvala.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8271
*.dynamic.sbb.rs.



+2636 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja26.01.2009. u 13:56 - pre 126 meseci
Citat:
cozi: Da li bi jedan od kontramodela mogao biti: D={a,b} F={a} G={0}


To pre svega nije model, jer 0 ne pripada domenu D, pa G nije podskup od D.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

cozi

Član broj: 6066
Poruke: 221
93.86.100.*



+111 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja26.01.2009. u 16:21 - pre 126 meseci
mislio sam prazan skup samo ne nadjoh simbol, pa stavih nula
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3980
*.dynamic.sbb.rs.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+573 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja26.01.2009. u 16:34 - pre 126 meseci
Prazan skup ne smeš pisati u vitičastim zagradama, jer onda ima sasvim drugo značenje (u koje ne bih sada da zalazim). Piše se samo , a ako ti nije dostupan taj simbol, dovoljno je jasno i (bez ičega unutra).
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8271
*.dynamic.sbb.rs.



+2636 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja27.01.2009. u 08:12 - pre 126 meseci
E, pa u tom slucaju nemas kontramodel jer je tacno, a netacno za bilo koje , pa je formula netacna, pa je cela formula tacna u tom modelu (jer iz netacnog sledi bilo sta).
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

logika1311
Marko Jovovic

Član broj: 320353
Poruke: 1
*.dynamic.sbb.rs.



Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja09.05.2014. u 19:05 - pre 62 meseci
∀x∃yFxy > ∃y∀xFxy

> je implikacija

Samo me interesuje ako je npr. F voleti, da li su ovde antecedens i konsekvens isto, odnosno Svako voli nekog? Nije mi jasno da li je ovo samo neki trik kada se samo menja raspored univerzalnog i egzistencijalnog kvantifikatora jer je i u konsekvensu pored x univerzalni a pored y egzistencijalni, ili se ipak ne bi to isto citalo.
Ja ovu recenicu citam kao: Ako svako voli nekog onda svako voli nekog, je l to dobro ili nije? Hvala puno, pozdrav.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8271
*.ptt.rs.



+2636 Profil

icon Re: Matematicka logika, predikatska logika, nekoliko pitanja09.05.2014. u 22:41 - pre 62 meseci
Ako svako voli bar nekoga, onda postoji neko koga vole svi (pa i on sam sebe).

Naravno, to nije logička istina. Obrnuti smer jeste.

Ako postoji neko koga svi vole (pa i on sam sebe), onda svako voli bar nekoga.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: Matematika :: Matematicka logika, predikatska logika, nekoliko pitanja

[ Pregleda: 6310 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.