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

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

Логика првог реда је формални дедуктивни систем који се користи у математици, филозофији, лингвистици и рачунарству. Позната је и под именом предикатски рачун првог реда. За разлику од природних језика попут српског, логика првог реда користи у потпуности недвосмислени формални језик који интерпретирају математичке структуре. Логика првог реда је дедукциони систем који проширује исказни рачун тако што омогућава да се користе квантификације индивидуа датог домена (универзума) који се разматра. На пример, у логици првог реда се може рећи да Свака индивидуа има својство P.

Док се исказни рачун бави простим декларативним исказима, логика првог реда покрива предикате и квантификаторе. Узмимо на пример следеће реченице: Сократ је човек, Платон је човек. У исказном рачуну би ово била два неповезана исказа означена просто са p и q. Међутим, у логици првог реда, ове две реченице би биле повезане истим својством: човек(x), где човек(x) значи да је x човек. Када је x=Сократ добијамо први исказ, p, а када је x=Платон, добијамо други исказ, q. Овакве конструкције омогућавају много моћнију логику када се уведу квантификатори, као што је за свако x..., на пример, за свако x, ако човек(x), онда.... Без квантификатора, сваки валидни исказ у логици првог реда је валидан у исказном рачуну и обратно.

Зашто је логика првог реда неопходна?[уреди]

Исказни рачун није адекватан за формализовање валидних исказа који се односе на унутрашњу структуру. Да бисмо ово увидели, посматрајмо следећи валидан силогизам:

  • Сви људи су смртни.
  • Сократ је човек.
  • Стога, Сократ је смртан.

који превођењем у исказни рачун даје:

  • A
  • B
  • \therefore C

(где \therefore значи стога).

Ово превођење није валидно: логика исказе чини валидним по њиховој структури, а ништа у структури преведеног силогизма (C следи из A и B, за произвољно A, B, C) не говори да је он валидан. Превод који чува интуитивну (и формалну) валидност силогизма мора да узме у обзир дубљу структуру исказа.

Исти силогизам се лако може превести у логику првог реда:

  • \forall x (covek(x) \rightarrow smrtan(x))
  • \,covek(Sokrat)
  • \therefore smrtan(Sokrat)

(Где \forall x значи за свако x, \rightarrow значи имплицира, covek(Sokrat) значи Сократ је човек, а smrtan(Sokrat) значи Сократ је смртан.) У српском језику, ово би се могло записати као

  • за свако x, ако x је човек, онда x је смртан.
  • Сократ је човек.
  • Стога, Сократ је смртан.

Логика првог реда такође може да изрази постојање нечега (\exists), као и предикате (функције које су имају вредност тачно или нетачно) са више од једног параметра. На пример, постоји неко ко може бити преварен сваки пут се може изразити као:

\exists x (osoba(x) \and \forall y (vreme(y) \rightarrow mozeBitiPrevaren(x,y)))

Где \exists x значи постоји x, \and значи и, а mozeBitiPrevaren(x,y) значи (особа) x може бити преварена (у тренутку) y.

Види још[уреди]