Логика првог реда

Логика првог реда или предикативни рачун првог реда је формални систем који се користи у математици, филозофији, лингвистици и рачунарству. Овде ћемо изложити само основни и најформалнији део нужан као потпора чланцима теорије скупова.

Логика првог реда

Логика првог реда или предикатска логика првог реда се базира на:

објектима,
својствима (унарним предикатима над објектима),
релацијама (н-арним предикатима над објектима),
функцијама (пресликавањима објеката на објекте).

Синтакса логике првог реда

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

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

       |¬ Реченица

       |(Реченица)

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

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

       | Променљива

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

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

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

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

Објекти су:
константе: <текст>, тј. 0, 1, "a", "ababa"
имена функција: $\operatorname {otac} ,\operatorname {brat} ,\operatorname {predji} ,\operatorname {saberi} ,...$ tj. $\operatorname {predji} (a,b,...),\operatorname {predji} (a),\operatorname {saberi} (0),\operatorname {saberi} (0,1),...$

Исказ је предикат над једним или више објеката. Предикат је неко својство или релација међу објектима који може бити истинит или лажан.
У горњим примерима $\operatorname {otac} (sin,kci,...)$ значи да $sin,kci,...$ имају заједничког оца, $\operatorname {brat} (brat,brat,...)$ да су $brat,brat,...$ браћа.
ПростИсказ је предикат примењен на објекте. Нпр.

 $\operatorname {poseduje} (Pero,auto)$  тј. Перо поседује ауто, 
 $\operatorname {brat} (Mujo,Suljo)$  тј, Мујо и Суљо су браћа.

Семантика Исказа и ПростогИсказа је истина или лаж.

Свезе се користе при конструкцији (сложених) Исказа

 $\operatorname {brat} (Mujo,Suljo)\land \operatorname {poseduje} (Mujo,auto)\land \neg \operatorname {poseduje} (Suljo,auto)$  тј. Мујо и Суљо су браћа, Мујо има ауто а  Суљо нема.

Квантификатори

Користе се ако се Исказ односи на колекцију објеката како би се избегло бројање објеката

Универзални квантификаторr: $\forall x$

Исказ је истинит за све вредности променљиве x.

 $\forall x\operatorname {pas} (x)\Rightarrow \operatorname {sisar} (x)$  Сви пси су сисари

Егзистенцијални квантификатор: $\exists x$

Исказ је истинит за бар једну вредност променљиве 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))$  На овом свету постоји бар једна особа која воли псе и мрзи мачке

Употреба квантификатора

Универзални квантификатор се користи импликативно

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

Егзистенцијални квантификатор се користи везивно:

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

Угнеждени квантификатори

Поредак квантификатора истог типа у исказу је неважан

 $\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))$

Поредак квантификатора различитог типа у исказу је неважан

 $\forall x\exists y(\operatorname {voli} (x,y))$  Свако воли некога, тј. свако има неког кога воли
 $\exists y\forall x(\operatorname {voli} (x,y))$  Постоји на овом свету неко кога свако воли

Подручје или зона важења променљиве

Подручје или зона важења променљиве је исказ на који је квантификатор применљив.
Променљива у логичком изразу се везује за најближи квантифиватор унутар исказа у коме се појављује

 $\exists x(\operatorname {pas} (x)\land \forall x(\operatorname {zut} (x)))$  Пси постоје и сви су жути.  $x$  у  $zut(x)$  је универзално квантифициран.

У добро написаној формули све променљиве морају бити квантификоване:

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

Логичка веза међу квантификаторима

Логичка веза међу универзалним и егзистенцијалним квантификатором:

$\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)$

Општеважећи идентитети:

$\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)$

Једнакост

Једнакост се укључује као примитивни логички предикат.
Примери:

 $\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)$  обезбеђује да сваки син има једног оца.

Логике вишег реда

У логици првог реда квантификатори су применљиви само на објекте.
У логици другог реда квантификатори су применљиви само на предикате и функције:

 $\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))]$  Две функције су једнаке ако и само ако имају исте вредности за све могуће аргументе.

Логика трећег реда допушта квантификацију предиката, итд.

На пример, предикат другог реда $p$ може бити $\operatorname {refleksivan} (p)$ тј. бинарни предикат $p$ је релација рефлексивности.

Литература

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

Спољашње везе