Alapkifejezés

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

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

A konyhanyelv alapkifejezései

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

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ó

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

Elsőrendű nyelvekben

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

Formularekurziós definíciót alkalmazva:

1. C elemei alaptermek;
2. Ha f∈F n-változós függvényjel és α₁, α₂ , …, α_n alaptermek, akkor f(α₂ , …, α_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. …
4. Á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$
5. Az összes alaptermek pontosan a $\bigcup _{i=0}^{\infty }$ halmaz elemei.

Alapformulák

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

1. Ha p∈P n-változós függvényjel, és α₁, α₂ , \cdots, α_n alaptermek, akkor p(α₁, α₂ , \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ő.