Chapter 3. Helyettesítések

3.1. Változók helyettesítése termekkel

Definíció Egy olyan függvényt, amely az elsőrendű nyelv véges sok változóján van értelmezve, és minden változóhoz termet rendel, termhelyettesítésnek nevezünk. Üres a termhelyettesítés, ha az értelmezési tartománya üres (jele:

).

Ha a

termhelyettesítés értelmezési tartománya

és

minden

-ra

,

-t megadhatjuk a

Equation 3.. 


táblázattal vagy a

felsorolással.

jelölje azt a termhelyettesítést, melyre

és minden

esetén

. Vezessük be továbbá a

jelölést a

kifejezés szerkezetétől és a

termhelyettesítéstől függő logikai kifejezésre:

  1. ha

    , akkor

    ,

  2. ha

    változó, akkor

    ,

  3. ,

  4. ,

  5. ,

  6. ,

  7. .

Vegyük észre, hogy az értékelő helyettesítések is termhelyettesítések, és ha

a

kifejezés értékelése, a

kifejezés éppen a

-beli paraméterek szabad előfordulásainak a

-val hozzájuk rendelt konstansszimbólumokkal való helyettesítésnek eredményeképpen kapott értékelt kifejezés.

Ugyanakkor nem minden

kifejezés és

termhelyettesítés esetén lesz alkalmas

a logika céljai számára. Hogy csak ezekkel a

kifejezésekkel foglalkozhassunk, vezessünk be néhány fogalmat. A

termhelyettesítés megengedett a

kifejezés számára, ha minden

esetén

minden

-beli szabad előfordulása kívül esik a

term valamennyi változóját megnevező kvantor hatáskörén.

Definíció

megengedettsége

számára

szerkezete szerint:

  1. Termek és atomi formulák számára minden termhelyettesítés megengedett.

  2. számára egy termhelyettesítés megengedett, ha megengedett

    számára.

  3. számára egy termhelyettesítés megengedett, ha megengedett

    és

    számára is.

  4. számára egy

    termhelyettesítés megengedett, ha

    1. egyetlen

      változó esetén sem fordul elő

      a

      termben,

    2. pedig megengedett

      számára.

Példa A

formula számára az

Equation 3.. 


termhelyettesítés megengedett, az

Equation 3.. 


termhelyettesítés pedig nem megengedett, mert a helyettesítendő szabad előfordulású

az

-et kötő

hatáskörében van, és a helyére beírandó

termben is előfordul az

változó.

Legyen

egy kifejezés és

egy termhelyettesítés. Konstruáljunk meg egy

-val kongruens olyan

formulát, amely számára

megengedett. Ekkor a

kifejezés a

termhelyettesítés

-ban való szabályos végrehajtásának eredménye. Jelölése:

.

Definíció

meghatározása

szerkezete szerint:

  1. Ha

    term vagy atomi formula, akkor

    .

    1. Ha egyetlen

      változó esetén sem fordul elő a

      termben

      , akkor

      .

    2. Ha van olyan

      változó, hogy

      paraméter

      -ben, akkor válasszunk egy új változót – például

      -t –, mely nem fordul elő sem

      -ban, sem

      termjeiben, és

      Equation 3.. 


Példa A

formulában az

Equation 3.. 


termhelyettesítés szabályos végrehajtásának eredménye a

Equation 3.. 


formula.

Definíció Legyenek

Equation 3.. 


egy nyelv termhelyettesítései.

és

kompozícióján a

Equation 3.. 


termhelyettesítést értjük, ahol

Equation 3.. 


Példa Legyenek

Equation 3.. 


termhelyettesítések. Ekkor

Equation 3.. 


és

Equation 3.. 


A példa mutatja, hogy a kompozíció művelete egy nyelv termhelyettesítéseinek halmazán nem kommutatív.

Tétel Egy elsőrendű logikai nyelv tetszőleges

,

és

termhelyettesítései esetén

Table 3.1. 
(1)

(a kompozíció asszociatív)
(2)

(

neutrális elem)

Azaz a kompozíció műveletével a termhelyettesítések halmaza neutrális elemmel rendelkező félcsoport.

Lemma Legyenek

és

egy nyelv termhelyettesítései. Ekkor tetszőleges

logikai kifejezés esetén

Equation 3.. 


Definíció Legyenek

és

termhelyettesítések. Az

helyettesítés általánosabb a

-nál, ha van olyan

termhelyettesítés, hogy

.

Példa Az

Equation 3.. 


helyettesítések esetén

általánosabb a

helyettesítésnél, mert

, ahol

Equation 3..