Függőség Logika

Tartalomjegyzék:

Függőség Logika
Függőség Logika
Anonim

Belépés navigáció

  • Nevezés tartalma
  • Bibliográfia
  • Tudományos eszközök
  • Barátok PDF előnézete
  • Szerző és idéző információ
  • Vissza a tetejére

Függőség logika

Elsőként publikálták 2017. február 23-án

A függőségi logika az elsőrendű logika kiterjesztése, amely hozzáteszi függőség atomjait, vagyis a (eqord (x_1 / ldots x_n, y)) kifejezéseket, amelyek azt állítják, hogy (y) értéke funkcionálisan függ (vagyis meghatározva) az ((x_1 / ldots x_n) értékektől. Ezek az atomok lehetővé teszik a nemlineárisan elrendezett függőségi minták meghatározását a változók között, lényegében ugyanolyan értelemben, mint az IF-Logic kicsinyített számszerűsítői; de az IF-logikától eltérően, a függőségi logika elválasztja a mennyiségi meghatározást az ilyen függőségi / függetlenségi feltételek meghatározásától. A függőségi logika fő szemantikája, az úgynevezett csapatszemantika általánosítja Tarski szemantikáját azzal, hogy a kifejezéseknek elégedetteknek vagy elégedetteknek kell lenniük a változó feladatok halmaza, nem pedig az egyes feladatok vonatkozásában. Ez a szemantika a tényleges függőségi logika kialakulását megelőzi, és eredetileg Wilfrid Hodges fejlesztette ki az IF logika keretében (Hodges 1997). Létezik még a játék-elméleti szemantika a függőség logikájához is, amely nem tökéletes információk játékán alapul, és nagyjából analóg a függetlenség-barát logika játék-elméleti szemantikájával (Väänänen 2007a). Sensu stricto, a „függőségi logika” kifejezés kizárólag arra a nyelvre vonatkozik, amelyet úgy kapunk, hogy a fent említett funkcionális függőségi atomokat hozzáadjuk az elsőrendű logika nyelvéhez; de a kifejezést általánosabb értelemben arra a kutatási területre utalják, amely a logika tulajdonságait vizsgálja, és amelyet a függőség és a függetlenség különböző fogalmainak az elsőrendű logikához, például a függetlenség logikához történő hozzáadásával nyernek (Grädel & Väänänen 2013),az intuitív függési logika (Yang 2013) vagy a beillesztési logika (Galliani 2012, Galliani & Hella 2013), vagy akár a többi logikai keretet hasonló atomokon keresztül kiterjesztő logikák, mint a modális függőség logika esetében (Väänänen 2008). Ebben a cikkben a „függőség logikája” kifejezés a valódi függőség logikára vonatkozik, a „függőség és függetlenség logikája” kifejezés ehelyett annak változataira és általánosításaira utal.és ehelyett a „függőség és függetlenség logikája” kifejezést használjuk annak változataira és általánosításaira.és ehelyett a „függőség és függetlenség logikája” kifejezést használjuk annak változataira és általánosításaira.

  • 1. A függőségi minták elsőrendű logikában és annak kiterjesztéseiben
  • 2. A csapat szemantikája

    2.1 Játék-elméleti szemantika

  • 3. Tulajdonságok

    • 3.1 Expresszivitás
    • 3.2 Hierarchiák a függőségi logikában
    • 3.3 tagadás a függőségi logikában
    • 3.4 Igazság, érvényesség és bizonyítási rendszerek a függőség logikájában
  • 4. A függőségi logika variánsai

    • 4.1 Függetlenség logika
    • 4.2 Befogadási logika
    • 4.3 Csapat logika
    • 4.4 Intuicionista függőségi logika
    • 4.5 Propozicionális függési logika
    • 4.6 Modális függőség logika
  • 5. A függőségi logika alkalmazásai

    • 5.1 Függőség logika és adatbázis elmélet
    • 5.2 A függőség logikája és a hitek ábrázolása
    • 5.3 Függőséglogika és Arrow tétel
    • 5.4 A kvantum csapat logikája és Bell egyenlőtlenségei
  • Bibliográfia
  • Tudományos eszközök
  • Egyéb internetes források
  • Kapcsolódó bejegyzések

1. A függőségi minták elsőrendű logikában és annak kiterjesztéseiben

Az elsőrendű logika egyik jellemzője, amely a kifejezőképesség és az alkalmazhatóság nagy részét befolyásolja, az a tény, hogy lehetővé teszi a mennyiségi mutatók beágyazását, és ennélfogva lehetővé teszi a számszerűsített változók közötti függőségi minták meghatározását. Vegyük például azt a (remélhetőleg hamis) állítást, miszerint „minden fiú szeret egy lányt, aki szeret egy másik fiút”. Egyértelműen lefordítható az elsőrendű logikába

) tag {1} label {eq: boygirl1} kezdődik {igazítás} & / forall x (fiú (x) jobbra nyíl / létezik y (lány (y) föld / szereti (x, y) földterület {} & / quad / létezik z (fiú (z) föld x / not = z / föld / szereti (y, z)))) vége {igazítás})

amelynek igazságszolgáltatása Tarski szokásos szemantikája szerint pontosan az, amit elvárhatnánk: a fenti kifejezés akkor igaz, ha és csak akkor, ha minden fiúra (b) megtalálható egy lány (g) és egy fiú (b ') olyan, hogy (b) szereti (g) és (g) szereti (b') és (b) és (b ') nem azonos. A lány identitása (g) természetesen függhet az első fiú identitásától (b) - elvégre ahhoz, hogy ez a kifejezés igaz legyen, nem követeljük meg, hogy minden fiú szerelmes minden lányba - és emellett a második fiú (b ') személyazonossága függhet az első fiú személyazonosságától is (b) (mivel a (b') -nak különböznie kell a (b ') -től) és annak a lánynak a személyazonosságából, akit (b) szeret. Tehát a számszerűsített változók közötti függőségi minta a következő: (y) (x) -től függ,míg a (z) mind a (x), mind a (y) függvénytől függ. Szintaktikai szempontból ezt tükrözi az a tény, hogy (létezik y) a (forall x) hatálya alá tartozik, míg a (létezik z) mindkettő (forall x) és (létezik y).

Az operátorok függőségi mintázatainak különbségei felhasználhatók a fontos megkülönböztetések formalizálására, mint például a függvény folytonossága közötti különbség (f)

) forall x / forall / epsilon / létezik / delta / forall x '(| x - x' | <\ delta / jobbra nyíl | f (x) - f (x ') | <\ epsilon))

és annak egységes folytonossága

) forall / epsilon / létezik / delta / forall x / forall x '(| x - x' | <\ delta / jobbra nyíl | f (x) - f (x ') | <\ epsilon))

vagy az elsőrendű logika intenzív kiterjesztésein, hogy kifejezzék a különbséget a De Dicto és a De Re között (pl. „Mindenki számára őrült lehet” lehet úgy érteni, hogy azt állítja, hogy mindenkinek (p), lehetséges, hogy (p) őrült, (forall x (személy (x) jobbra nyíl / Diamond / őrült (x))), vagy kijelenti, hogy lehetséges, hogy mindenki őrült együtt, (Gyémánt / forall x (személy (x) jobbra nyíl / őrült (x)))).

Az elsőrendű logikában a számszerűsített változók közötti függőségi minták szükségszerűen tranzitívek, mivel ezt egyértelművé teszik a megfelelő al-kifejezések terjedelmével való kapcsolataik is: ha (létezik y) a (forall x) és (létezik z) a (létezik y) hatókörén belül, akkor feltétlenül (létezik z) a (és ezért attól függ) (forall x). Ezenkívül az összes számszerűsítő sorozat, amelynek hatókörébe néhány alformuláció (alpha) tartozik, lineárisan van rendezve: ha (alpha) (Q_1 x_1) és (Q_2 x_2) hatókörén belül van, akkor vagy (Q_1 x_1) a (Q_2 x_2) hatálya alá tartozik, vagy fordítva.

Ez korlátozza az elsőrendű logika kifejező lehetőségeit. Tegyük fel például, hogy a következõképpen szeretnénk módosítani a fiúkkal és lányokkal kapcsolatos korábbi állításunkat: minden fiú szeret egy lányt, aki szereti a másik fiút, és ez a második fiú az elsõnél önállóan választható meg. Ez intuitív szempontból azt jelenti, hogy elég egyszerű: minden fiúhoz (b) megtalálhatunk egy lányt (g), amelyben (b) szereti (g), és minden ilyen lányhoz keressen egy olyan fiút (b '), amelyben (g) szereti (b') és (b / not = b '), továbbá megtalálhatjuk a második fiú azonosítóját is (b') anélkül, hogy tudná a (b) tényt, kizárólag a lány (g) személyazonossága alapján. Ez továbbra is igaz lehet bizonyos forgatókönyvekben, például amikor két fiú (b_1) és (b_2) szeret két gyermeket, (g_1) és (g_2),akik azonban csak (b_2) és (b_1) szeretik. Könnyen belátható azonban, hogy ez nem felel meg az előző állításunknak: például ha a világegyetemünk (a fenti b) pont szerint két fiúból (b) és (b ') és egy lányból áll (g) és (b) és (b ') mindkettő szeretni (g), akik mindkettőt szeretik, akkor korábbi állításunk igaz, de a jelenlegi hamis.

[két hasonló ábra, mindkét ábra tetején vízszintes tér választja el egymástól a fiúk és a lányok szavakat. Az (a) ábra bal felső sarkában van a b1 pont, a jobb felső sarokban a g1, a bal alsó részén a b2 és a jobb alsó sarokban a g2 pont látható. A nyilak g1-től b1-ig, b1-től g2-ig, g2-től b2-ig és b2-től g1-ig mutatnak. A (b) ábrán bal felső sarokban van b1, bal alsó sarokban b2, jobb felső sarokban g1. Egy nyíl a b1-re és g1-re, és a b2-re és g1-re mutat.]
[két hasonló ábra, mindkét ábra tetején vízszintes tér választja el egymástól a fiúk és a lányok szavakat. Az (a) ábra bal felső sarkában van a b1 pont, a jobb felső sarokban a g1, a bal alsó részén a b2 és a jobb alsó sarokban a g2 pont látható. A nyilak g1-től b1-ig, b1-től g2-ig, g2-től b2-ig és b2-től g1-ig mutatnak. A (b) ábrán bal felső sarokban van b1, bal alsó sarokban b2, jobb felső sarokban g1. Egy nyíl a b1-re és g1-re, és a b2-re és g1-re mutat.]

Két forgatókönyv, amelyben ((ref {eq: boygirl1})) igaz. Az a) pontban a (z) jelentése egymástól függetlenül választható a (z) közül; ab) pontban nem tudja.

Ugyanakkor nem világos, hogy ezt a feltételt hogyan lehet az elsőrendű logikában formalizálni. Lényegében módosítanunk kellene ((ref {eq: boygirl1})) úgy, hogy (z) ne legyen (x) hatálya, és ennélfogva nem függ tőle; továbbra is azt szeretnénk, ha (z) (y) és (y) (x) -től függ. Amint azt a fentiekben tárgyaltuk, egy ilyen függőségi minta az elsőrendű logikában nem valósítható meg. A kérdést elkerülhetjük a magasabb rendű mennyiségi meghatározás igénybevételével: valóban láthatjuk, hogy ez a kifejezés

) tag {2} label {boygirl2} kezdődik {igazítás} és / létezik F / forall x (fiú (x) jobbra nyíl / létezik y (lány (y) föld / szereti (x, y) föld / fiú (F (y)) föld {} & / quad x / not = F (y) földet szereti (y, F (y)))) vége {igazítás})

megragadja a szándékolt értelmezésünket, de csak a függvények kifejezett egzisztenciális számszerűsítése árán.

Egy lehetséges alternatíva az elsőrendű logika szintaxisának kibővítése a számszerűsített változók közötti függőségi mintákra vonatkozó korlátozások megszüntetése érdekében. Ezt az utat hajtja végre az elágazó kvantitatív logika (Henkin 1961), amelyben a ((ref {boygirl2})) igazságfeltételei megegyeznek a

) tag {3} label {boygirl3} kezdődik {igazítás} & / balra (kezdődik {smallmatrix} forall x & / létezik y \\ / forall z & / létezik w / end {smallmatrix} jobbra) (fiú (x) jobbra nyíl (lány (y) föld / szereti (x, y) föld {} & / quad (y = z / jobbra nyíl (fiú (w) föld x / not = w / földet szeret (z, w))))), / vége {igazítás})

és a függetlenség-barát logika, amelyben a ((ref {boygirl2})) egyenértékű a

) tag {4} label {boygirl4} kezdődik {igazítás} & / forall x / létezik y (fiú (x) jobbra mutató nyíl (lány (y) föld / szereti (x, y) föld (létezik z / x) (fiú (z) föld {} & / quad x / not = z / földet szeret (y, z)))). / vége {igazítás})

Nem adunk itt részletes magyarázatot e két formalizmus szemantikájáról; elegendő azt mondani, hogy a ((ref {boygirl3})) (w) értéke nem függ a (x) és a (y) értékektől (bár függhet az értékétől (z) értékét), mivel a komplex számszerűsítő különböző „soraihoz” tartoznak (balra (kezdődik {smallmatrix} forall x & / létezik y \\ / forall z & / létezik w / end {smallmatrix } jobbra]), míg a ((ref {boygirl4})) (z) értéke nem függ a (x) értékétől, mivel ezt a függőséget kifejezetten „eltörlik” a számszerűsítővel ((létezik z / x)).

Az ábrázoló kvantitatív logika és a függetlenség logika egyik közös vonása, mint láthatjuk, az, hogy nem választják el a változók számszerűsítését a nem szabványos függőségi minták specifikációjától: mint az elsőrendű logika esetében, akkor is, ha számszerűsített A (v_1) változó függ vagy nem függ más kvantitatív változótól (v_2) a mennyiségi meghatározók megfelelő pozíciója és formája alapján.

A függőségi logika más megközelítést alkalmaz az elsőrendű logika kibővítésének problémájára annak ábrázolása érdekében ((ref {boygirl2})). A ((ref {eq: boygirl1})) -hez képest az egyetlen új feltétel az, amely kimondja, hogy a (z) értékét a (vagyis funkcionálisan függő) érték határozza meg a (y); és ez megfelel egy új atomi feltételnek (eqord (y, z)), úgynevezett függőségi atomnak, amelynek szándékolt jelentése, hogy (a) (z) értéke a (y) érték függvénye). Az elágazó kvantitatív logika és a függetlenség-logika eseteitől eltérően ez a (y) és (z) értékek fölötti feltétel, nem pedig a számszerűsítő viselkedésének feltétele (létezik z): valójában általában nincs ok arra, hogy a (z) egy számszerűsített változó egyáltalán legyen, inkább szabad változó lehet,vagy néhány összetett kifejezés, amely több változót foglal magában.

A függőségi logikában a ((ref {boygirl2})) formázható mint

) tag {5} label {boygirl5} kezdődik {igazítás} & / forall x / létezik y / létezik z (eqord (y, z) föld (fiú (x) jobbra nyíl (lány (y)) földet szeret (x, y) jobbra mutató {} & / quad (fiú (z) földet x / nem = z / földet szeret (y, z))))) vége {igazítás})

A ((ref {boygirl2})), ((ref {boygirl3})), ((ref {boygirl4})) és ((ref {boygirl5}) igazságfeltételei) pontosan ugyanazok: bármelyik modell, amely kielégíti ezen kifejezések egyikét (az adott nyelven) kielégíti mind a négyet. Általánosabban, amint látni fogjuk, az egzisztenciális másodrendű logika, a függetlenség-barát logika és a függőségi logika kifejező képességei a modellosztályok definiálhatóságát illetően pontosan ugyanazok. Ez azonban nem érvényes a szabad változókat tartalmazó képletekre; és ezen túlmenően, ezek a logikák kibővíthetők és módosíthatók jelentősen különböző vonal mentén.

2. A csapat szemantikája

A csapatszemantika, amelyet először Wilfrid Hodges fejlesztett ki a függetlenség-barát logika keretében (Hodges 1997), Tarski szemantikájának általánosítása az elsőrendű logika számára az elemek többszörös kiosztása esetén a változókhoz. Az ilyen feladatok halmazai, amelyeket történeti okokból csapatoknak neveznek, képezik a csapat szemantika alapvető szemantikai fogalmát, és a képletek elégedettek vagy nem elégedettek rájuk, nem pedig az egyes feladatokra. A csapatszemantika és a Tarski szemantika kapcsolatát a következő eredmény mutatja, amely a függőségi logikában és az összes elsőrendű változatában is érvényes:

Fenntarthatóság:

Az elsőrendű képletet a csoport (X) (a csapat szemantikája értelmében) akkor és csak akkor teljesíti, ha az összes feladat (az X-ben X) kielégíti azt (Tarski szemantika értelmében).

Általánosabban: a csapatokat úgy lehet megérteni, mint egy hitkészletet, amely képviseli a világ összes államát (= feladatokat), amelyeket egyes ügynökök lehetségesnek tartanak. Akkor (X) csapat akkor teljesíti valamilyen képletet (phi), ha és csak akkor, ha (phi) tart, ha (X) az összes lehetséges állapot halmaza; és ebben az esetben a következőt fogjuk írni: (X / modellek / phi) (vagy (M, X / modellek / phi), ha a modell választása nem egyértelmű). Ebben a részben megvizsgáljuk a csapat szemantikájának szabályait és értelmezését ezen elv szempontjából; majd a következő részben megvitatjuk, hogy ez hogyan alakul ki a függőség logikájának hiányos információs játék-elméleti szemantikájából is.

Az új függőségi atomok feltétele (eqord (x_1 / ldotok x_n, y)), amelyek megfelelnek annak a kijelentésnek, hogy (y) értéke a ((x_1 / ldots x_n) értékének függvénye), könnyen érthető:

TS-dep:

(X / modellek ~ / eqord (x_1 / ldots x_n, y)) akkor és csak akkor, ha bármelyik két feladat (s_1, s_2 / X-ben), amelyek megegyeznek a (x_1 / ldots értékeiben x_n) megegyeznek a (y) értékben is.

Tegyük fel például, hogy (X) a három változóhoz tartozó (x_1), (x_2) és (y) kiosztások halmaza, ahol (x_1) a jelölt nemzetiségét jelöli. egy pozíció, (x_2) képviseli pontszámukat (egy megfelelő értékelési módszer szerint) és (y) azt jelzi, hogy elfogadták-e vagy elutasították-e őket. Akkor az atom ((eqord (x_2, y))) megfelel annak az állításnak, hogy az ajánlatot kizárólag a pontszám határozza meg: ha két jelöltnek azonos pontszáma van, pontosan ugyanazt az ajánlatot kapják, bármilyen egyéb tényezõtõl függetlenül. A függőség atomjának különleges esetét az állandósági atomok (eqord (y)) adják, amelyeket - a fenti szemantika szerint - akkor felel meg a csapat, ha és csak akkor, ha az összes feladat megegyezik a (y).

) kezdő {tömb} {l | ccc} textbf {hozzárendelés} & / mathbf {x_1} & / mathbf {x_2} & / mathbf {y} / \ hline s_0 & 0 & 0 & 0 \\ s_1 & 0 & 1 & 1 \\ s_2 & 1 & 0 & 1 \\ s_3 & 1 & 1 & 2 / end {array})

1. táblázat: Az a csapat (X), ahol (y = x_1 + x_2). Itt a (y) (x_1) és (x_2) függvénye, tehát (= \! \! (X_1 x_2, y)) tart; a (y) azonban nem csak a (x_1) függvénye, tehát a (= \! \! (x_1, y)) nem érvényes.

Ugyanezen értelmezés szerint az elsőrendű literálok és konjunkciók szabályai (az egyszerűség kedvéért feltételezzük, hogy kifejezéseink normál formában tagadják, és a szokásos módon feltételezzük, hogy a függőségi atomok negatívumai soha nem teljesülnek). könnyen levezethető:

TS világít:

Az összes elsőrendű literál esetében ((alfa), (X / modellek / alfa) csak akkor, ha az összes hozzárendelésnél (s / X-ben), (s / model / alpha) a szokásos Tarski szemantika értelmében;

TS - (föld):

(X / modellek / phi / land / psi) akkor és csak akkor, ha (X / modellek / phi) és (X / modellek / psi).

Érdemes megemlíteni, hogy amint ezekből a szabályokból már láthatjuk, a kirekesztett középső törvénye nem tartja fenn a függőség logikáját (csakúgy, mint a függetlenség barátságos logikája): például ha egy csapat (X) egyaránt tartalmaz feladatokat (s) (s (x) = s (y)) és (s ') (s' (x) not = s '(y)) majd (X / not / modellek x = y) és (X / not / modellek x / not = y). Ebben a szakaszban mindenképpen bemutatjuk a függőség logikájának nyelvét kifejezett tagadási operátor nélkül; majd később megvitatjuk annak nyelvéhez való hozzáadásának következményeit.

Mi lenne az egyetemes mennyiségi meghatározással? Milyen körülmények között kell egy csoportban egy univerzálisan számszerűsített kifejezést (forall v / psi) tartani? Emlékeztetnünk kell még arra az intuícióra, miszerint egy csapat képviseli a dolgok lehetséges állapotát. Ha értékelni akarjuk (forall v / psi), akkor milyen dolgok állapotát kell értékelnünk (psi)? A természetes válasz az, hogy a dolgok minden olyan állapotát figyelembe kell venni, amely különbözik a (X) -ben szereplőktől, csak a (v) érték szempontjából. Ez indokolja a következő szabályt:

TS - (forall):

(X / modellek / forall v / psi) akkor és csak akkor, ha (X [M / v] modellek / phi), ahol (X [M / v]) a ({s ': / létezik s / az X / mbox {st} s' / sim_v x }) halmazban

ahol (s '\ sim_v s) azt jelenti, hogy a (s) és (s') két feladat legfeljebb (v) változó értéke szempontjából különbözik egymástól.

[X = / kezdődik {tömb} {l | c} textbf {hozzárendelés} & x \\ / hline s_0 & 0 \\ s_1 & 1 / vége {tömb} jobbra mutató nyíl X [HH / I] = / kezdődik {tömb} {l | c | c} textbf {hozzárendelés} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 \\ s'_3 & 1 & 1 / end {tömb})

2. táblázat: (X) és (X [M / y]) két elemmel, (0) és (1).

Most mérlegeljük a disjúciót. Mikor kell tartani (phi / lor / psi)? Erre a válaszra emlékeztetünk még egyszer: a csapatokat a lehetséges állapotállapotok halmazának lehet értelmezni, és ezért a (Y) és (Z) csapatok egyesülése minden olyan állapotot képvisel, amely a akkor fordul elő, ha (Y) vagy (Z) van ilyen. Ezért, ha a (phi) és (psi) két képletet kielégíti a csoportok: ({Y_1 / ldots Y_n, / ldots }) és ({Z_1 / ldots Z_n, / ldots }), diszjunktúrájukkal (phi / lor / psi) a csapathalmaznak kell teljesülnie ({Y_i / cup Z_j: i, j / in 1, / ldots }), vagy ezzel egyenértékűen

TS - (lor):

(X / modellek / phi / lor / psi) akkor és csak akkor, ha (X = Y / kupa Z) két csapat számára (Y) és (Z) oly módon, hogy (Y / modellek / phi) és (Z / modellek / psi).

Érdemes itt kiemelni, hogy általában nem követeljük meg, hogy (Y) és (Z) egymástól függetlenek legyenek. A lefelé mutató záró tulajdonság miatt, amelyet hamarosan megvitatunk, ez a kiegészítő feltétel nem változtatna a függőségi logika szemantikájában; de a függőségi logika bizonyos kiterjesztései és variációi esetében ez a kiegészítő követelmény ellentétes lenne a lokalitás elvével, amely szerint egy kifejezés elégedettségének feltételei csak a benne szabadon felmerülő változók értékétől függenek (Galliani 2012).

Fontos megjegyezni, hogy a függőség logikájában a diszjunkció nem idempotáns: például a (eqord (x, y) lor / eqord (x, y)) nem egyenértékű a (eqord (x), y)), és egy (X) csapat akkor és csak akkor elégedett, ha minden olyan három feladat esetében, amelyben a (z) (x) egyetértésben vannak legalább három, legalább két kettő megegyezik a (y). Ez kissé ellentmondásosnak tűnik; de ez egyértelmű következménye annak, hogy értelmezésünk szerint a (eqord (x, y) lor / eqord (x, y)) -ot úgy kell értelmezni, hogy „a dolgok minden lehetséges állapota az egyik a dolgok két halmaza, és mindkettőben (y) (x) függvénye”. Mivel a funkciók egyesítése általában nem funkció, nem meglepő, hogy a függőség logikájában való diszjunktúra nem büntetlen.

Végül megvizsgáljuk az egzisztenciális számszerűsítés esetét. Mikor teljesíti a csapat a (létezik v / psi) kifejezést? Ennek megválaszolásához kezdhetjük azzal a korlátozási operátor értelmezésével, amely bármelyik csapat számára ((X)) eredményez egy (X _ { backslash v}) csapatot, amelyet az (v változó eltávolításával kapunk.) (ha van) az összes hozzárendelésből (s / X-ben) (majd, mivel (X) egy halmaz, azonos hozzárendelések összecsukásával). Ezt egy elfelejtő műveletként lehet értelmezni, amelyen keresztül töröljük az (v) értékére vonatkozó összes információt - például azért, mert az, amit ezen az értékben hittünk, megbízhatatlan volt, vagy azért, mert ez az érték megváltozott. Tegyük fel, hogy (X _ { backslash v} = Y _ { backslash v}): akkor értelmezésünk szerintez azt jelenti, hogy a (X) és (Y) által képviselt lehetséges állapotok halmaza legfeljebb eltér a (v) érték tekintetében. Tehát, ha (Y) teljesíti a (phi) feltételt, akkor azt mondhatjuk, hogy (X) teljesíti (phi), ha nem (y) értékre, vagy ezzel egyenértékûen, hogy (X) kielégíti (létezik v / psi). Ez indokolja a következő szabályt:

TS - (létezik):

(X / modellek / létezik v / psi) akkor és csak akkor, ha létezik valamilyen (Y), a (X) és (v) változók felett, oly módon, hogy (X _ { visszajelzés v} = Y _ { visszajelzés v}) és (Y / modellek / psi).

Egyértelmű ellenőrizni, hogy ez a helyzet-e, csak akkor, ha (Y) (X [F / y] = {s [a / y]: s / ben X, a / F-ben (s) }) bizonyos funkciókhoz (F), az (X) -ben szereplő hozzárendelésektől a modellünk nem-üres elemek halmazáig.

Érdemes megemlíteni, hogy a fenti meghatározás általánosságban nem követeli meg, hogy a (X) és (Y) azonos számú hozzárendelést tartalmazzon: az (X) -ben szereplő egyetlen hozzárendelés többnek is megfelelhet hozzárendelések (Y) -ben, és -ha (v) már egy változó, amely előfordul a (X) hozzárendeléseknél - az (Y) egyetlen hozzárendelése is megfelelhet több feladatnak a (X)).

[X = / kezdődik {tömb} {l | c} textbf {hozzárendelés} & x \\ / hline s_0 & 0 \\ s_1 & 1 / vége {tömb} jobbra mutató nyíl X [F / y] = / kezdődik {tömb} {l | c | c} textbf {hozzárendelés} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 / end {array})

3. táblázat: (X) és (X [F / y]) a (F (s_0) = {0,1 }), (F (s_1) = {0 })

A függőség logika tulajdonságainak alapos megvitatását a játék-elméleti szemantika meghatározása után elhalasztjuk. Ezt a részt a fenti szabályok következő három fontos következménnyel zárjuk le:

Helység:

Ha a (z) (X) és (Y) korlátozások a (phi) -ben ingyenesen előforduló változókra azonosak, akkor (X / modellek / phi) akkor csak akkor, ha (Y / modellek / phi).

Lefelé történő bezárás:

ha (X / modellek / phi) és (Y / subseteq X), akkor (Y / modellek / phi).

Üres beállított tulajdonság:

Ha (emptyset) a hozzárendelés nélküli csapat, akkor (emptyset / models / phi) az összes függőségi logikai képlethez (phi).

A lokalitás elve, valamint a szakasz elején említett konzervativitás elve fontos „józan állapotot” jelent, amelyet a függési logika bármely változatának és kiterjesztésének meg kell felelnie. Ugyanez nem mondható el a lefelé történő bezárásról és az üres halmaz tulajdonságáról, amelyeket - mint látni fogunk - megsértnek a függőségi logika variánsai.

Végül meg kell határoznunk egy függőség logikai mondatának az igazságát egy modell szempontjából. Mivel egy mondatnak nincsenek szabad változói, a lokalitás elve szerint egyszerre azt mondhatjuk, hogy vagy az összes nem bátorságos csapat kielégíti azt, vagy egyetlen bölcs csapat sem teljesíti azt. Ez analóg a Tarski szemantikájának esetével, amikor egy mondatot vagy minden változó feladat kielégíti, vagy egyik sem teljesíti. Így az igazságot a szokásos módon definiálhatjuk:

Igazság a csapat szemantikájában:

A (phi) mondat igaz a modellben (M), ha és csak akkor, ha (M, { emptyset } modellek / phi), ahol ({ emptyset }) az a csapat, amely csak az üres feladatot tartalmazza. Ebben az esetben azt írjuk, hogy (M / models / phi).

2.1 Játék-elméleti szemantika

Mint már említettük, a függőségi logika játék-elméleti szemantikája a függetlenség-barát logika tökéletlen információ-szemantikájának egy változata, amely maga az elsőrendű logika játékteoretikus szemantikájának adaptációja. Hivatkozunk az olvasóra a Väänänen 2007a-hoz, hogy formálisan, részletesen meghatározza ezt a szemantikát.

A játék-elméleti szemantika során a (phi) mondat és a modell (M) megfelel a (általában kétjátékos) játéknak (G_M (phi)). Akkor az igazságot úgy kell meghatározni, hogy létezik-e egy játékos nyerési stratégiája (akit ebben a műben egyszerűen „Player (0)” -nek neveznek): más szóval, ha (sigma_0) a (valószínűleg nem determinisztikus) stratégia a Player (0) és (Pi (G_M (phi), / sigma_0)) számára az összes lejátszás halmaza, amely kompatibilis a (sigma_0), majd a (phi) igaz akkor és csak akkor, ha a (Pi (G_M (phi), / sigma_0)) összes játékban megnyerik a Player (0) játékot. A játékról (G_M (phi)) két játékos között folytatott vitaként gondolhatunk, amelyek közül az egyik (Player (0)) azt akarja demonstrálni, hogy ez a helyzet a (phi) míg a másik (Player (1)) azt akarja demonstrálni, hogy nem ez a helyzet (phi).

Mint az elsőrendű logika és a függetlenség-logika esetében, a függőségi logika tökéletlen információs játékában a játék pozíciói párban vannak ((theta, s)), ahol (theta) egy (phi) alformula példánya (vagyis a (phi) alformulájával azonos kifejezés többszörös előfordulásait külön kell figyelembe venni) és (s) egy változó hozzárendelés a modell (M). [1] A kezdeti pozíció: ((phi, / emptyset)), ahol (emptyset) az üres hozzárendelés; és egy nemdeterminisztikus stratégia (sigma_0) a Player (0) számára, minden diszjuncióra és egzisztenciális számszerűsítésre kiválasztja az aktuális pozíció egy vagy több utódját a következő szabályok szerint:

  • Ha a jelenlegi helyzet formája ((psi / lor / theta, s)), akkor annak utódjai a következők: ((psi, s)) és ((theta, s));
  • Ha az aktuális pozíció ((létezik v / psi, s)), akkor annak utódjai mind ((psi, s ')) pozíciók (s' / sim_v s).

Hasonlóképpen a ((psi / land / theta, s)) utódjai ((psi, s)) és ((theta, s)), valamint a ((forall v / psi, s)) a ((psi, s ')) űrlap minden pozíciója (s' / sim_v s) számára; de a Player (0) stratégiája nem határozhat meg utódot ezekre a pozíciókra, mivel feltételezzük, hogy a Player (1) kiválasztja, melyik pozíció követi őket.

A pozíciósorozatok (overline / rho = / rho_0 / rho_1 / ldots / rho_n) (G_M (phi)) játék csak és csak akkor, ha

  1. (rho_0 = (phi, / emptyset));
  2. Minden (i = 1 / ldots n) esetén (rho_ {i}) a (rho_ {i-1}) utódja.

Ha ezenkívül (rho_ {i + 1} a / sigma_0 (rho_i)) -ben, ha (rho_i) diszjunciónak vagy egzisztenciális számszernek felel meg, akkor azt mondjuk, hogy (overline / rho) tiszteletben tartja a stratégia (sigma_0); és amint említettem, (Pi (G_M (phi), / sigma_0)) írunk az összes, (G_M (phi)) feletti lejátszás halmazára, amely tiszteletben tartja a (sigma_0).

Azt mondjuk, hogy egy stratégia (sigma_0) nyer, ha minden játék (overline / rho) olyan helyzetben végződik, ahol ((alfa, s)) ahol (alfa) egy első a sorrend szerinti olyan, hogy az (s) feladat kielégíti (alpha) értéket Tarski szemantikájának szokásos értelmében. A függőségi atomok - és a függőségi atomokkal végződő játékok - nem relevánsak annak eldöntésében, hogy egy adott stratégia nyer-e. Ezeket azonban arra használják, hogy meghatározzák, hogy egy adott stratégia egységes-e:

Egységesség feltétele

A (G_M (phi)) stratégiája (sigma_0) egységes, ha bármelyik játszik (overline / rho, / overline / gamma / in / Pi (G_M (phi), / sigma_0)) amelyek két pozícióban végződnek ((eqord (x_1 / ldots x_n, y), s)), ((eqord (x_1 / ldots x_n, y), s ')) ugyanarra a példányra a függőségi atom (eqord (x_1 / ldots x_n, y))

) textrm {If} s (x_1) ldots s (x_n) = s '(x_1) ldots s' (x_n) textrm {then} s (y) = s '(y).)

Akkor az alábbiak szerint definiálhatjuk az igazságot a játék-elméleti szemantikában:

Az igazság a játék-elméleti szemantikaban:

A (phi) mondat igaz a modellre (M) (a játék-elméleti szemantika vonatkozásában) akkor és csak akkor, ha a Player (0) egységes nyerési stratégiával rendelkezik a (G_M (phi)).

Megmutatható, hogy ez a fogalom egyenértékű az igazság fogalmával a csapat szemantikájában. Valójában ennél többet is meg tudunk mutatni. Ha bármelyik csapatnak (X) és a képletnek (phi) a (G_ {M, X} (phi)) játékot (G_M (phi)) formátumban játsszák, de a a ({(phi, s): s / az X } -ben) véletlenszerűen kiválasztott kezdeti pozíciót minden lejátszáshoz, majd a következő áll fenn:

A GTS és a csapat szemantikájának egyenértékűsége:

A (phi) képletet akkor teljesíti a csapat (X) (a modellhez (M) vonatkoztatva), ha és csak akkor, ha a (0) játékos egységes nyertes stratégia itt: (G_ {M, X} (phi)).

Ez az eredmény félreértve világossá teszi, hogy a függőségi logika csapatszemikája miért felel meg az üres készlet tulajdonságnak és a lefelé mutató zárási tulajdonságnak. Valójában, ha (X = / emptyset), akkor a (G_ {M, X} (phi)) Player (0) játékosra vonatkozó minden stratégiája triviálisan nyer és egységes; és ha (X / subseteq Y), akkor a (G_ {M, X} (phi)) játékosban egységes nyerési stratégia a (0) játékosnak is egységes nyerési stratégia a (0) játékos számára. itt: (G_ {M, Y} (phi)).

3. Tulajdonságok

3.1 Expresszivitás

A mondat szempontjából a függőségi logika ekvivalens a másodrendű logika egzisztenciális töredékével (Sigma_1 ^ 1). Pontosabban bizonyítható (Väänänen 2007a), hogy

A függőség logikájának és (Sigma_1 ^ 1) mondatban kifejezett egyenértékűsége:

Minden függőségi logikai mondatra (phi) létezik egy (Sigma_1 ^ 1) mondat (phi ^ *), amely szerint

) tag {6} label {eq: DLESO} M / modellek / phi / Leftrightarrow M / modellek / phi ^ * / textrm {minden modellnél} M.)

Hasonlóképpen, minden (Sigma_1 ^ 1) mondathoz (phi ^ *) létezik olyan függési logikai mondat (phi), amelyet ((ref {eq: DLESO})) tart.

Mivel Fagin-tétel (Fagin 1974) azt mutatja, hogy a véges modellek tulajdonsága meghatározható (Sigma_1 ^ 1) -ben csak akkor, ha a polinomiális időben felismerhető egy nemdeterminisztikus Turing-gép (vagyis akkor és csak akkor, ha az NPTIME-ben), rögtön következik

Függőségi logika és NPTIME:

Minden függőségi logikai mondatra (phi) az összes véges modell, amely kielégíti azt, az NPTIME osztályba tartozik. Ezenkívül a véges modellek bármelyik NPTIME osztályához (matematikai K) létezik olyan függőségi logikai mondat (phi), amelyben (M / modellek / phi) akkor és csak akkor, ha (M / in / matematikai K).

A függőségi logika és a ((Sigma_1 ^ 1)) mondatok szintű ekvivalenciájának másik közvetlen következménye az, hogy a kompaktság tétel és a Löwenheim-Skolem tétel mind a függőség logikájára vonatkozik (Väänänen 2007a):

Kompaktivitás:

Ha a véges függőség logikai mondatok halmaza (Phi) egyetlen modellben sem kielégíthető, akkor annak néhány véges részhalmaza (Phi_0 / subseteq_f / Phi) már nem kielégítő.

Löwenheim-Skolem tétel:

Ha egy függőség logikai mondatnak végtelen modellje van, akkor az minden végtelen kardinalitás modelljéhez tartozik.

Ugyanakkor a kérdések kényesebbek, ha a szabad változókat tartalmazó képletekről van szó. Ezután meg lehet mutatni (Kontinen és Väänänen 2009), hogy a függőségi logika megfelel az egzisztenciális másodrendű logika lefelé zárt részének:

Csapat definiálhatóság a függőségi logikában

A csoportok (matematikai X) modelljei (M) és a változók halmaza ((V)) formája ({X: M, X / modellek / phi }) valamilyen függőségi logikai képlethez (phi), szabad változókkal a (V) fájlban, csak akkor, ha

  1. (matematikai X) nem üres;
  2. (mathcal X) lefelé van bezárva, vagyis (Y / subseteq X / in / mathcal X / Rightarrow Y / in / mathcal X);
  3. (mathcal X) (Sigma_1 ^ 1) - meghatározható (M) -ban, vagyis létezik egy ((Sigma_1 ^ 1) mondat (Psi (R)), a (M) szókincsén, valamint az új (| V |) - ary reláció szimbólumon (R) úgy, hogy

    [X / in / mathcal X / textrm {csak akkor, ha} M, / textrm {Rel} (X) modellek / Psi (R))

    ahol (textrm {Rel} (X)) a (| V |) - ary kapcsolat ({s (V): s / az X }), amely megfelel a csapatnak (X).

3.2 Hierarchiák a függőségi logikában

A Durand & Kontinen 2012-ben megvizsgálták a függőségi atomok függő változóinak vagy az univerzális számszerűsítők számának korlátozásának hatását. Megmutatták, hogy a függőségi logika töredékeinek mindkét meghatározási módja hierarchiákat idéz elő:

  • Minden (k) esetében legyen (mathcal D (k- / forall)) függési logika, amely legfeljebb (k) univerzális mennyiségi mutatókra korlátozódjon, és (mathcal D (k-dep)) legyen függőségi logika, a (eqord (vec x, y)) függőségi atomjaira korlátozva (| / vec x | / leq k) függőségi atomjaira. Azután

    ) kezdje {igazítsuk ki}} matematikai D (k- / forall) és <\ matematikai D (k + 1-dep), \\ / mathcal D (k- / forall) & / leq / matematikai D (k- dep) leq / matematikai D (k + 1 - dep) vége {igazítás *})

    és

    ) matematikai D (k- / forall) <\ mathcal D (2k + 2 - / forall))

    a mondatok kifejező erejét illetően.

3.3 tagadás a függőségi logikában

Eddig feltételeztük, hogy az összes függőség logikai kifejezés negatív normál formában van, és hogy a függőségi atomokat soha nem tagadják meg. Másrészről kissé problematikus az explicit tagadási operátor hozzáadása a függőség logikájának nyelvéhez, mivel az egzisztenciális másodrendű logika nem tagadás alatt áll. Valójában a „nyilvánvaló” tagadási szabály

[X / modellek / sim / phi / textrm {akkor és csak akkor, ha} X / not / models / phi)

jelentősen növeli a függőség logikájának kifejező erejét, kiterjesztve azt a csapat logikára (Väänänen 2007a, b), amely nagyon erős értelemben egyenértékű a teljes második rendű logikával (Kontinen & Nurmi 2009).

Egy kevésbé erős, „kettős” tagadást (lnot) de Morgan szabályaival lehet meghatározni, (lnot (phi / lor) land] psi) equiv (lnot / phi) land) lor] (lnot / psi)) és (lnot (létezik v) forall v] phi) equiv / forall v) létezik v] (lnot / phi)), valamint a a kettős tagadás (lnot / lnot / phi / equiv / psi) törvény és a szabály

[X / modellek { lnot / eqord} (vec x, y) textrm {akkor és csak akkor, ha} X = / emptyset)

a függőségi atomok negatívumaira (Väänänen 2007a, b). Az eredményül kapott nyelv kifejezetten egyenértékű a tagadásmentes függőségi logikával, és valójában a Väänänen 2007a függőségi logikájának leírása szerint ez a tagadás a nyelv része; ugyanakkor, amint azt a Kontinen és Väänänen 2011-ben is kimutatták, a függőségi logikai formula és annak tagadásának elégedettségi feltételei kevés kapcsolatban állnak egymással. Pontosabban:

Kettős tagadás és függőségi logika:

Bármely olyan függőségi logikai képletnek (phi) és (psi), amelynél a (phi / land / psi) nem teljesíthető, létezik függőségi logikai képlet (theta) úgy, hogy

[M, X / modellek / theta / textrm {csak akkor, ha} M, X / modellek / phi)

és

[M, X / modellek / nem lehet / theta / textrm {csak akkor, ha} M, X / modellek / psi)

minden modellhez (M) és a csapathoz (X).

Tehát általánosságban semmit nem lehet mondani a (phi) kettős tagadásáról, azzal a különbséggel, hogy ez valamilyen függési logikai kifejezéssel egyenértékû, amelyet egy olyan csapat sem elégedett, amely kielégíti a (phi) elemet. Mivel, mint már említettük, a kirekesztett középső törvény nem működik a függőség logikájában, ez nem nagyon informatív tulajdonság; Különösen a függőségi logikában (kettős tagadással) lehet ekvivalens kifejezéseket találni nem ekvivalens negatívumokkal, mint például a (x / not = x / föld y / not = y) és (lnot / eqord (x, y)).

3.4 Igazság, érvényesség és bizonyítási rendszerek a függőség logikájában

A függetlenség logikájához hasonlóan a függőség logika meghatározhatja saját igazságkezelőjét (Väänänen 2007a), vagyis ha minden képletre (phi) van, hogy (lceil / phi / rceil) a Gödel-szám, (phi), akkor találunk egy képletet (tau (x)), amelynek (x) az egyetlen szabad változója, így

[M / modellek / phi / textrm {csak és akkor, ha} M / modellek / tau (lceil / phi / rceil))

minden olyan modellel (M), amely megfelel a Peano természetes számok axiómájának. Ez nincs ellentmondásban Tarski meghatározhatatlanságának tételével, mivel a függőségi logika ellentmondásos tagadás alatt nem záródik le.

A függőségi logikai mondat érvényességének (vagyis minden modellben igaz) eldöntésének problémája nem aritmetikai, és a Levy hierarchia (Pi_2) osztályához viszonyítva teljes. Ennek ellenére a függőség logikájának bizonyított elméletét tanulmányozták. Különösen a Kontinen & Väänänen 2013-ban egy megbízható és teljes bizonyítási rendszert fejlesztettek ki a függőségi logika elméletének elsőrendű következményeinek felkutatására.

4. A függőségi logika variánsai

Ebben a részben röviden összefoglaljuk a függőségi logika leginkább tanulmányozott változatainak tulajdonságait. Sok ilyen változat létezik, és sok munkát végeztek osztályozásukkal és összehasonlításukkal. Ebben a munkában csak azokat a változatokat említjük, amelyek különös jelentőséggel bírnak a függőségi logikával való kapcsolat miatt.

4.1 Függetlenség logika

Az elsőrendű logika függőségi atomokkal történő kiterjesztése helyett (eqord (vec x, y)), a függetlenség logika (Grädel és Väänänen 2013) kiterjeszti függetlenségi atomokkal (vec x / mathop { bot _ { vec z }} vec y), amelynek értelmezése „a (vec z) bármilyen lehetséges választására vonatkozik, a (vec x) és (vec y) lehetséges értékei függetlenek” -in Más szavakkal, ha a (vec z) rögzített választást kap, a (vec x) által megfogalmazott érték ismerete nem ad információt a (vec y) által vett értékről. Ez egy jelentős fogalmi jelentőségű fogalom: például ki lehet fejezni, hogy ha nem ismeri a titkosítási kulcsot - akkor az üzenet titkosított verziójának látása nem tartalmaz információt a megfelelő tiszta szövegű verzióról. Ha (x) jelzi a titkosított üzenetet, és (y) a sima szöveget jelenti,akkor ez megfelel a (x / mathop { bot} y) feltételnek, ahol (vec z) ebben az esetben üres. Hasonlóképpen, ha (k) képviseli a kulcsot, akkor (x / mathop { bot} k) azt az állítást képviseli, hogy a kulcs nem vonható le a titkosított üzenetből; és a (eqord (k, x, y)) (amely, amint látni fogjuk, a függetlenség logikájában ábrázolható) kötődésfüggőség atomja azt az állítást képviseli, hogy a sima szöveges üzenet dekódolható a titkosított üzenethez és a kulcsot.ábrázolható függetlenségi logikában) azt az állítást képviseli, hogy a sima szöveges üzenet dekódolható a titkosított üzenet és a kulcs alapján.ábrázolható függetlenségi logikában) azt az állítást képviseli, hogy a sima szöveges üzenet dekódolható a titkosított üzenet és a kulcs alapján.

A független atomok elégedettségére vonatkozó szabályt formálisan a következőképpen lehet megadni:

TS-indep:

(M / models_X / vec x / mathop { bot _ { vec z}} vec y) csak akkor, ha az összes (s, s '\ X-ben) és (s (vec z) = s '(vec z)) létezik egy (s' '\ X-ben), ahol (s' '(vec z \, / vec x) = s (vec {x }, / vec {z})) és (s '' (vec y) = s '(vec y)).

) kezdő {tömb} {l | ccc} textbf {hozzárendelés} & / mathbf {x_1} & / mathbf {x_2} & / mathbf {x_3} / \ hline s_0 & 0 & 0 & 0 \\ s_1 & 0 & 1 & 1 \\ s_2 & 1 & 0 & 1 \\ s_3 & 1 & 1 & 0 / end {array})

A függetlenség logikája szigorúan kifejezőbb, mint a függőség logika: valójában hiányzik a lefelé mutató zárási tulajdonság, és a (eqord (vec x, y)) függőségi atom egyenértékű a (y / mathop { bot_) függetlenségi atommal. { vec x}} y). Ezenkívül azt is kimutatható (Galliani és Väänänen 2014), hogy a kondicionált függetlenségi atomok (vec x / mathop { bot _ { vec y}} vec z) meghatározhatók a feltétel nélküli függetlenségi atomok (vec x / mathop { bot} vec y).

A mondat szempontjából a függetlenség logika egyenértékű az egzisztenciális másodrendű logikával is (Sigma_1 ^ 1); de a formula szempontjából kifejezőbb és kifejezőbb, és a Galliani 2012-ben kimutatták, hogy képes rögzíteni az összes nem (Sigma_1 ^ 1) - meghatározható csapattulajdonságot.

4.2 Befogadási logika

Az inklúziós logika (Galliani 2012, Galliani & Hella 2013) kibővíti az elsőrendű logikát inkluzív atomokkal (vec x / subseteq / vec y), emlékeztetve az adatbázis-elmélet inklúziós függőségeire. Szemantikája:

TS-inc:

(M / modellek_X / vec x / subseteq / vec y) akkor és csak akkor, ha az összes (s / X-ben) létezik olyan (s '\ X-ben), hogy (s (vec x) = s '(vec y)).

) kezdő {tömb} {l | cc} textbf {hozzárendelés} & / mathbf {x_1} & / mathbf {x_2} / \ hline s_0 & 0 & 0 \\ s_1 & 0 & 1 \\ s_2 & 1 & 2 \\ s_3 & 2 & 3 / end {tömb})

A függőség és a függetlenség logikájától eltérően az inklúziós logika (mondat-bölcs) szigorúan gyengébb, mint az egzisztenciális másodrendű logika. Valójában kimutatható (Galliani és Hella 2013), hogy egyenértékű a legnagyobb rögzített pont logika pozitív töredékével, és ezért a modellek PTIME tulajdonságait a véges sorrendű modellekhez viszonyítva rögzíti. A képlet szempontjából az inklúziós logika szigorúan gyengébb, mint a függetlenség logikája, de összehasonlíthatatlan a függőségi logikával: valójában a képletek kielégítési feltételei nem lefelé vannak zárva, hanem szakszervezetek zárják őket abban az értelemben, hogy

[M, X_i / modellek / phi / forall i / in I / Rightarrow M, / bigcup_i X_i / models / phi.)

4.3 Csapat logika

A csapat logika (Väänänen 2007a, b; Kontinen és Nurmi 2009) kiterjeszti a függőség logikáját azzal, hogy ellentmondásos tagadást ad hozzá (lnot). Egyenértékű a teljes második rendű logikával, mind a modellek definiálhatóságának szempontjából (Väänänen 2007b), mind a csapatok azon osztályai tekintetében, amelyeket a team logikai kifejezések egy adott modellhez viszonyítva meghatározhatnak (Kontinen & Nurmi 2009)..

4.4 Intuicionista függőségi logika

Az intuitív függőségi logika (Abramsky és Väänänen 2009; Yang 2013) kiterjeszti a függőségi logikát egy impliciációs összekötő (phi / jobbra nyíl / psi) hozzáadásával, amelynek elégedettségi szabályait a csapat szemantikája adta

TS - (jobbra nyíl):

(X / modellek / phi / jobbra nyíl / psi) csak akkor, ha (X) minden részhalmaza (Y), ha (Y / modellek / phi) majd (Y / modellek / psi).

Ezt az operátort „intuitív implikációnak” hívják, mert szemantikája és a Kripke intuitív logika szemantikájának implikációs operátora hasonlósága miatt hasonlít egymáshoz (Kripke 1965). Értelmezése a meggyőződés szempontjából meglehetősen egyszerű: ha a (X) -ben megadott feladatok olyan dolgok állapotát képviselik, amelyet egyes ügynökök lehetségesnek tartanak, akkor a (X) alcsoport (Y) egy hitelesítés, amelyben az ügynök elutasítja a korábban feltételezett esetleges állapotokat, és (phi / rightarrow / psi) állapotok, mint bármely olyan frissítés, amely a (phi) megtartását idézné elő, (psi) tartani. Ebből a szempontból ez egy nagyon természetes koncepció, amely lehetővé teszi számunkra, hogy leírjuk azokat az előrejelzéseket, amelyek szerint egy ilyen ügynök általános hitállapota reagálna a hit frissítésére.

Ugyanakkor a szemantikájában rejtett második rendű univerzális számszerűsítés miatt ez az összekötő elem elegendő ahhoz, hogy jelentősen megnövelje a logika kifejező komplexitását: különösen, amint azt Yang 2013-ban megmutatta, a második rendű logika bármelyik mondata egyenértékű az intuitív függőség valamilyen mondatával. logika. Az intuíciós függőségi logika megtartja a lefelé mutató bezárási tulajdonságot: ha egy csapat kielégíti az intuitív függőségi logikai képletet, akkor tegye meg az összes részhalmazt.

4.5 Propozicionális függési logika

Az eddig vizsgált függőségi és függetlenségi atomok kifejezik az összefüggéseket a változók lehetséges értékei között egy feladatcsoportban. Ugyanezek a függőség és függetlenség fogalmak ugyanúgy természetesen alkalmazhatók magukra az állításra is, mivel ez történik a természetes nyelvi kifejezésekben, például: „Hogy megteszi-e a kurzust, csak a záróvizsga tartalmától függ”..

Propozicionális függési logika ezeket az atomokat a javaslati logika összefüggésében veszi figyelembe. Propozicionális függőségi logikai csoportok értékelési készletek (v) a javaslati atomoktól (p_1 / ldots p_n) és ({T, F }) értékig. Szemantikai szabályai - és azok indokolása - nagyon jól tükrözik az elsőrendű csapat szemantikáját, és a függőségi atomok szabálya

PTS-dep:

(X / modellek / eqord (p_1 / ldots p_n, q)) akkor és csak akkor, ha bármelyik két érték (v_1, v_2 / X-ben), amelyek megegyeznek a (p_1 / ldots p_n értékben) is megállapodnak a (q) értékben.

Az elsőrendű függőségi logika sokféle változatát és általánosítását a javaslati szintre bármilyen nehézség nélkül le lehet engedni: így például meg lehet tanulmányozni a javaslati inklúziós logika, a javaslati csapat logika, a javaslati intuitív függési logika tulajdonságait stb..

Míg az (elsőrendű) függőségi logika szigorúan kifejezőbb, mint az elsőrendű logika, a proposíciós függőségi logika nem kifejezőbb, mint a javaslati logika, mivel az azonnali következtetésből következik, hogy az állítási logikában minden állítási függvény kifejezhető. Ugyanakkor szoros kapcsolat áll fenn az állítólagos függési logika csoportjai és a kíváncsi logika információs állapota között (Groenendijk 2009; Ciardelli & Roelofsen 2011), a jelentés jelentésének és az információcserének a szemantikai kerete között: az kíváncsi logika implikációja pontosan megegyezik a javaslati intuitív függőség logikájával.

A tételezési függőség logikájának szorongása és számos kiterjesztése megtalálható a Yang & Väänänen 2016-ban.

4.6 Modális függőség logika

A modális függőség logikája (Väänänen 2008) és variánsai kiterjesztik a modális logikát azáltal, hogy hozzáadják ugyanazokat a függőségi atomokat (eqord (p_1 / ldots p_n, q)), amelyeket már figyelembe vettek a javaslati függőség logika esetében.

Megelégedettségének feltételei a csapat szemantikájának egyik változatával határozhatók meg, amelyben a csapatokat a lehetséges világok halmaza váltja fel.

Sok kutatás vizsgálta ennek a logikanak, fragmentumainak és kiterjesztéseinek a komplexitás-elméleti tulajdonságait (Ebbing, Lohmann, & Yang 2011; Ebbing & Lohmann 2012; Lohmann & Vollmer 2013).

5. A függőségi logika alkalmazásai

5.1 Függőség logika és adatbázis elmélet

A csapatszemantika csapata és a relációs adatbázis elméletben vizsgált kapcsolatok között egyértelmű kapcsolat van: adott egy csapat (X) és a feladataiban előforduló változók (vec v = v_1 / ldots v_k), meghatározható a kapcsolat (X (vec v) = { langle s (v_1), / ldots, s (v_n) csengő: s / az X }). Ezenkívül a függőségi logikában vizsgált függőségi atomok és azok variánsai hasonlóak az adatbázis-elméletben figyelembe vett függőségekhez, és sok esetben ezekből származnak, mint például funkcionális függőségek (Väänänen 2007a), többértékelt függőségek (Engström 2012), valamint a beillesztési és kizárási függőségek (Galliani 2012). A függőségi logika és az adatbázis-elmélet közötti kapcsolat nemcsak a függőségi logika továbbfejlesztéséhez, hanem az adatbázis-elmélethez is hozzájárult:a Hannula & Kontinen 2016-ban a befogadás, a funkcionális és a beágyazott többértékű adatbázis-elméleti függőségek korlátlan implikációs problémájának véges axiomatizációját találták egy hasonló probléma kutatásával a csapat szemantika keretében.

5.2 A függőség logikája és a hitek ábrázolása

Amint azt a Yang 2014 és Yang & Väänänen 2016 tárgyalja, szoros kapcsolat van a (javaslati) intuitív függőségi logika és a kíváncsi logika között (Ciardelli & Roelofsen, 2011), azaz a jelentés és az ügynökök közötti információcsere keretének. Általánosabban: a csoportszemantikában tanulmányozott függőségi atomok és összeköttetések természetes értelmezéseket tesznek lehetővé a hitállapotok és a hit-frissítések szempontjából, amint azt a Galliani 2015 tárgyalja. Ebben az időben az ilyen logika és a dinamikus-episztatikus logika közötti kapcsolat pontos jellege és annak variánsai (Van Ditmarsch, van Der Hoek és Kooi 2007) nagyrészt felfedezetlenek, de elegendő ok van feltételezni a matematikai és a filozófiai logika e két területének további kapcsolatait.

5.3 Függőséglogika és Arrow tétel

Arrow tétele (Arrow 1950) a társadalmi választási elmélet mélyreható befolyásos eredménye, amely röviden azt mutatja, hogy nem létezik szavazási rendszer (azaz nincs olyan rendszer, amely az alternatívák közötti egyéni preferenciák rangsorolását globális, társadalmi szintű preferencia rangdá konvertálja). amelyek megfelelnek három ésszerűen hangzó feltételnek, nevezetesen

  • Ha minden szavazó előnyben részesíti (A), mint a (B), akkor a csoport egésze előnyben részesíti a (A) és (B) szavakat;
  • Az, hogy a csoport egésze elõnyben részesíti-e a (A) -tól (B) -ig, vagy fordítva, kizárólag minden választópolgár preferenciáitól függ ((A) és (B), és nem az egyéb lehetséges alternatívákra vonatkozó preferenciáiktól;
  • Egyetlen választó nem diktátor, azaz a csoport preferenciáit nem egy adott választó preferenciái határozzák meg.

Amint maga a megfogalmazás azt sugallja, a második és a harmadik feltétel természetes értelmezést tesz lehetővé a függőség és a függetlenség szempontjából: valójában, amint azt a Pacuit & Yang 2016 bemutatja, Arrow tétele formalizálható függetlenségi logikában és bebizonyítható egy megfelelő természetes dedukciós rendszerben.

5.4 A kvantum csapat logikája és Bell egyenlőtlenségei

Hyttinenben, Paoliniban és a Väänänen 2015-ben bevezetik a javaslati csapatlogika egy kvantumcsapat-logikának nevezett változatát. Ebben a formalizmusban a csapatokat kvantumcsoportok váltják fel, amelyek különböznek a szokásos csoportos logikai csapatoktól abban az értelemben, hogy lehetővé teszik, hogy bizonyos változók értékei meghatározhatatlanok legyenek bizonyos értékelések szempontjából, és abban, hogy lehetővé teszik ugyanazon esemény több példányát. értékelés (ezáltal mennyiségi szempontot ad hozzá a csapat szemantikájához). Ezután meghatározunk egy szemantikát kvantumcsoportok között egy nyelv számára, amely lehetővé teszi az események valószínűségével kapcsolatos egyenlőtlenségek meghatározását, és ehhez kidolgozunk egy megbízható és teljes bizonyítási rendszert; és végül: bebizonyosodik, hogy Bell egyenlőtlenségei ellentétes mintákat vesznek fel e rendszerekben,a kvantummechanika előrejelzései szerint és a kísérleti bizonyítékok szerint (Einstein, Podolsky és Rosen 1935; Bell 1964; Aspect, Grangier és Roger 1981), míg a keret klasszikus változatában nem.

Bibliográfia

  • Abramsky, Samson és Jouko Väänänen, 2009, „IF-től BI-ig: Mese a függőségről és szétválasztásról”, Synthese, 167 (2): 207–230. doi: 10,1007 / s11229-008-9415-6
  • Arrow, Kenneth J., 1950, „A szociális jólét fogalmának nehézségei”, The Journal of Political Economy, 328–346. doi: 10,1086 / 256963
  • Aspect, Alain, Philippe Grangier és Gérard Roger, 1981, „A reális helyi elméletek kísérleti tesztei Bell-tétel segítségével”, Physical Review Letters, 47 (7): 460–463. doi: 10,1103 / PhysRevLett.47.460
  • Bell, JS, 1964, “Az Einstein-Podolsky-Rosen paradoxonon”, Fizika, 1 (3): 195–200.
  • Ciardelli, Ivano és Floris Roelofsen, 2011, „Kíváncsi logika”, Journal of Philosophical Logic, 40 (1): 55–94. doi: 10,1007 / s10992-010-9142-6
  • van Ditmarsch, Hans, Wiebe van der Hoek és Barteld Kooi, 2007, Dynamic Epistemic Logic (Synthese Library 337), Dordrecht: Springer. doi: 10,1007 / 978-1-4020-5839-4
  • Durand, Arnaud és Juha Kontinen, 2012, „Hierarchiák a függőségi logikában”, ACM tranzakciók a számítógépes logikán (TOCL), 13. (4): 1–21. doi: 10,1145 / 2.362.355,2362359
  • Ebbing, Johannes és Peter Lohmann, 2012, „A modális függőség logikájának modellellenőrzésének komplexitása”, SOFSEM 2012: Nemzetközi konferencia a számítástechnika elméletének és gyakorlatának jelenlegi trendeiről (Lecture Notes in Computer Science, 7147), Berlin, Heidelberg: Springer, 226–237. doi: 10,1007 / 978-3-642-27660-6_19
  • Ebbing, Johannes, Peter Lohmann és Fan Yang, 2013, „A modellek ellenőrzése a modális intuíciós függőség logikájáról”, Nemzetközi logikai, nyelvi és számítástechnikai szimpózium 2011 (Számítástechnikai előadások, 7758), Berlin, Heidelberg: Springer, 231–256. doi: 10,1007 / 978-3-642-36976-6_15
  • Einstein, A., Podolsky B. és N. Rosen, 1935, „A fizikai valóság kvantum-mechanikus leírása teljesnek tekinthető?” Fizikai áttekintés, 47 (10): 777–780. doi: 10,1103 / PhysRev.47.777
  • Engström, Fredrik, 2012, „Általános számszerűsítők a függőségi logikában”, Journal of Logic, Language and Information, 21 (3): 299–324. doi: 10,1007 / s10849-012-9162-4
  • Fagin, Ronald, 1974, „Általános elsőrendű spektrumok és polinomiális időben felismerhető készletek”, a számítás komplexitása (SIAM-AMS Proceedings 7), Richard M. Karp (szerk.), Providence, RI: American Mathematical Society, pp. 27-41.
  • Galliani, Pietro, 2012, „Befogadás és kizárás függőségei a csapat szemantikájában - A hiányos információk néhány logikájáról”, Annals of Pure and Applied Logic, 163 (1): 68–84. doi: 10.1016 / j.apal.2011.08.005
  • ––– 2015, „A csapatszemantika doxastikus értelmezése”, Határok nélküli logika: esszék set-elméletről, modell-elméletről, filozófiai logikáról és a matematika filozófiájáról (Ontos Mathematical Logic, 5), Hirvonen Åsa, Juha Kontinen, Roman Kossak, és Andrés Villaveces (szerk.), Berlin, Boston: De Gruyter, 167–192. doi: 10,1515 / 9781614516873,167
  • Galliani, Pietro és Lauri Hella, 2013, „Inclusion Logic and Fixed Logic”, Computer Science Logic 2013 (Leibniz International Proceedings in Informatics (LIPIcs), 23), Dagstuhl, Németország: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 281-295. doi: 10,4230 / LIPIcs. CSL.2013.281
  • Galliani, Pietro és Jouko Väänänen, 2014, „A függőségi logikáról”, Johan van Benthemben a logikáról és az információdinamikáról (Kiemelkedő hozzájárulás a logikához, 5), Alexandru Baltag és Sonja Smets (szerk.), Cham: Springer, 101. o. 119. doi: 10,1007 / 978-3-319-06025-5_4
  • Grädel, Erich és Jouko Väänänen, 2013, „Függőség és függetlenség”, Studia Logica, 101 (2): 399–410. doi: 10,1007 / s11225-013-9479-2
  • Groenendijk, Jeroen, 2009, „Kíváncsi szemantika: A diszjunktúra két lehetősége”, Peter Bosch, David Gabelaia és Jérôme Lang (szerk.), Hetedik nemzetközi Tbilisi Nyelv, logika és számítás szimpóziumán (Számítógéptudományi előadások: 5422. Kötet)), Springer-Verlag, 80–94. doi: 10,1007 / 978-3-642-00665-4_8
  • Hannula, Miika és Juha Kontinen, 2016, „A feltételes függetlenség és az integrációs függőségek véges axiomatizálása”. Információ és számítás, 249: 121–137. doi: 10.1016 / j.ic.2016.04.001
  • Henkin, Leon, 1961, „Néhány megjegyzés a végtelenül hosszú képletekre”, az infinitistikus módszerekben (A matematika alapjainak szimpóziumának folyóiratai, Varsó, 1959), Oxford: Pergamon Press, 167–183.
  • Hodges, Wilfrid, 1997, “Kompozitív szemantika a tökéletlen információ nyelvéhez”, IGPL Logic Journal, 5 (4): 539–563. doi: 10,1093 / jigpal / 5.4.539
  • Hyttinen, Tapani, Gianluca Paolini és Jouko Väänänen, 2015, „Quantum Team Logic and Bell's egyenlőtlenségek”, The Symbolic Logic Review, 8 (4): 722–742. doi: 10,1017 / S1755020315000192
  • Kontinen, Juha és Ville Nurmi, 2009, „Csapat logika és másodrendű logika”, a logikáról, nyelvről, információról és számításról szóló 16. nemzetközi műhelymunka előadásain (előadási jegyzetek a számítógépes tudományban, 5514), Berlin, Heidelberg: Springer, 230–241. doi: 10,1007 / 978-3-642-02261-6_19
  • Kontinen, Juha és Jouko Väänänen, 2009, „A függőség logikájának meghatározhatóságáról”, Logic, Language and Information Journal, 18 (3): 317–332.doi: 10.1007 / s10849-009-9082-0
  • ––– 2011, „Megjegyzés a függőség logikájának tagadásáról”, Notre Dame Journal of Formal Logic, 52 (1): 55–65. doi: 10,1215 / 00294527-2010-036
  • ––– 2013, „Az elsőrendű következmények szorongása a függőségi logikában”, Annals of Pure and Applied Logic, 164 (11): 1101–1117. doi: 10.1016 / j.apal.2013.05.006
  • Kripke, Saul A., 1965, „Az intuíciós logika szemantikai elemzése”, a formális rendszerekben és rekurzív funkciókban: A nyolcadik logikai kollokvium folyóiratai, Oxford, 1963. július (Tanulmányok a logika és a matematika alapjai, 40), John N. Crossley és Michael AE Dummett (szerk.), Észak-Holland, 92–130. doi: 10.1016 / S0049-237X (08) 71685-9
  • Lohmann, Peter és Heribert Vollmer, 2013, „A modális függőség logikájának komplexitási eredményei”, Studia Logica, 101 (2): 343–366. doi: 10,1007 / s11225-013-9483-6
  • Pacuit, Eric és Yang Fan, 2016, „Függőség és függetlenség a társadalmi választásban: Arrow tétele”, a Függőség logikájában, Simson Abramsky, Juha Kontinen, Jouko Väänänen és Heribert Vollmer (szerk.), Dordrecht: Springer, 235–260.. doi: 10,1007 / 978-3-319-31803-5_11
  • Väänänen, Jouko, 2007a, Függőséglogika: Új megközelítés a függetlenség kedvező logikájához, (London Mathematical Society hallgatói szövegek, 70), Cambridge: Cambridge University Press. doi: 10,1017 / CBO9780511611193
  • ––– 2007b, „Csapat logika”, interaktív logika: Kiválasztott iratok a 7. Augustus de Morgan műhelyből (Logikai és játékszövegek, 1), Johan van Benthem, Dov Gabbay és Benedikt Löwe (szerk.), Amszterdam: Amsterdam University Press, 281–302.
  • –––, 2008, „A modális függőség logikája”, Új távlatok a játékra és az interakcióra (Logikai és játékok szövegek, 4), Krzysztof R. Apt és Robert van Rooij (szerk.), Amszterdam: Amsterdam University Press, 237. o. 254.
  • Yang, Fan, 2013, „Másodrendű mondatok kifejezése az intuitív függőségi logikában”, Studia Logica, 101 (2): 323–342. doi: 10,1007 / s11225-013-9476-5
  • ––– 2014, „A függőségi logika kiterjesztéseiről és variánsairól: Intuicionista kapcsolatok tanulmányozása a csapat szemantika beállításában”. PhD értekezés tézisei, Helsinki Egyetem.
  • Yang, Fan és Jouko Väänänen, 2016, „A függőség propozicionális logikája”, Annals of Pure and Applied Logic, 167 (7): 557–589. doi: 10.1016 / j.apal.2016.03.003

Tudományos eszközök

sep ember ikonra
sep ember ikonra
Hogyan idézhetem ezt a bejegyzést.
sep ember ikonra
sep ember ikonra
A bejegyzés PDF-verziójának előnézete a SEP Barátok társaságában.
inpho ikonra
inpho ikonra
Nézze meg ezt a belépési témát az Internet Filozófia Ontológiai Projektben (InPhO).
phil papírok ikonra
phil papírok ikonra
Továbbfejlesztett bibliográfia erre a bejegyzésre a PhilPapersnél, az adatbázisához kapcsolódó hivatkozásokkal.

Egyéb internetes források

  • Függőséglogika a Wikipedia-n
  • Előadások az Akadémia kollokvium-függőségének logikájában, Amszterdam, 2014

Ajánlott: