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.

Néhány matematikai diszciplína logikai nyelve

Néhány matematikai diszciplína logikai nyelve

A továbbiakban néhány matematikai diszciplína logikai tárgyalási nyelvét szeretnénk kialakítani. Ennek érdekében megvizsgáljuk a matematika néhány ága esetén azt, hogy milyen, lehetőleg minimális ábécéjű logikai nyelv lenne alkalmas az ott felmerülő állítások leírására. Foglalkozunk e nyelvek sajátosságaival és az általánosítási lehetőségekkel is [22].

3.2.1. DEFINÍCIÓ. Legyen U tetszőleges nemüres halmaz, az U-n értelmezett relációk, az U-n értelmezett műveletek halmaza, C pedig U-beli elemek egy halmaza. Ekkor az U;;;C négyest (matematikai) struktúrának vagy modellnek nevezzük.

U a struktúra alaphalmaza vagy univerzuma, elemei az alaprelációk, elemei az alapműveletek. A cCU kiválasztott elemeket konstansoknak hívjuk. Abban az esetben, ha üres, algebrai struktúráról vagy algebráról, ha üres, akkor relációrendszerről beszélünk.

3.2.2. DEFINÍCIÓ. Legyen U;;;C egy struktúra. Ha R és R:Un{i,h}, akkor legyen ν1(R)=n. Továbbá ha m és m:UnU, akkor legyen ν2(m)=n. ν3 pedig adja meg C elemeinek a számát. A (ν1,ν2,ν3) hármast a struktúra szignatúrájának nevezzük.

A ν1(R)=n, illetve a ν2(m)=n azt fejezi ki, hogy R, illetve m értelmezési tartománya az U-beli elem n-esek halmaza. A struktúra egy másik megadási módja szerint az U halmaz után a , az és a C halmaz elemeit felsoroljuk, tehát: U;R1,R2,,Ri;m1,m2,,mj;c1,c2,,ck. Vegyük észre, hogy az aritások sorrendhelyes felsorolása, illetve a konstansok számának megadása a szignatúra megadása más formában, amit egyes szerzők a struktúra típusának is neveznek.

Most megadjuk két struktúra elsőrendű logikai nyelvét. Az elsőként vizsgált struktúra – az elemi aritmetika – a matematika egyik többezer éves ága, amit a számelmélet tanulmányoz. A másik struktúra egy rögzített halmaz részhalmazaival foglalkozik.

Az elemi aritmetika logikai nyelve: az Ar nyelv

A struktúra az N0;=;s,+,×;0 négyes.

  • univerzuma: N0

  • alaprelációja (matematikai szerepe szerint logikai függvény, logikai szerepe szerint predikátum):

    • kétváltozós: = (egyenlő)

  • alapműveletei (matematikai szerepük szerint matematikai függvények, logikai szerepük szerint individuumleírások):

    • egyváltozós: s(x) (rákövetkezés)

    • kétváltozós: + (összeadás), × (szorzás)

  • konstansa: 0

  • szignatúrája:

R

ν 1 ( R )

m

ν 2 ( m )

ν 3

=

2

s

1

1

+

2

×

2

A struktúrát leíró logikai nyelvet nevezzük Ar nyelvnek. Az Ar nyelv ábécéjének

  • ,,logikán kívüli” (speciális) része:

ábécé

= ; s , + , × ; 0

szignatúra

(2; 1, 2, 2; 1)

  1. ,,logikai” része:

    • individuumváltozók: x,y,z,

    • logikai összekötők jelei: ¬, , ,

    • kvantorok: ,

  2. elválasztójelek: (),

Az Ar nyelv szintaxisa

megmondja, hogyan lehet az ábécé segítségével aritmetikai kifejezéseket leírni, tulajdonságaikat és a közöttük fennálló relációkat megfogalmazni.

  • termek: a 0 konstans, az individuumváltozók, továbbá tetszőleges t1 és t2 termekből az alapműveletek felhasználásával felírt s(t1),(t1+t2),(t1×t2) alakú kifejezések termek.

termek például: s(0),(x+s(0)),(x×(y+z))

  • formulák:

    • atomi (egyszerű) formulát nyerünk, ha két termet az alapreláció felhasználásával kapcsolunk össze. például: (x=y),(z=s(0))

    • tetszőleges A és B formulákból logikai összekötők és kvantorok felhasználásával felírt ¬A, (AB), (AB), (AB), xA, xA alakú kifejezések is formulák.

Az Ar nyelv szemantikája

  • egy n individuumváltozót tartalmazó term egy N0nN0 műveletet ír le, melyet az alapműveletek ismeretében határozhatunk meg.

  • egy n (szabad) individuumváltozót tartalmazó formula egy N0n{i,h} logikai függvényt ír le, melyet az alapreláció ismeretében, valamint a logikai összekötők és a kvantorok értelmezése alapján határozhatunk meg. A formulák tehát relációkat írnak le, így mondhatjuk, hogy az alaprelációk felhasználásával megadott formulák új relációkat definiálnak. Az aritmetikában elegendő az egyenlőség (=) alapreláció, mivel a gyakran használt relációk ennek segítségével definiálhatók:

    • x nem egyenlő y-nal: xy¬(x=y)

    • x kisebb, vagy egyenlő y-nal: xyz((x+z)=y)

    • x osztója y-nak: x|y(x0)z((x×z)=y)

    • x prím: (x0)(xs(0))z((z|x)((z=s(0))(z=x))

Egy halmaz részhalmazait leíró logikai nyelv: a Részh nyelv

A struktúra a P(H);;; négyes.

  • univerzuma egy rögzített H halmaz hatványhalmaza: P(H)

  • alaprelációja kétváltozós: (tartalmazás)

  • alapművelete és konstansa nincs

  • szignatúrája: ν1()=2

A Részh nyelv ábécéjének

  • ,,logikán kívüli” (speciális) része:

ábécé

; ;

szignatúra

( 2 ; ; )

  • ,,logikai” része és az elválasztójelek megegyeznek az Ar nyelv ábécéjének megfelelő részével

A Részh nyelv szintaxisa

  • termek: az individuumváltozók

  • formulák:

    • atomi formulák a termekből az alapreláció felhasználásával felírt kifejezések. például: (xy)

    • tetszőleges A és B formulákból az Ar nyelvben elmondottak szerint előállított kifejezések.

A Részh nyelv szemantikája

  • az Ar nyelvéhez hasonlóan határozható meg. Példaként néhány fontosabb reláció definiálása:

    • az x és az y részhalmazok egyenlőek: x=y(xy)(yx)

    • az x és az y részhalmazok nem egyenlőek: xy¬(x=y)

    • az x részhalmaz az y részhalmaz valódi része: xy(xy)(xy)

    • az x részhalmaz az y és a z részhalmazok metszete: x=(yz)(xy)(xz)v((vy)(vz)(vx))

3.2.3. MEGJEGYZÉS. Az Ar nyelv és a Részh nyelv ábécéje meghatározásánál arra törekedtünk, hogy az ábécében a lehető legkevesebb logikán kívüli jel legyen, ugyanakkor a jeleknek megfelelő alapműveletek, illetve alaprelációk segítségével ezekben a struktúrákban – mint ahogy azt tapasztaltuk is – a gyakran használt műveletek, illetve relációk definiálhatók.

A fenti két matematikai struktúra univerzumaiban egyféle elemek voltak (egyikben természetes számok, másikban H részhalmazai). Ezért az alapműveletek, a termek által leírt műveletek, az alaprelációk és a formulák által leírt logikai függvények értelmezési tartománya mindig az univerzum önmagával vett valahányszoros Descartes-szorzata. Vannak azonban olyan matematikai struktúrák, amelyekben az alaphalmazban különböző fajta elemek is vannak. Az ilyen struktúrákat többfajtájú struktúráknak[5] nevezzük. A leíró nyelvben minden elemfajtához bevezetik a megfelelő fajtájú individuumváltozókat.

3.2.4 DEFINÍCIÓ. Legyen S fajták[6] halmaza. Egy általános matematikai struktúra olyan U;S;;;C ötös, amely U univerzumában minden elem valamilyen S-beli fajta. Jelölje Uπ a πS fajta univerzumbeli elemek halmazát. elemei Uπ1×Uπ2××Uπi{i,h} logikai függvények, elemei Uπ1×Uπ2××UπiUπ matematikai függvények, C elemei U különböző fajta kitüntetett elemei, konstansai.

Egy U;S;;C általános matematikai struktúrában is elemeit a struktúra alaprelációinak, elemeit pedig a struktúra alapműveleteinek nevezzük.

3.2.5. DEFINÍCIÓ. Legyen U;S;;;C egy általános matematikai struktúra. Ha R és R:Uπ1×Uπ2××Uπi{i,h}, akkor ν1(R)=(π1,π2,,πi). Ha m és m:Uπ1×Uπ2××UπiUπ, akkor ν2(m)=(π1,π2,,πi,π). Minden cC esetén ha cUπ, akkor ν3(c)=(π). A (ν1,ν2,ν3) hármast a többfajtájú struktúra szignatúrájának nevezzük.

A ν1(R)=(π1,π2,,πi), illetve a ν2(m)=(π1,π2,,πi,π) azt fejezi ki, hogy az R logikai függvény, illetve az m matematikai függvény értelmezési tartománya olyan elem i-sek halmaza, melyekben az első elem π1, a második π2, …, az i-edik πi fajtájú, továbbá az m matematikai függvény eredménye éppen π fajtájú.

Ha S egyelemű, ez az elem meghatározza az U elemeinek fajtáját. Ebben az esetben egyfajtájú struktúráról beszélünk. Eddig ilyen matematikai struktúrákkal foglalkoztunk. Ha S egynél több elemet tartalmaz, többfajtájú a struktúra. Többfajtájú matematikai struktúrára példa a háromdimenziós euklideszi geometria.

A háromdimenziós euklideszi geometria logikai nyelve: a Geom nyelv

A struktúra az UpUeUs;=,e,s;; rendszer.

  • univerzuma a háromdimenziós euklideszi tér, amelyben az individuumelemek lehetnek pontok (p), egyenesek (e) és síkok (s), így tehát az univerzum a

    • pontok Up

    • egyenesek Ue

    • síkok Us halmazának uniója

  • alaprelációi kétváltozósak:

    • = : Up×Up{i,h} (két pont egyenlősége)

    • e : Up×Ue{i,h} (pont illeszkedése egyenesre)

    • s : Up×Us{i,h} (pont illeszkedése síkra)

  • alapműveleteket és konstansokat nem definiálunk

  • szignatúrája: ν1(=)=(p,p), ν1(e)=(p,e), ν1(s)=(p,s)

A Geom nyelv ábécéjének

  • ,,logikán kívüli” (speciális) része:

ábécé

= , e , s ; ;

szignatúra

( ( p , p ) , ( p , e ) , ( p , s ) ; ; )

  • ,,logikai” része megegyezik az Ar nyelv ábécéjének logikai részével, de az individuumváltozók különböző fajtájúak: legyenek {A,B,} pontváltozók, {q,r,} egyenesváltozók, {a,b,} síkváltozók.

A Geom nyelv szintaxisa

  • termek: az individuumváltozók

  • formulák:

    • atomi formulák a termekből az alaprelációk segítségével épülnek fel például: (A=B), (Asq), (Bsa)

    • tetszőleges A és B formulákból az Ar nyelvben elmondottak szerint előállított kifejezések például: a q egyenes illeszkedik az a síkra:

q e , s a A ( ( A e q ) ( A s a ) )

Összefoglalva a felsorolt matematikai struktúrákat leíró logikai nyelvek szerkezetét, a következőket állapíthatjuk meg:

  • a nyelvek ábécéjének ,,logikai része” megegyezik

  • a nyelvek ábécéjének ,,logikán kívüli” része: relációk, műveletek és konstansok jelei, amelyeket a szignatúra jellemezhet

univerzum

relációk

műveletek

konstansok

szignatúra

N 0

=

s , + , ×

0

( 2 ; 1,2,2 ; 1 )

P ( H )

( 2 ; ; )

U p U e U s

= , e , s

( ( p , p ) , ( p , e ) , ( p , s ) ; ; )

  • a nyelvek szemantikája: a termek által leírt matematikai leképezések és a formulákkal leírt logikai leképezések meghatározhatók a term, illetve a formula alkotóelemeinek ismeretében.

Feladatok

3.2.1. FELADAT. Adjunk meg olyan formulákat az Ar logikai nyelven, melyek N0;=;s,+,×;0-beli jelentése rendre az, hogy

  1. x kisebb, mint y: xy;

  2. z az x és az y legnagyobb közös osztója: z=(x,y);

  3. z az x és az y legkisebb közös többszöröse: z=[x,y];

  4. a prímszámok száma végtelen;

  5. a prímszámok száma véges;

  6. az ikerprímek száma végtelen;

  7. minden természetes szám előállítható négy négyzetszám összegeként;

  8. van legnagyobb a természetes számok között.

3.2.2.FELADAT. Adjunk meg olyan formulákat a Részh logikai nyelven, melyek P(H);;;-beli jelentése rendre a következő:

  1. Az x részhalmaz maga az alaphalmaz: x=U.

  2. Az x részhalmaz üres halmaz: x=.

  3. Az x részhalmaz egyelemű.

  4. Az x részhalmaz az y és a z részhalmazok uniója: x=yz.

  5. Az x részhalmaz az yz-re vonatkozó komplementere: x=zy.

  6. x az univerzum legkisebb, illetve az univerzum legnagyobb eleme.

3.2.3. FELADAT. Adjunk meg olyan formulákat a Geom logikai nyelven, amelyeknek az UpUeUs;=,e,s;; struktúrabeli jelentése rendre a következő:

  1. A q és a r egyenesek egybeesnek: q=r.

  2. A q és a r egyenesek metszik egymást.

  3. A q és a r egyenesek egy síkban vannak.

  4. A q és a r egyenesek párhuzamosak: qr.

  5. Az a és a b síkok egybeesnek: a=b.

  6. Az a és a b síkok párhuzamosak: ab.



[5] Angolul many sorted structures.

[6] Angolul sorts.