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 → $\vee |\wedge |\Rightarrow |\iff$

Kvantifikator → $\mathrm{\exists }|\mathrm{\forall }$
Konstanta → <tekst> tj. "A" | "1" | "a"  
Promenljiva → x | y | z |...

Predikat → otac| brat| poseduje| ...

Funkcija →  saberi| predji|...

Objekti su:
konstante: <tekst>, tj. 0, 1, "a", "ababa"
imena funkcija: $\mathrm{otac},\mathrm{brat},\mathrm{predji},\mathrm{saberi},...$ tj. $\mathrm{predji}(a,b,...),\mathrm{predji}(a),<\mathrm{saberi}(0),\mathrm{saberi}(0,1),...$

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 $\mathrm{otac}(sin,kci,...)$ znači da $sin,kci,...$ imaju zajedničkog oca, $\mathrm{brat}(brat,brat,...)$ da su $brat,brat,...$ braća.
ProstIskaz je predikat primenjen na objekte. Npr.

$\mathrm{poseduje}(Pero,auto)$ tj. Pero poseduje auto, 
$\mathrm{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

$\mathrm{brat}(Mujo,Suljo)\wedge \mathrm{poseduje}(Mujo,auto)\wedge \mathrm{\neg }\mathrm{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: $\mathrm{\forall }x$

Iskaz je istinit za sve vrednosti promenljive x.

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

• Egzistencijalni kvantifikator: $\mathrm{\exists }x$

Iskaz je istinit za bar jednu vrednost promenljive x.

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

Upotreba kvantifikatora

• Univerzalni kvantifikator se koristi implikativno

$\mathrm{\forall }x\mathrm{covek}(x)\wedge \mathrm{sisar}(x)$ Sve na ovom svetu je čovek i sisar

• Egzistencijalni kvantifikator se koristi vezivno:

$\mathrm{\exists }x\mathrm{poseduje}(Jovan,x)\Rightarrow \mathrm{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

$\mathrm{\forall }x\mathrm{\forall }y(\mathrm{roditelj}(x,y)\wedge \mathrm{musko}(y)\Rightarrow \sin (y,x))$
$\mathrm{\exists }x\mathrm{\exists }y(\mathrm{voli}(x,y)\wedge \mathrm{voli}(y,x))$

• Poredak kvantifikatora različitog tipa u iskazu je nevažan

$\mathrm{\forall }x\mathrm{\exists }y(\mathrm{voli}(x,y))$ Svako voli nekoga, tj. svako ima nekog koga voli
$\mathrm{\exists }y\mathrm{\forall }x(\mathrm{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

$\mathrm{\exists }x(\mathrm{pas}(x)\wedge \mathrm{\forall }x(\mathrm{zut}(x)))$ Psi postoje i svi su žuti. x u zut(x) je univerzalno kvantificiran.

• U dobro napisanoj formuli sve promenljive moraju biti kvantifikovane:

$\mathrm{\exists }xP(y)$ Ova formula nije dobro napisana

Logička veza među kvantifikatorima

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

$\mathrm{\forall }x\mathrm{\neg }\mathrm{voli}(x,bandit)\iff \mathrm{\neg }\mathrm{\exists }x\mathrm{voli}(x,bandit)$
$\mathrm{\forall }x\mathrm{voli}(x,bog)\iff \mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }\mathrm{voli}(x,bog)$

•Opšte važeći identiteti:

$\mathrm{\forall }x\mathrm{\neg }P\iff \mathrm{\neg }\mathrm{\exists }xP$
$\mathrm{\neg }\mathrm{\forall }xP\iff \mathrm{\exists }x\mathrm{\neg }P$
$\mathrm{\forall }xP\iff \mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }P$
$\mathrm{\exists }xP\iff \mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }P$
$\mathrm{\forall }xP(x)\wedge Q(x)\iff \mathrm{\forall }xP(x)\wedge \mathrm{\forall }xQ(x)$
$\mathrm{\exists }xP(x)\vee Q(x)\iff \mathrm{\exists }xP(x)\vee \mathrm{\exists }xQ(x)$

Jednakost

• Jednakost se uključuje kao primitivni logički predikat.
• Primeri:

$\mathrm{\exists }x\mathrm{\exists }y(\mathrm{poseduje}(Jovan,x)\wedge \mathrm{pas}(x)\wedge \mathrm{poseduje}(Jovan,y)\wedge \mathrm{pas}(y)\wedge \mathrm{\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

$\mathrm{\forall }x\mathrm{\exists }y\mathrm{sinOtac}(x,y)\wedge \mathrm{\forall }z(\mathrm{sinOtac}(x,z)\Rightarrow y=z)$ 
Svaki sin ima oca. Druga sveza $\mathrm{\forall }z(\mathrm{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:

$\mathrm{\forall }x\mathrm{\forall }y[(x=y)\iff (\mathrm{\forall }\mathrm{p}\mathrm{p}(x)\iff \mathrm{p}(y))]$ Dva objekta su jednaka ako i samo ako imaju ista svojstva.

$\mathrm{\forall }\mathrm{f}\mathrm{\forall }\mathrm{g}[(\mathrm{f}=\mathrm{g})\iff (\mathrm{\forall }x\mathrm{f}(x)=\mathrm{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 $\mathrm{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)