Elsőrendű logika

Az elsőrendű logika a matematikai logikának az elsőrendű nyelvekkel foglalkozó ága. Az elsőrendű nyelvek olyan formális nyelvek, melyekben lehetőség van az individuumváltozók kvantifikálására, vagyis a „van olyan x amelyre A teljesül” és a „minden x-re A teljesül” típusú állítások megfogalmazására.

Az elsőrendű logika elméletének két fő - egymást nem kizáró, hanem kiegészítő - paradigmája a szintaktikai és a szemantikai megközelítés. A szintaxis a logikai jelek, jelsorozatok, formulák formai jellemzésével foglalkozik; a szemantika pedig a jelek értelmezésével, azzal, hogy hogyan lehet kitölteni őket tartalommal és használni a matematikában, más tudományterületeken, illetve a köznapi életben ipari, kereskedelmi stb. alkalmazásokban.

Az elsőrendű logika bizonyításelmélet nevű ága inkább (de nem kizárólag) szintaktikai megközelítésből vizsgálja az elsőrendű nyelveket, míg a modellelmélet inkább a szemantikára koncentrál.

Ágak, területek

Az elsőrendű logika főbb ágai, illetve fontosabb kutatási területei a következők:

• Bizonyításelmélet – az elsőrendű logikán belül neve Predikátumkalkulus. A logikai kalkulusok azzal foglalkoznak, hogy hogyan lehet az illető logikai elméletet axiomatikusan felépíteni. Megadunk néhány, általában szemantikai érvek alapján „elfogadott” formulát (axiómák) és néhány szintaktikai levezetési szabályt, melyek segítségével „elfogadott” formulából „elfogadott” formulák gyárthatóak úgy, hogy ami nem gyártható le, az ne is számítson „elfogadottnak” (záradék). Ez a három összetevő (lásd: rekurzív definíció) alkot egy kalkulust. A cél, hogy egyrészt minden „elfogadott” formulát le tudjunk vezetni (a kalkulus teljes legyen), másrészt minden levezethető formula „elfogadott” legyen (a kalkulus helyes legyen). Röviden szólva, minden igazságot bizonyítani lehessen, de egy hülyeséget sem. Az elsőrendű predikátumkalkulus fejlesztésében szerepet vállaló legfontosabb kutatók: G. Frege, B. Russell, D. Hilbert, K. Gödel, G. Gentzen, L. Henkin, A. Tarski, J.A. Robinson, J. Łukasiewicz. A főbb elméletek, alágak:
  • Az elsőrendű Hilbert-kalkulus,
  • Az elsőrendű Frege-kalkulus
  • Gentzen-stílusú kalkulusok (természetes levezetőkalkulus, szekventkalkulus),
  • Tablókalkulus,
  • Rezolúciós kalkulus.
• Modellelmélet – Egy formula vagy nyelv modelljének egyszerűen egy olyan interpretációt (matematikai struktúrát) nevezünk, mely a formulát kielégíti. A modellelmélet ezen interpretációk egymáshoz és a formulához való viszonyaival foglalkozik. Tehát ez egy elsősorban szemantikai jellegű tudományág. Legfontosabb területe a modelluniverzumok számosságának kutatása, az itt elért fő eredmény a Löwenheim-Skolem-tétel. A legnevesebb kutatók: L. Löwenheim, K. Gödel, A. I. Malcev.
• A bizonyításelméletből nőtt ki mára önálló tudományággá a „számításelméleti” vagy „számítógépes logika”, melynek fő területe az automatikus tételbizonyítás kutatása. Legfontosabb elmélete a rezolúciós kalkulus. Ezenkívül foglalkozik a logika számításelméleti vonatkozásaival is (kielégíthetőségi problémák [SAT] és megoldhatóságuk kutatása és jellemzése).

Elsőrendű nyelvek

Az elsőrendű nyelveket, ahogy a formális nyelveket általában logikai formulák, betűsorozatok halmazaként definiáljuk. Ahogy minden formális nyelv esetén, adva van egy nyelvbázis, azaz egy betűkészlet és szabályok egy halmaza, mely megadja, hogy a betűket milyen sorrendben lehet és kell összerakni. Ezeket a szabályokat nevezzük a nyelv szintaxisának. A nyelv elemei a következő osztályokban sorolhatók:

• nem-logikai konstansok és individuumváltozók, melyek valamilyen adott U halmaz, az univerzum elemeit reprezentálják,
• az U halmazon értelmezett homogén műveleteket (függvényeket) jelölő függvényszimbólumok, melyek az U halmazba képeznek,
• az U halmazon értelmezett, de az {„igaz”, „hamis”} (más jelöléssel {0,1}) halmazba képző heterogén műveleteket, a logikai függvényeket vagy predikátumokat jelölő predikátumszimbólumok
• segédjelek (a nyitó- és csukózárójel)
• logikai jelek (kvantorok és logikai műveletek jelei).

Egy véges sok szimbólumot tartalmazó, adott jelkészlet vagy ábécé feletti logikai nyelvben – Frege nyomán ^{ld. itt} kétféle szimbólumot különböztetünk meg: állandókat és változókat. A modern elsőrendű logikában e megkülönböztetés a következőképp differenciálódott:

• A segédjelek „értelmetlennek”, szakszerűbben „jelentés nélkülinek” ^{#MIniesszé erről lentebb} nevezhetőek, csak a formulák elválasztását és szintaktikai-pragmatikai támogatását végzik: az elsőrendű nyelvekben két segédjel van, a nyitó- és csukó zárójel ( ( és ) ); mellesleg megoldható lenne az is (az ún. lengyel jelöléssel vagy a Fogalomírásban, de akár jelölési konvenciók/axiómák bevezetése által is), hogy ne is kelljen szerepelniük az elsőrendű logikában.
• Az állandók vagy konstansok értelme az adott nyelvben mindig ugyanaz. Kétféle állandót különböztethetünk meg a logikai nyelvekben:
  • A logikai konstansok, ide tartoznak a logikai összekötőjelek ($\lnot ,\wedge ,\vee ,\rightarrow ,\leftrightarrow ,\equiv ,=$) és a kvantorok ( $\forall ,\exists$ ), melyek adott halmazból az {„igaz”, „hamis”} (vagy {0, 1} ) halmazba képező, azaz logikai függvények
  • A nem-logikai konstansok, vagy egyszerűen csak konstansok, melyek nem ilyenek, azaz ún. individuumokat jelölnek;
• A változók jelentése viszont nem feltétlenül állandó, ugyanazon formula egy-egy példányában (ha mondjuk a lap tetején vagy alján fordul elő) mást és mást jelenthet ugyanaz a szimbólum, még ha pontosan ugyanazon a helyen is van. Ezeknek a jeleknek a jelentését meg kell adni, ezt úgy mondjuk, hogy a jeleket interpretáljuk. Ezen belül a változókat is két csoportra oszthatjuk:
  • logikai változók vagy individuumváltozók ezek adott interpretáción belül is többféle dolgot jelenthetnek, értékük megadását kiértékelésnek nevezzük;
  • nem-logikai változók ezek a függvényjelek és a predikátumjelek, az ún. többfajtájú nyelvekben még az ún. fajtajelek is (hogy megkülönböztessük őket a logikai változóktól, gyakran csak „jeleknek” vagy „szimbólumoknak” nevezzük őket, és nem tekintjük őket „logikai értelemben vett” változóknak). Ezek értelme egy adott interpretációban nem változik.

---

Lásd még

• Formális nyelv

Hivatkozások

• Bach, Iván. Formális nyelvek: Egyetemi tankönyv. Budapest: Typotex (2002). ISBN 963 9132 92 6 
• Csirmaz, László: Matematikai logika egyetemi jegyzet, ELTE Bp., 1994 (Postscript változat)