Savremena logika: Predikatski račun

Ograničenja iskaznog računa i potreba za predikatskim računom

• Problematika elementarne logike: Iskazni račun, iako precizan u radu sa iskaznim vezama, nije u stanju da adekvatno prikaže unutrašnju strukturu iskaza koja je neophodna za silogističko rezonovanje.
• Primer zakazivanja iskazne formalizacije:     * Silogizam:         1. Svi ljudi su smrtni.         2. Svi Grci su ljudi.         3. Dakle, svi Grci su smrtni.     * U jeziku iskaznog računa, ovo bi se prikazalo kao tri nepovezana iskaza: $p$, $q$, $r$, što ne prikazuje nužnost veze između premisa i konkluzije.
• Uzroci neuspeha iskaznog računa:     * Raspodeljenost termina: Nužnost u silogizmu zavisi od toga kako su termini raspodeljeni, što iskazni račun ne vidi.     * Kvalitet i kvantitet: Iskazni račun može izraziti kvalitet (putem negacije), ali je kvantitet tvrdnji (univezalnost ili partikularnost) za njega potpuno neproziran.     * Dubinska struktura: Neophodan je jezik koji ne predstavlja čitave iskaze promenljivama, već razlaže subjekatske i predikatske termine.
• Problem srednjevekovne notacije: Iako su postojali oblici poput $M a P$ (vidi: subjekat-kopula-predikat), oni su se pokazali nedovoljno preciznima.     * Primer:         1. Sve planete su veće od asteroida ($P a VA$)         2. Sve zvezde su veće od planeta ($Z a VP$)         3. Sve zvezde su veće od asteroida ($Z a VA$)     * Iako je rezonovanje ispravno, formalizacija ne uspeva da jasno identifikuje srednji termin kao ključni element.
• Fregeov doprinos: Gotlob Frege je predložio napuštanje subjekat-kopula-predikat obrasca u korist matematičkog modela funkcija. U ovom modelu, predikat se tretira kao funkcija koja se primenjuje na subjekat, što omogućava bogatiji formalni jezik.

Elementi predikatskog računa

• Predikatski račun je identičan iskaznom u svim aspektima osim u načinu formiranja formula. On koristi sledeće specifične elemente:
• Individualne konstante (imena): Simboli $a, b, c…$ označavaju tačno određene entitete ili subjekte.     * Primeri: lična imena ("Ana", "Beograd") ili opšte imenice ako specifikuju jedan entitet ("cipela").
• Individualne promenljive: Simboli $x, y, z…$ označavaju neodređene predmete ("nešto") ili neodređene entitete iz specifične grupe ("neki čovek").
• Predikati / Funkcije: Simboli $P, Q, R…$ označavaju karakteristike koje se pripisuju subjektima (npr. "je vredna", "je beo").     * Argumenti: Subjekatski entiteti se nazivaju argumentima funkcije.     * Istinosna vrednost: Funkcije uzimaju argumente kao ulazne vrednosti i povezuju ih sa izlaznim vrednostima koje su zapravo istinosne vrednosti (istinito ili neistinito).     * Primer: "Ana je vredna" se može zapisati kao $V (a) = 1$, gde je $a$ (Ana) povezana funkcijom $V$ (je vredna) sa vrednošću istinito.
• Kvantifikatori: Služe za označavanje opsega primene predikata.     * Univerzalni kvantifikator ($\forall$): Označava da se predikatska funkcija primenjuje na sve subjekatske entitete (od nemačkog Alle ili engleskog All).     * Egzistencijalni kvantifikator ($\exists$): Označava da se predikatska funkcija primenjuje na neke subjekte, odnosno da postoji bar jedan entitet na koji se odnosi (od nemačkog Einige ili engleskog somE).
• Veznici i pravila: Svi veznici, interpunkcijski znaci i osnovna pravila iskaznog računa ostaju na snazi.

Pravila formiranja formula i atomske tvrdnje

• Struktura atomskih tvrdnji: Dobro formirana atomska tvrdnja sastoji se od predikatske funkcije iza koje sledi odgovarajući broj argumenata.
• Arnost predikata (broj argumenata): Predikati mogu zahtevati različit broj argumenata (od $0$ do $n$):     * Jednoargumentni: "Ana je devojčica" $D(a)$ (Zahteva pitanje: ko?)     * Dvoargumentni: "Ana je Bobanova sestra" $S(a, b)$ (Zahteva pitanja: ko i kome?)     * Troargumentni: "Ana je Bobanu poklonila cipelu" $P(a, b, c)$ (Zahteva pitanja: ko, kome i šta?)     * Notacija se može vršiti i bez zagrada ($Pabc$), ali je tada manje pregledna.

Kvantifikacija i promenljive

• Veza između imena i kvantifikacije: Kada se koriste konkretna imena, nije potrebna kvantifikacija jer je referenca jasna.
• Slobodne promenljive: Promenljive koje stoje u formuli bez kvantifikatora nazivaju se slobodne (npr. $D(x)$). One nisu iskazi jer ne saopštavaju ništa precizno (ne znamo da li mislimo na sve ili samo na neke).
• Vezivanje promenljivih: Da bi formula sa promenljivom bila iskaz, mora biti "vezana" kvantifikatorom koji se piše ispred formule.     * $(\forall x) P(x)$: Svako $x$ je $P$.     * $(\exists x) Q(x)$: Postoji bar jedno $x$ koje je $Q$.     * $(\exists x)(\forall y) R(x, y)$: Postoji bar jedno $x$ koje je $R$ svakom $y$.
• Apelacije i klase:     * "Svo voće je ukusno" $(\forall x) U(x)$ (nad klasom voća).     * "Ovo je kisela voćka" (pokazujući na konkretnu voćku) $K(v)$ (ime, ne kvantifikuje se).
• Definisanje kvantifikatora preko negacije:     * $(\forall x) S(x) = (\neg \exists x) \neg S(x)$ (Svi su smrtni = Ne postoji čovek koji nije smrtan).     * $(\exists x) P(x) = (\neg \forall x) \neg P(x)$ (Neki su pošteni = Nisu svi nepošteni).

Redosled kvantifikovanja i interpretacija

• Redosled može drastično promeniti značenje formule ako su kvantifikatori različiti. Primer sa predikatom $R$ (razume), $x$ (učenici) i $y$ (zadaci):     1. $(\forall x) (\exists y) R (x, y)$: Svaki učenik razume bar jedan zadatak (svako ima svoj, možda različit).     2. $(\exists y) (\forall x) R (x, y)$: Postoji bar jedan zadatak koji razumeju svi učenici (isti zadatak za sve).     3. $(\exists x) (\forall y) R (x, y)$: Postoji bar jedan (veoma pametan) učenik koji razume sve zadatke.     4. $(\forall y) (\exists x) R (x, y)$: Za svaki zadatak postoji bar jedan učenik koji ga razume (sve je rešivo).

Kategorički iskazi u predikatskom računu

• Svi tradicionalni kategorički iskazi se prevode u složene molekularne tvrdnje:     * Univerzalno-afirmativna (A): "Svi psi su sisari" — $(\forall x) ( P(x) \rightarrow S(x) )$     * Univerzalno-negativna (E): "Nijedna ptica nije sisar" — $(\forall x) ( P(x) \rightarrow \neg S(x) )$     * Partikularno-afirmativna (I): "Neki političari su sebični" — $(\exists x) ( P(x) \land S(x) )$     * Partikularno-negativna (O): "Neki političari nisu savesni" — $(\exists x) ( P(x) \land \neg S(x) )$

Pravila zaključivanja u predikatskom računu

• Osnovna procedura dokazivanja:     1. Formule sa kvantifikatorima pretvoriti u formule bez njih kroz pravila eliminacije.     2. Primeniti standardna pravila iskaznog računa (MPP, MT, itd.).     3. Vratiti kvantifikatore na dobijene rezultate kroz pravila uvođenja.

1. Eliminacija univerzalnog kvantifikatora ($E\forall$)

• Definicija: Ako nešto važi za sve članove klase, važi i za pojedinačni član (dictum de omni).
• Pravilo: Iz $(\forall x) P(x)$ možemo zaključiti $P(a)$, gde je $a$ konkretno ime.
• Primer dokaza:     1. $P(a)$ - A     2. $(\forall x) ( P(x) \rightarrow S(x) )$ - A     3. $P(a) \rightarrow S(a)$ (iz koraka 2, putem $E\forall$)     4. $S(a)$ (iz koraka 1 i 3, putem MPP)

2. Uvođenje egzistencijalnog kvantifikatora ($U\exists$)

• Definicija: Ako predikat pripada konkretnom imenu, to dokazuje da postoji bar jedan slučaj u kom taj predikat nekome pripada.
• Pravilo: Iz $S(a)$ zaključujemo $(\exists x) S(x)$.

3. Uvođenje univerzalnog kvantifikatora ($U\forall$)

• Problem indukcije: Kako iz jednog primera zaključiti o svima?
• Rešenje (Pravilo proizvoljnosti): Može se univerzalizovati samo ako je ime u argumentu potpuno proizvoljno.     * Metafora geomatra: Dokaz na nacrtanom trouglu važi za sve trouglove jer su konkretne mere nacrtane figure nebitne; bitno je samo da pripada klasi trouglova.
• Kriterijum proizvoljnosti: Ime je proizvoljno ako se ne javlja ni u jednoj "živoj" (aktivnoj) premisi iz koje je dobijen zaključak.
• Postupak: Uvek prvo "ubiti" uslovne pretpostavke pre pokušaja univerzalizacije.

4. Eliminacija egzistencijalnog kvantifikatora ($E\exists$)

• Složenost: Ne znamo tačno o kom se entitetu radi iz tvrdnje "postoji neko".
• Postupak sa tipičnim imenom: Koristi se pretpostavka sa tipičnim primerom koji uslovno zamenjuje egzistencijalno kvantifikovanu formulu.
• Metafora kaskadera:     * Glavni glumac (egzistencijalna tvrdnja) je skup i trapav (teško je raditi sa njim direktno u dokazu).     * Kaskader (uslovna pretpostavka sa tipičnim imenom $a$) sliči glumcu i izvodi opasne akcije (primenu pravila u dokazu).     * Čim se akciona scena završi, kaskader odlazi, a glavni glumac se vraća na scenu (vraćanje početne egzistencijalne tvrdnje uz oslobađanje od uslovne pretpostavke).
• Stipulacije: Tipično ime ne sme biti u drugim premisama niti se sme naći u konačnom zaključku.

Meta-logika i teoreme nepotpunosti

• Logika prvog reda (Predikatski račun): Ovo je poslednji red logike koji je istovremeno dosledan (ne proizvodi protivrečja) i potpun (sve istinite tvrdnje u sistemu su dokazive).
• Logike višeg reda: Doslednost i potpunost više nisu istovremeno ostvarive.
• Odnos sa matematikom: Za oblikovanje aritmetike neophodna je barem logika drugog reda. Zato je geometrija (logika prvog reda) aksiomatizovana još u antici (Euklid), dok aritmetika nije mogla biti.
• Kurt Gedel (Kurt Gödel): Sredinom 20. veka dokazao je teoreme nepotpunosti:     1. Svaki sistem u kom se može iskazati osnovna aritmetika je ili nedosledan ili nepotpun.     2. U takvim sistemima uvek će postojati istinite tvrdnje koje se ne mogu dokazati.     3. Ako se sistem upotpuni tako da se sve tvrdnje mogu dokazati, nužno će se pojaviti kontradikcije.
• Konkluzija: Što je logički sistem kompleksniji, to je teže (ili nemoguće) pomiriti doslednost i potpunost.