Ugrás a tartalomhoz

A matematikai logika alkalmazásszemléletű tárgyalása

Pásztorné Varga Katalin, Várterész Magda, Sági Gábor

Panem Kft.

Elsőrendű logikai nyelvek – szemantika

Elsőrendű logikai nyelvek – szemantika

Legyen [Vν] egy elsőrendű logikai nyelv. Hogy meghatározhassuk, mit jelentenek [Vν] termjei és formulái, meg kell adni, milyen individuumhalmazt futnak be a nyelv individuumváltozói, melyik individuumokat jelölik a konstansszimbólumok, milyen matematikai függvényeket (műveleteket) a függvényszimbólumok és mely logikai függvényeket (relációkat, predikátumokat) a predikátumszimbólumok. Ennek az információnak a rögzítését nevezzük az elsőrendű logikai nyelv egy interpretációjának.

5.2.1. DEFINÍCIÓ. [ V ν ] interpretációja egy =Srt,Pr,Fn,Cnst függvénynégyes, ahol

  1. az Srt:πUπ függvény megad minden egyes πSrt fajtához egy Uπ nemüres halmazt, a π fajtájú individuumok halmazát (a különböző fajtájú individuumok halmazainak uniója az interpretáció individuumtartománya vagy univerzuma),

  2. az Pr:PP függvény megad minden (π1,π2,,πk) alakú PPr predikátumszimbólumhoz egy P:Uπ1×Uπ2××Uπk{i,h} logikai függvényt (relációt),

  3. az Fn:ff függvény hozzárendel minden (π1,π2,,πk,π) alakú fFn függvényszimbólumhoz egy f:Uπ1×Uπ2××UπkUπ matematikai függvényt (műveletet),

  4. az Cnst:cc függvény pedig minden π fajtájú cCnst konstansszimbólumhoz az Uπ individuumtartománynak egy individuumát rendeli, azaz cUπ.

5.2.2. PÉLDA. Rögzítsük most az p1 nyelv egy interpretációját és jelölje ezt az interpretációt p1. Uπ1 legyen az {a,b,c} háromelemű, Uπ2 pedig legyen az {1,2} kételemű halmaz, továbbá a

P p 1 : { a , b , c } { i , h } Q p 1 : { a , b , c } × { 1 , 2 } { i , h } R p 1 : { 1 , 2 } × { 1 , 2 } { i , h } f p 1 : { a , b , c } × { 1 , 2 } { 1 , 2 }

logikai és matematikai függvények ebben az interpretációban legyenek az alábbi relációtáblákkal és függvénytáblával adottak:

P p 1

a

b

c

i

h

i

Q p 1

a

b

c

1

i

h

i

2

h

i

i

R p 1

1

2

1

h

i

2

i

i

f p 1

a

b

c

1

1

2

2

2

2

2

1

Jelölje a c konstansszimbólum a c individuumot. Ezzel megadtuk az p1 nyelv egy lehetséges interpretációját, az p1 interpretációt.

Miután az [Vν] nyelv logikán kívüli szimbólumainak jelentését rögzítettük egy interpretációval, rátérhetünk a nyelv kifejezései – ezen interpretációbeli – jelentésének megadására. Mivel a nyelv kifejezései általában szabad változókat is tartalmaznak, szükségünk lesz a változókiértékelés fogalmára.

5.2.3. DEFINÍCIÓ. Legyen az [Vν] nyelvnek egy interpretációja, az interpretáció univerzuma legyen U és jelölje V a nyelv változóinak a halmazát. Egy olyan κ:VU leképezést, ahol ha xπ fajtájú változó, akkor κ(x)Uπ, -beli változókiértékelésnek nevezünk.

5.2.4. DEFINÍCIÓ. t ( V ν ) szemantikája. Legyen az [Vν] nyelvnek egy interpretációja és κ egy -beli változókiértékelés. Az [Vν] nyelv egy π fajtájú t termjének értéke-ben a κ változókiértékelés mellett az alábbi – |t|,κ-val jelölt – Uπ-beli individuum:

  1. ha cCnstπ fajtájú konstansszimbólum, akkor |c|,κ az Uπ-beli c individuum,

  2. ha xπ fajtájú változó, akkor |x|,κ az Uπ-beli κ(x) individuum,

  3. ha t1,t2,,tk rendre π1,π2,,πk fajtájú termek és ezek értékei a κ változókiértékelés mellett -ben rendre az Uπ1-beli |t1|,κ, az Uπ2-beli |t2|,κ, … és az Uπk-beli |tk|,κ individuumok, akkor egy (π1,π2,,πk,π) alakú fFn függvényszimbólum esetén |f(t1,t2,,tk)|,κ az Uπ-beli f(|t1|,κ,|t2|,κ,,|tk|,κ) individuum.

Az [Vν] nyelv termjeinek értékét ez a (szerkezeti rekurzió elvén alapuló) definíció rögzített interpretációban rögzített κ változókiértékelés mellett megadja. Az érték egy – a term fajtájához tartozó univerzumbeli – individuum.

5.2.5. PÉLDA. Határozzuk meg most az p1 nyelv f(c,f(x,x˜)) termjének p1-beli értékét a következő változókiértékelés mellett: legyen κ(x)=b, κ(y)=a, és κ minden ezektől különböző π1 fajtájú változóhoz a c, minden π2 fajtájú változóhoz pedig az 1 individuumot rendelje.

| f ( c , f ( x , x ˜ ) ) | p 1 , κ = = f p 1 ( | c | p 1 , κ , | f ( x , x ˜ ) | p 1 , κ ) = = f p 1 ( | c | p 1 , κ , f p 1 ( | x | p 1 , κ , | x ˜ | p 1 , κ ) ) .

Mivel |c|p1,κ=cp1=c, |x|p1,κ=κ(x)=b és |x˜|p1,κ=κ(x˜)=1, így

f p 1 ( | c | p 1 , κ , f p 1 ( | x | p 1 , κ , | x ˜ | p 1 , κ ) ) = f p 1 ( c , f p 1 ( b , 1 ) ) ,

ami fp1(b,1)=2 miatt fp1(c,2), ez pedig éppen 1. Tehát

| f ( c , f ( x , x ˜ ) ) | p 1 , κ = 1 ,

vagyis az f(c,f(x,x˜)) term p1-beli értéke a κ változókiértékelés mellett 1.

Különböző változókiértékelések mellett viszont ugyanannak a termnek a term fajtájához tartozó univerzum különböző elemei lehetnek az értékei. Be lehet azonban bizonyítani, hogy különböző változókiértékelések mellett egy termnek különböző értékei csak akkor lehetnek, ha legalább egy, a termben előforduló változóhoz a változókiértékelések különböző individuumot rendelnek. Mivel a bizonyítást a szerkezeti indukció termekre vonatkozó elve alapján könnyű elvégezni, gyakorlásképpen ezt az olvasóra hagyjuk.

5.2.6. LEMMA. Az [Vν] nyelvnek legyen egy interpretációja, κ1 és κ2 pedig olyan változókiértékelések -ben, amelyek megegyeznek individuumváltozóknak egy S halmazán. Ha egy t termben csak S-beli változók fordulnak elő, akkor

| t | , κ 1 = | t | , κ 2 .

Ezek szerint egy term értéke rögzített interpretációban csak a benne előforduló individuumváltozók változókiértékelésétől függ, meghatározásához elegendő csak a kérdéses term változóihoz rendelt individuumokat ismerni, azaz a term egy változókiértékelését megadni. Tehát egy n individuumváltozót tartalmazó term interpretációbeli jelentése egy olyan n-változós matematikai függvény, amely az individuumváltozók fajtáinak megfelelő individuum n-esekhez a term fajtájának megfelelő individuumokat rendel. Ha viszont a term alapterm – nem fordul elő benne változó – értéke nyilván nem függ a változókiértékeléstől. Alaptermek esetén ezért |t|,κ helyett gyakran |t|-t írunk.

5.2.7. PÉLDA. Az p1 nyelv p1 interpretációjában az f(x,f(c,x˜)) term jelentését az alábbi függvénytábla adja meg:

κ ( x )

κ ( x ˜ )

| f ( x , f ( c , x ˜ ) ) | κ

a

1

2

a

2

1

b

1

2

b

2

2

c

1

1

c

2

2

Most meghatározzuk [Vν] formuláinak az interpretációbeli logikai jelentését. Ehhez szükségünk van a következő fogalomra.

5.2.8. DEFINÍCIÓ. Legyen x egy változó. A κ* változókiértékelés a κ változókiértékelés x-variánsa, ha κ*(y)=κ(y) minden x-től különböző y változó esetén.

5.2.9. DEFINÍCIÓ. f(Vν) SZEMANTIKÁJA. Legyen az [Vν] nyelvnek egy interpretációja és κ egy -beli változókiértékelés. Az [Vν] nyelv egy C formulájához -ben a κ változókiértékelés mellett az alábbi – |C|,κ-val jelölt – igazságértéket rendeljük:

  1. | P ( t 1 , t 2 , , t k ) | , κ { i ha P ( | t 1 | , κ , | t 2 | , κ , , | t k | , κ ) = i , h egyébként .

  2. | ¬ A | , κ legyen ¬|A|,κ,

  3. | A B | , κ legyen |A|,κ|B|,κ,

  4. | A B | , κ legyen |A|,κ|B|,κ,

  5. | A B | , κ legyen |A|,κ|B|,κ,

  6. | x A | , κ { i ha | A | , κ * = i κ minden κ * x variánsára , h egyébként .

  7. | x A | , κ { i ha | A | , κ * = i κ valamely κ * x variánsára , h egyébként .

5.2.10. MEGJEGYZÉS. Felhívjuk a figyelmet arra, hogy a definícióban a ,,bal oldalon” szereplő ¬, , és jelek az [Vν] nyelv ábécéjének szimbólumai, a ,,jobb oldalon” pedig ezek a jelek logikai műveletek az igazságértékek kételemű Boole-algebrájában.

Hasonlóan a termekhez, ez a (szerkezeti rekurzió elvén alapuló) definíció a nyelv minden formulájához rögzített interpretációban rögzített κ változókiértékelés mellett egy igazságértéket rendel.

5.2.11. PÉLDA. Határozzuk meg most az p1 nyelv Q(y,f(c,f(x,x˜))) atomi formulájának p1-beli értékét az 5.2.5. példabeli κ változókiértékelés mellett.

| Q ( y , f ( c , f ( x , x ˜ ) ) ) | p 1 , κ = Q p 1 ( | y | p 1 , κ , | f ( c , f ( x , x ˜ ) ) | p 1 , κ ) .

| y | p 1 , κ = κ ( y ) = a , az 5.2.5. példában pedig kiszámoltuk, hogy

| f ( c , f ( x , x ˜ ) ) | p 1 , κ = 1 .

Tehát

| Q ( y , f ( c , f ( x , x ˜ ) ) ) | p 1 , κ = Q p 1 ( a , 1 ) = i .

Ha viszont a Q(y,f(x,f(x,x˜))) atom p1-beli értékét akarjuk kiszámolni κ mellett, ehhez az |f(x,f(x,x˜))|p1,κ értékre van szükség, ami 2. Tehát

| Q ( y , f ( x , f ( x , x ˜ ) ) ) | p 1 , κ = Q p 1 ( a , 2 ) = h .

Továbbá a zQ(y,f(z,f(x,x˜))) formula p1-beli értéke a κ változókiértékelés mellett i, hiszen magára κ-ra (κ egyik lehetséges z-variánsa önmaga)

| Q ( y , f ( z , f ( x , x ˜ ) ) | p 1 , κ = i .

A zQ(y,f(z,f(x,x˜))) formula p1-beli értéke κ mellett viszont h, hiszen κ azon κ*z-variánsa mellett, melyre κ*(z)=b, az adódik, hogy

| Q ( y , f ( z , f ( x , x ˜ ) ) ) | p 1 , κ * = h .

Különböző változókiértékelések mellett ugyanannak a formulának az igazságértéke különböző lehet. Formulákra is be lehet bizonyítani, hogy különböző változókiértékelések mellett egy formulának különböző igazságértéke csak akkor lehet, ha legalább egy, a formulában előforduló szabad változóhoz a változókiértékelések különböző individuumot rendelnek. Mivel az állítást a szerkezeti indukció formulákra vonatkozó elve alapján egyszerű igazolni, ezt a bizonyítást is az olvasóra bízzuk.

5.2.12. LEMMA. Az [Vν] nyelvnek legyen egy interpretációja, κ1 és κ2 pedig olyan változókiértékelések -ben, amelyek megegyeznek individuumváltozóknak egy S halmazán. Ha az A formula olyan, hogy Par (A)S, akkor

| A | , κ 1 = | A | , κ 2 .

Ezek szerint egy formula igazságértéke is – rögzített interpretációban – csak a benne előforduló individuumváltozók változókiértékelésétől függ, meghatározásához elegendő csak a formula változóihoz rendelt individuumokat ismerni, azaz a formula egy változókiértékelését megadni. Egy n individuumváltozót tartalmazó formula interpretációbeli jelentése egy n-változós logikai függvény (reláció), amely az individuumváltozók fajtáinak megfelelő individuum n-esekhez igazságértékeket rendel. Ha a formula zárt – nem fordul elő benne szabad változó – igazságértéke nyilván nem függ a változókiértékeléstől. Ebben az esetben ezért |C|,κ helyett gyakran most is |C|-t írunk.

5.2.13. PÉLDA. Az p1 nyelv p1 interpretációjában az y˜¬R(y˜,f(x,f(c,x˜)) formula jelentését az alábbi relációtábla írja le:

κ ( x )

κ ( x ˜ )

| y ˜ ¬ R ( y ˜ , f ( x , f ( c , x ˜ ) ) | κ

a

1

h

a

2

i

b

1

h

b

2

h

c

1

i

c

2

h

5.2.14. TÉTEL. Rögzítsük az [Vν] nyelv egy interpretációját. Legyenek a nyelvben s és t tetszőleges termek, x a t-vel megegyező fajtájú változó, κ-ben egy tetszőleges változókiértékelés, és

κ ( y ) { κ ( y ) h a y x , | t | , κ h a y = x .

Ekkor

| s ( x t ) | , κ = | s | , κ .

BIZONYÍTÁS. Rögzítsük az [Vν] nyelv egy interpretációját. Legyen t tetszőleges term, x egy a t-vel megegyező fajtájú változó és κ(x) legyen épp |t|,κ, máshol pedig κ és κ ne különbözzenek. Nevezzük a bizonyítás során [Vν] egy s termjét jónak, ha

| s ( x t ) | , κ = | s | , κ .

A szerkezeti indukció elve segítségével igazolni fogjuk, hogy a nyelv minden termje jó.

(alaplépés:) Ha s konstansszimbólum vagy egy yx változó, akkor s-t az (xt) termhelyettesítés változatlanul hagyja. Mivel pedig x nem fordul elő s-ben, az 5.2.6. lemma miatt s jó. Ha pedig s éppen az x változó, |x(xt)|,κ=|t|,κ és |x|,κ=κ(x)=|t|,κ, tehát x is jó.

(indukciós lépés:) Most vizsgáljunk egy tetszőleges f(s1,s2,,sk) termet. Tegyük fel, hogy az s1,s2,,sk termek jók, azaz

| s j ( x t ) | , κ = | s j | , κ

minden j=1,2,,k-ra. Ekkor egyrészt a termhelyettesítés végrehajtásának definíciója miatt

| f ( s 1 , s 2 , , s k ) ( x t ) | , κ = | f ( s 1 ( x t ) , s 2 ( x t ) , , s k ( x t ) ) | , κ ,

ami az 5.2.4. definíció miatt

f ( | s 1 ( x t ) | , κ , | s 2 ( x t ) | , κ , , | s k ( x t ) | , κ ) .

Mivel az s1,s2,,sk termek jók, ezért ehelyett írhatjuk, hogy

f ( | s 1 | , κ , | s 2 | , κ , , | s k | , κ ) ,

ami pedig újból az 5.2.4. definíció miatt |f(s1,s2,,sk)|,κ. Ezek szerint az f(s1,s2,,sk) term is jó.

Az alaplépésben és az indukciós lépésben megfogalmazott felTÉTELek teljesülnek, tehát a szerkezeti indukció elve szerint minden [Vν]-beli term jó.

5.2.15. TÉTEL. Rögzítsük az [Vν] nyelv egy interpretációját. Legyen A egy formulája, t pedig egy termje a nyelvnek és x egy a t-vel megegyező fajtájú változó. Legyen κ-ben egy tetszőleges változókiértékelés, és

κ ( y ) { κ ( y ) h a y x , | t | , κ h a y = x .

Ekkor

| [ A ( x t ) ] | , κ = | A | , κ .

Bizonyítás. Rögzítsük az [Vν] nyelv egy interpretációját és egy κ változókiértékelését tetszőlegesen. Nevezzük a bizonyítás során az A formulát jónak, ha

| [ A ( x t ) ] | , κ = | A | , κ

fennáll minden olyan κ változókiértékelésre, melyre κ(x)=|t|,κ. A szerkezeti indukció elve segítségével igazolni fogjuk, hogy minden [Vν]-beli formula jó.

(alaplépés:) Legyen P(s1,s2,,sk) atomi formula. Ekkor egyrészt a termhelyettesítés végrehajtásának definíciója miatt

| P ( s 1 , s 2 , , s k ) ( x t ) | , κ = | P ( s 1 ( x t ) , s 2 ( x t ) , , s k ( x t ) ) | , κ ,

ami az 5.2.9. definíció miatt

P ( | s 1 ( x t ) | , κ , | s 2 ( x t ) | , κ , , | s k ( x t ) | , κ ) .

Az 5.2.14. tétel szerint viszont minden j=1,2,,k-ra

| s j ( x | | t ) | , κ = | s j | , κ

teljesül, tehát

| P ( s 1 , s 2 , , s k ) ( x t ) | , κ = P ( | s 1 | , κ , | s 2 | , κ , , | s k | , κ ) ,

ez pedig éppen |P(s1,s2,,sk)|,κ. Így az atomi formulák jók.

(indukciós lépések:) A negációs, konjunkciós, diszjunkciós és implikációs formulák esetén a bizonyítást az olvasóra bízzuk.

Most vizsgáljunk egy kvantált formulát: QzA-t. Ha z=x, akkor

[ ( Q x A ) ( x t ) ] = Q x A ,

mivel pedig x nem fordul elő szabadon QxA-ban, az 5.2.12. lemma miatt QxA jó. Ha pedig zx,

[ ( Q z A ) ( x t ) ] = Q u [ A ( z u ) ( x t ) ] ,

ahol u egy z-vel azonos fajtájú, x-től különböző olyan változó, amely nem fordul elő sem t-ben, sem A-ban. A |Qu[A(zu)(xt)]|,κ igazságérték meghatározásához κu-variánsai mellett kell az [A(zu)(xt)] formula igazságértékét kiszámolni. Legyen κ* a κ változókiértékelés u-variánsa. Mivel uPar (t), így |t|,κ*=|t|,κ. Továbbá az indukciós feltevésünk szerint A jó, és mivel A(zu) vele azonos szerkezetű, így az indukciós feltevésünk szerint A(zu) is jó, ezért

| [ A ( z u ) ( x t ) ] | , κ * = | A ( z u ) | , κ * ,

ahol

κ * ( y ) { κ * ( y ) ha y x , | t | , κ ha y = x .

Tehát minden κ* esetén κ*κ valamely u-variánsa, továbbá κ összes u-variánsa előáll κ valamely κ*u-variánsából a fenti módon származtatva. Így az |A(zu)|,κ* igazságértékek meghatározzák a |Qu(A(zu))|,κ' igazságértéket. De az

| [ A ( z u ) ( x t ) ] | , κ * = | A ( z u ) | , κ * ' ,

egyenlőség miatt

| Q u [ A ( z u ) ( x t ) ] | , κ = | Q u ( A ( z u ) ) | , κ .

Mivel pedig Par (Qu(A(zu)))=Par (QzA), az 5.2.12. lemma miatt

| Q u ( A ( z u ) ) | , κ = | Q z A | , κ ,

ami azt jelenti, hogy

| [ ( Q z A ) ( x t ) ] | , κ = | Q z A | , κ ,

tehát QzA is jó.

Az alaplépésben és az indukciós lépésekben megfogalmazott feltételek teljesülnek, tehát a szerkezeti indukció elve szerint minden [Vν]-beli formula jó.

Vizsgáljuk most meg még azt, hogyan függ egy interpretációban a formula egy változókiértékelése mellett a formula igazságértéke prímkomponensei igazságértékeitől. Legyenek az A formula prímkomponensei A1,A2,,An. Mivel A a prímkomponenseiből csupán a logikai összekötőjelek segítségével épül fel, ha ismernénk az A1,A2,,An formulák igazságértékét az adott interpretációban és változókiértékelés mellett, a formula igazságértékét az 5.2.9. definíció szerint már véges sok lépésben ki tudnánk számolni. Vegyük észre, hogy az 5.2.9. definícióban egy interpretációban és változókiértékelés mellett egy negációs, egy konjunkciós, egy diszjunkciós, illetve egy implikációs formulához igazságértéket ugyanúgy rendelünk a közvetlen részformulái igazságértékének függvényében, mint ahogy azt az ítéletlogikai formulák Boole-értékelésénél tettük. Tehát ha a különböző prímkomponenseket gondolatban különböző ítéletváltozóknak tekintenénk, az így kapott ítéletlogikai formulához megadhatnánk az igazságtáblát. Az elsőrendű formulához így megkonstruált táblázatot Quine-féle táblázatnak hívjuk. Ebben a táblázatban a sorokban szereplő igazságértékekről azonban nem tudhatjuk, hogy van-e egyáltalán olyan interpretáció és az interpretációban olyan változókiértékelés, ami mellett a prímkomponensek igazságértékei rendre ezek lennének. Az viszont nyilvánvaló, hogy minden interpretáció és minden változókiértékelés esetén a prímkomponensek igazságértékei a Quine-táblázat valamelyik sorában a prímkomponensekhez tartozó oszlopban rendre megtalálhatók.

5.2.16. PÉLDA. A ¬x¬P(x)xP(x) formula prímkomponensei x¬P(x) és xP(x). A formula Quine-féle táblázata a következő:

x ¬ P ( x )

x P ( x )

¬ x ¬ P ( x ) x P ( x )

i

i

i

i

h

i

h

i

i

h

h

h

A továbbiakban foglalkozzunk az egyfajtájú nyelvekkel. Legyen tehát az [Vν] nyelvben az Srt egyelemű halmaz. [Vν] interpretációja egy -vel jelölt olyan Srt,Pr,Fn,Cnst függvénynégyes, ahol

  1. az Srt:πU függvény megad az egyetlen πSrt fajtához egy U nemüres halmazt, az interpretáció univerzumát,

  2. az Pr:PP függvény megad minden (π,π,,π) alakú – k aritású – PPr predikátumszimbólumhoz egy P:Uk{i,h} relációt,

  3. az Fn:ff függvény hozzárendel minden (π,π,,π,π) alakú – k aritású – fFn függvényszimbólumhoz egy f:UkU műveletet,

  4. az Cnst:cc függvény pedig minden cCnst konstansszimbólumhoz az U univerzum egy individuumát rendeli.

5.2.17. PÉLDA. Az p2 nyelvet az 5.1.38. példában adtuk meg. A nyelv egyetlen fajtát tartalmazott. Megadjuk most az p2 nyelv egy lehetséges interpretációját. Jelöljük ezt az interpretációt p2-vel. Legyen a nyelv univerzuma az {a,b,c} halmaz. Legyenek a Pp2 és a Qp2 relációk relációtáblával adottak:

P p 2

a

b

c

i

i

h

Q p 2

a

b

c

a

i

h

i

b

h

i

i

c

h

h

h

Az Rp2 reláció pedig a következő:

R p 2 ( x , y , z ) { i ha y = a és x és z megegyeznek , h egyébként .

Az fp2 és a gp2 műveletek művelettáblái:

f p 2

a

b

c

i

i

h

g p 2

a

b

c

a

a

a

a

b

a

b

b

c

a

b

c

A hp2 művelet pedig a következő:

h p 2 ( x , y , z ) { a ha x , y és z közül legalább egy a , b ha x , y és z is b , c egyébként .

Ezzel megadtuk az p2 interpretációját az p2 nyelvnek.

Vizsgáljuk most meg néhány p2 nyelvbeli formula p2-beli jelentését.

  1. Tekintsük először a x(P(x)Q(x,x)) zárt formulát. Zárt formula igazságértéke nem függ a változókiértékeléstől (tetszőleges κ változókiértékelés mellett ugyanaz). A formulánk igazságértékének megállapításához meg kell határozni tehát egy tetszőlegesen rögzített κ összes lehetséges x-variánsa mellett a P(x)Q(x,x) formula p2-beli igazságértékét. κ* jelölje κ egy-egy lehetséges x-variánsát. Az 5.2.12. lemma miatt elég κ* értékét P(x)Q(x,x) paraméterénél ismerni. A következő táblázat felsorolja a lehetséges különböző eseteket:

κ * ( x )

| P ( x ) | κ *

| Q ( x , x ) | κ *

| P ( x ) Q ( x , x ) | κ *

a

i

i

i

b

i

i

i

c

h

h

i

Tehát κ összes lehetséges x-variánsa mellett P(x)Q(x,x)) igazságértéke i, így a x(P(x)Q(x,x)) formula igazságértéke p2-ben i.

  1. Vizsgáljuk most a ¬P(x)R(x,y,x) formulát. A formula paraméteres, paraméterei x és y. p2-ben egy-egy rögzített változókiértékelés mellett igazságértékét meghatározhatjuk. Ehhez elegendő a változókiértékelést a paramétereken ismerni.

κ ( x )

κ ( y )

| P ( x ) | κ

| ¬ P ( x ) | κ

| R ( x , y , x ) | κ

| ¬ P ( x ) R ( x , y , x ) | κ

a

a

i

h

i

h

a

b

i

h

h

h

a

c

i

h

h

h

b

a

i

h

i

h

b

b

i

h

h

h

b

c

i

h

h

h

c

a

h

i

i

i

c

b

h

i

h

h

c

c

h

i

h

h

Ez egy {a,b,c}2{i,h} reláció táblája, ez a reláció a ¬P(x)R(x,y,x) formula p2 interpretációbeli jelentése.

  1. Nézzük meg azt, hogy mit jelent a y(¬P(x)R(x,y,x)) formula. Ez a formula is paraméteres, paramétere x. Most is minden κ változókiértékelés mellett meg kell határozni a formula igazságértékét. A változókiértékeléseket megint elegendő csak x-re ismerni. De mivel a formulánk kvantált, minden κ esetén vizsgálni kell az y-variánsai mellett a kvantor hatáskörébe eső formula igazságértékeit is. Az előző táblázat első három sorában viszont épp olyan változókiértékelések szerepelnek, melyre κ(x)=a, és κ(y)=a, κ(y)=b, κ(y)=c rendre éppen a κ(x)=a lehetséges y-variánsai. A következő három sorban κ(x)=b lehetséges y-variánsai, majd κ(x)=c lehetséges y-variánsai találhatók. Így a fenti táblázatból a kvantált formulánk igazságértékeit is kiolvashatjuk paraméterei tetszőleges kiértékelése mellett. A leolvasás eredményeképpen a következő táblázatot kapjuk:

κ ( x )

| y ( ¬ P ( x ) R ( x , y , x ) ) | κ

a

h

b

h

c

i

Ez egy {a,b,c}{i,h} reláció táblája, ez a reláció a y(¬P(x)R(x,y,x)) formula p2 interpretációbeli jelentése.

Feladatok

5.2.1. FELADAT. Adjuk meg egy lehetséges interpretációját az 5.1.38. példában megadott p2 elsőrendű logikai nyelvnek. Mit jelentenek ebben az interpretációban a nyelv következő kifejezései?

  1. f ( g ( x , y ) )

  2. Q ( f ( x ) , g ( y , x ) )

  3. x Q ( x , z )

5.2.2. FELADAT. Legyen a {π},{P},{f1,f2},{c1,c2} nyelv szignatúrája:

ν 1

P

( π , π )

ν 2

f 1

( π , π , π )

f 2

( π , π , π )

ν 3

c 1

( π )

c 2

( π )

Legyenek x,y,z, a nyelv individuumváltozói. Interpretáljuk a nyelvet a következőképpen:

  1. univerzum: N0

  2. P : két természetes szám egyenlőségét kifejező reláció,

  3. f 1 : két természetes szám összeadása

f 2 : két természetes szám szorzása

  1. c 1 a nulla (0) természetes szám

c 2 az egy (1) természetes szám

Mit jelentenek ebben az interpretációban az alábbi kifejezések:

  1. f 1 ( c 2 , f 1 ( c 2 , c 2 ) )

  2. x P ( f 2 ( x , x ) , f 1 ( x , x ) )

  3. x P ( f 1 ( x , c 1 ) , x )

  4. x y P ( f 2 ( x , f 1 ( y , c 2 ) ) , f 1 ( f 2 ( x , y ) , x ) )

5.2.3. FELADAT. Legyen a {π1,π2},{P1,P2},{f1,f2,f3,f4},{c1,c2} nyelv szignatúrája

ν 1

P 1

( π 1 , π 1 )

P 2

( π 2 , π 2 )

ν 2

f 1 és f2

( π 1 , π 1 , π 1 )

f 3

( π 1 , π 2 , π 2 )

f 4

( π 2 , π 2 , π 2 )

ν 3

c 1

( π 1 )

c 2

( π 2 )

Legyenek x,y,z,π1 fajtájú és x_,y_,z_, pedig π2 fajtájú változók.

  1. Igazoljuk, hogy lehet ezt az elsőrendű logikai nyelvet úgy is interpretálni, hogy az interpretáció eredménye épp az alábbi struktúra:

V 3 ; { skalár , vektor } ; { = , } ; { + , × , + _ , × _ } ; { 0, 0 _ }

3 -dimenziós valós vektortér, ahol a skalárváltozók értékei valós számok, a vektorváltozók értékei 3-dimenziós vektorok és

=

két skalár egyenlősége,

két vektor egyenlősége,

+

két skalár összeadása,

×

két skalár szorzása,

+ _

két vektor összeadása,

× _

vektor szorzása skalárral.

0

a nulla valós szám,

0 _

a nullvektor,

  1. Mit jelentenek ebben az interpretációban az alábbi kifejezések:

    • f 3 ( c 1 , x _ )

    • x _ P 2 ( f 3 ( c 1 , x _ ) , c 2 )

    • x _ y _ P 2 ( f 4 ( x _ , y _ ) , c 2 )

    • x _ y _ x y ( P 2 ( f 4 ( f 3 ( x , x _ ) , f 3 ( y , y _ ) ) , c 2 ) P 2 ( x _ , c 2 ) P 2 ( y _ , c 2 ) )

  2. Adjunk meg olyan x_,y_ és z_ paramétereket tartalmazó formulát, melynek jelentése az interpretációban az ,,x_,y_, és z_ lineárisan független vektorok” reláció.