Univerzális kvantifikáció

A Wikipédiából, a szabad enciklopédiából

Az univerzális kvantifikáció az a logikai operátor (speciális kvantor), mely a „minden”, „bármely”, „összes” természetes nyelvi szavaknak feleltethető meg valamely formális nyelven belül. Univerzális kvantor szerepét töltik be például az alábbi mondatokban a dőlt betűs szavak:

Minden ember halandó.”
„Ezügyben érdeklődhet bármelyik munkatársunknál.”
„A gyerek az összes tojást összetörte.”

Az említett szavak akkor válnak univerzális kvantorrá, ha a mondatokat egy formális nyelv kifejezéseiből állítjuk össze, például ekképpen:

ha φ(x) jelentése az, hogy „x halandó”, akkor (∀x)φ(x) jelentése „Minden ember halandó.”

Itt (∀x)φ(x)-t úgy mondjuk ki, hogy „minden x-re fí-x” és a

\forall\,

szimbólum az univerzális kvantifikáció jele.

Szintaktika és szándékolt jelentés[szerkesztés | forrásszöveg szerkesztése]

A (∀x)φ formulát akkor veszünk egy elsőrendű formális nyelvben, ha a „Minden dolog 'φ' tulajdonságú.” metanyelvi mondatot kívánjuk a tárgynyelvben megfogalmazni (fordítani). Ez az univerzális kvantor szándékolt jelentése. Vegyük észre, hogy míg a formalizálatlan metanyelv fenti mondatában nincsenek változók, addig a tárnynyelvben már vannak. Mi több, például a (∀x)(x=y) tárgynyelvi formula szándékolt jelentése:

„minden egyenlő a ...-tal”

ami egy hiányos mondat, egy predikátum. A (∀x)(x=y)-ben két külön típusú változó szerepel. A metanyelvi fordításban az x, mely a kvantifikáció megfogalmazásának segédváltozója, nem szerepel. Az y a metaelmélet természetes nyelvében egy kitöltetlen hely marad. A szintaktikai vonatokozásoknál a változók ezen megkülönböztetése nagy odafigyelést követel a formalizálótól. A szándékolt jelentés a formális nyelvvel szemben természetes követelményeket támaszt, melyek némelyikének az elsőrendű nyelvek tökéletesen megfelelnek, másokat csak részben teljesít. A formális tudományokban, például a matematikában a szándékolt jelentésre úgy kell tekintenünk, mint egy kezdeti feltevésre, melynek fennállását mindig ellenőriznünk kell. Könnyen előfordulhat, hogy a formalizálás elején még összhangban van a metanyelv és a tárgynyelv, de formális manipulációk sorozata után a kezdetben betáplált szándékolt jelentés már nem öröklődik a végállapotra. Erre a legjobb példa a második Gödel-tétel, melyben bizonyos metaelméleti mondatok fordítása során olyan tárgynyelvi mondatok jönnek létre, melyek pont fordításuk ellenkezőjét állítják.

Változók lekötése[szerkesztés | forrásszöveg szerkesztése]

Formális nyelvekben a kvantorok változót lekötő operátorok. Ez azt jelenti, hogy míg a φ(x,y) formula kétbemenetűnek tekinthető (x és y is szabad változója a φ-nek), addig a (∀x)φ(x,y) már csak egy bemenettel rendelkezik (x szabad változója φ-nek, y pedig kötött változója φ-nek). Ekkor még azt is mondjuk, hogy a (∀x)φ(x,y) formulában szereplő (∀x) kvantor hatóköre a φ(x,y) formula, amelyen belül tehát az x kötött módon szerepel.

Például, míg a

φ ≡ 'x=x'

formulában az x változót a c konstansra cserélve az új

φ[x/c] ≡'c=c'

zárt formulát (mondatot) kapjuk, addig a

(∀x)φ

már maga is zárt formula, x nem szabad változója, így helyettesítése a c konstanssal definíció szerint nem eredményez új mondatot:

((∀x)φ)[x/c] ≡ (∀x)φ

Ezt úgy is mondjuk, hogy kötött változóba nem lehet semmit behelyettesíteni.

Tiltott helyettesítések[szerkesztés | forrásszöveg szerkesztése]

Egy

ψ ≡ (∀x)φ(x,y)

alakú formulában formálisan (grafikusan) végrehajtható az [y/x] helyettesítés:

((∀x)φ(x,y))[y/x] ≡ (∀x)φ(x,x)

de egy ilyen helyettesítés az y helyére kerülő x-et bevonja a kvantor hatókörébe, miközben az y eredetileg ψ-nek szabad változója volt. Világos, hogy egy ilyen helyettesítés lényegesen megváltoztatja a ψ jelentését. Például a

ψ(y) ≡ (∀x)(x = y)

szándékolt jelentése:

ψ(y) ≡ „y mindennel egyenlő”,

míg

ψ[y/x] ≡ (∀x)(x = x) ≡ „minden egyenlő saját magával”.

Mindeközben például a

ψ[y/z] ≡ (∀x)(x = z) ≡ „z mindennel egyenlő”

egy jelentésmegőrző helyettesítés.

Azt mondjuk, hogy a (∀x)φ(x,y) formulában az t kifejezés szabad az y-ba történő helyettesítésre nézve, ha t-nek nem szabad változója az x. Ekkor a ((∀x)φ(x,y))[y/t] helyettesítés nem köt le t-beli szabad x-et, mivel nincs is olyan.

Bizonyításelméleti szemantika[szerkesztés | forrásszöveg szerkesztése]

Egy formális elméletbeli univerzális kvantifikációnak nem csak szándékolt jelentése (vagyis hogy a „minden” szót rövidíti) létezik. Értelmet adhatunk a (∀x)φ univerzális kijelentéseknek, ha megmondjuk, hogy milyen szabály örökíti az igazságot rájuk és mire örökítik az igazságot. Az elsőrendű nyelvekben a következő alapvető jelentőségű levezetési szabályok érvényesek az univerzális kijelentésekre.

Univerzális generalizáció[szerkesztés | forrásszöveg szerkesztése]

Az univerzális generalizáció az a következtetési szabály, mely valamely premisszából egy (∀x)φ formulára enged következtetni. A következő természetes nyelvi aktusról van szó:

Tegyük fel, hogy egy φ tulajdonság tetszőleges t dologra igaz. Ekkor helyesen következtetünk, ha azt mondjuk: „Minden dolog φ tulajdonságú”.

Példa. Igazoljuk, hogy minden kettőnél nagyobb prímszám páratlan!

  1. (tetszőleges választás) Legyen p tetszőleges kettőnél nagyobb prímszám.
  2. (indirekt feltevés) Ha p páros lenne, akkor lenne k pozitív egész, hogy 2k = p
  3. (ellentmondás) De mivel p > 2, ezért k > 1, azaz p fölbontható két olyan pozitív egész szám szorzatára, mely közül egyik sem az 1, azaz p nem prím.
  4. (konklúzió) Tehát p páratlan.
  5. (univerzális generalizáció) Mivel p tetszőleges volt, ezért kijelenthetjük: minden kettőnél nagyobb prímszám páratlan.

Az érvelésben, amikor 1. és 4. fennállása miatt 5.-re következetettünk, univerzális generalizációt végeztünk.

Az univerzális kvantor bevezetési szabálya lényegesen függ attól, hogy Γ |- φ levezethetőség esetén levezetési szabályok közé veszik-e föl a korlátozatlan generalizációt (GEN) is vagy egyedüli levezetési szabálynak a modus ponenst (MP) tekintik. Az egyik lehetséges definíciója Γ |- φ-nek az, hogy létezik olyan (ψ1,...,ψn) formulasorozat, hogy ψn≡φ és minden k<n-re

  1. ψk logikai axióma vagy eleme Γ-nak vagy
  2. (MP) létezik i,j < k ψj≡ψi\toψk vagy
  3. (GEN) létezik i < k (∀x)ψi≡ψk

Ha ezzel szemben (GEN)-t elhagyjuk és a logikai axiómákat bővítjük a φ\to(∀x)φ sémával (melyben x nem szerepel szabadon φ-ben), akkor megváltoznak az univerzális kvantorra vonatkozó alapvető szabályok.

Korlátozatlan univerzális generalizáció[szerkesztés | forrásszöveg szerkesztése]

(GEN)-nel.

Tetszőleges φ formulára, Γ formulahalmazra és x változóra:

\frac{\Gamma\vdash\varphi}{\Gamma\vdash(\forall\,x)\varphi\;}\quad\quad(\mathrm{UG})

Ebben az esetben viszont a dedukciótételt nem lehet korlátozatlan formában alkalmazni, legegyszerűbb esetben csak zárt premisszákra. Például az alábbi gondolatmenetben azt látjuk be, hogy ha minden dolog olyan, hogy ha az a, akkor b is, akkor minden dolog b. Ilyen következtetés például a {c≠b,a=b} elméletben nyilvánvalóan érvénytelen.

c\ne b,a=b \vdash(\forall x)(x=a\;\rightarrow\;x=b)
c\ne b,a=b\vdash x=a\;\rightarrow\;x=b
c\ne b,a=b,x=a\vdash x=b
c\ne b,a=b,x=a\vdash (\forall x)(x=b) [korlátozatlan univerzális generalizálás: x szerepel az |- jel előtt]
c\ne b,a=b\vdash x=a\;\rightarrow\;(\forall x)(x=b) [korlátozatlan dedukciótétel: x-től függő premissza felvétele]
c\ne b,a=b\vdash (\forall x)(x=a\;\rightarrow\;(\forall x)(x=b))
c\ne b,a=b\vdash a=a\;\rightarrow\;(\forall x)(x=b) [univerzális specifikáció a külső x-re]
c\ne b,a=b\vdash (\forall x)(x=b) [a=a axióma]

Ezekben az elméletekben a változók azon a kitüntetett szerepen kívül, hogy szabad és kötött szereplésük is létezik oly módon is kitüntetettek a konstansokkal szemben, hogy minden körülmények között (amikor egy levezethető formulában szerepelnek) univerzálisan generalizálhatók.

Korlátozott univerzális generalizáció[szerkesztés | forrásszöveg szerkesztése]

Ha a GEN-t nem tekintjük levezetési szabálynak, akkor az azzal az előnnyel jár, hogy a dedukciótétel feltételek nélkül érvényes: ha Γ U {ψ} |- φ, akkor Γ |- ψ \rightarrow φ (DT). Cserébe azonban az UG szabály csak az alábbi formában érvényes:

Tetszőleges φ formulára, Γ formulahalmazra és x változóra:

\frac{\Gamma\vdash\varphi}{\Gamma\vdash(\forall\,x)\varphi\;}\quad\quad(\mathrm{UG})
ahol x nem szabad változója Γ egyetlen elemének sem.

Az előző szakaszban említett példa ezesetben is mutatja, hogy korlátozatlan módon egyszerre DT-t és UG-t nem lehet alkalmazni.

Mindkét esetben igaz az, hogy konstanssal is működik a generalizálás a következő formában:

\frac{\Gamma\vdash\varphi(c)}{\Gamma\vdash(\forall\,x)\varphi[x/c]\;}\quad\quad(\mathrm{UG-konst})
ahol c nem szerepel  Γ egyetlen elemében sem és
x szabad a c-be történő behelyettesítésre nézve a φ-ben.

Ez mutatja, hogy ha GEN-t nem szerepeltetjük, mint levezetési szabályt (a bizonyíthatóság definíciójában), akkor a változóknak (azon felül, hogy létezik kötött és szabad előfordulásuk) lényegében nincs kitüntetett szerepük a konstansokat történő összevetésben.

Univerzális specifikáció[szerkesztés | forrásszöveg szerkesztése]

Az univerzális specifikálás vagy univerzális instanciáció az a következtetési szabály, mely a (∀x)φ premisszából valamely más formulára enged következtetni. A következő természetes nyelvi aktusról van szó:

Tegyük fel, hogy „Minden dolog φ tulajdonságú”. Ekkor helyesen következtetünk, ha tetszőleges t dologról azt állítjuk: „A t dolog φ tulajdonságú”.

Például:

Szókratész ember \vdash Minden ember halandó
-----------------------------------------
Szókratész ember \vdash  Szókratész halandó

∀ kiküszöbölési szabálya (az univerzális specifikáció)

Tetszőleges φ formulára, Γ formulahalmazra, x változóra és t kifejezésre:

\frac{\Gamma\vdash(\forall\,x)\varphi\;}{\Gamma\vdash\varphi[t/x]}\quad\quad(\mathrm{UE})
ahol t szabad φ-ben az x-be történő behelyettesítésre nézve
(másként: a [t/x] helyettesítés megengedett φ-ben).

A megfogalmazott kitétel arra vonatkozik, hogy az érv nem érvényes például a következő esetben:

\frac{a\ne b\vdash(\forall\,x)(\exists y)(x \ne y)\;}{a\ne b\vdash(\exists y)(y \ne y)}\quad\quad\scriptstyle{/((\exists y)(x \ne y))[y/x]}

Ugyanis a két különböző a és b konstansot tartalmazó elméletben érvényes a φ ≡ (∀x)(∃y)(x ≠ y) formula, hiszen van két különböző individuum, de a

((∃y)(x ≠ y))[y/x]

nem megengedett helyettesítéssel nyert

(∃y)(y ≠ y)

formula már semelyik ellentmondásmentes elméletben sem lehet érvényes. Itt persze a jelentés is csorbul: φ(x) jelentése: „x olyan, amitől létezik különböző”, míg (∃y)(y ≠ y) nem azt jelenti, hogy „y-tól nincs különböző”, ahogy az x-be történő helyettesítés után értenének, hanem hogy „létezilk olyan dolog, ami saját magától különbözik”. Egy ilyen jelentésváltozás nem szándékolt, ezért tiltjuk el az példában végrehajtott következtetést.

Modellelméleti szemantika[szerkesztés | forrásszöveg szerkesztése]

Alfred Tarski az 1930-as években adott először osztályelméleti jelentést a kvantoroknak. Ennek szellemében, legyen \scriptstyle{\mathfrak{M}=(M,(f_i)_{i\in I},(r_j)_{j\in J},(c_k)_{k\in K})} modellje egy \scriptstyle{\mathcal{L}} elsőrendű nyelvnek. Adott φ formulára, az i-edik vi változójelre és adott a=(a1, a2,...) ∈ Mω végtelen értékeléssorozatra fennáll, hogy

\mathfrak{M}\models(\forall v_i)\varphi[a]

azaz „(∀vi)φ igaz az a értékelés szerint”, pontosan akkor, ha

minden u ∈ M-re \mathfrak{M}\models\varphi[a^{u}_{i}]

azaz akármilyen értéket adva az a i-edik elemének az így létrejövő értékelés szerint is igaz a φ formula az \scriptstyle{\mathfrak{M}} modellben.

Kapcsolata az ∧ konnektívummal[szerkesztés | forrásszöveg szerkesztése]

Az univerzális kvantor működésében rokonítható az „és” szót megjelenítő ∧ logikai konjunkcióval: ∀ bizonyos értelemben egy végtelen konjunkciónak felel meg. Véges modell esetén előállítható a modellnek olyan bővítése, mely konjunkcióvá alakítja az univerzális formulákat. Ha \scriptstyle{\mathfrak{M}} véges modell, \scriptstyle{\mathcal{L}_{M}=\mathcal{L}\cup\{c_m\}_{m\in M}} bővített nyelvben az új konstansok {cm}m∈M halmaza |M| elemszámú és \scriptstyle{(\mathfrak{M},m)_{m\in M}} az \scriptstyle{\mathcal{L}_{M}} nyelv azon modellje, mely \scriptstyle{\mathfrak{M}}-nek bővítése és melyben az új konstansok különböző M-beli értékeket vesznek fel, akkor

(\mathfrak{M},m)_{m\in M}\models(\forall x)\varphi(x)\quad\quad\Longleftrightarrow\quad\quad(\mathfrak{M},m)_{m\in M}\models\bigwedge\limits_{m\in M}\varphi(c_m)

Ha a konstansokat beszámozzuk: {uk}k=1...n={cm}m∈M, akkor tehát

(\forall x)\varphi(x)\quad\quad\Longleftrightarrow\quad\quad\varphi(u_1)\wedge\varphi(u_2)\wedge...\wedge\varphi(u_n)

a mondott modellben. Tehát a „12. a. osztály minden tanulója ötöst kapott” mondat ekvivalens azzal, hogy „Almási Anna ötöst kapott és Bán Balázs ötöst kapott és ... és Zoltán Zsófi ötöst kapott.”.

A jobb oldali formula általában nem írható fel a nyelvben. Egyrészt nem biztos, hogy egy modellben minden elem meg van nevezve, másrészt ha ez igaz is lenne, végtelen modellben végtelen hosszú formulát kellene felírni, ami nincs.

Algebrai modellelméleti szemantika[szerkesztés | forrásszöveg szerkesztése]

Ha \scriptstyle{\mathbf{A}=(A,\cup,\cap,\setminus,0,U^{\omega},\mathrm{C}_i,\mathrm{d}_{ij})_{i,j\in\omega}}\in\mathsf{Cs}_\omega olyan cilindrikus halmazalgebra, mely reguláris és lokálisan véges dimenziós, akkor izomorfizmus erejéig egyértelműen megfeleltethető egy elsőrendű nyelv \scriptstyle{\mathfrak{M}} modelljének. Ebben az algebrában a C cilindrifikáció lényegében az egzisztenciális kvantifikáció:

X\in A:\quad\quad\mathrm{C}_iX=\{a:\omega\to U\mid (\exists u\in U)(b\in X:\quad b_j=a_j\quad(j\ne i),\;b_i=u)\}

tehát, mely egy A-beli X sorozathalmazhoz azon sorozatok halmazát rendeli, melyek megváltoztathatók úgy, hogy még mindig X-ben legyenek.

Ez esetben az univerzális kvantor algebrai művelettel megfogalmazva:

\mathrm{C}^\partial_iX=U^{\omega}\setminus\mathrm{C}_i(U^{\omega}\setminus X)

(itt ∂ a Ci operátor duálisára utal.) Ezzel például a következő logikai azonosságok az alábbi algebrai alakot öltik:

\mathrm{C}^\partial_i(X\cap Y)=(\mathrm{C}^\partial_i X)\cap (\mathrm{C}^\partial_iY)\quad\quad \mathrm{minden}\; X,Y\in A
\mathrm{C}^\partial_i(X\cup Y)\supseteq(\mathrm{C}^\partial_i X)\cup (\mathrm{C}^\partial_iY)\quad\quad \mathrm{minden}\; X,Y\in A

Megjegyezzük, hogy a cilindrikus halmazalgebrák egyben Boole-halmazalgebrák is, annyiban többek, hogy a kvantifikációnak és az egyenlőségnek művelet is be van vezetve.

Logikai azonosságok[szerkesztés | forrásszöveg szerkesztése]

Tetszőleges modellben igazak ill. minden elméletben érvényesek a következő formulák:

(\forall x)\varphi\leftrightarrow\neg(\exists x)\neg\varphi
(\forall x)(\forall y)\varphi\leftrightarrow(\forall y)(\forall x)\varphi
(\exists x)(\forall y)\varphi\rightarrow(\forall y)(\exists x)\varphi
(\forall x)(\varphi\wedge \psi)\leftrightarrow(\forall x)\varphi\wedge(\forall x)\psi
(\forall x)\varphi\vee(\forall x)\psi\rightarrow(\forall x)(\varphi\vee \psi)

Továbbá, ha ψ-ben nem szerepel szabadon az x változó, akkor

(\forall x)(\psi\vee \varphi)\leftrightarrow\psi\vee(\forall x) \varphi
(\forall x)(\psi\wedge \varphi)\leftrightarrow\psi\wedge(\forall x)\varphi

Feltételes és halmazbeli univerzális kvantor[szerkesztés | forrásszöveg szerkesztése]

Ha ψ tetszőleges formula, akkor a ψ feltétel melletti univerzális kvantifikáció:

(\forall_{\psi} x)\equiv(\forall x)(\psi\rightarrow\varphi)

Speciálisan, ha a halmazelméletben ψ egy ' xH ' alakú formula, akkor az ezen feltétel melletti kvantort halmazbeli kvantornak nevezzük:

(\forall x\in H)\varphi\equiv(\forall_{x\in H}x)\varphi

Intuicionista univerzális kvantor[szerkesztés | forrásszöveg szerkesztése]

Az intuicionista logika univerzális kvantora (mint az összes többi logikai operátora) különbözik a klasszikus logika szerintitől. A klasszikus (∀x)φ jelentése, hogy az, hogy φ a tárgyalási univerzum minden elemére igaz. Ezzel szemben az intuicionista (∀x)φ egy jellegzetes interpretációja a Kolmogorov-féle feladatinterpretáció. Ebben a φ formulák paraméteres feladatok és a

(∀x)φ feladatot megoldani nem más, mint általános eljárást adni a φ(x) x-szel paraméterezett feladat megoldására (tehát az x paraméter minden értékére).

Ezt az interpretációt tekintve egyáltalán nem meglepő, hogy az intuicionista kvantifikációelméletben csak a következő formulák levezethetők:

(\forall x)\varphi(x)\rightarrow\neg(\exists x)\neg\varphi(x)\,

a ∀ megfogalmazhatósága egzisztenciális kvantorral csak negatív φ-re teljesül:

(\forall x)\neg\varphi(x)\leftrightarrow\neg(\exists x)\varphi(x)\,
(\forall x)\neg\neg\varphi(x)\leftrightarrow\neg(\exists x)\neg\varphi(x)\,

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • Mendelson, Elliott, Introduction to Mathematical Logic, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, Calif. (1964) OCLC 13580200
  • Ruzsa Imre–Máté András, Bevezetés a modern logikába, Budapest, Osiris Kiadó 1997.
  • Monk, J. Donald, An introduction to cylindric set algebras (with an appendix by H. Andreka) Logic Journal of the IGPL 8 (2000), pp. 451–506. online