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

Исказ → ПростИсказ
       |Исказ Свеза Исказ

       |Квантификатор Променљива Исказ

       |¬ Реченица

       |(Реченица)

ПростИсказ → Предикат(Објект, Објект, ...)
       | Објект = Објект

Објект = Функција(Објект, Објект, ...)
       | Константа

       | Променљива

Свеза →  $\lor |\land |\Rightarrow |\Leftrightarrow$ 

Квантификатор →  $\exists |\forall$ 
Константа → <tekst> тј. "A" | "1" | "а"  
Променљива → x | y | z |...

Предикат → otac| brat| poseduje| ...

Функција →  saberi| predji|...

Objekti su:
konstante: <tekst>, tj. 0, 1, "a", "ababa"
imena funkcija: $\operatorname {otac} ,\operatorname {brat} ,\operatorname {predji} ,\operatorname {saberi} ,...$ tj. $\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 $\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)$  тј. Перо поседује ауто, 
 $\operatorname {brat} (Mujo,Suljo)$  тј, Мујо и Суљо су браћа.

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)$  тј. Мујо и Суљо су браћа, Мујо има ауто а  Суљо нема.

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)$  Сви пси су сисари

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))$  Марија има (бар једну) мачку црне боје
 $\exists x(\forall y\operatorname {pas} (y)\Rightarrow \operatorname {voli} (x,y))\land (\forall z\operatorname {macka} (z)\Rightarrow \operatorname {mrzi} (x,z))$  На овом свету постоји бар једна особа која воли псе и мрзи мачке

Upotreba kvantifikatora

Univerzalni kvantifikator se koristi implikativno

 $\forall x\operatorname {covek} (x)\land \operatorname {sisar} (x)$  Све на овом свету је човек и сисар

Egzistencijalni kvantifikator se koristi vezivno:

 $\exists x\operatorname {poseduje} (Jovan,x)\Rightarrow \operatorname {pas} (x)$  На овом свету има нешто што Јован не поседује или постоји на овом свету пас

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))$  Свако воли некога, тј. свако има неког кога воли
 $\exists y\forall x(\operatorname {voli} (x,y))$  Постоји на овом свету неко кога свако воли

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)))$  Пси постоје и сви су жути.  $x$  у  $zut(x)$  је универзално квантифициран.

U dobro napisanoj formuli sve promenljive moraju biti kvantifikovane:

 $\exists xP(y)$  Ова формула није добро написана

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števažeći identiteti:

$\forall x\neg P\Leftrightarrow \neg \exists xP$
$\neg \forall xP\Leftrightarrow \exists x\neg P$
$\forall xP\Leftrightarrow \neg \exists x\neg P$
$\exists xP\Leftrightarrow \neg \forall x\neg P$
$\forall xP(x)\land Q(x)\Leftrightarrow \forall xP(x)\land \forall xQ(x)$
$\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:

 $\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))$ 
Јован има два пса. Једнакост се користи овде да се обезбеди да су  $x$  и  $y$  различити, тј. да се искључи интерпретација да  $x$  и  $y$  могу бити исти пас

 $\forall x\exists y\operatorname {sinOtac} (x,y)\land \forall z(\operatorname {sinOtac} (x,z)\Rightarrow y=z)$  
Сваки син има оца. Друга свеза  $\forall z(\operatorname {sinOtac} (x,z)\Rightarrow y=z)$  обезбеђује да сваки син има једног оца.

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))]$  Два објекта су једнака ако и само ако имају иста својства.

 $\forall \operatorname {f} \forall \operatorname {g} [(\operatorname {f} =\operatorname {g} )\Leftrightarrow (\forall x\operatorname {f} (x)=\operatorname {g} (x))]$  Две функције су једнаке ако и само ако имају исте вредности за све могуће аргументе.

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

Spoljašnje veze