Matematicka logika (informacija)

[Gost]

Ok, ja sam prošla i ne moram na usmeni, no čisto ak nekog zanima...
prema pravilima, što ne bi trebalo dijeliti samo broj bodova s kolokvija s 3 i tome pribrojit sve bodove iz šk zadaća?
Ugl, osim ako su ovo neka nova pravila, ono nije baš dobro izračunato...pa ako netko ne želi na usmeni i tak...

Što se tiće usmenog, moraš znati dobro sve one definicije i primjere.. nemam drugih informacija.

Sretno!

[fireball]

[Gost]

Da li mi netko može reći kako glasi jaki teorem potpunosti za sistem PD?

To je bilo pitanje sad na popravnom, a ja ne vidim gdje se to nalazi u skripti, tj. nema ga kod dedukcije.. bila sam na pred kad se radila dedukcija i nemam to zapisano.

[fireball]

[Megy Poe]

[Gost]

[fireball]

[Sorcererosaurus]

Pozdrav!

Zovem se Josip Žubrinić i ovaj semestar držat ću demonstrature iz Matematičke logike.
Termin demonstratura je četvrtkom od 14 do 16.
Preporučam da mi se najavite za demonstrature mailom na jzubrin@student.math.hr sa pitanjima koja vas zanimaju.

Josip

[momento]

Pozdrav,

nisam bio u Zagrebu zadnjih 2 tjedna. Da li mi moze netko reci do kud smo dosli na vjezbama kod asistenta Cacica, i da li je spominjao prvi blic i njegovo odrzavanje?

Hvala

[luka_m]

Evo sa stranica VČ:
https://sites.google.com/site/mathnastava/home/matematicka-logika/prvaskolskazadaca-2

[Anonymous123]

Pozdrav,

zadnje gradivo koje ulazi u kolokvij je glavni test?

[snoops]

Iz vježbi da, a predavanja do dedukcije, tj. zadnje je prop 1.52 (i to ulazi)

[Ryssa]

Koje gradivo vježbi ulazi u 2. školsku zadaću ?

[nuclear]

Kod dokazivanja valjanosti (i ostalog) neke formule, bunim se koje sve točno elemente skupa M (nosača) moram testirati na kojim formulama. Na primjer:

Ex ( R(x,x) <-> Vy R(x,y) ) testira se valjanost, pretpostavimo suprotno, da nije
-uvodi se novi element, a i grana na dvije mogućnosti
-jedna daje kontradikciju, druga:

R(a,a) T
Vy R(a,y) neT -> tu moramo uvesti novi element, b
R(a,b) neT

sada me muči, treba li testirati prethodne formule za b ili smo došli do kraja i pronašli mogućnost? Gledam riješeni zadatak od nekoga (?) i ta osoba je dalje provjeravala prvotnu formulu za a i b i išla u beskonačnost. Dok bi ja evo stala . Kako odlučiti koje sve treba točno provjeriti?

[luka_m]

Trebalo bi testirati sve elemente uvedene na istoj grani, ispod ili iznad formule koja je AT ili E_|_.

Može se dogoditi da glavni test ne može završiti; ta se mana nikako ne može u potpunosti sanirati, tj. za bilo kakav test valjanosti/slijeda postojat ce formule koje se ne mogu algoritamski provjeriti.

U konkretnim situacijama je moguće doći do rješenja uz varijantu glavnog testa (koja je opskurno spomenuta u jednom primjeru u knjizi); naime kod formula koje su A_|_ ili ET može se uvesti stari element. To je moguće ako pretpostavimo da nam je domena (nosač) konačna, pa mora doći do ponavljanja. No i tu treba biti oprezan sa zaključivanjem, osim u slučaju da pretpostavimo da je domena jednoclana. Korisnost toga je u tome sto za npr. za dokazati da formula nije valjana, dovoljno je pokazati da postoji bilo kakva struktura na kojoj nije valjana. Kako god, sumnjam da se očekuje da koristimo takve trikove u nastavi, s obzirom da nisu objašnjeni u knjizi (tako da bih ja koristio standardni test i stavio tri točkice kad dode do periodicnog ponavljanja već videnog)

[Gost]

Moraš vratiti b i u gornju formulu. Uvijek moraš testirati za sve koje si uvela u toj grani, i prije i poslije formule.

Da staneš tu kako si mislila, dobila si strukturu M={a,b}, i fi(R)={(a,a)}.
Ti tvdiš da zadana formula nije istinita u toj stukturi. Ali kad uvrstiš b u formulu imaš:

Rbb <-> (za svaki y) Rby

Lijeva strana ne vrijedi, niti desna, znači formula je istinita.

Znači da u toj strukturi postoji x takav da je ( Rxx <-> (za svaki y) Rxy ) tj. zadana formula je istinita pa ti to nije dobar primjer za oborivost formule.

[student_92]

Može li netko napisati ukratko dokaz ove tvrdnje?

"Svaka instanca sheme aksioma [tex]\forall x (A \to B) \to (A \to \forall x B)[/tex],
gdje formula [tex]A[/tex] ne sadrži slobodne nastupe varijable [tex]x[/tex],
jest valjana formula."

[luka_m]

Uzmemo proizvoljnu instancu te formule za neki (sigma-) jezik, proizvoljnu strukturu s i valuaciju v. Treba pokazati da je naša instanca istinita na interpretaciji (s, v). Recimo da u instanci na mjesto A dolazi neka formula F, a na mjesto B neka formula G.

Istinita je akko nije istinito Ax(F -> G), ili je istinito F -> AxG. Pretpostavimo da je istinito Ax(F -> G) (trebamo dobiti da je u (s, v) istinito F -> AxG). Za svaku valuaciju vx tada vrijedi F -> G. Ako je F istinito u (s, v), istinito je i na (s, vx) (F ne sadrži x), pa je na (s, vx) istinito i G. vx je proizvoljna pa je u (s, v) istinito i AxG. F ili nije istinita ili je istinita u (s, v); u drugom slučaju je istinita i AxG, pa (po def. istine kondicionala za (s, v)) imamo da (s, v) |= F -> AxG

[student_92]

Zahvaljujem.
Ako nije problem, može li još i ovaj:
"Dokazati da je svaka instanca sheme aksioma [tex]\forall x A(x) \to A(t/x)[/tex],
gdje je t term slobodan za varijablu x u formuli A."

(Zanima me kako se upotrebljava podcrtana pretpostavka.)

[luka_m]

Evo skica. Uzimamo proizvoljnu (s, v). U F(t/x), svaka (nova) pojava t (neka su to podformule t1, ..., tk) biva slana u neke elemente m1, ..., mk nosača. Mogli bismo indukcijom po složenosti terma i formule pokazati da m1 = ... = mk, no recimo da je to očito (valuacija konstanti i funkcija u t ne ovisi ni o čemu, valuacija varijabli u t ovisi o kvantifikatorima u čiji doseg upadaju varijable iz t, a kojih - ovdje koristimo pretpostavku - nema). Stavimo m := m1 (= ... = mk)

Uzmimo valuaciju v'(var) = v(var) osim za var = x; za slučaj var = x stavimo v'(x) = m. Pretpostavimo da AxF. Za svaku vx, F(x) je istinito za (s, vx). Tada je i za našu v' F istinito za (s, v'), jer je naša v' jedna od vx formula, jer od v se razlikuje najviše kod v(x) != v'(x). (s, v') se slaže s (s, v) za F(t/x) jer smo tako definirali v', pa je F(t/x) istinita za (s, v).

* - cijelo vrijeme pišem "u"/"na" (s, v), a trebalo bi "za" (istinito za interpretaciju )