„Elsőrendű nyelv” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Rendezés a gondolatjelek körül |
a Robot: Szomszédos írásjelek kurziválása |
||
1. sor:
Az '''elsőrendű logikai nyelv'''ek, rövidebb és gyakoribb megnevezésben ''elsőrendű nyelv''ek 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
Az „elsőrendű” kifejezés általában egy [[#Szemantika|szemantikai]], de [[#Szintaxis|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, ''fajtajel''ek, ''műveleti-'' / ''függvény-'' és ''relációjel''ek (vagy függvényváltozók és relációváltozók), ''konstansjel''ek – ezeken kívül '''mindegyik elsőrendű nyelv, ahogyan mindegyik logikai nyelv, tartalmaz legalább két ''logikai jel''et''' (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ójel]]eket).
* A szabályok
* 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 '''''[[#A nyelvbázis|bázis]]'''''ának nevezzük.
25. sor:
** 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 '''''modell'''''jé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|szintaxis]] részeként pontosan meg lehet adni [[#Szignatúra|(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ójel''ek vagy ''predikátumszimbólumok'' vagy ''predikátumváltozók,''
** 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
** 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 <math> L </math>-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élet]]et leíró [[#A halmazelmélet nyelve|elsőrendű nyelvben]] a ''konstansszimbólumok'' segítenek ezen). Gyakran előfordul pl., hogy úgy válassztjuk 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árom[[dimenzió]]s [[euklideszi geometria|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.
39. sor:
== Az elsőrendű [[nyelvbázis]] ==
Valamely <math> \Lambda </math> ábécé feletti '''elsőrendű nyelvbázis''' (teljes nevén ''többfajtájú elsőrendű logikai nyelvbázis)''
* <math> \Lambda = \left( Sr, C, F, P, V, L, Z \right) </math> különféle fajtájú szimbólumokból álló halmazrendszer, az '''''[[#Az ábécé|ábécé]]''''';
** Az Sr, C, F, P, elemei ún. '''''nemlogikai jel'''''ek, ezek nyelvről nyelvre változnak;
47. sor:
** <math> \Sigma </math> pedig valamilyen formában adott [[#A szintaktikai szabályok|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 [[halmaz]]a épp <math> \bigcup{\Lambda} </math>. Az ezen ábécé felett elvileg felírható szavakat az utóbbi [[unió (halmazelmélet)|unióhalmaz]] elemeiből képezett összes véges sorozattal azonosítjuk, vagyis a <math> \Lambda </math> ábécé feletti összes szó halmaza legyen <math> \bar{\Lambda} := \bigcup_{i=0}^{\mathcal{1}} \left( \bigcup{\Lambda} \right)^{i} </math>. A [[#Szintaxis|szintaxis]] azt adja meg, hogy ez utóbbi halmazból melyek azok a szavak, melyeket értelmesnek, ''jólképzett''nek
Egy formális nyelv felépítését lehetővé tévő elemek összességére, ami nálunk a <math> \left( \Lambda, \sigma, \Sigma \right) </math> 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észlet''nek nevezik (a jelkészletbe nem szokás beleérteni a szintaktikai szabályokat, csak az [[#Az ábécé|ábécét]] és a [[#Szignatúra|szignatúrát]] – így e fogalom sokkal egyszerűbb, de épp azért, mert a szintaxis egy része „elsikkad”).
54. sor:
<math> \left( Sr, C, F, P, V, L, Z \right) </math> halmazrendszer, ahol
* <math> Sr </math> a '''''fajtajel'''''ek
* <math> C </math> a '''''konstansjel'''''ek,
* <math> F </math> a '''''műveleti'''''- vagy '''''függvényjel'''''ek,
93. sor:
* 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
# '''A konstanjelek termek'''; mégpedig ha <math> c \in C </math> és c egy π fajtájú konstansjel, akkor egyben π fajtájú term is.
# '''Az individuumváltozók termek'''; mégpedig ha <math> v \in V </math> és v egy π fajtájú konstansjel, akkor egyben π fajtájú term is.
100. sor:
# Ha P n-változós predikátumszimbólum, és <math> t_{1}, t_{2}, ..., t_{n} </math> termek, akkor <math> P \left( t_{1}, t_{2}, ..., t_{n} \right) </math> (elsőrendű) formula. Az ilyen, csak termeket, predikátumszimbólumokat és kiegészítő jeleket tartalmazó formulákat '''atomi formulák'''nak nevezzük.
# Ha <math> P </math> formula, akkor <math> \lnot (P) </math> is formula ; ha P atomi formula, akkor ehelyett <math> \lnot P </math> is írható (atomi formula negációja esetén a zárójeleket nem kell kitenni).
# Ha <math> P, Q </math> két formula, és <math> \oplus \in L - \{ \lnot \} </math>, akkor <math> (P) \oplus (Q) </math> is formula. Tehát ekkor <math> (P) \wedge (Q) </math>, <math> (P) \vee (Q) </math>, <math> (P) \rightarrow (Q) </math> is formulák. Ha ''P,''
# Ha <math> x \in V </math> individuumváltozó, ''A'' tetszőleges formula, ''Q'' pedig kvantor – <math> Q \in \left\{ \forall , \exist \right\} </math> – akkor <math> Qx(A) </math> is formula. Az ilyen alakú formulákat '''''kvantált formulá'''''nak (kvantifikációnak) nevezzük. Tehát pl. ekkor <math> \forall x(P(x,y)) </math> is kvantált formula
# 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.
110. sor:
** Az individuumváltozót nem tartalmazó formulák az '''''alapformulák'''''
** Az individuumváltozót nem tartalmazó atomi formulák az '''''alapatom'''''ok.
* A kvantált formulákban az A formulát a formula '''''mag'''''jának nevezzük. Ha a Q kvantor a <math> \forall </math> ''[[univerzális kvantor]],''
* Azokat a formulákat, melyek nem tartalmaznak kvantort, logikusan '''''kvantormentes'''''nek nevezzük, míg a kvantort tartalmazókat '''''kvantoros''''' formulának. Vigyázzunk: minden kvantált formula kvantoros, de fordítva nem igaz! A <math> \forall x \left( P(x) \rightarrow Q(f(a) \right) </math> formula kvantált. A <math> Q(f(a), f(x)) \wedge \forall x \left( P(x) \rightarrow Q(f(a) \right) </math> formula viszont kvantoros, de nem egy kvantált formula.
* Speciális alakra hozott kvantoros formulák a [[prenex formula|prenex formulák]] és a [[Skolem-formulák]].
119. sor:
=== Definíció ===
Maga a <math> \mathcal{B} </math> [[#Az elsőrendű nyelvbázis|nyelvbázis]] feletti <math> \mathcal{L} </math> ''formális elsőrendű (és többfajtájú) matematikai logikai nyelv,''
Ha még precízebbek akarunk lenni, a nyelvet formálisan megadhatjuk mint egy <math> \mathcal{L} </math> <math> = </math> <math> \left( \Lambda , \ \sigma , \ \Sigma , \ W[ \mathcal{L} ] \right) </math> <math> = </math> <math> \left( \mathcal{B} , W[ \mathcal{L} ] \right) </math> halmazrendszert, ahol <math> \mathcal{B} </math> a [[#Az elsőrendű nyelvbázis|nyelvbázis]], <math> W[\mathcal{L}] </math> pedig a jólképzett szavak (formulák, termek) halmaza vagy ezek halmazainak rendszere.
125. sor:
<u> Megjegyzések </u>:
* Egyesek szerzők elsőrendű nyelven csak magát a szimbólumhalmazt azaz [[#Az ábécé|ábécét]], tehát csupán a <math> \Lambda = \left( Sr, C, F, P, V, L, Z \right) </math> 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 [[didaktika]]i 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
A [[#Szintaxis|szintaktikai szabályok]] alapján a nyelv kifejezései (azaz maga a nyelv), [[halmazelmélet]]ileg 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
=== A termek halmazának megkonstruálása a szintaxis alapján ===
170. sor:
Egy <math> \Xi := \left( \mathcal{U} , \ \mathcal{T} , \ \mathcal{R} , \ \mathcal{M} , \ \mathcal{C} \ \right) </math> ötelemű [[halmazrendszer]]t '''''[[Matematikai struktúra#Többfajtájú struktúrák|matematikai struktúrának]]''''' nevezünk, ahol
* <math> \mathcal{U} = \left\{ u_{1} , u_{2} , ... , u_{i} , ... \right\} </math> tetszőleges [[halmaz]], az '''''univerzum''''');
* <math> \mathcal{T} \subseteq \mathcal{P} \left( \mathcal{U} \right) </math> az <math> \mathcal{U} </math> valamilyen [[partíció (matematika)|partíciója]], azaz az univerzumnak egy, lehetőleg véges <math> I </math> [[halmazrendszer|indexhalmaz]] feletti <math> \mathcal{T} := \left\{ \ \mathcal{U} _{i} \ \mathcal{j} \ i \in I \ \right\} </math> nemüres halmazokból álló, páronként diszjunkt, a tagokat egyesítve épp <math> \mathcal{U} </math> -t kiadó [[halmazrendszer]]e; a <math> \mathcal{T} </math> rendszer elemeit, azaz <math> \mathcal{U} </math> osztályait az univerzumelemek '''''fajtá'''''inak ([[Angol nyelv|ang.]] ''tribe
* <math> \mathcal{M} </math> nem más, mint <math> \mathcal{U} </math> feletti valahány változós és valamilyen fajtájú függvények egy halmaza, azaz <math> M </math> minden eleme egy <math> f : U_{ t_{1} } \times U_{ t_{2} } \times ... \times U_{ t_{n} } \mapsto \mathcal{U} _{n+1} </math> ahol az <math> n = \alpha _{f} \in \mathbb{N} </math> szám a függvény vagy művelet ''aritás'''a; azaz változóinak száma;
* <math> \mathcal{C} \subseteq \mathcal{U} </math> az <math> \mathcal{U} </math> egy részhalmazam, mely bizonyos kitüntetett elemekből áll. Elemeit '''''konstans'''''oknak (vagy kitüntetett elemeknek) fogjuk nevezni.
234. sor:
=== Könyvek ===
* ''Urbán János:''
* ''Pásztorné Varga Katalin'' – ''Várterész Magda:''
* ''Papadimitriou C. H.:''
* ''Ruzsa Imre:''
* ''Csirmaz László:''
* ''Fritz Reinhardt'' – ''Heinrich Soeder'' : '''''SH Atlasz – Matematika'''''. Springer-Verlag, Bp., 1995. ISBN 963 8455 91 8.
| |||