Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIČKA LOGIKA

Teorema potpunosti

[inlmath]\left[p\land\left(q\Rightarrow\lnot p\right)\right]\Leftrightarrow\lnot\left(p\Rightarrow q\right)[/inlmath]

Teorema potpunosti

Postod Vv123 » Subota, 16. Februar 2019, 16:55

Da li mi neko moze pojasniti teoremu potpunosti? :(
Vv123  OFFLINE
 
Postovi: 25
Zahvalio se: 7 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Teorema potpunosti

Postod ubavic » Subota, 16. Februar 2019, 17:18

Hajde nam preciziraj na koju tačno teoremu misliš (pošto postoje barem dve teoreme potpunosti). Takođe, napiši nam iz kog kursa si radila ovu teoremu (ako ovo pitaš za faks), da bih znao koje predznanje imaš.

Takođe, možeš i pogledati tekst na adresi https://ubavic.rs/work/propositional_logic/ (pogotovu poslednju glavu) u kom je jedna od teorema potpunosti pojašnjena i dokazana.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta

Re: Teorema potpunosti

Postod Daniel » Subota, 16. Februar 2019, 17:23

@Vv123, ovako se pitanja ne postavljaju.
Pored ovog što reče kolega Ubavic, potrebno je da napišeš kompletan tekst teoreme (tačka 11. Pravilnika), kao i da preciziraš koji ti njen deo nije jasan (tačka 6. Pravilnika).
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Teorema potpunosti

Postod Vv123 » Ponedeljak, 18. Februar 2019, 20:16

Izvinjavam se sto sam tek tako postavila pitanje bez ikakvih objasnjenja i smernica.
Znam da postoje teorema slabe i jake potpunosti (ovde konkretno za Lukasijevicev formalni sistem L).

Teorema slabe potpunosti sistema [inlmath]L[/inlmath] glasi: [inlmath]\models\phi[/inlmath] ako i samo ako [inlmath]\vdash_L\phi[/inlmath]. ([inlmath]\phi[/inlmath] je neka formula.)

Teorema jake potpunosti sistema [inlmath]L[/inlmath]: Za svaku teoriju [inlmath]T[/inlmath] i formulu [inlmath]A[/inlmath] vazi: [inlmath]T\vdash_LA[/inlmath] ako i samo ako [inlmath]T\models A[/inlmath].

([inlmath]T\vdash_LA[/inlmath] znaci da je formula [inlmath]A[/inlmath] deduktivna posledica teorije [inlmath]A[/inlmath], dok [inlmath]T\models A[/inlmath] znaci da je [inlmath]A[/inlmath] logicka posledica teorije [inlmath]T[/inlmath]. Za [inlmath]\models A[/inlmath] nisam sigurna sta znaci, a [inlmath]\vdash_LA[/inlmath] mislim da znaci da [inlmath]A[/inlmath] ima dokaz u [inlmath]L[/inlmath], odnosno [inlmath]A[/inlmath] je teorema formalnog sistema [inlmath]L[/inlmath].)

Znam i teoriju o postojanju modela (svaka neprotivrecna teorija ima model), kao i Lindenbaumovu teoremu (svaka neprotivrecna teorija je sadrzana u maksimalnoj, neprotivrecnoj teoriji), znam da se one koriste za teoreme potpunosti, ali mi to nije bas najjasnije.
(Teorija je protivrecna akko postoji neka formula [inlmath]A[/inlmath] takva da su i [inlmath]A[/inlmath] i [inlmath]\neg A[/inlmath] deduktivne posledice teorije [inlmath]T[/inlmath].
Teorija je maksimalna ako za svaku formulu [inlmath]A[/inlmath] vazi tacno jedno od [inlmath]A\in T[/inlmath] i [inlmath]\neg A\in T[/inlmath].)
Vv123  OFFLINE
 
Postovi: 25
Zahvalio se: 7 puta
Pohvaljen: 0 puta

  • +1

Re: Teorema potpunosti

Postod ubavic » Sreda, 20. Februar 2019, 11:20

Logici se može pristuputi iz dva ugla, preko teorije dokaza, i preko teorije modela.
Prvo, možemo logičke izraze posmatrati kao nizove simbola (reči), a dokaze kao transformacije tih nizova po nekim određenim pravilima. U ovom kontekstu se javlja simbol [inlmath]T\vdash_L\phi[/inlmath], koji oznacava da se formula [inlmath]\phi[/inlmath] može dokazati u sistemu [inlmath]L[/inlmath] uz pomoć formula iz skupa [inlmath]T[/inlmath]. Ako je [inlmath]T[/inlmath] prazan skup tada pišemo [inlmath]\vdash_L\phi[/inlmath], i to znači da se formula [inlmath]\phi[/inlmath] može dokazati bez dodatnih pretpostavki (odnosno samo sa aksiomama sistema [inlmath]L[/inlmath]). Drugim rečima, [inlmath]\phi[/inlmath] je teorema formalnog sistema [inlmath]L[/inlmath].
S druge strane, imamo semantički pristup logici, odnosno pristup preko teorije modela. U ovom pristupu se konstruiše funkcija koja svakoj formuli dodeljuje istinitosnu vrednost ([inlmath]0[/inlmath] ili [inlmath]1[/inlmath]). U ovom pristupu se koristi relacija [inlmath]\models_L[/inlmath] na sledeći način: izraz [inlmath]T\models \phi[/inlmath] znači da kad god su sve formule u skupu [inlmath]T[/inlmath] tačne, tada je tačna i formula [inlmath]\phi[/inlmath]. Izraz [inlmath]\models \phi[/inlmath] nam govori da je [inlmath]\phi[/inlmath] uvek tačna formula, odnosno da je [inlmath]\phi[/inlmath] tautologija (šta u ovom kontekstu znači uvek, ne mogu sad da pojašnjavam. Pogledaj tekst koji sam linkovao.).
Teorema potpunosti spaja ova dva pogleda. Ona nam govori da sve što možemo dokazati u sistemu [inlmath]L[/inlmath] je tautologija, i obrnuto, svaku tautologiju možemo dokazati u sistemu [inlmath]L[/inlmath] (i slično za teoremu jake potpunosti, s tim što sada imamo dodatan skup formula koje smatramo za dodatne pretpostavke (pazi da u tom slučaju neće sve formule koje dokažemo biti tautologije)). Teorema potpunosti je teorema o samom formalnom sistemu [inlmath]L[/inlmath], odnosno ona je metateorema (takve su i ostale teoreme koje si navela).

Možda ovo sve izgleda besmisleno, ali nije baš tako. Evo jednog primera koji će možda malo dati osećaj zašto su ovakve stvari važne (primer će se odnositi na predikatsku logiku, umesto na iskaznu logiku, ali to ne bi trebalo da bude problem):
Euklid je pre 2500 godina formulisao neke aksiome geometrije, i na osnovu njih izgradio teoriju euklidske geometrije, dokazujući razne teoreme uz pomoć aksioma. On je tad imao pogled na geometriju iz ugla teorije dokaza. Dva milenijuma kasnije, matematičari su pristupili euklidskoj geometriji iz ugla teorije modela. Matematičari su dali konktretne matematičke objekte koji zadovoljavaju Euklidove aksiome (to je na primer prostor [inlmath]\mathbb{R}^3[/inlmath]), i time pokazali da je u nekom smislu Euklidova teorija tačna.
Mi možemo promeniti Euklidove aksiome, i tako dobiti neku novu teoriju koja možda izgleda suludo. Na primer umesto aksiome:
A. Za svaku datu pravu i tačku van te prave postoji jedinstvena prava koja prolazi kroz datu tačku i koja ne seče datu pravu,
možemo da uzmemo aksiomu
B. Za svaku datu pravu i tačku van te prave postoje dve različite prave koje prolaze kroz datu tačku i koje ne seku datu pravu.
Postoje geometrijske teorije u kojima važi i sledeće tvrđenje
C. Za svaku datu pravu, ne postoji prava koja je ne seče.
Iako mi možemo da uzmemo tvrđenja B i C i krenemo da nešto dokazujemo iz njih, ona nam deluju intuitivno netačno. Međutim konstrusani su modeli u kojima ova tvrđenja važe (na primer u sfernoj geometriji, svake dve prave se seku u tačno dve tačke). Prema tome takve teorije smatramo tačnim. Ovo je bila mala digresija koja pojašnjava razliku između iskaza koji imaju dokaz, i iskaza koji su tačni.

Takođe, postoje i teorije koje nisu potpune, odnosno u kojima nećeš moći dokazati svaku tautologiju (ali to je već neka druga priča...)
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta


Povratak na MATEMATIČKA LOGIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 32 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 11:41 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs