Elsőrendű nyelv

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

Az elsőrendű nyelvek (vagy másképpen elsőrendű logikai nyelvek) fogalma a matematikai logika egyik legalapvetőbb fogalma. Ezeket, és általában az n-edrendű nyelv fogalmát, elsősorban annak modellelmélet nevű ága vizsgálja. Az elsőrendű nyelvek matematikai elméleteinek összefoglaló neve elsőrendű logika.

Röviden szólva, egy elsőrendű nyelv egy csomó olyan matematikai logikai kifejezés (azaz betűsorozat) halmaza, melyekben a betűk változók (individuum- vagy szubjektumváltozók, függvényváltozók, predikátumváltozók) és logikai jelek, illetve különféle egyéb szimbólumok. A betűk egy speciális halmazból vagy halmazrendszerből, az ábécéből kerülhetnek ki.

Az „elsőrendű” kifejezés általában egy szemantikai, de szintaktikus úton definiált tulajdonságra utal, utóbbi definíció pontatlanul a következő: a függvény- és predikátumváltozók formális argumentumai – melyek szintén változók – nem lehetnek maguk is predikátumváltozók. A pontos szemantikai leírás halmazelméleti eszközökkel tehető meg: a nyelv tehet kijelentéseket az általa vizsgált elmélet, „univerzum” elemeiről, de az elemek tetszőleges halmazáról, vagyis az univerzum hatványhalmazának elemeiről már nem.

A betűk egy halmaz, az ábécé különféle jelei lehetnek: pl. ún. individuumváltozók, fajtajelek, műveleti- / függvény- és relációjelek (vagy függvényváltozók és relációváltozók), konstansjelek – ezeken kívül mindegyik elsőrendű nyelv, ahogyan mindegyik logikai nyelv, tartalmaz legalább két logikai jelet (az egyik egy logikai művelet jele, a másik egy kvantor) és két elválasztójelet (általában a közönséges nyitó- és csukó zárójeleket).
A szabályok (szintaxis) megadják, hogy a szimbólumokból hogyan képezzünk olyan sorozatokat, melyeket értelmesnek, azaz a nyelv részeinek tartunk. Ezen szabályokat többféle módszerrel is megfogalmazhatjuk (mi a logikában általánosan használt és legkézenfekvőbbnek tekintett szintaktikus rekurziót alkalmazzuk, de lehetséges halmazelméleti fogalmakra; és/vagy generatív nyelvtanokra, Markov-algoritmusokra vagy egyebekre is építeni).
Maga a nyelv, mint kifejezéseinek halmaza, a betűkből a szabályok segítségével építhető fel. A betűket és szabályokat együtt a nyelv bázisának nevezzük.

Néha az „elsőrendű” kifejezésen pedig az előző tulajdonsággal szoros kapcsolatban álló, de vele mégsem teljesen ekvivalens, szintén szintaktikai jellegű tulajdonságot értenek, ti. hogy a nyelv tartalmaz kvantorokat (tehát több mint nulladrendű), de csak az individuumváltozók a valódi, logikai értelemben vett változók. Azaz csak ezek azok, melyek a nyelv interpretációi által sem egyértelműen meghatározott jelentésűek, vagy ami ezzel szoros kapcsolatban van, csak ezek a kvantifikálható változók; tehát a nyelv még nem másodrendű – mert másodrendű nyelvekben a függvény- és predikátumszimbólumok sem egyértelműen meghatározottak az interpretáció által, hanem kvantifikálhatóak). Az utóbbi két dolog, „interpretációfüggetlenség”/„logikaiság” és kvantifikiálhatóság valóban majdnem ugyanaz, hisz nem-logikai változók kvantifikálása a logikában valóban teljesen értelmetlen/lehetetlen, hiszen ezek egy adott interpretációban konkrét és rögzített jelentést kapnak (lásd az x. példát).

Az elsőrendűség jelentős korlátozást jelent mind a természetes nyelvekhez, a köznyelvhez, de még a matematikában az elméletek leírására általában használt formális nyelvhez képest is. Sok probléma azonban egyszerűbben, ugyanakkor még elegendő részletességgel vizsgálható így is.

Az elsőrendű nyelveknek rendkívüli szerepük volt az egész modern formalista matematika kifejlődése szempontjából (ld. az elsőrendű nyelvek történetéről szóló részt). E nyelvek, és általában a logikai nyelvek legközvetlenebb haszna a következtetések elméletének precíz matematikai leírása. Ezen kívül az informatikában is fontos szerepet kapnak mint alkalmazások, hisz sok programnyelv tulajdonképp többé-kevésbé egy elsőrendű nyelvnek tekinthető, legalábbis tartalmaz ilyen nyelvet részként.

[szerkesztés] Bevezetés

Az elsőrendű nyelvek elmélete rengeteg speciális, precízen és formálisan definiált szakkifejezést tartalmaz, melyeknek e szakaszban a szemléletes leírása és motivációi olvashatóak:

Egy logikai nyelvet gyakran valamilyen konkrét dolog vagy elmélet (struktúra) vizsgálatára, modellezésére használunk. Ez egy halmazrendszer, amely az elmélet által vizsgált objektumok halmazából, az univerzumból, és az e fölött értelmezett relációkból, műveletekből, függvényekből áll.
A logikai nyelvek kutatásának egy részterülete, a szemantika foglalkozik azzal, hogy hogyan lehet/kell egy adott nyelvet értelmezni, interpretálni.
- Nézzük, pontosan miből is áll egy struktúra. A matematikai struktúrák tradicionálisan négy-öt fontos dolgot szoktak tartalmazni, melyek megkülönböztetik őket a többi struktúrától: 1). az univerzumot, azaz alaphalmazt; 2). az univerzum feletti különféle fontosabb halmazrendszereket („topológiai struktúra”); 3). fontosabb két- vagy többváltozós (nem egyértelmű) relációit („relációs struktúra”), egyéb 4). Az egyértelmű relációknak annyira kitüntetett szerepük van, hogy ezeket külön szoktuk venni (függvények és/vagy műveletek, „algebrai struktúra”); 5). azon kívül az univerzum bizonyos kitüntetett elemeit („konstansok”). Valójában elegendő lenne csak a relációs struktúra fogalma, mert a struktúra összes többi eleme is reláció, de megszokásból és egyéb okok miatt ragaszkodni szoktunk a fenti tipizáláshoz.
- Ha megvan a nyelv és az általa leírt, modellezett struktúra, meg kell adni, a nyelv melyik elemének a modell melyik eleme feleljen meg. Matematikailag ez a megadás egy leképezést, függvényt jelent a fontosabb elemek között. Ezt a leképezést vagy leképezésrendszert a nyelv interpretációjának nevezzük, a struktúrát mint az interpretáció eredményét pedig a nyelv modelljének (némileg helytelenül, mivel a „modell” szó értelme szerint inkább a nyelvet kellene a struktúra modelljének nevezni).
- Egy adott nyelv több különböző „univerzum” vagy „struktúra” leírására is alkalmas lehet, azaz persze többféleképp interpretálható (ennek feltételeit az ún. szintaxis részeként pontosan meg lehet adni (lentebb).
- A fentieknek megfelelően a nyelv egy struktúra minden fontosabb eleméhez szimbólumokat rendel. Az univerzum elemeinek megnevezésére az individuumváltozók, a relációk megnevezésére a relációjelek vagy predikátumszimbólumok vagy predikátumváltozók, a műveletek/függvények megnevezésére a függvényjelek vagy függvényváltozók, a konstansok megnevezésére a konstansjelek, az univerzum egy adott halmazrendszerének megnevezésére a fajtajelek szolgálnak.
- Még egy megkülönböztetést kell tennünk; ugyanis a „változó” kifejezést a logikában egy kicsit szűkebb értelemben használjuk, mint a matematikában. A matematikában egy nyelv változója olyan nyelvi szimbólum, mely többféleképp interpretálható. Ebben az értelemben a logikai nyelvek bármely szimbóluma („nem-logikai”) változó. Azonban „logikai (értelemben vett) változónak” csak akkor nevezhetünk egy szimbólumot, ha egy adott, rögzített interpretációban is többféle értéket vehet fel. Ebben az értelemben az elsőrendű nyelvekben csak az individuumjelek számítanak változónak.
- Vegyük észre, hogy „az interpretáció kivisz minket a nyelvből”: az interpretált szimbólumok már nem részei az adott logikai nyelvnek. E szempontból egy logikai nyelv bármely szimbóluma – az ún. logikai összekötőjeleket leszámítva, melyek halmazát később $L$ -lel fogjuk jelölni – értelmetlennek nevezhető (más szempontból azonban nem, hogy ti. a szimbólumok interpretálhatóak, tehát lehet hozzájuk jelentést tulajdonítani – csakhogy a jelentés már kívül van a nyelven).
- Megjegyzés: a dolog nem mindig jelenti a logikai nyelv kifejezőerejének semmisségét (néhány fontos nyelvben – például a halmazelméletet leíró elsőrendű nyelvben a konstansszimbólumok segítenek ezen). Gyakran előfordul pl., hogy úgy választjuk meg őket, hogy a konstans- és függvényszimbólumokból képezett kifejezések segítségével a nyelv által leírt struktúrák univerzumának minden eleme előálljon. Ilyen esetben tulajdonképp a nyelv szavainak interpretálatlanul is értelmet tulajdoníthatunk. Azonban ilyen kitüntetett konstans elemek sok nyelvben nem léteznek (pl. a háromdimenziós euklideszi geometriát leíró elsőrendű nyelvben a pontok közt nincs kitüntetett), így ez a követelmény nem építhető a matematikai definícióba.
Szintaxis: A nyelv szimbólumaiból bizonyos előírások alapján (szintaxis) sorozatokat („jólképzett szavakat”) képezhetünk. Mivel egy interpretáció minden elemnek egy struktúra valamely elemét felelteti meg, ezért egy szimbólumsorozatnak is a struktúra valamely eleme: univerzumelem, vagy függvény, vagy ezekről szóló állítás felel meg. A nyelv szavai különféle szintaktikai és szemantikai osztályokba (termek, formulák, prímformulák, formulamagok stb.) tartozhatnak, azaz különféle előírt alakúak és jelentésűek lehetnek, és elsősorban az ilyesfajta megkülönböztetésekről szól e nyelvek elmélete.
- Hangsúlyozni kell tehát, hogy az elsőrendű nyelv valójában nem pusztán szimbólumhalmazból álló formális nyelv, hanem van szintaxisa és szemantikája is. Azonban, ahogy az látható is lesz lentebb, ezt a matematikai definícióba – különféle okok miatt – nem minden szerző szokta beleépíteni, ami viszont bizonyos hiányt okoz. Ennek betöltésére két megoldás is elképzelhető:

úgy fogjuk fel a dolgot, hogy a szintaktikai és szemantikai előírások megalapozásával nem a logikai nyelvelmélet, hanem egyrészt a filozófia, másrészt, a matematikán és matematikai logikán belül, a kijelentésfüggvények elmélete foglalkozik (ez egy nagyon egyszerű, kombinatorikus jellegű elmélet, a matematikai logikai tankönyveknek mindig az első, bevezető fejezete szokott lenni).
a fenti elmélet egy lebutított változatát a nyelv szintaxisa c. fejezetben közöljük.

Mi ennek az egésznek az értelme? Az elsőrendű nyelvek, és a matematikai logikai nyelvek általában, abban különböznek a többi formális nyelvtől, illetve az az egyik elsődleges motivációjuk, hogy néhány kitüntetett művelet segítségével a következtetés fogalmának matematikai leírására alkalmasak.

A fogalom pontosabb (vagy, a fentieket is figyelembe véve, inkább formálisabb) leírása lentebb olvasható.

[szerkesztés] Az elsőrendű nyelvbázis

Valamely $Λ$ ábécé feletti elsőrendű nyelvbázis (teljes nevén többfajtájú elsőrendű logikai nyelvbázis) olyan $\mathcal{B} = \left ( \Lambda, \mathcal{S} \right)$ kéttagú halmazrendszer, ahol

különféle fajtájú szimbólumokból álló halmazrendszer, az ábécé;
- Az Sr, C, F, P, elemei ún. nemlogikai jelek, ezek nyelvről nyelvre változnak;
- a V, L, Z elemei az ún. logikai jelek, ezek minden elsőrendű nyelvben lényegében ugyanazok.
is (kéttagú) halmazrendszer, mely a nyelv „szerkezetét” írja le, s melyet a nyelv(bázis) szintaktikai részének, vagy a nyelv szintaxisának nevezünk. Tagjai:
- $σ$ a nyelv(bázis) szignatúrája; ami megadja, az ábécé elemei formálisan hány változósak és a változók milyen fajtájúak – mellesleg a szignatúra maga is egy halmazrendszer (függvényrendszer);
- $Σ$ pedig valamilyen formában adott formális szabályok halmaza. Ezek precíz formában, formális módszerekkel is megadhatóak, de meg szoktunk elégedni a matematikai szakkkifejezésekkel bővített köznyelven való megfogalmazásukkal is, ha ez elvben formálissá tehető.

Az ábécé, mint halmazrendszer összes betűinek halmaza épp $\bigcup{\Lambda}$ . Az ezen ábécé felett elvileg felírható szavakat az utóbbi unióhalmaz elemeiből képezett összes véges sorozattal azonosítjuk, vagyis a $Λ$ ábécé feletti összes szó halmaza legyen $\bar{\Lambda} := \bigcup_{i=0}^{\mathcal{1}} \left( \bigcup{\Lambda} \right)^{i}$ . A szintaxis azt adja meg, hogy ez utóbbi halmazból melyek azok a szavak, melyeket értelmesnek, jólképzettnek (well-formed) tekintünk, és hogy kell ezeket jól képezni; míg a szemantika vizsgálja, hogy ha már értelmesek, akkor mi lehet, mi legyen az értelmük.

Egy formális nyelv felépítését lehetővé tévő elemek összességére, ami nálunk a $\left( \Lambda, \sigma, \Sigma \right)$ elemhármast jelenti, Ruzsa Imre filozófus vezette be a nyelvbázis fogalmát (bár az ő definíciója eltér az ittenitől, ennél bővebb, pontosabb). Más szerzők is definiálnak hasonló fogalmakat, csak jelkészletnek nevezik (a jelkészletbe nem szokás beleérteni a szintaktikai szabályokat, csak az ábécét és a szignatúrát – így e fogalom sokkal egyszerűbb, de épp azért, mert a szintaxis egy része „elsikkad”).

[szerkesztés] Az ábécé

$\left( Sr, C, F, P, V, L, Z \right)$ halmazrendszer, ahol

$S r$ a fajtajelek (sort = fajta),
$C$ a konstansjelek,
$F$ a műveleti- vagy függvényjelek,
$P$ a relációjelek vagy predikátumszimbólumok halmaza, ha $= \ \in \ P$ , azaz individuum-egyenlőségi reláció eleme a predikátumszimbólumoknak); akkor egyenlőségjeles elsőrendű nyelvről beszélünk. E négy halmaz tartalmazza a nemlogikai jeleket; továbbá vannak logikai jelek is, három halmazt alkotnak:
$V$ a változók (-jelek),
$L$ a (logikai) összekötőjelek (vagy logikai függvényjelek, logikai műveleti jelek);
$Z$ a zárójelek és kiegészítő jelek (vessző) halmaza – a legtöbb szerzőnél Z = { , , ( , ) }.

Ha $Sr = \empty$ , egyfajtájú, egyébként többfajtájú nyelvről beszélünk (egyfajtájú a legtöbb matematikai diszciplina leírására használt nyelv, többfajtájú a geometria nyelve, mert a változók többféle halmazból – pontok, egyenesek, síkok, esetleg terek, hipersíkok stb. – vehetnek fel értékeket). Sok szerző nem is szokta az egyfajtájú/többfajtájú megkülönböztetést véghezvinni, hanem csak egyfajtájú nyelveket vizsgál.
Változójelekből megszámlálhatóan végtelen sok van: $x_{1} , x_{2}, ... x_{n}, ... \in V$ , ezeket néha az $x, y, z, ... \in V$ betűkkel is jelöljük az egyszerűség kedvéért. A változójelek csak ún. individuumváltozók lehetnek, e korlátozásra utal az „elsőrendű” megjelölés.
Relációjelekből és függvényjelekből (ezek megkülönböztetése igazából általában fölösleges , csak a tradíció miatti) is megszámlálható (de nem feltétlenül végtelen) sok van: $r_{1}, r_{2}, ... \in P$ és $f_{1}, f_{2}, ... \in F$ .
a logikai összekötőjelek általában a következők közül kerülnek ki: $\lnot , \wedge , \vee , \rightarrow , \leftrightarrow , \forall , \exist$ , de a vizsgálat tárgyától függően esetleg más logikai függvényjelek is megengedhetőek (arról van szó, hogy a használt szimbólumok halmaza lehetőleg funkcionálisan teljes legyen). Elsőrendű nyelvekben a $\forall$ és $\exist$ kvantorok azonban kötelezően szerepelnek a logikai jelek közt, és általában a $\rightarrow$ implikációjel is. A legtöbb szerző szerint $L := \left\{ \lnot , \wedge , \vee , \rightarrow , \forall , \exist \right\}$ .
A kiegészítő jelek halmaza általában, ahogy említettük, $Z := \left\{ \ ( \ , \ ) \ , \ , \ \right\}$ .

[szerkesztés] Szintaxis

A szintaxis elemei: a szimbólumokat – röviden mondjuk úgy, hogy egymással való összekapcsolhatóságuk szempontjából – szintaktikai osztályokba soroljuk, ehez bevezetjük a szignatúra (vagy típus stb.) fogalmát vagy valamilyen hasonló segédfogalmat. Maguk a szimbólumokból összetett kifejezések is szintaktikai – azaz betűkből való felépítésük szerinti – osztályokba sorolhatóak, az egyes osztályok felépítését a szintaktikai szabályok adják meg.

[szerkesztés] Szignatúra

Fontos még a szignatúra vagy típus fogalma. Ez nagyjából olyan függvényt jelent, ami a műveleti- és relációjelekhez hozzárendeli az aritásukat, azaz azt, hogy formálisan hány változósak, és az alakjukat, azaz hogy változóik milyen fajtákba tartoznak.

Pontosabban a következőket mondhatjuk:
- Minden $f \in F$ műveleti jelhez tartozik egy $a_{f} \in \mathbb{N}$ természetes szám, a jel aritása vagy változószáma, és egy $\alpha _{f} = \left( s_{1}, s_{2}, ... , s_{m}, s \right) \in Sr^{a_{f}+1}$ fajta-n-es, mely megadja, hogy a műveleti jel i-edik változója $s i$ fajtájú (az $a f + 1$ -edik fajtajel a függvényszimbólum „kimenetének”, függő változójának fajtáját adja majd meg). Összességében tehát létezik az $\alpha(f): F \mapsto \bigcup_{i=1}^{ \mathcal {1} } Sr^{i} ; \forall f \in F: \alpha(f) = \alpha_{f}$ függvény.
- Hasonlóan minden $\rho \in P$ relációjelhez is tartozik egy $b_{\rho} \in \mathbb{N}$ aritási szám és egy $\beta _{\rho} = \left( s_{1}, s_{2}, ... , s_{m} \right) \in Sr^{b_{\rho}}$ fajta-n-es; összességében tehát létezik az $\beta( \rho ): P \mapsto \bigcup_{i=1}^{ \mathcal {1} } Sr^{i} ; \forall \rho \in P: \beta( \rho ) = \beta_{ \rho }$ függvény.
- A $c \in C$ konstansok mindegyikéhez egy $\gamma _{c} \in Sr$ fajtába tartozik; összességében tehát létezik az $\gamma (c): C \mapsto Sr;$ függvény.
Ennyit az aritási függvényekről. Meg kell adnunk azonban nemcsak a változók számát, hanem azok fajtáit is:
- Mivel az $α(f),β(ρ),γ(c)$ függvények bizonyos rendezett párok halmazai, vehetjük ezek unió (halmazelmélet)unióját. Nem nehéz belátni, hogy a három függvény értelmezési tartományainak páronkénti diszjunktsága miatt (ezt az alapkövetelményt az ábécé leírásánál említettük) a függvények uniója is függvény lesz, értelmezési tartománya a három függvény értelmezési tartományának uniója. A $\sigma = \alpha_{f} \cup \beta_{\rho} \cup \gamma_{c} ; F \cup P \cup C \mapsto \bigcup_{i=1}^{\mathcal{1}}Sr^{i}$ uniófüggvényt nevezhetjük a nyelv(bázis) szignatúrájának (vagy típusának, fajtájának stb.).
- Nevezhetjük szignatúrának a $\sigma = \left( \alpha_{f} , \beta_{\rho} , \gamma_{c} \right)$ függvényhármast is. Az utóbbit tesszük, mert a konkrét nyelvekre egyszerűbb és átláthatóbb külön-külön megadni a szignatúrát (pl. táblázattal), mint unió alakban.
- A szignatúra úgy is megadható, hogy rendre felsoroljuk az ábécé jeleit: konstans-, függvény- és predikátumszimbólumokat, ez egy rendezett (esetleg végtelen sok tagú) elem-sokaság, azután minden kérdéses szimbólum fajtáját/alakját is hasonló rendezett elem-sokaságként adjuk meg, az első rendszerben az i-edik szimbólum alakját a második rendszerben az i-edik elem adja meg. Ezt a formát, melyet ha jól megnézünk, nem különbözik lényegesen az uniófüggvényként való megadástól, a nyelv típusának szokás nevezni.

Megjegyzés : Ha a szignatúra, például mint a szimbólumokhoz rendelt fajta-n-esek rendszere adott, akkor ezzel együtt az aritási függvények is adottak, hiszen ha minden szimbólumhoz hozzá van rendelve egy fajta-n-es, a szimbólum típusa, akkor a fajta-n-es tagszáma (ha a szimbólum relációjel) vagy ennél eggyel kevesebb (ha a szimbólum függvényjel) épp a szimbólum aritása; tehát az aritási függvény(ek) „benne van(nak)” a szignatúrában, így felesleges rájuk külön tekintettel lenni, elegendő a szignatúra megadása.

A szignatúra fogalma egyértelműen szintaktikai fogalom, de a szemantikában is fontos szerepe van. Egy konkrét elmélet (egy matematikai struktúra) és egy nyelv akkor modelljei egymásnak, ha szignatúrájuk megegyezik, vagyis elegendő pusztán az elemek „formális” hasonlósága. Lásd még szemantika.

[szerkesztés] A szintaktikai szabályok

A szimbólumokból bizonyos szabályok alkalmazásával szavakat építhetünk. * A logikailag legegyszerűbb szavak a termek (kifejezések, terminusok); ezek tkp. olyan szavak, melyek interpretálva a nyelv által leírt „valóság” (ld. lentebb) egy individuumát, nem pedig egy ilyenekről szóló kiértékelhető mondatot jelentenek.

Ezzel szemben a formula olyan szó, amely már relációjelet is tartalmaz, tehát amely lényegében egy kiértékelhető mondat sémáját jelenti.

A szintaktikai szabályokat precíz köznyelvi formában írjuk le; különféle fogalmak alkalmazásával tiszta, formális matematikai alakra is hozhatóak. A fogalmak pontos definíciója szerkezeti rekurzión (szintaktikus rekurzión, formularekurzión) alapul (ld. lentebb):

A konstanjelek termek; mégpedig ha $c \in C$ és c egy π fajtájú konstansjel, akkor egyben π fajtájú term is.
Az individuumváltozók termek; mégpedig ha $v \in V$ és v egy π fajtájú konstansjel, akkor egyben π fajtájú term is.
Ha $t 1, t 2,..., t n$ termek, rendre az $s 1, s 2,..., s n$ fajtából, és $f$ formálisan n-változós és $\sigma(f) = \left( s_{1} , s_{2} , ..., s_{n} , s \right)$ fajtájú műveleti jel, akkor $f \left( t_{1}, t_{2}, ... , t_{n} \right)$ term, mégpedig $s$ fajtájú.
Valami pontosan akkor term, ha az ábécé $C, F, V$ -beli betűiből az 1)., 2). és 3). szabályok véges sokszori alkalmazásával állítható elő. Tehát termek lényegében a függvényszimbólumokból, változókból és konstansokból képezett összetett kifejezések.
Ha P n-változós predikátumszimbólum, és $t 1, t 2,..., t n$ termek, akkor $P \left( t_{1}, t_{2}, ..., t_{n} \right)$ (elsőrendű) formula. Az ilyen, csak termeket, predikátumszimbólumokat és kiegészítő jeleket tartalmazó formulákat atomi formuláknak nevezzük.
Ha $P$ formula, akkor $\lnot (P)$ is formula ; ha P atomi formula, akkor ehelyett $\lnot P$ is írható (atomi formula negációja esetén a zárójeleket nem kell kitenni).
Ha $P, Q$ két formula, és $\oplus \in L - \{ \lnot \}$ , akkor $(P) \oplus (Q)$ is formula. Tehát ekkor $(P) \wedge (Q)$ , $(P) \vee (Q)$ , $(P) \rightarrow (Q)$ is formulák. Ha P,'Q egyike atomi formula, akkor a zárójelezés elhagyható: azaz pl. $P \rightarrow (Q)$ is formula az esetben, ha P atomi.
Ha $x \in V$ individuumváltozó, A tetszőleges formula, Q pedig kvantor – $Q \in \left\{ \forall , \exist \right\}$ – akkor $Q x (A)$ is formula. Az ilyen alakú formulákat kvantált formulának (kvantifikációnak) nevezzük. Tehát pl. ekkor $\forall x(P(x,y))$ is kvantált formula (univerzálisan kvantált) és $\exist x(P(x,z))$ is kvantált formula (egzisztenciálisan kvantált). Ha $A$ atomi formula, a zárójelezés elhagyható.
Minden formula az 5).-8). szintaktikai szabályok véges sokszori alkalmazásával áll elő az ábécé elemeiből és a termekből.

[szerkesztés] Néhány további fontos szintaktikai alosztály

Az atomi és a kvantált formulák közös neve prímformula. Ezek azért kitüntetettek, mert a nyelv összes formulája belőlük épül fel, a további logikai összekötőjelek és kiegészítő jelek $\left( \lnot \ , \ \wedge \ , \ \vee \ , \ \rightarrow \ , \ \leftrightarrow \ , \ ( \ , \ ) \ , \ , \ \right)$ segítségével.
Egy elsőrendű nyelvben azokat a szavakat/kifejezéseket (formulák, termek stb.), melyek individuumváltozót nem tartalmaznak, alapkifejezésnek nevezzük. Mit tartalmaznak tehát - konstansokat, függvényjeleket, predikátumjeleket, logikai- és kiegészítő jeleket. Konkrétan:
- Az individuumváltozót nem tartalmazó termek az alaptermek;
- Az individuumváltozót nem tartalmazó formulák az alapformulák
- Az individuumváltozót nem tartalmazó atomi formulák az alapatomok.
A kvantált formulákban az A formulát a formula magjának nevezzük. Ha a Q kvantor a $\forall$ univerzális kvantor, akkor univerzálisan kvantált formuláról vagy univerzális kvantifikációról, ha pedig a $\exist$ egzisztenciális kvantor, akkor egzisztenciálisan kvantált formuláról vagy egzisztenciális kvantifikációról beszélünk.
Azokat a formulákat, melyek nem tartalmaznak kvantort, logikusan kvantormentesnek nevezzük, míg a kvantort tartalmazókat kvantoros formulának. Vigyázzunk: minden kvantált formula kvantoros, de fordítva nem igaz! A $\forall x \left( P(x) \rightarrow Q(f(a) \right)$ formula kvantált. A $Q(f(a), f(x)) \wedge \forall x \left( P(x) \rightarrow Q(f(a) \right)$ formula viszont kvantoros, de nem egy kvantált formula.
Speciális alakra hozott kvantoros formulák a prenex formulák és a Skolem-formulák.
Azokat a kvantoros formulákat, melyeknek minden változója kötött, azaz szabad változót nem tartalmaznak, zárt formuláknak nevezzük.

[szerkesztés] Az elsőrendű nyelv

[szerkesztés] Definíció

Maga a $\mathcal{B}$ nyelvbázis feletti $\mathcal{L}$ formális elsőrendű (és többfajtájú) matematikai logikai nyelv, röviden elsőrendű nyelv az ábécé betűiből az előző szabályoknak megfelelő (jólképzett) sorozatok, a nyelv szavainak (termek, formulák) halmaza vagy rendszere.

Ha még precízebbek akarunk lenni, a nyelvet formálisan megadhatjuk mint egy $\mathcal{L}$ $=$ $\left( \Lambda , \ \sigma , \ \Sigma , \ W[ \mathcal{L} ] \right)$ $=$ $\left( \mathcal{B} , W[ \mathcal{L} ] \right)$ halmazrendszert, ahol $\mathcal{B}$ a nyelvbázis, $W[\mathcal{L}]$ pedig a jólképzett szavak (formulák, termek) halmaza vagy ezek halmazainak rendszere.

Megjegyzések :

Egyesek szerzők elsőrendű nyelven csak magát a szimbólumhalmazt azaz ábécét, tehát csupán a $\Lambda = \left( Sr, C, F, P, V, L, Z \right)$ különféle fajtájú szimbólumokból álló halmazrendszert értik, míg mások elsősorban a szavak halmazát értik. A matematika jelenlegi más ágaival (számítógéptudomány) a második megoldás nagyobb összhangban van, hátránya, hogy nagyon bonyolulttá teszi a fogalmat (az első változat vélhetően didaktikai okokból keletkezett egyszerűsítés).
Mivel minden függvény relációnak tekinthető, és minden konstansjel – nullváltozós – függvénynek, elegendő lenne az ábécében az F, P, C halmazokat összevonni, és pusztán R relációjelekről beszélni. Egyes szerzők ezt meg is teszik, mi e cikkben nem; ízlés kérdése.

A szintaktikai szabályok alapján a nyelv kifejezései (azaz maga a nyelv), halmazelméletileg is teljesen kifogástalanul megkonstruálhatóak. Rekurzióval ugyanis megkonstruálhatjuk a termek és a formulák halmazait. A következőkben a betűk egymás után írását (konkatenációját) egyszerűen a rendezettpár-képzéssel azonosítjuk.

[szerkesztés] A termek halmazának megkonstruálása a szintaxis alapján

Talán hihetetlen, de a fenti félig-meddig precízen és formálisan megfogalmazott szabályok valóban jól meghatározzák a nyelv kifejezéseit. Egy $\mathcal{L}$ elsőrendű nyelv összes termje egy halmazt alkot, ami halmazelméleti eszközökkel megkonstruálható az ábécé elemeiből, a következőképp (a $σ$ jelölés, mint eddig is e cikkben, a szignatúrát jelenti).

Legyen $T_{0} := C \cup V$ a „nulladosztályú termek” halmaza, tehát a konstansjelek és a változók ilyenek. Ezek az 1).-2). szintaktikai szabály alapján tényleg termek kell hogy legyenek.
Legyen most $n \in \mathbb{N}$ , $t_{1}, t_{2}, ... , t_{n} \in T_{0}$ mind nulladosztályú term, rendre az $s_{1}, s_{2}, ... , s_{n} \in Sr$ fajtából, és $f \in F$ n-változós és $\sigma (f) = \left( s_{1} , s_{2} , ..., s_{n} , s \right)$ fajtájú függvényszimbólum. Definiáljuk az „elsőosztályú termek” halmazát így: $T_{1} := \left\{ \ f \left( t_{1} , t_{2} , ..., t_{n} \right) \in F \times \left\{ ( \right\} \times \left( \ T_{0} \times \left\{ , \right\} \ \right) ^{n-1} \times T_{0} \times \left\{ ) \right\} \ \mathcal{j} \right.$ $\left. \mathcal{j} \ n \in \mathbb{N} ^{+} \wedge \sigma (f) = \left( \sigma ( t_{1} ) , \sigma ( t_{2}) , ..., \sigma ( t_{n} ) , s \right) \ \right\}$ $\subseteq$
$\subseteq$ $F \times Z \times \left( T_{0} \times Z \right) ^{n-1} \times T_{0} \times Z$ .
...
Ha minden $i \in \left\{ 0, 1, 2, ... \right\}$ -re már definiáltuk a $T i$ halmazt (az i-edosztályú termekét), az addig definiált termek halmaza ekkor persze $U_{i} := \bigcup_{j=0}^{i} {T_{i}}$ ; akkor teljesen $T 1$ definíciójához hasonlóan folytathatjuk a(z i+1-edosztályú) termek definiálását: $T_{i+1} := \left\{ \ f \left( t_{1} , t_{2} , ..., t_{n} \right) \in F \times \left\{ ( \right\} \times \left( \ U_{i} \times \left\{ , \right\} \ \right) ^{n-1} \times U_{i} \times \left\{ ) \right\} \ \mathcal{j} \right.$ $\left. \mathcal{j} \ n \in \mathbb{N} ^{+} \wedge \sigma (f) = \left( \sigma ( t_{1} ) , \sigma ( t_{2}) , ..., \sigma ( t_{n} ) , s \right) \ \right\}$ $\subseteq$
$\subseteq$ $F \times Z \times \left( U_{i} \times Z \right) ^{n-1} \times U_{i} \times Z$ ..
Legyen az $\mathcal{L}$ elsőrendű nyelv termjeinek halmaza pedig $T[\mathcal{L}] := \bigcup_{i=0}^{\mathcal{1}} T_{i}$ .

A termek halmaza más (egyszerűbb, de kevésbé szemléletes) úton is megkonstruálható. Belátható u.is, hogy a fent kapott unióhalmaz a legszűkebb halmaz az 1).-2).-3). szintaktikai szabályoknak megfelelő halmazok között. Egyrészt van e szabályokat kielégítő szóhalmaz (a $Λ$ ábécé feletti összes betűsorozat $\bar{\Lambda}$ halmaza például ilyen), másrészt nagyon könnyű belátni, hogy az összes ilyen szóhalmaz metszete is ilyen. Be lehet látni, hogy e metszet épp a fent konstruált $T[\mathcal{L}]$ halmazzal egyenlő. Utóbbiról röviden annyit, hogy mivel a $T i$ halmazokat a szintaktikai szabályok figyelembevételével alkottuk, és a konstansok és a változók halmaza része a metszetnek, ezért a belőlük képzett $T i$ halmazok minden eleme is eleme a metszetnek, így ezek egyesítése, az unió része a metszetnek (a $T i$ halmaz konstrukciós szabályai „nem visznek ki” a metszethalmazból). Ha pedig valami eleme a metszethalmaznak, akkor a 4). szintaktika szabály biztosítja azt, hogy valamelyik $T i$ halmaznak az eleme legyen (egy részletes bizonyításban ez utóbbi állítást a legnehezebb belátni).

[szerkesztés] A formulák halmazának megkonstruálása a szintaxis alapján

Az 1).-9). szabályok a formulák halmazát ugyanúgy jól definiálják, mint a termekét, e halmaz is megkonstruálható, rekurzióval (a rekurzió lényegében a formulák bonyolultsága szerint megy):

Az atomi formulák lesznek a kiindulópontok („nulladosztályú formulák”), legyen $F 0 : =$ $:= \left\{ \ R \left( t_{1} , t_{2} , ... , t_{n} \right) \in P \times \left\{ \, ( \, \right\} \times \left( T[ \mathcal{L} ] \times \left\{ \, , \, \right\} \right) ^{n-1} \times T[ \mathcal{L} ] \times \left\{ \, ) \, \right\} \ \mathcal{j} \ \right.$ $\left. \ \mathcal{j} \ n \in \mathbb{N}^{+} \ \right\}$ $\subseteq$ $P \times Z \times \left( T[ \mathcal{L} ] \times Z \right) ^{n-1} \times T[ \mathcal{L} ] \times Z$ .

E definíció lényegében az 5). szintaktikai szabály precízebb, matematikai formába öntése.

Ezután az atomi formulákból képezett elsőosztályú kvantifikációs formulákat is előállítjuk. Definiáljuk így a $K 1$ formulahalmazt:
$K_{1} := \left\{ \ Qx(R) \ \ \mathcal{j} \ \ Q \in \left\{ \exist , \forall \right\} \ \wedge \ R \in F_{0} \ \right\}$ $=$ $\left\{ \exist , \forall \right\} \times V \times \left\{ \, ( \, \right\} \times F_{0} \times \left\{ \, ) \, \right\} \$ (megjegyzés: ha tartjuk azt a megállapodást, hogy atomi kvantált formula esetén a magot nem kell zárójelbe tenni, akkor egy kis módosításra szorul a definíció, a Z-vel egyenlő tényezők elhagyhatóak).
Ezután az atomi és kvantifikációs formulákat logikai jelekkel kötjük össze, hogy az elsőosztályú összetett formulákat is megkonstruáljuk. Így kapjuk a $O 1$ nulladosztályú halmazt:

$O_{1} := \left\{ P \oplus Q \in \bar{\Lambda} \ \mathcal{j} \ P,Q \in F_{0} \cup K_{1} \ \wedge \ \oplus \in L \right\}$

Az összes elsőosztályú formula halmaza $F_{1} := K_{1} \cup O_{1} \cup F_{0}$ .
... az eljárást ismételjük, azaz ...
Legyen i > 1. Ha már definiáltuk az halmazt – természetesen az K_i,O_i-vel együtt, akkor definiálható K_{i + 1},O_{i + 1}, és innen F_{i + 1} is.
- $K_{i+1} := \left\{ \ Qx(R) \ \mathcal{j} \ Q \in \left\{ \exist , \forall \right\} \ \wedge \ x \in V \ \wedge \ R \in F_{i} \ \right\}$ $=$ $\left\{ \exist , \forall \right\} \times V \times \left\{ \, ( \, \right\} \times F_{i} \times \left\{ \, ) \, \right\} \$ ;
- $O_{i+1} := \left\{ \ (P) \oplus (Q) \in \bar{\Lambda} \ \mathcal{j} \ P,Q \in F_{i} \cup K_{i} \ \wedge \ \oplus \in L \ \right\}$
- $F_{i+1} := K_{i+1} \cup O_{i+1} \cup F_{i}$ .
Ez folytatható a végtelenségig. Legyen az $\mathcal{L}$ nyelv formuláinak halmaza pedig $F[\mathcal{L}] := \bigcup_{i=0}^{\mathcal{1}} F_{i}$

Természetesen ehelyett a bonyolult, de hasznos és viszonylag szemléletes „alulról történő” felépítés helyett választhatjuk most is a „felülről történő”, a szintaktikai szabályoknak megfelelő szóhalmazok metszeteként való előállítást is, ahogy az a termeknél is lehetséges volt; és most is belátható, hogy a két konstrukció ugyanazt a formulahalmazt eredményezi.

A termek és formulák konstrukciójából következik az ún. egyértelmű formulaelemzés tétele.

[szerkesztés] Szemantika

[szerkesztés] Struktúra, -típus és modell

Bővebben: Matematikai struktúra

Egy $\Xi := \left( \mathcal{U} , \ \mathcal{T} , \ \mathcal{R} , \ \mathcal{M} , \ \mathcal{C} \ \right)$ ötelemű halmazrendszert matematikai struktúrának nevezünk, ahol

$\mathcal{U} = \left\{ u_{1} , u_{2} , ... , u_{i} , ... \right\}$ tetszőleges halmaz, az univerzum);
$\mathcal{T} \subseteq \mathcal{P} \left( \mathcal{U} \right)$ az $\mathcal{U}$ valamilyen partíciója, azaz az univerzumnak egy, lehetőleg véges $I$ indexhalmaz feletti $\mathcal{T} := \left\{ \ \mathcal{U} _{i} \ \mathcal{j} \ i \in I \ \right\}$ nemüres halmazokból álló, páronként diszjunkt, a tagokat egyesítve épp $\mathcal{U}$ -t kiadó halmazrendszere; a $\mathcal{T}$ rendszer elemeit, azaz $\mathcal{U}$ osztályait az univerzumelemek fajtáinak (ang. tribe, sort) nevezzük; * $\mathcal{R}$ efölött értelmezett valahány (véges) változós relációk ( $\rho \subseteq \mathcal{U} _{1} \times \mathcal{U} _{2} \times ... \mathcal{U} _{n}$ alakú halmazok) vagy predikátumok ( $\rho \in \mathcal{R}$ relációk karakterisztikus függvényeit, azaz az $χ ρ :$ $: \mathcal{U} _{1} \times \mathcal{U} _{2} \times ... \times \mathcal{U} _{ \alpha _{ \rho } } \mapsto \left\{ 0 , 1 \right\} ;$ $\ \forall x \in \mathcal{U} _{1} \times \mathcal{U} _{2} \times ... \mathcal{U} _{ \alpha _{ \rho } } : \left( \chi _{ \rho} (x) = 1 : \Leftrightarrow x \in \rho \right)$ előírással definiált függvényeket (0, 1 itt felfoghatóak logikai értékeknek)) halmaza; ahol $n \in \mathbb{N}$ csak a $ρ$ -tól függő természetes szám lehet; a $ρ$ reláció/predikátum aritása vagy változószáma; jele $α ρ$ ; informális szemléletben – a predikátumok a normális köznyelven vagy a matematika nyelvein tett eldönthető kijelentések, a relációk pedig épp ezek halmazelméleti modelljei. Matematikailag sincs köztük lényeges különbség, a logikában inkább a predikátumos kifejezésmódot használjuk (a halmazelméletben a relációsat).
$\mathcal{M}$ nem más, mint $\mathcal{U}$ feletti valahány változós és valamilyen fajtájú függvények egy halmaza, azaz $M$ minden eleme egy $f : U_{ t_{1} } \times U_{ t_{2} } \times ... \times U_{ t_{n} } \mapsto \mathcal{U} _{n+1}$ ahol az $n = \alpha _{f} \in \mathbb{N}$ szám a függvény vagy művelet aritás'a; azaz változóinak száma;
$\mathcal{C} \subseteq \mathcal{U}$ az $\mathcal{U}$ egy részhalmazam, mely bizonyos kitüntetett elemekből áll. Elemeit konstansoknak (vagy kitüntetett elemeknek) fogjuk nevezni.

Az előzőek szerint minden adott struktúrához egyértelműen létezik (a struktúra által meghatározottan) egy elemhármas, a struktúra aritási függvénye;
- $\alpha _{ \ \mathcal{C} } : = \left| \ \mathcal{C} \ \right|$ a konstansok száma;
A szignatúra ezen kívül a változók fajtáit is hozzárendeli a szimbólumokhoz, minden adott struktúrához egyértelműen létezik (a struktúra által meghatározottan) egy elemhármas, a struktúra szignatúrája;
- $\sigma _{ \ \mathcal{C} } : \mathcal{C} \mapsto \mathcal{T} ; \ \forall c \in \mathcal{C} : \sigma _{ \ \mathcal{C} } \left( c \right) = t : \Leftrightarrow c \in t \in \mathcal{T}$ ; tehát ha a $c$ konstans a $\mathcal{T} = \left( \mathcal{U} _{i} \right) _{ i \in I}$ halmazrendszer $t := \mathcal{U} _{i}$ tagjába esik, azaz c éppen t fajtájú, akkor mondjuk t szignatúrájúnak/fajtájúnak/típusúnak;

Egy struktúrát és egy elsőrendű nyelvet kompatibilisnek nevezük, ha szignatúrájuk „megegyezik”. Néa azt is szokás mondani, hogy modelljei egymásnak, ezt a kifejezést azonban mi más fogalomra tartjuk fenn.

[szerkesztés] Interpretáció

Röviden szólva, az interpretáció egy olyan leképezés(rendszer), mely egy nyelv egyes főbb elemeinek (a változókat kivéve szinte mindennek – konstansok, függvényjelek, relációjelek) egy adott struktúra megfelelő elemeit felelteti meg. Ha összevetjük ezt a szakaszt a bevezetéssel, rájöhetünk, hogy az elsőrendűség fogalma és az interpretáció fogalmának definíciója szoros kapcsolatban van. Többedrendű nyelvekre más lesz a definíció.

Legyen adott egy $\Lambda = \left( Sr , C, F , P , V , L , Z \right)$ ábécével rendelkező $\mathcal{B} = \left( \Lambda, \sigma , \Sigma , \right)$ nyelvbázis feletti $\mathcal{L} = \left( \ \Lambda , \ \sigma , \ \Sigma , \ T[\mathcal{L}] , \ F[\mathcal{L}] \ \right)$ elsőrendű nyelv. Ennek egy $\mathcal{U}$ univerzum feletti $\mathcal{I}$ interpretációja egy $\left( \mathcal{I}_{Sr} , \ \mathcal{I}_{C} , \ \mathcal{I}_{F} , \ \mathcal{I}_{R} \right)$ függvénynégyes; melynek tagjai a következő függvények:

$\mathcal{I} _{Sr} : Sr \mapsto \mathcal{P} \left( \mathcal{U} \right) ; \ \forall \pi \in Sr: \mathcal{I} _{Sr} \left( \pi \right) = \mathcal{U} _{ \pi } \subseteq \mathcal{U}$ ; e függvény tehát minden fajtajelhez hozzárendeli $\mathcal{U}$ egy részhalmazát. Feltesszük, hogy a $\left\{ \mathcal{U} _{\pi} \mathcal{j} \pi \in Sr \right\}$ halmazrendszer partíciója $\mathcal{U}$ -nak, azaz nemüres halmazokból álló páronként diszjunkt halmazrendszer, melynek uniója épp $\mathcal{U}$ ;
$\mathcal{I} _{C} : C \mapsto \mathcal{U} ; \ \forall c \in C : \mathcal{I} _{C} \left( c \right) = u \in \mathcal{U}$ minden konstansszimbólumhoz hozzárendel egy univerzumelemet; mégpedig $γ(c) = π$ fajtájú konstansszimbólumhoz egy $\mathcal{I} _{Sr} \left( \pi \right) = \mathcal{ U_{ \pi } }$ osztályú/fajtájú univerzumelemet;
$\mathcal{I} _{F} : F \mapsto \mathcal{M} ; \ \forall f \in F : \mathcal{I} _{Sr} \left( f \right) = \mu \in \mathcal{M} \subseteq \mathcal{U}$ minden függvényszimbólumhoz hozzárendel egy univerzum feletti műveletet; n-változóshoz n-változósat;
$\mathcal{I} _{P} : P \mapsto \mathcal{R} ; \ \forall p \in P : \mathcal{I} _{Sr} \left( p \right) = \rho \in \mathcal{R} \subseteq \mathcal{U}$ ; e függvény minden predikátumszimbólumhoz (relációjelhez) hozzárendel egy U feletti relációt (predikátumot), n-váltpzóshoz n-változósat;
a fajtákat mindegyik függvény megőrzi.

[szerkesztés] Kiértékelés

Röviden szólva, egy $\mathcal{I}$ interpretációbeli $\mathfrak{B} ^{ \mathcal{I} }$ kiértékelés azt jelenti, hogy minden konstansnak, termnek és formulának nemcsak egy konkrét struktúrabeli univerzumelemet, műveletet és predikátumot feleltetünk meg, hanem ezek igazságértékét is „eldöntjük”. Ezt úgy tesszük, hogy „rögzítjük” az egyetlen rögzítetlenül maradó szimbólumcsoport, a változók értékét is. Ezek után a formulák kiértékelése rekurzióval már automatikusan adódik, meghatározott.

[szerkesztés] Az elsőrendű nyelvek története

Bővebben: A logika története

Teljes értékűnek mondható elsőrendű logikai nyelv(ek)et először igazából Gottlob Frege konstruált (sőt az Aritmetika alaptörvényei c. munkájában meg is haladta az elsőrendű nyelvek elméletét), bár Giuseppe Peano is jelentős haladást ért el az elméletben. A logikai nyelvek elméletének továbbfejlesztői közt volt Bertrand Russell. További neves kutatók Alfred Tarski, Kurt Gödel, Gerhard Gentzen, Leon Henkin, Thoralf Skolem, és még sokan mások. Jelenleg az elsőrendű nyelvek elméletének alighanem az automatikus tételbizonyítások vizsgálata az egyik legintenzívebben fejlődő részterülete.

[szerkesztés] Lásd még

[szerkesztés] Források

[szerkesztés] Könyvek

Urbán János: Matematikai logika. Példatár. Műszaki Könyvkiadó, Bp., 1983. ISBN 963-10-4683.
Pásztorné Varga Katalin – Várterész Magda: A matematikai logika alkalmazásszemléletű tárgyalása. Panem, Bp., 2003. ISBN 963 545 364 7.
Papadimitriou C. H.: Számítási bonyolultság. Novadat Bt., Bp., 1999. ISBN 963 9056 20 0.
Ruzsa Imre: Logikai szintaxis és szemantika I.. Akadémiai Kiadó, Bp., 1988. ISBN 963 05 4720 1.
Csirmaz László: Matematikai logika. Jegyzet, Hajnal András előadásainak felhasználásával. ELTE Bp., 1994. ELTE 94024. (Postscript változat)
Fritz Reinhardt – Heinrich Soeder : SH Atlasz – Matematika. Springer-Verlag, Bp., 1995. ISBN 963 8455 91 8.

[szerkesztés] Külső hivatkozások

Kategóriák: Logika | Matematikai logika

See also ebooksgratis.com: no banners, no cookies, totally FREE.