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

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