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

Főoldal > TAMOP 4.2.5 Pályázat könyvei > Könyvek > Természettudományok > Matematika

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

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

Panem Kft.

Beágyazás

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 $c \in C \subseteq U$ 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 \in ℛ$ és $R : U^{n} \to {i, h}$ , akkor legyen $ν_{1} (R) = n$ . Továbbá ha $m \in ℳ$ és $m : U^{n} \to U$ , 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; R_{1}, R_{2}, \dots, R_{i}; m_{1}, m_{2}, \dots, m_{j}; c_{1}, c_{2}, \dots, c_{k} 〉$ . 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 $〈 N_{0}; =; s, +, \times; 0 〉$ négyes.

univerzuma: $N_{0}$
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), $\times$ (szorzás)
konstansa: $0$
szignatúrája:

$R$	$ν_{1} (R)$	$m$	$ν_{2} (m)$	$ν_{3}$
$=$	$2$	$s$	$1$	$1$
		$+$	$2$
		$\times$	$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, +, \times; 0 〉$
szignatúra	(2; 1, 2, 2; 1)

,,logikai” része:
- individuumváltozók: $x, y, z, \dots$
- logikai összekötők jelei: $\neg$ , $\land$ , $\lor$ , $\supset$
- kvantorok: $\forall$ , $\exists$
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 $t_{1}$ és $t_{2}$ termekből az alapműveletek felhasználásával felírt $s (t_{1}), (t_{1} + t_{2}), (t_{1} \times t_{2})$ alakú kifejezések termek.

termek például: $s (0), (x + s (0)), (x \times (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 $\neg A$ , $(A \land B)$ , $(A \lor B)$ , $(A \supset B)$ , $\forall x A$ , $\exists x A$ alakú kifejezések is formulák.

Az Ar nyelv szemantikája

egy $n$ individuumváltozót tartalmazó term egy $N_{0}^{n} \to N_{0}$ műveletet ír le, melyet az alapműveletek ismeretében határozhatunk meg.
egy $n$ (szabad) individuumváltozót tartalmazó formula egy $N_{0}^{n} \to {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: $x \neq y ⇌ \neg (x = y)$
- $x$ kisebb, vagy egyenlő $y$ -nal: $x \leq y ⇌ \exists z ((x + z) = y)$
- $x$ osztója $y$ -nak: $x | y ⇌ (x \neq 0) \land \exists z ((x \times z) = y)$
- $x$ prím: $(x \neq 0) \land (x \neq s (0)) \land \forall z ((z | x) \supset ((z = s (0)) \lor (z = x))$

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

A struktúra a $〈 P (H); \subseteq;; 〉$ négyes.

univerzuma egy rögzített $H$ halmaz hatványhalmaza: $P (H)$
alaprelációja kétváltozós: $\subseteq$ (tartalmazás)
alapművelete és konstansa nincs
szignatúrája: $ν_{1} (\subseteq) = 2$

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

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

ábécé	$〈 \subseteq;; 〉$
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: $(x \subseteq y)$
- 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 ⇌ (x \subseteq y) \land (y \subseteq x)$
- az $x$ és az $y$ részhalmazok nem egyenlőek: $x \neq y ⇌ \neg (x = y)$
- az $x$ részhalmaz az $y$ részhalmaz valódi része: $x \subset y ⇌ (x \subseteq y) \land (x \neq y)$
- az $x$ részhalmaz az $y$ és a $z$ részhalmazok metszete: $x = (y \cap z) ⇌ (x \subseteq y) \land (x \subseteq z) \land \forall v ((v \subseteq y) \land (v \subseteq z) \supset (v \subseteq x))$

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 $π \in S$ fajta univerzumbeli elemek halmazát. $ℛ$ elemei $U_{π_{1}} \times U_{π_{2}} \times \dots \times U_{π_{i}} \to {i, h}$ logikai függvények, $ℳ$ elemei $U_{π_{1}} \times U_{π_{2}} \times \dots \times U_{π_{i}} \to U_{π}$ 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 \in ℛ$ és $R : U_{π_{1}} \times U_{π_{2}} \times \dots \times U_{π_{i}} \to {i, h}$ , akkor $ν_{1} (R) = (π_{1}, π_{2}, \dots, π_{i})$ . Ha $m \in ℳ$ és $m : U_{π_{1}} \times U_{π_{2}} \times \dots \times U_{π_{i}} \to U_{π}$ , akkor $ν_{2} (m) = (π_{1}, π_{2}, \dots, π_{i}, π)$ . Minden $c \in C$ esetén ha $c \in U_{π}$ , 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}, \dots, π_{i})$ , illetve a $ν_{2} (m) = (π_{1}, π_{2}, \dots, π_{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 $〈 U_{p} \cup U_{e} \cup U_{s}; =, \in_{e}, \in_{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 $U_{p}$
- egyenesek $U_{e}$
- síkok $U_{s}$ halmazának uniója
alaprelációi kétváltozósak:
- $=$ : $U_{p} \times U_{p} \to {i, h}$ (két pont egyenlősége)
- $\in_{e}$ : $U_{p} \times U_{e} \to {i, h}$ (pont illeszkedése egyenesre)
- $\in_{s}$ : $U_{p} \times U_{s} \to {i, h}$ (pont illeszkedése síkra)
alapműveleteket és konstansokat nem definiálunk
szignatúrája: $ν_{1} (=) = (p, p)$ , $ν_{1} (\in_{e}) = (p, e)$ , $ν_{1} (\in_{s}) = (p, s)$

A Geom nyelv ábécéjének

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

ábécé	$〈 =, \in_{e}, \in_{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, \dots}$ pontváltozók, ${q, r, \dots}$ egyenesváltozók, ${a, b, \dots}$ 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)$ , $(A \in_{s} q)$ , $(B \in_{s} a)$
- 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 \in_{e, s} a ⇌ \forall A ((A \in_{e} q) \supset (A \in_{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, +, \times$	0	$(2; 1,2,2; 1)$
$P (H)$	$\subseteq$			$(2;;)$
$U_{p} \cup U_{e} \cup U_{s}$	$=, \in_{e}, \in_{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 $〈 N_{0}; =; s, +, \times; 0 〉$ -beli jelentése rendre az, hogy

$x$ kisebb, mint $y$ : $x \leq y$ ;
$z$ az $x$ és az $y$ legnagyobb közös osztója: $z = (x, y)$ ;
$z$ az $x$ és az $y$ legkisebb közös többszöröse: $z = [x, y]$ ;
a prímszámok száma végtelen;
a prímszámok száma véges;
az ikerprímek száma végtelen;
minden természetes szám előállítható négy négyzetszám összegeként;
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); \subseteq;; 〉$ -beli jelentése rendre a következő:

Az $x$ részhalmaz maga az alaphalmaz: $x = U$ .
Az $x$ részhalmaz üres halmaz: $x = \emptyset$ .
Az $x$ részhalmaz egyelemű.
Az $x$ részhalmaz az $y$ és a $z$ részhalmazok uniója: $x = y \cup z$ .
Az $x$ részhalmaz az $y$ $z$ -re vonatkozó komplementere: $x = z ∖ y$ .
$x$ az univerzum legkisebb, illetve az univerzum legnagyobb eleme.

3.2.3. FELADAT. Adjunk meg olyan formulákat a Geom logikai nyelven, amelyeknek az $〈 U_{p} \cup U_{e} \cup U_{s}; =, \in_{e}, \in_{s};; 〉$ struktúrabeli jelentése rendre a következő: