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

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

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

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

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

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

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

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

       |¬ Реченица

       |(Реченица)

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

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

       | Променљива

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

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

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

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

Објекти су:
константе: <текст>, тј. 0, 1, "a", "ababa"
имена функција: ${\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),...}$

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \exists x(\operatorname {macka} (x)\land \operatorname {boja} (x,crna)\land \operatorname {poseduje} (Marija,x))}$ Марија има (бар једну) мачку црне боје
${\displaystyle \exists x(\forall y\operatorname {pas} (y)\Rightarrow \operatorname {voli} (x,y))\land (\forall z\operatorname {macka} (z)\Rightarrow \operatorname {mrzi} (x,z))}$ На овом свету постоји бар једна особа која воли псе и мрзи мачке

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Једнакост

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

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

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

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

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

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

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

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

На пример, предикат другог реда ${\displaystyle p}$ може бити ${\displaystyle \operatorname {refleksivan} (p)}$ тј. бинарни предикат ${\displaystyle 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)