5. Uvod u logiku

Logika drugog reda

Autor: Nikola Vujačić


Što je logika 2. reda

Logika drugog reda nastala je sa svrhom proširenja logike prvog reda koja zapisuje odnose između pojmova, tj. svojstva i objekta sa tim svojstvima. Nekim oblikom logike drugog reda, služio se Frege iako je bio uvjeren da zapravo zapisuje ono što mi danas definiramo logiku prvog reda.

Logika prvog reda relativno je bliska prirodnom jeziku jer njena gramatika dopušta i izražavanje formula sa kvantifikatorima svi i neki. Korištenjem kvantifikatora, donekle možemo formulom izraziti sud izrečen prirodnim jezikom.

Logika drugog reda ima identičnu sintaksu kao i logika prvog reda s jednom bitnom razlikom - dopušta izražavanje svojstva ili predikata uz pomoć kvantifikatora.

U tom smislu, logika 2. reda znatno je bliža ekspresiji prirodnog jezika no logika 1. reda.

Promotrimo primjer:

Svi ljudi vole palačinke = Vx(L(x) → P(y) ∧ V(x, y) ) [Logika prvog reda]

Svi ljudi vole sve palačinke = VxVP(L(x) → P ∧ V(x, P)) [Logika drugog reda]

ili

VxVy(L(x) → P(y) ∧ V(x, y)) [Logika prvog reda].

Kao što je očito, formula u drugoj rečenici ekspresivnija je i jasnija, možda čak i jednostavnija jer sustav dopušta kvantificiranje predikata. Kada bismo bili samo u sustavu logike prvog reda, morali bismo kvantificirati varijablu koja ima pojam palačinke za predikat.

Logika drugog reda prilagodljivija je ljudskom toku misli, no opet nudi egzaktnost, sistematičnost i matematičnost (mogućnost kalkulacija) kao i logika prvog reda koja je naslijedila slična svojstva iz propozicijske logike.

Semantika i dokaz

Tzv. standardna semantika nalaže, dopušta uporabu kvantifikatora za sve elemente nekog skupa i ne samo to, već doseg kvatifikatora je takav da uključuje sve skupove funkcije ili predikata. Neki takvu semantiku nazivaju i potpunom semantikom.

Postoji, također Henkinova semantika koja je vrlo slična semantici logici 1. reda. Dakle doseg kvantifikatora je ograničen. Ne obuhvaća sve skupove funkcije ili predikata pa je time manje ekspresivnija, posljedično tome i ograničavajuća. No zato je jasnija jer nam je poznat doseg kvantifikatora.

Problem oko logike 2. reda leži u nemogućnosti izvođenja klasičnog deduktivnog dokaza. Varijable mogu biti takve da obuhvaćaju sve podskupove nekog skupa. Rješenje tog problema možemo inicirati na način da na logiku drugog reda gledamo samo kao na modalnu logiku – dakle varijable i predikati odgovaraju samo jednom specifičnom svemiru/modelu. Onda se postavlja pitanje, čemu tolika ekspresivnost ako se opet moramo ograničiti na samo jedan univerzum? Stoga, logičari skloni deduktivom dokazivanju, smatraju da domena formule treba biti definirana (dakle kvantifikatori obuhvaćaju samo neke podskupove, kako za univerzalni tako i za egzistencijalni kvantifikator.) služeći se Henkinovom semantikom. Do takve nejasnoće dolazi zato što logika 2. reda nije potpuna i konačna. U potpunim sustavima vi možete formirati jasna uzročno-posljedična pravila za izvođenje dokaza. Neki logičari i filozofi, smatraj da logika 2. reda, zbog spomenutih manjkavosti i nije prava logika.


Literatura:

Enderton, Herbert B., "Second-order and Higher-order Logic", The Stanford Encyclopedia of Philosophy (Fall 2015 Edition), Edward N. Zalta (ed.), URL = https://plato.stanford.edu/archives/fall2015/entries/logic-higher-order/

Vaanane, Jouko, Second-order logic and foundations of mathematics, The Bulletin of Symbolic Logic, Volume 7, Number 4, Dec. 2001

Rossberg, Marcus, First-Order Logic, Second-Order Logic, and Completeness