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 → ${\displaystyle \lor |\land |\Rightarrow |\Leftrightarrow }$

Kvantifikator → ${\displaystyle \exists |\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: ${\displaystyle \operatorname {otac} ,\operatorname {brat} ,\operatorname {predji} ,\operatorname {saberi} ,...}$ tj. ${\displaystyle \operatorname {predji} (a,b,...),\operatorname {predji} (a),<\operatorname {saberi} (0),\operatorname {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 ${\displaystyle \operatorname {otac} (sin,kci,...)}$ znači da ${\displaystyle sin,kci,...}$ imaju zajedničkog oca, ${\displaystyle \operatorname {brat} (brat,brat,...)}$ da su ${\displaystyle brat,brat,...}$ braća.
ProstIskaz je predikat primenjen na objekte. Npr.

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

${\displaystyle \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: ${\displaystyle \forall x}$

Iskaz je istinit za sve vrednosti promenljive x.

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

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

Iskaz je istinit za bar jednu vrednost promenljive x.

${\displaystyle \exists x(\operatorname {macka} (x)\land \operatorname {boja} (x,crna)\land \operatorname {poseduje} (Marija,x))}$ Marija ima (bar jednu) mačku crne boje
${\displaystyle \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

${\displaystyle \forall x\operatorname {covek} (x)\land \operatorname {sisar} (x)}$ Sve na ovom svetu je čovek i sisar

• Egzistencijalni kvantifikator se koristi vezivno:

${\displaystyle \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

${\displaystyle \forall x\forall y(\operatorname {roditelj} (x,y)\land \operatorname {musko} (y)\Rightarrow \operatorname {sin} (y,x))}$
${\displaystyle \exists x\exists y(\operatorname {voli} (x,y)\land \operatorname {voli} (y,x))}$

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

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

${\displaystyle \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:

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

Logička veza među kvantifikatorima

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

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

•Opšte važeći identiteti:

${\displaystyle \forall x\neg P\Leftrightarrow \neg \exists xP}$
${\displaystyle \neg \forall xP\Leftrightarrow \exists x\neg P}$
${\displaystyle \forall xP\Leftrightarrow \neg \exists x\neg P}$
${\displaystyle \exists xP\Leftrightarrow \neg \forall x\neg P}$
${\displaystyle \forall xP(x)\land Q(x)\Leftrightarrow \forall xP(x)\land \forall xQ(x)}$
${\displaystyle \exists xP(x)\lor Q(x)\Leftrightarrow \exists xP(x)\lor \exists xQ(x)}$

Jednakost

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

${\displaystyle \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 ${\displaystyle x}$ i ${\displaystyle y}$ različiti, tj. da se isključi interpretacija da ${\displaystyle x}$ i ${\displaystyle y}$ mogu biti isti pas

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

${\displaystyle \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.

${\displaystyle \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 ${\displaystyle p}$ može biti ${\displaystyle \operatorname {refleksivan} (p)}$ tj. binarni predikat ${\displaystyle 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

Eksterni linkovi

• First order logic (Cornell)
• First order logic (Wolfram MathWorld)