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

Из Википедије, слободне енциклопедије

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

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

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

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

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

Исказ → ПростИсказ
       |Исказ Свеза Исказ
|Квантификатор Променљива Исказ
|¬ Реченица
|(Реченица)
ПростИсказ → Предикат(Објект, Објект, ...) | Објект = Објект
Објект = Функција(Објект, Објект, ...) | Константа
| Променљива
Свеза →
Квантификатор → Константа → <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

Екстерни линкови[уреди]