Univerzális kvantifikáció

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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

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

Szintaktika és szándékolt jelentés[szerkesztés]

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]

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]

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]

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]

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ψ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 φ(∀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]

(GEN)-nel.

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


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.

[korlátozatlan univerzális generalizálás: x szerepel az |- jel előtt]
[korlátozatlan dedukciótétel: x-től függő premissza felvétele]
[univerzális specifikáció a külső x-re]
[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]

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 Γ |- ψ φ (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:


ahol x nem szabad változója Γ egyetlen elemének sem.

Az előző szakaszban említett példa ez esetben 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:


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]

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  Minden ember halandó
-----------------------------------------
Szókratész ember   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:


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:

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]

Alfred Tarski az 1930-as években adott először osztályelméleti jelentést a kvantoroknak. Ennek szellemében, legyen modellje egy 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

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

minden u ∈ M-re

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 modellben.

Kapcsolata az ∧ konnektívummal[szerkesztés]

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 véges modell, bővített nyelvben az új konstansok {cm}m∈M halmaza |M| elemszámú és az nyelv azon modellje, mely -nek bővítése és melyben az új konstansok különböző M-beli értékeket vesznek fel, akkor

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

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]

Ha 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 modelljének. Ebben az algebrában a C cilindrifikáció lényegében az egzisztenciális kvantifikáció:

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:

(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:

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]

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

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

Feltételes és halmazbeli univerzális kvantor[szerkesztés]

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

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

Intuicionista univerzális kvantor[szerkesztés]

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:

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

Hivatkozások[szerkesztés]

  • 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