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

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

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

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

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

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

Исказ → ПростИсказ
       |Исказ Свеза Исказ
|Квантификатор Променљива Исказ
|¬ Реченица
|(Реченица)
ПростИсказ → Предикат(Објект, Објект, ...) | Објект = Објект
Објект = Функција(Објект, Објект, ...) | Константа
| Променљива
Свеза →  
Квантификатор →   Константа → <tekst> тј. "A" | "1" | "а" Променљива → x | y | z |...
Предикат → otac| brat| poseduje| ...
Функција → saberi| predji|...

Објекти су:
константе: <текст>, тј. 0, 1, "a", "ababa"
имена функција:   tj.  

Исказ је предикат над једним или више објеката. Предикат је неко својство или релација међу објектима који може бити истинит или лажан.
У горњим примерима   значи да   имају заједничког оца,   да су   браћа.
ПростИсказ је предикат примењен на објекте. Нпр.

  тј. Перо поседује ауто, 
  тј, Мујо и Суљо су браћа.

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

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

  тј. Мујо и Суљо су браћа, Мујо има ауто а  Суљо нема.

Квантификатори уреди

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

  • Универзални квантификаторr:  

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

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

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

  Марија има (бар једну) мачку црне боје
  На овом свету постоји бар једна особа која воли псе и мрзи мачке

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

  • Универзални квантификатор се користи импликативно
  Све на овом свету је човек и сисар
  • Егзистенцијални квантификатор се користи везивно:
  На овом свету има нешто што Јован не поседује или постоји на овом свету пас

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

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

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

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

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

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

 
 

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

 
 
 
 
 
 

Једнакост уреди

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

  
Сваки син има оца. Друга свеза   обезбеђује да сваки син има једног оца.

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

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

На пример, предикат другог реда   може бити   тј. бинарни предикат   је релација рефлексивности.

Литература уреди

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

Спољашње везе уреди