Alapkifejezés

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

Alapkifejezésnek (angolul ground expression) a matematikai logikában egy logikai nyelv azon kifejezéseit (termjeit és formuláit) nevezzük, melyek nem tartalmaznak logikai változókat. A fogalom elsősorban az elsőrendű nyelvek elméletében fordul elő (a nulladrendű nyelvek formulái alapból nem tartalmaznak logikai változókat, mivel maguk a nulladrendű nyelvek sem tartalmaz ilyeneket).

Megjegyezzük, hogy az elnevezés félreérthető, mert „kifejezésen” sokak által elfogadott szóhasználat szerint csak a nyelv termeit szoktuk érteni, a formulákat nem; holott az alapkifejezésekbe a formulák egy részét (az ún. alapformulákat) is beleértjük.

Szemléletesen e fogalmat valahogy úgy képzelhetjük el, hogy az alapkifejezések írják le a „konkrét”, a „rögzített” objektumokat és a róluk szóló (igaz vagy hamis) állításokat a nyelvben, míg a többi, nem-alapkifejezés inkább valami általánosságot vagy határozatlanul eldönthető állítást ír le. De hangsúlyozzuk, ez csak egy nem precíz, köznapi, elmosódott interpretálása a fogalomnak. A pontosabb és formális definíciót lásd lentebb.

Az alapkifejezések osztályzása[szerkesztés | forrásszöveg szerkesztése]

Mivel egy nyelv kifejezései elsősorban a relációjelet nem tartalmazó termekre (függvénykifejezésekre) és a relációjeleket is tartalmazó formulákra (mondatokra) oszthatóak, ezért ez az alapja az alapkifejezések osztályzásának is. Tehát:

  1. a logikai változót és predikátumszimbólumot nem tartalmazó termek az alaptermek,
  2. míg a logikai változót szintén nem, de predikátumszimbólumot mégis tartalmazó formulák az alapformulák.

Példák[szerkesztés | forrásszöveg szerkesztése]

A konyhanyelv alapkifejezései[szerkesztés | forrásszöveg szerkesztése]

Legyenek egy menza egyik négyfős asztalának napi vendégei András, Bea, Cili, Dóri! Aznap Andrástól balra Bea ül, azzal szemben pedig Dóri. Tegyük fel, hogy aznap háromféle főétel közül választhatnak: Káposztás tészta, Párizsi szelet és Hortobágyi palacsinta!

Ha abban az elsőrendű nyelvben, melynek konstansjelei a tagok neveivel kezdődő betűk (A,B,C,D);

  • b(x) az a függvény, ami mindegyik taghoz hozzárendeli az aznapi bal oldali szomszédját;
  • j(x) pedig az, ami mindegyikhez a jobb oldali szomszédját
  • és ez az összes függvényszimbólum;

predikátumszimbólumai pedig a következők:

  • H(x) jelenti azt, hogy húsos palacsintát eszik aznap az x tag;
  • K(x) pedig azt, hogy káposztás tésztát;
  • P(x) azt, hogy párizsi módra készült hússzeletet;
  • és ez az összes predikátumszimbólum;

Akkor alaptermek például a következők:

  • A,B,C,D
  • b(A); ami mellesleg a jelenlegi ülésrendben (interpretációban) ugyanazt jelenti, mint B(ea) – (felhívjuk a figyelmet azonban arra, hogy a b(A) és B „konstansok” nem ugyanazok, csak ugyanazt jelentik!);
  • továbbá hasonlóan b(B), b(C), b(D)
  • hasonlóan alaptermek j(A), j(B), j(C), j(D)

Vigyázzunk arra, hogy ezzel még nem soroltuk fel az összes alaptermet, csak az egyszerű alaptermeket (melyek argumentumában nincs további függvényszimbólum). De ezeken kívül végtelen sok alapterm van még:

  • b(b(A)), b(b(b(A))), b(b(b(b(A)))), … stb.
  • ezen kívül például b(j(b(A))), j(b(b(b(b(A))))), …
  • Hasonlóan a legegyszerűbb, atomi alapformulák:
    • H(A) jelenti például, hogy aznap András bizony húsos palacsintát eszik;
    • H(B), H(C), H(D); K(A), K(B), K(C), K(D); P(A), P(B), P(C), P(D)

Ezen kívül azonban még végtelen sok alapformula van. Például:

  • a ¬H(C)∨(P(j(j(A)))) formula úgy interpretálható, hogy ha Cili nem húsos palacsintát eszik aznap, akkor András jobb oldali szomszédjának (aki aznap épp Cili) jobb oldali szomszédja (ez épp Dóri aznap) párizsi szeletet eszik. Ki tudja, talán mert aznap épp így állapodtak meg: az okokról az alapformula már nem beszél, csak a konkrét, aznapi tényeket írja le; helyesen vagy hamisan.

A természetes számok leíró nyelvének alapkifejezései[szerkesztés | forrásszöveg szerkesztése]

Például a természetes számokat leíró elsőrendű nyelvben, ha 0 jelöli a nulla konstanst, s(x) a rákövetkezés függvényét (amelyre s(x) = x+1), + az összeadás műveletét, ¤ a szorzásét, akkor

  • s(0), s(s(0)), s(s(s(0))) … stb. alaptermek;
  • 0+1, 0+1+1, … szintén alaptermek
  • viszont x+s(1) és s(x) termek bár, de nem alaptermek;
  • s(0)=1 és 0+0=0 alapformulák;
  • viszont s(z)=1 és ∀x: (s(x)+1=s(s(x))) nem alapformulák.

Az utolsó ∀x: (s(x)+1=s(s(x))) formula példájából is látható, hogy bár egy alapkifejezés mindig zárt, de fordítva ez nem igaz. A fenti formula is zárt (a benne előforduló logikai változót kvantor köti), mégsem alapkifejezés, mert tartalmaz logikai változót, még ha ez kötött is.

Definíció[szerkesztés | forrásszöveg szerkesztése]

A definíciót az ún. elsőrendű nyelvekre adjuk meg. Nulladrendű nyelvek minden kifejezése automatikusan alapkifejezés.

Elsőrendű nyelvekben[szerkesztés | forrásszöveg szerkesztése]

Legyen  \mathcal{L} egy elsőrendű nyelv, a  C konstansjelek,  V individuumváltozók,  F függvényjelek,  P relációjelek halmazaival mint jelkészlettel.

Alaptermek[szerkesztés | forrásszöveg szerkesztése]

Formularekurziós definíciót alkalmazva:

  1. C elemei alaptermek;
  2. Ha f∈F n-változós függvényjel és α1, α2 , …, αn alaptermek, akkor f(α2 , …, αn) is alapterm.
  3. Az összes alaptermek az előző két szabály véges sokszori alkalmazásával állnak elő.

Ezt kicsit kirészletezve halmazelméleti rekurzió alakjában:

  1.  C elemei alaptermek, legyen  C := T_0 ;
  2. Ha  f \in F n-változós függvényjel és  c_1, c_2 , \cdots, c_n \in C , akkor  f \left( c_1, c_2 , \cdots, c_n \right) is alapterm, legyen az így kapott alaptermek halmaza  T_1 . A  C \cup T_1 halmaz elemei az L nyelv egyszerű alaptermjei.
  3. Általában ha  f \in F n-változós függvényjel és  \alpha_1, \alpha_2 , \cdots, \alpha_n \in \bigcup_{j=0}^{i}T_i  (i∈ℕ+) , akkor  f \left( \alpha_1, \alpha_2 , \cdots, \alpha_n \right) is alapterm, legyen az így kapott alaptermek halmaza  T_i+1
  4. Az összes alaptermek pontosan a  \bigcup_{i=0}^{\infty} halmaz elemei.

Alapformulák[szerkesztés | forrásszöveg szerkesztése]

Formularekurziót alkalmazva definiáljuk az alapformula fogalmát:

  1. Ha p∈P n-változós függvényjel, és α1, α2 , \cdots, αn alaptermek, akkor p(α1, α2 , \cdots, αn) alapformula;
  2. Ha p és q alapformulák, akkor ¬(p), (p)∨(q), (p)∧(q), (p)→(q) is alapformulák
  3. Ha p alapformula és q úgy keletkezik belőle, hogy bizonyos zárójeleket elhagyunk vagy hozzáteszünk; de az így kapott zárójelezés is szabályos, és p és q ekvivalensek, akkor q is alapformula.
  4. Az összes alapformula a fenti három szabály véges sokszori alkalmazásával áll elő.