Logika prvog reda

**Logika prvog reda** ili predikativni račun prvog reda je formalni sistem koji se koristi u matematici, filozofiji, lingvistici i računarstvu. Ovde ćemo izložiti samo osnovni i najformalniji deo nužan kao potpora člancima teorije skupova.
## Logika prvog reda
Logika prvog reda ili predikatska logika prvog reda se bazira na:
*objektima,
*svojstvima (unarnim predikatima nad objektima),
*relacijama (n-arnim predikatima nad objektima),
*funkcijama (preslikavanjima objekata na objekte).
### Sintaksa logike prvog reda
 Iskaz → ProstIskaz
        |Iskaz Sveza Iskaz
        |Kvantifikator Promenljiva Iskaz
        |¬ Rečenica
        |(Rečenica)
 ProstIskaz → Predikat(Objekt, Objekt, ...)
        | Objekt = Objekt
 Objekt = Funkcija(Objekt, Objekt, ...)
        | Konstanta
        | Promenljiva
 Sveza → \lor | \land | \Rightarrow | \Leftrightarrow 
 Kvantifikator → \exists | \forall
 Konstanta →  tj. "A" | "1" | "a"  
 Promenljiva → x | y | z |...
 Predikat → otac| brat| poseduje| ...
 Funkcija →  saberi| predji|...
Objekti su:
konstante: , tj. 0, 1, "a", "ababa"
imena funkcija: \operatorname{otac}, \operatorname{brat}, \operatorname{predji}, \operatorname{saberi}, ... tj. \operatorname{predji}(a, b,...), \operatorname{predji}(a), 

Iskaz je predikat nad jednim ili više objekata. Predikat je neko svojstvo ili relacija među objektima koji može biti istinit ili lažan. U gornjim primerima \operatorname{otac}(sin, kci,...) znači da sin, kci, ... imaju zajedničkog oca, \operatorname{brat}(brat,brat,...) da su brat,brat,... braća. 
ProstIskaz je predikat primenjen na objekte. Npr. 
 \operatorname{poseduje}(Pero,auto) tj. Pero poseduje auto, 
 \operatorname{brat}(Mujo,Suljo) tj, Mujo i Suljo su braća.

Semantika Iskaza i ProstogIskaza je istina ili laž.

Sveze se koriste pri konstrukciji (složenih) Iskaza
 \operatorname{brat}(Mujo,Suljo) \land \operatorname{poseduje}(Mujo,auto) \land \neg \operatorname{poseduje}(Suljo,auto) tj. Mujo i Suljo su braća, Mujo ima auto a  Suljo nema.

### Kvantifikatori
Koriste se ako se Iskaz odnosi na kolekciju objekata kako bi se izbeglo brojanje objekata

* Univerzalni kvantifikatorr: \forall x
Iskaz je istinit za sve vrednosti promenljive  x.

 \forall x \operatorname{pas}(x) \Rightarrow \operatorname{sisar}(x) Svi psi su sisari

* Egzistencijalni kvantifikator: \exists x
Iskaz je istinit za bar jednu vrednost promenljive  x.

 \exists x(\operatorname{macka}(x) \land \operatorname{boja}(x,crna) \land \operatorname{poseduje}(Marija,x)) Marija ima (bar jednu) mačku crne boje
 \exists x(\forall y \operatorname{pas}(y) \Rightarrow \operatorname{voli}(x,y)) \land (\forall z \operatorname{macka}(z) \Rightarrow \operatorname{mrzi}(x,z)) Na ovom svetu postoji bar jedna osoba koja voli pse i mrzi mačke

### Upotreba kvantifikatora
* Univerzalni kvantifikator se koristi implikativno
 \forall x \operatorname{covek}(x) \land \operatorname{sisar}(x) Sve na ovom svetu je čovek i sisar
* Egzistencijalni kvantifikator se koristi vezivno:
 \exists x \operatorname{poseduje}(Jovan,x) \Rightarrow \operatorname{pas}(x) Na ovom svetu ima nešto što Jovan ne poseduje ili postoji na ovom svetu pas

### Ugneždeni kvantifikatori
* Poredak kvantifikatora istog tipa u iskazu je nevažan
 \forall x \forall y(\operatorname{roditelj}(x,y) \land \operatorname{musko}(y) \Rightarrow \operatorname{sin}(y,x))
 \exists x \exists y(\operatorname{voli}(x,y) \land \operatorname{voli}(y,x))
* Poredak kvantifikatora različitog tipa u iskazu je nevažan
 \forall x \exists y(\operatorname{voli}(x,y)) Svako voli nekoga, tj. svako ima nekog koga voli
 \exists y \forall x(\operatorname{voli}(x,y)) Postoji na ovom svetu neko koga svako voli

### Područje ili zona važenja promenljive
* Područje ili zona važenja promenljive je iskaz na koji je kvantifikator primenljiv.
* Promenljiva u logičkom izrazu se vezuje za najbliži kvantifivator unutar iskaza u kome se pojavljuje
 \exists x (\operatorname{pas}(x) \land \forall x(\operatorname{zut}(x))) Psi postoje i svi su žuti. x u zut(x) je univerzalno kvantificiran.
* U dobro napisanoj formuli sve promenljive moraju biti kvantifikovane:
 \exists x P(y) Ova formula nije dobro napisana

### Logička veza među kvantifikatorima
•Logička veza među univerzalnim i egzistencijalnim kvantifikatorom:

\forall x \neg \operatorname{voli}(x,bandit) \Leftrightarrow \neg \exists x \operatorname{voli}(x,bandit)
\forall x \operatorname{voli}(x,bog) \Leftrightarrow \neg \exists x \neg \operatorname{voli}(x,bog)

•Opšte važeći identiteti:

\forall x \neg P \Leftrightarrow \neg \exists x P
\neg \forall x P \Leftrightarrow \exists x \neg P
\forall x P \Leftrightarrow \neg \exists x \neg P
\exists x P \Leftrightarrow \neg \forall x \neg P
\forall x P(x) \land Q(x) \Leftrightarrow \forall x P(x) \land \forall x Q(x)
\exists x P(x) \lor Q(x) \Leftrightarrow \exists x P(x) \lor \exists x Q(x)

### Jednakost
* Jednakost se uključuje kao primitivni logički predikat.
* Primeri:
 \exists x \exists y(\operatorname{poseduje}(Jovan, x) \land \operatorname{pas}(x) \land  \operatorname{poseduje}(Jovan,y) \land \operatorname{pas}(y) \land \neg (x=y))
 Jovan ima dva psa. Jednakost se koristi ovde da se obezbedi da su x i y različiti, tj. da se isključi interpretacija da x i y mogu biti isti pas
 
 \forall x \exists y \operatorname{sinOtac}(x, y) \land \forall z(\operatorname{sinOtac}(x,z) \Rightarrow y=z) 
 Svaki sin ima oca. Druga sveza \forall z(\operatorname{sinOtac}(x,z) \Rightarrow y=z) obezbeđuje da svaki sin ima jednog oca.

## Logike višeg reda
* U logici prvog reda kvantifikatori su primenljivi samo na objekte.
* U logici drugog reda kvantifikatori su primenljivi samo na predikate i funkcije:
 \forall  x \forall y [ (x=y) \Leftrightarrow (\forall \operatorname{p}  \operatorname{p}(x) \Leftrightarrow \operatorname{p} (y)) ] Dva objekta su jednaka ako i samo ako imaju ista svojstva.

 \forall \operatorname{f} \forall \operatorname{g} [ (\operatorname{f} = \operatorname{g}) \Leftrightarrow (\forall x  \operatorname{f}(x) = \operatorname{g}(x)) ] Dve funkcije su jednake ako i samo ako imaju iste vrednosti za sve moguće argumente.

* Logika trećeg reda dopušta kvantifikaciju predikata, itd.
Na primer, predikat drugog reda p može biti \operatorname{refleksivan}(p) tj. binarni predikat p je relacija refleksivnosti.

## Literatura
* Raymond M. Smullyan: First-order Logic, Courier Corporation, 1995 
* Leigh S. Cauman: First-order Logic: An Introduction, Walter de Gruyter, 1998

## Vanjske veze
* First order logic (Cornell)
* First order logic (Wolfram MathWorld)