Elsőrendű logika

A Wikipédiából, a szabad lexikonból.

Az elsőrendű logika a matematikai logika egyik elmélete, mely az elsőrendű logikai nyelvekkel foglalkozik. Ezek első közelítésben olyan logikai nyelvek, melyekben lehetőség van az individuumváltozók kvantifikálására, vagyis a „van olyan ... amelyre ... ” ( $\exist x: ...$ ) és „minden ...-re igaz ... ” ( $\forall x: ...$ ) és ehhez hasonló állítások megfogalmazására – noha e meghatározás pontatlan, és további taglalaásra szorul, ami lentebb található.

Az elsőrendű nyelveket, ahogy a formális nyelveket általában legkézenfekvőbb logikai formulák, betűsorozatok halmazaként definiálni. Ahogy minden formális nyelv esetén, adva van egy nyelvbázis, azaz egy betűkészlet és egy csomó szabály, mely megadja, hogy a betűket milyen sorrendben lehet és kell összerakni. Ezt a folyamatot vizsgálja a szintaxis. A nyelvben vannak nem-logikai konstansok és individuumváltozók, melyek valamilyen adott U halmaz, az univerzum elemeit jelenthetik, vannak az U halmazon értelmezett „homogén” műveleteket (függvényeket) jelölő függvényszimbólumok, melyek az U halmazba képeznek, és vannak 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, vannak segédjelek (a nyitó- és csukózárójel), és végül vannak logikai jelek (kvantorok és logikai műveleteket jelölő összekötőjelek, junktorok).

Erre az alapra épül aztán az elsőrendű logika elmélete. 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, uram bocsá' más tudományterületeken, horribile dictu, a köznapi életben (ipar, kereskedelem, stb.).

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. Lásd még lentebb .

Tartalomjegyzék

1 Ágak, területek
- 1.1 Az elsőrendű nyelv
- 1.2 Az elsőrendű nyelv és nyelvbázis

[szerkesztés] Ágak, területek

Az elsőrendű logika főbb ágai, a fontosabb kutatási területek:

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. Ez a két összetevő 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, L. Łukasievicz. 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 modellunivwerzumok 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).

[szerkesztés] Az elsőrendű nyelv

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 , \exist$ ) , 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.