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.

A matematikai logika leíró nyelve

A matematikai logika leíró nyelve

A matematikai logika leíró nyelvének ábécéjében a ,,logikán kívüli” rész egy olyan szimbólumhalmaz, amelynek elemeivel a matematikai struktúrák minden logikán kívüli komponense szimbolizálható. Ez a szimbólumhalmaz megadható Srt,Pr,Fn,Cnst alakban, ahol

  • az Srt halmaz elemei fajtákat szimbolizálnak,

  • P r a predikátumszimbólumok,

  • F n a függvényszimbólumok és

  • C n s t a konstansszimbólumok halmaza.

Rendeljen

  • ν 1 minden PPr-hez egy (π1,π2,,πi),

  • ν 2 minden fFn-hez egy (π1,π2,,πi,π),

  • ν 3 minden cCnst-hez egy (π)

fajtákból álló sorozatot. A (ν1,ν2,ν3) hármas a logika leíró nyelvének szignatúrája. A (ν1,ν2,ν3) szignatúrájú Srt,Pr,Fn,Cnst halmaznégyest Vν-vel fogjuk jelölni.

A matematikai logika leíró nyelve ábécéjének ,,logikai része” a kiválasztott logikai összekötőkből, a kvantorokból és az individuumváltozókból áll. Ezt az elsőrendű – Vν-től függő – logikai nyelvet jelöljük [Vν]-vel.

Az [Vν] elsőrendű logikai nyelv modellje vagy interpretációja egy általános matematikai struktúra, ha a szignatúrájuk megegyezik. Ilyenkor a struktúra megfelel a logikai nyelvnek. Főleg olyan logikai nyelvekkel foglalkozunk, amelyeknek egyfajtájú struktúrák felelnek meg. Tehát az ábécé Pr,Fn,Cnst, vagy ha a konstansokat nullváltozós műveletként kezeljük, akkor Pr,Fn. Ekkor az ábécét megadhatjuk úgy is, hogy felsoroljuk a predikátum-, a függvény- és a konstansszimbólumokat: P1,,Pi;f1,,fj;c1,,ck. Majd sorrendhelyesen felsoroljuk a predikátum- és a függvényszimbólumok aritásait, és megadjuk a konstansszimbólumok számát: (ρ1,,ρi;μ1,,μj;k).

Table 3.4. Logikán kívüli rész a struktúrák és leíró nyelvük ábécéjében

struktúra

a logika leíró nyelve

jelölés

univerzumelemek

individuumváltozók

x , y , , x i ,

alaprelációk aritással

predikátumszimbólumok aritással

P , Q , , P i ,

alapműveletek aritással

függvényszimbólumok aritással

f , g , , f i ,

konstansok

konstansszimbólumok

c , , c i ,


Megjegyezzük, hogy ha egy elsőrendű logikai nyelvben az egyenlőség (=) predikátumszimbólum is szerepel, szokás a nyelvet egyenlőségjeles elsőrendű nyelvnek is nevezni.

A szemantika a nyelv ábécéjének modellezését – interpretációját – jelenti. Így minden logikán kívüli jel az interpretáló struktúra megfelelő művelete, relációja vagy konstansa jelölésének tekinthető. Egy [Vν] nyelvi kifejezés így struktúrabeli kifejezéssé válik, ahol az értelmezés már ismert.

3.3.1. PÉLDA. Legyen P;f1,f2,f3;c egy elsőrendű matematikai logikai nyelv a (2;1,2,2;1) szignatúrával. Ekkor az N0;=;s,+,×;0(2;1,2,2;1) szignatúrájú matematikai struktúra (elemi aritmetika) modellje a nyelvnek.

-kifejezés

a kifejezés interpretáltja

f 2 ( f 1 ( c ) , x )

( s ( 0 ) + x )

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

( s ( 0 ) + x ) = ( s ( 0 ) × x )

Az elsőrendű nyelvek kifejezőerejét növelendő, első lépésben olyan állítások megfogalmazásának lehetővé tétele a cél, amelyek egy adott univerzum összes relációinak halmazáról állítanak valamit. Ehhez első közelítésben bevezetik az aritásos predikátumváltozó és a függvényváltozó fogalmat. Mivel egy n-változós reláció az alaphalmazának egy részhalmazával azonosítható, egy (n1)-változós művelet pedig az értelmezési tartomány és az értékkészlet direktszorzatának egy részhalmazával, elegendő bevezetni az aritásos halmazváltozó fogalmát. Jelben: Xn,Yn,Xin,.

Egyfajtájú nyelvek esetén az interpretáló struktúra univerzuma homogén. Ezért e halmazváltozók értelmezési tartománya itt P(Un), többfajtájú esetben az interpretáló struktúrában a megfelelő direktszorzat hatványhalmaza (lásd 3.5. táblázat). E változók kvantálásával írhatók le a kívánt állítások. Az így kapott nyelvet másodrendű nyelvnek nevezzük. A további magasabbrendű logikai nyelvek bevezetése hasonló módon valósítható meg [56]. Másodrendű logikai nyelvre van szükség néhány olyan fogalom, mint például az egyenlőség és a teljes indukció formalizálásánál.

Table 3.5. A formalizált nyelv ábécéje és jellemzőik

formalizált nyelv ábécéje

jelölés

minősítés

nyelv rendje

individuumváltozók

x , y , , x i ,

logikai

0,1,2

függvényszimbólumok aritással

f , g , , f i ,

logikán kívüli

0,1,2

predikátumszimbólumok aritással

P , Q , , P i ,

logikán kívüli

0,1,2

egyenlőség predikátumszimbólum

=

logikai

0,1,2

logikai összekötők

¬ , , ,

logikai

0,1,2

kvantorok

,

logikai

1,2

halmazváltozók

X n , Y n ,

logikai

2


Legyenek a és b tetszőleges individuumnevek és X egy egyváltozós predikátumváltozó (X egy adott halmazon definiálható egyváltozós relációk halmazát futja be). Azt, hogy a azonos b-vel a következő másodrendű formulával írhatjuk le:

a = b X ( X ( a ) X ( b ) ) .

A teljes indukció formalizálása az elemi aritmetika másodrendű logikai nyelvén:

X ( X ( 0 ) y ( X ( y ) X ( s ( y ) ) ) x X ( x ) ) .

Másodrendű logikai nyelvet a programozáselméletben már a kezdetekkor is használtak a programok tulajdonságainak formalizálására [42].