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

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

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

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

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

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

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

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

       |¬ Реченица

       |(Реченица)

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

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

       | Променљива

Свеза → $\vee |\wedge |\Rightarrow |\iff$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\mathrm{\exists }x(\mathrm{macka}(x)\wedge \mathrm{boja}(x,crna)\wedge \mathrm{poseduje}(Marija,x))$ Марија има (бар једну) мачку црне боје
$\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))$ На овом свету постоји бар једна особа која воли псе и мрзи мачке

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Једнакост

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

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

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

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

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

$\mathrm{\forall }x\mathrm{\forall }y[(x=y)\iff (\mathrm{\forall }\mathrm{p}\mathrm{p}(x)\iff \mathrm{p}(y))]$ Два објекта су једнака ако и само ако имају иста својства.

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

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

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

Литература

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

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

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