Matematicka logika, predikatska logika, nekoliko pitanja

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.

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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.

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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)

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



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.



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)}.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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.

To pre svega nije model, jer 0 ne pripada domenu D, pa G nije podskup od D.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

mislio sam prazan skup samo ne nadjoh simbol, pa stavih nula

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).

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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).

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

∀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.