Logika Odvisnosti

Kazalo:

Logika Odvisnosti
Logika Odvisnosti

Video: Logika Odvisnosti

Video: Logika Odvisnosti
Video: Н П Брусенцов о расширении традиционной логики дек 2004 2024, Marec
Anonim

Vstopna navigacija

  • Vsebina vpisa
  • Bibliografija
  • Akademska orodja
  • Prijatelji PDF predogled
  • Informacije o avtorju in citiranju
  • Nazaj na vrh

Logika odvisnosti

Prvič objavljeno dne 23. februarja 2017

Logika odvisnosti je razširitev logike prvega reda, ki ji doda atome odvisnosti, to je izraze oblike (eqord (x_1 / ldots x_n, y)), ki trdijo, da je vrednost (y) enaka funkcionalno odvisna od (z drugimi besedami, določene z) vrednosti (x_1 / ldots x_n). Ti atomi omogočajo določitev nelinearno urejenih vzorcev odvisnosti med spremenljivkami, podobno v istem pomenu poševnih kvantifikatorjev IF-Logic; vendar, za razliko od logike IF, odvisnostna logika loči kvantifikacijo od specifikacije takih pogojev odvisnosti / neodvisnosti. Glavna semantika logike odvisnosti, imenovana timska semantika, posplošuje Tarskijevo semantiko tako, da izrazi zadovoljujejo ali niso zadovoljni glede nabora spremenljivih dodeljevanj in ne glede na posamezne naloge. Ta semantika vnaprej določa razvoj logike odvisnosti, prvotno pa jo je razvil Wilfrid Hodges v okviru logike IF (Hodges 1997). Obstaja tudi igra-teoretična semantika za logiko odvisnosti, ki temelji na igrah nepopolnih informacij in je približno analogna igro-teoretična semantika za neodvisnost prijazno logiko (Väänänen 2007a). Sensu stricto se izraz "logika odvisnosti" nanaša izključno na jezik, ki ga dobimo z dodajanjem zgoraj omenjenih atomov funkcionalne odvisnosti v jezik logike prvega reda; vendar se izraz uporablja tudi v splošnejšem pomenu, da se nanaša na področje raziskovanja, ki proučuje lastnosti logike, pridobljene z dodajanjem različnih pojmov odvisnosti in neodvisnosti logiki prvega reda, kot je logika neodvisnosti (Grädel & Väänänen 2013),intuicijska logika odvisnosti (Yang 2013) ali logika vključevanja (Galliani 2012, Galliani & Hella 2013) ali celo logika, ki razširi druge logične okvire skozi podobne atome, kot v primeru logike modalne odvisnosti (Väänänen 2008). V tem članku se bo izraz "logika odvisnosti" uporabljal za pravilno logiko odvisnosti, izraz "logika odvisnosti in neodvisnosti" pa bo uporabljen za sklicevanje na njene različice in posplošitve.in izraz "logika odvisnosti in neodvisnosti" se bo uporabljal za sklicevanje na njene različice in posplošitve.in izraz "logika odvisnosti in neodvisnosti" se bo uporabljal za sklicevanje na njene različice in posplošitve.

  • 1. Vzorci odvisnosti v logiki prvega reda in njegove razširitve
  • 2. Ekipna semantika

    2.1 Igra-teoretska semantika

  • 3. Lastnosti

    • 3.1 ekspresivnost
    • 3.2 Hierarhije v logiki odvisnosti
    • 3.3 Negacija v logiki odvisnosti
    • 3.4 Sistemi resnice, veljavnosti in dokazovanja v odvisni logiki
  • 4. Različice logike odvisnosti

    • 4.1 Logika neodvisnosti
    • 4.2 Logika vključevanja
    • 4.3 Ekipna logika
    • 4.4 Intuitionistična logika odvisnosti
    • 4.5 Logika predloga odvisnosti
    • 4.6 Modalna logika odvisnosti
  • 5. Uporaba logike odvisnosti

    • 5.1 Logika odvisnosti in teorija baz podatkov
    • 5.2 Logika odvisnosti in reprezentacija prepričanja
    • 5.3 Logika odvisnosti in Arremov izrek
    • 5.4 Kvantna logika moštva in Bellove neenakosti
  • Bibliografija
  • Akademska orodja
  • Drugi internetni viri
  • Povezani vnosi

1. Vzorci odvisnosti v logiki prvega reda in njegove razširitve

Ena izmed značilnosti logike prvega reda, ki predstavlja večino njene ekspresivnosti in uporabnosti, je dejstvo, da omogoča vstavljanje kvantifikatorjev, zato omogoča določitev vzorcev odvisnosti med količinsko opredeljenimi spremenljivkami. Razmislite na primer o (upam napačni) izjavi, da "vsak fant ljubi neko dekle, ki ljubi drugega dečka". Lahko je enostavno preveden v logiko prvega reda kot

(oznaka {1} oznaka {eq: boygirl1} začeti {poravnati} & / forall x (fant (x) rightarrow / obstaja y (dekle (y) land / ljubi (x, y) zemlja {} & / quad / obstaja z (fant (z) land x / not = z / land / ljubi (y, z)))) konec {poravnati})

katerih resnični pogoj je po Tarski običajni semantiki natanko to, kar bi človek pričakoval: zgornji izraz je resničen, če in le, če je za vsakega fanta (b) mogoče najti dekle (g) in dečka (b ') tako, da (b) ljubi (g) in (g) ljubi (b') in (b) in (b ') nista enaka. Identiteta deklice (g) je seveda lahko odvisna od identitete prvega fanta (b) - navsezadnje, da bi bil ta izraz resničen, ne potrebujemo, da so vsi dečki zaljubljeni v vsa dekleta - poleg tega je identiteta drugega dečka (b ') lahko odvisna od identitete prvega dečka (b) (ker mora biti (b') drugačna od (b)) in iz identitete deklice (g), ki jo ljubi (b). Vzorec odvisnosti med našimi količinsko opredeljenimi spremenljivkami je naslednji: (y) je odvisen od (x),medtem ko je (z) odvisen od (x) in (y). S skladenjskega vidika se to odraža z dejstvom, da je (obstaja y) v območju (forall x), medtem ko je (obstaja z) na območju obeh (forall x) in (obstaja y).

Razlike v vzorcih odvisnosti med operaterji se lahko uporabijo za formalizacijo pomembnih razlik, na primer tiste med neprekinjenostjo funkcije (f)

(forall x / forall / epsilon / obstaja / delta / forall x '(| x - x' | <\ delta / rightarrow | f (x) - f (x ') | <\ epsilon))

in enotna kontinuiteta

(forall / epsilon / obstaja / delta / forall x / forall x '(| x - x' | <\ delta / rightarrow | f (x) - f (x ') | <\ epsilon))

ali v intenzivnih razširitvah logike prvega reda izraziti razliko med odčitki De Dicto in De Re (npr. "Vsak človek je lahko nor", lahko razumemo bodisi kot navajanje, da to velja za vsako osebo (p), je mogoče, da je (p) nor, (forall x (oseba (x) rightarrow / Diamond / crazy (x))) ali kot navaja, da je mogoče, da so vsi nori skupaj, (Diamond / forall x (oseba (x) rightarrow / nor (x)))).

Vzorci odvisnosti med količinsko opredeljenimi spremenljivkami v logiki prvega reda so nujno prehodni, kar je razvidno iz njihovih povezav z obsegom ustreznih podpredstavkov: če je (obstaja y) v območju (forall x) in (obstaja z) je na področju (obstaja y), potem bo nujno (obstaja z) na področju (in je torej od njega odvisno) (forall x). Poleg tega je nabor vseh kvantifikatorjev, katerih področje uporabe je podformula (alfa), linearno urejeno: če je (alfa) v območju (Q_1 x_1) in (Q_2 x_2), potem ali (Q_1 x_1) spada v področje (Q_2 x_2) ali obratno.

To omejuje izrazne možnosti logike prvega reda. Denimo, da na primer spremenimo svojo prejšnjo trditev o dečkih in deklicah: vsak fant ljubi neko dekle, ki ljubi drugega fanta, in tega drugega fanta lahko izberemo samostojnega. Intuitivno gledano to pomeni, da je dovolj preprosto: za vsakega fanta (b) lahko najdemo dekle (g) takšno, da (b) ljubi (g), in za vsako takšno dekle lahko najti fanta (b ') takega, da (g) ljubi (b') in (b / not = b '), poleg tega pa lahko najdemo tudi identiteto drugega fanta (b') ne da bi to vedeli (b), na podlagi identitete same deklice (g). To lahko še vedno velja v nekaterih scenarijih, na primer, če dva dečka (b_1) in (b_2) ljubita dve deklici (g_1) in (g_2),ki pa imajo radi samo (b_2) in (b_1). Vendar je mogoče zlahka videti, da ni enakovredna naši prejšnji izjavi: če na primer naše vesolje sestavljata (kot v (b) zgoraj) dva fanta (b) in (b ') in dekle (g) in (b) in (b ') ljubita (g), ki ljubi oba, potem je naša prejšnja trditev resnična, trenutna pa je napačna.

[na dveh podobnih figurah imata obe sliki besedi "Fantje" in "Dekleta", ločena z vodoravnim presledkom na vrhu. Slika (a) ima točko b1 zgoraj levo, g1 zgoraj desno, b2 spodaj levo in g2 spodaj desno. Puščice kažejo od g1 do b1, od b1 do g2, od g2 do b2 in b2 do g1. Slika (b) ima b1 zgoraj levo, b2 spodaj levo, g1 na sredini desno. Puščica kaže od in do b1 in g1 in podobno od b2 do g1.]
[na dveh podobnih figurah imata obe sliki besedi "Fantje" in "Dekleta", ločena z vodoravnim presledkom na vrhu. Slika (a) ima točko b1 zgoraj levo, g1 zgoraj desno, b2 spodaj levo in g2 spodaj desno. Puščice kažejo od g1 do b1, od b1 do g2, od g2 do b2 in b2 do g1. Slika (b) ima b1 zgoraj levo, b2 spodaj levo, g1 na sredini desno. Puščica kaže od in do b1 in g1 in podobno od b2 do g1.]

Dva scenarija, v katerih je ((ref {eq: boygirl1})) res. V (a) lahko (z) izberemo neodvisno od (x); v (b) ne more.

Vendar ni jasno, kako formalizirati ta pogoj v logiki prvega reda. V bistvu bi morali spremeniti ((ref {eq: boygirl1})) tako, da (z) ne spada v področje (x) in zato ni odvisno od njega; vendar bi še vedno želeli, da je (z) odvisen od (y) in (y) od (x). Kakor je bilo ravnokar razpravljeno, pa takšen vzorec odvisnosti po logiki prvega reda ni mogoče uresničiti. Težavi se lahko izognemo tako, da se zatečemo kvantifikaciji višjega reda: res je, da je to izraz

(oznaka {2} oznaka {boygirl2} začeti {poravnati} & / obstaja F / forall x (fant (x) rightarrow / obstaja y (girl (y) land / ljubi (x, y) land / fant (F (y)) land {} & / quad x / not = F (y) land / ljubi (y, F (y)))) konec {poravnati})

zajema našo nameravano razlago, vendar le na račun eksplicitne eksistencialne kvantifikacije funkcij.

Možna alternativa bi bila razširitev skladnje logike prvega reda, da bi odpravili omejitve glede vzorcev odvisnosti med količinsko opredeljenimi spremenljivkami. To je pot, uporabljena z razvejano logiko kvantifikatorja (Henkin 1961), v kateri resnični pogoji ((ref {boygirl2}) ustrezajo pogojem

(oznaka {3} oznaka {boygirl3} začeti {poravnati} & / levo (začeti {smallmatrix} forall x & / obstaja y \\ / forall z & / obstaja w / end {smallmatrix} desno) (fant (x) rightarrow (dekle (y) land / ljubi (x, y) land {} & / quad (y = z / rightarrow (boy (w) land x / not = w / land / ljubi (z, w))))), / konec {poravnati})

in do neodvisnosti prijazne logike, v kateri je ((ref {boygirl2})) enakovreden

(oznaka {4} oznaka {boygirl4} začeti {poravnati} & / forall x / obstaja y (fant (x) rightarrow (girl (y) land / ljubi (x, y) land (obstaja z / x) (fant (z) zemlji {} & / quad x / not = z / zemlja / ljubi (y, z)))). / konec {poravnati})

Tukaj ne bomo dali podrobne razlage semantike teh dveh formalizmov; zadostuje, da v ((ref {boygirl3})) vrednost (w) ni odvisna od vrednosti (x) in (y) (čeprav je lahko odvisna od vrednosti od (z)), saj pripadajo različnim "vrsticam" zapletenega kvantifikatorja (levo (začeti {smallmatrix} forall x & / obstaja y \\ / forall z & / obstaja w / end {smallmatrix } desno)), medtem ko v ((ref {boygirl4})) vrednost (z) ni odvisna od vrednosti (x), ker je ta odvisnost izrecno "zmanjšana" s kvantifikatorjem ((obstaja z / x)).

Ena značilnost, ki je skupna razvejani logiki kvantifikatorja in neodvisni prijazni logiki, je, da količinsko določitev spremenljivk ne ločuje od specifikacije nestandardnih vzorcev odvisnosti: kot v primeru logike prvega reda, ali je količinsko opredeljen spremenljivka (v_1) bo ali ne bo odvisna od neke druge količinsko opredeljene spremenljivke (v_2) bo določena z ustreznim položajem in obliko njihovih kvantifikatorjev.

Logika odvisnosti zavzema drugačen pristop k razširitvi logike prvega reda, da bi jo predstavljali ((ref {boygirl2})). V primerjavi z ((ref {eq: boygirl1})) je edini nov pogoj tisti, ki navaja, da vrednost (z) določa (torej funkcionalno odvisna od) vrednosti (y); in to ustreza novemu atomskemu stanju (eqord (y, z)), imenovanem odvisni atom, katerega predvideni pomen je, da je (vrednost) (z) funkcija vrednosti (y). Različno od primerov razvejane logike kvantifikatorja ali neodvisnosti prijazne logike je to pogoj za vrednosti, ki ju lahko prevzameta (y) in (z), ne pa pogoj vedenja kvantifikatorja (obstaja z): v resnici ni razloga, da bi zahtevali, da je (z) količinsko ovrednotena spremenljivka - lahko je namesto tega brezplačna spremenljivka,ali kak zapleten izraz, ki vključuje več spremenljivk.

V odvisnosti od logike je ((ref {boygirl2})) lahko formaliziran kot

(oznaka {5} oznaka {boygirl5} začeti {poravnati} & / forall x / obstaja y / obstaja z (eqord (y, z) land (boy (x) rightarrow (girl (y) land / ljubi (x, y) rightarrow {} & / quad (fant (z) land x / not = z / land / ljubi (y, z))))) end {align})

Pogoji resnice ((ref {boygirl2})), ((ref {boygirl3})), ((ref {boygirl4})) in ((ref {boygirl5})) so popolnoma enaki: vsak model, ki izpolnjuje enega od teh izrazov (v ustreznih jezikih), izpolnjuje vse štiri. Bolj na splošno, kot bomo videli, so ekspresivne moči eksistencialne logike drugega reda, neodvisnosti prijazna logika in logika odvisnosti glede določljivosti razredov modelov popolnoma enake. Vendar to ne velja za formule z brezplačnimi spremenljivkami; poleg tega pa se lahko te logike razširijo in spremenijo v izrazito različnih vrsticah.

2. Ekipna semantika

Ekipna semantika, ki jo je Wilfrid Hodges prvič razvil v okviru neodvisnosti prijazne logike (Hodges 1997), je posploševanje Tarške semantike za logiko prvega reda na primer večkratnih dodeljevanj elementov spremenljivkam. Nabori takšnih nalog, ki jih zaradi zgodovinskih razlogov imenujemo skupine, predstavljajo temeljni semantični pojem timske semantike in formule z njimi niso zadovoljne ali niso zadovoljne, ne pa glede na posamezne naloge. Povezava med semantiko ekipe in pomensko semensko Tarško je prikazana z naslednjim rezultatom, ki je odvisen od logike odvisnosti kot tudi v vseh njegovih različicah prvega reda:

Konzervativnost:

Formula prvega reda izpolnjuje skupina (X) (v smislu semantika ekipe), če in samo, če jo izpolnjujejo vse naloge (s / v X) (v smislu pomenske pomenske Tarške).

Na splošno lahko ekipe razumemo kot sklope prepričanj, ki predstavljajo nabor vseh stanj sveta (= naloge), za katere nekateri agent meni, da so možni. Potem bo ekipa (X) izpolnila neko formulo (phi), če in samo, če ima (phi) državo, kadar je (X) nabor vseh možnih stanj; in v tem primeru bomo napisali (X / modeli / phi) (ali (M, X / modeli / phi), če izbira modela (M) ni jasna). V tem razdelku bomo preučili pravila semantike ekipe in njihovo interpretacijo v smislu tega načela; Nato bomo v naslednjem razdelku razpravljali o tem, kako izhaja tudi iz igre-teoretična semantika nepopolnih informacij-teorije za logiko odvisnosti.

Pogoj za nove atome odvisnosti (eqord (x_1 / ldots x_n, y)), ki ustrezajo trditvi, da je vrednost (y) funkcija vrednosti vrednosti (x_1 / ldots x_n), je enostavno razumeti:

TS-dep:

(X / modeli ~ / eqord (x_1 / ldots x_n, y)), če in samo, če imata dve nalogi (s_1, s_2 / v X), ki se ujemata z vrednostmi (x_1 / ldots x_n) se tudi strinjata glede vrednosti (y).

Recimo, da je (X) niz dodelitev treh spremenljivk (x_1), (x_2) in (y), pri čemer (x_1) predstavlja državljanstvo kandidata, da pozicija, (x_2) predstavlja njihovo oceno (v skladu s primerno metodo ocenjevanja) in (y) predstavlja, ali so bili sprejeti ali zavrnjeni. Nato atom (eqord (x_2, y)) ustreza trditvi, da ponudbo določa samo rezultat: če imata dva kandidata enako oceno, bosta prejela popolnoma isto ponudbo, ne glede na kateri koli drug dejavnik. Poseben primer atoma odvisnosti dajejo atomi konstante (eqord (y)), ki jih - glede na zgornjo semantiko - skupina zadovolji, če in le, če se vse njene dodelitve strinjajo z vrednostjo (y).

(začni {array} {l | ccc} textbf {dodelitev} & / 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 / konec {matrika})

Tabela 1: Skupina (X), v kateri je (y = x_1 + x_2). Tukaj je (y) funkcija (x_1) in (x_2) in zato drži (= \! \! (X_1 x_2, y)); vendar (y) ni samo funkcija (x_1), zato (= \! \! (x_1, y)) ne drži.

Pod isto razlago veljajo pravila za dobesedne dobe in veznike prvega reda (za preprostost bomo domnevali, da so naši izrazi v negativni normalni obliki; in, kot je običajno, bomo domnevali, da negacije atomov odvisnosti nikoli niso zadovoljene) enostavno izpeljati:

TS-lit:

Za vse literale prvega reda (alfa), (X / modeli / alfa), če in samo, če za vse dodelitve (s / v X), (s / modeli / alfa) v običajnem pomenu Tarške semantike;

TS - (land):

(X / modeli / phi / land / psi) če in samo, če (X / modeli / phi) in (X / modeli / psi).

Velja poudariti, da, kot lahko že vidimo po teh pravilih, zakon izključene sredine ne drži logike odvisnosti (tako kot ne drži neodvisne prijazne logike): na primer, če ekipa (X) vsebuje obe nalogi (s) z (s (x) = s (y)) in dodelitve (s ') z (s' (x) not = s '(y)) potem (X / ne / modeli x = y) in (X / ne / modeli x / ne = y). V tem delu bomo v vsakem primeru predstavili jezik logike odvisnosti brez izrecnega operaterja negacije; potem bomo kasneje razpravljali o posledicah dodajanja le-tega v svoj jezik.

Kaj pa univerzalno količinsko določanje? V katerih okoliščinah bi moral biti v ekipi univerzalno količinsko opredeljen izraz (forall v / psi)? Spet se moramo spomniti intuicije, po kateri ekipa predstavlja nabor možnih stanj. Če želimo oceniti (forall v / psi), glede na katera možna stanja stvari bi morali oceniti (psi)? Naravni odgovor je, da bi morali razmisliti o vseh stanjih stvari, ki se razlikujejo od stanj v (X) samo glede na vrednost (v). To upravičuje naslednje pravilo:

TS - (forall):

(X / modeli / forall v / psi), če in samo, če (X [M / v] modeli / phi), kjer (X [M / v]) je niz ({s ': / obstaja s / v X / mbox {st} s' / sim_v x })

pri čemer (s '\ sim_v s) pomeni, da se dve dodelitvi (s) in (s') medsebojno razlikujeta glede na vrednost spremenljivke (v).

[X = / začeti {matrika} {l | c} textbf {dodelitev} & x \\ / hline s_0 & 0 \\ s_1 & 1 / konec {matrika} Rightarrow X [M / y] = / start {matrika} {l | c | c} textbf {dodelitev} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 \\ s'_3 & 1 & 1 / konec {matrika})

Tabela 2: (X) in (X [M / y]) v modelu z dvema elementoma (0) in (1).

Zdaj razmislimo o ločitvi. Kdaj naj se zadrži (phi / lor / psi)? Da odgovorimo na to, naj spomnimo, da ekipe lahko razumemo kot sklope možnih stanj in da torej zveza dveh skupin (Y) in (Z) predstavlja vsa stanja stvari, ki lahko se zgodijo, če je (Y) ali (Z). Če sta torej dve formuli (phi) in (psi) izpolnjeni z naborom skupin ({Y_1 / ldots Y_n, / ldots }) in ({Z_1 / ldots Z_n, / ldots }) bi moralo njihovo ločitev (phi / lor / psi) izpolnjevati nabor moštev ({Y_i / cup Z_j: i, j / in 1, / ldots }) ali, kar je primerno,

TS - (lor):

(X / modeli / phi / lor / psi), če in samo, če (X = Y / skodelica Z) za dve ekipi (Y) in (Z) tako, da (Y / modeli / phi) in (Z / modeli / psi).

Tu je treba poudariti, da na splošno ne zahtevamo, da sta (Y) in (Z) ločena. Zaradi lastnosti zapiranja navzdol, o kateri bomo kmalu razpravljali, ta dodatni pogoj ne bi pomenil nobene ustrezne semantike logike odvisnosti; toda v primeru nekaterih razširitev in različic logike odvisnosti bi bila ta dodatna zahteva v nasprotju z načelom lokalnosti, v skladu s katerim so pogoji izpolnjevanja izraza odvisni samo od vrednosti spremenljivk, ki se v njem pojavljajo (Galliani 2012).

Pomembno je tudi opozoriti, da disjunkcija v logiki odvisnosti ni idempotentna: na primer (eqord (x, y) lor / eqord (x, y)) ni enakovredna (eqord (x, y)) in izpolnjuje ga skupina (X), če in samo, če se za vsake tri naloge v (X), ki se dogovorijo o (x), vsaj dva strinjata (y). To se lahko zdi nekoliko kontra intuitivno; vendar je neposredna posledica dejstva, da je v skladu z našo interpretacijo (eqord (x, y) lor / eqord (x, y)) treba razumeti kot "vsako možno stanje stvari izvira iz enega od dva niza stanja stvari in v obeh je (y) funkcija (x) ". Ker združitev funkcij na splošno ni funkcija, nas nekoliko preseneti, da disjunkcija v logiki odvisnosti ni nepopustljiva.

Za konec razmislimo o primeru eksistencialne kvantifikacije. Kdaj skupina izraza (obstaja v / psi) izpolnjuje? Da bi odgovorili na to, lahko začnemo z razlago operaterja omejitev, ki glede na katero koli ekipo (X) povzroči, da je skupina (X _ { backslash v}), pridobljena z odstranitvijo spremenljivke (v) (če je prisoten) iz vseh dodelitev (s / v X) (in potem, ker je (X) niz, s sestavljanjem enakih dodelitev). To bi lahko razumeli kot operacijo pozabljanja, s katero izbrišemo vse podatke o vrednosti (v) - na primer zato, ker smo verjeli o tej vrednosti nezanesljivi ali ker je bila ta vrednost spremenjena. Predpostavimo, da je (X _ { backslash v} = Y _ { backslash v}): potem v naši razlagi oz.to pomeni, da se množice možnih stanj stvari, predstavljenih z (X) in (Y), v največji meri ne strinjajo glede vrednosti (v). Torej, če (Y) izpolnjuje pogoj (phi), lahko rečemo, da bi (X) izpolnjeval (phi), če ne, vrednost (y) ali, kar je podobno, da (X) izpolnjuje (obstaja v / psi). To upravičuje naslednje pravilo:

TS - (obstaja):

(X / modeli / obstaja v / psi), če in le, če obstaja nekaj (Y), preko spremenljivk (X) in (v), tako, da sta (X _ { backslash v} = Y _ { backslash v}) in (Y / modeli / psi).

Preprosto je preveriti, ali je to tako, če in samo, če je (Y) oblike (X [F / y] = {s [a / y]: s / v X, a / v F (s) }) za nekatere funkcije (F) iz dodelitev v (X) do nepopolnih nizov elementov našega modela.

Tu je treba poudariti, da zgornja definicija na splošno ne zahteva, da (X) in (Y) vsebujeta isto število dodeljenih: ena dodelitev v (X) lahko ustreza več dodelitve v (Y) in - če je (v) že spremenljivka, ki se pojavlja v dodelitvah (X) - ena dodelitev v (Y) lahko ustreza tudi večim dodeljevanjem v (X).

[X = / začeti {matrika} {l | c} textbf {dodelitev} & x \\ / hline s_0 & 0 \\ s_1 & 1 / konec {matrika} Rightarrow X [F / y] = / start {matrika} {l | c | c} textbf {dodelitev} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 / konec {matrika})

Tabela 3: (X) in (X [F / y]) za (F (s_0) = {0,1 }), (F (s_1) = {0 })

Poglobljeno razpravo o lastnostih logike odvisnosti bomo preložili na specifikacijo njegove igro-teoretične semantike. Vendar pa ta del zaključujemo s tremi pomembnimi posledicami zgoraj navedenih pravil:

Lokalnost:

Če sta omejitvi (X) in (Y) spremenljivk, ki se pojavita v (phi), enaki, potem (X / modeli / phi), če in le, če (Y / modeli / phi).

Zapiranje navzdol:

Če (X / modeli / phi) in (Y / poddsetek X), potem (Y / modeli / phi).

Lastnost praznega niza:

Če je (prazna garnitura) skupina, ki ne vsebuje nobenih dodelitev, potem (prazna garnitura / modeli / phi) za vse logične formule odvisnosti (phi).

Načelo lokalnosti skupaj z načelom konzervativnosti, omenjenim na začetku tega oddelka, predstavlja pomemben "zdravstven pogoj", ki ga mora izpolnjevati vsaka različica in razširitev logike odvisnosti. Enako ne moremo trditi za zaporo navzdol in prazno nastavljeno lastnost, ki jo - kot bomo videli - kršijo različice logike odvisnosti.

Končno moramo določiti resničnost stavka logike odvisnosti glede na model. Ker stavek nima prostih spremenljivk, na podlagi načela lokalnosti naenkrat ugotovimo, da ga izpolnjujejo bodisi vse nepopolne ekipe bodisi nobene prazne ekipe ne izpolnjujejo. To je analogno primeru Tarške semantike, v kateri stavek izpolnjujejo vse spremenljive dodelitve ali pa nobena. Tako lahko resnico definiramo na običajen način:

Resnica v semantiki moštva:

Stavek (phi) je resničen v modelu (M), če in samo, če je (M, { emptyset } modeli / phi), kjer je ({ emptyset }) je skupina, ki vsebuje samo prazno nalogo. V tem primeru zapišemo, da (M / modeli / phi).

2.1 Igra-teoretska semantika

Kot rečeno, je igra-teoretična semantika za logiko odvisnosti različica semantike nepopolnih informacij za neodvisnost prijazno logiko, ki je sama prilagoditev igro-teoretične semantike logike prvega reda. Bralca napotimo na Väänänen 2007a za formalno, natančno opredelitev te semantike.

V teoretični semantiki iger sta stavek (phi) in model (M) enaka (ponavadi za dva igralca) igra (G_M (phi)). Potem je resnica opredeljena v smislu obstoja zmagovalnih strategij za enega od igralcev (ki se bo v tem delu imenoval preprosto "Player (0)"): z drugimi besedami, če je (sigma_0) (po možnosti neopredeljena) strategija za Player (0) in (Pi (G_M (phi), / sigma_0)) je nabor vseh predvajanj, ki so združljive z (sigma_0), potem (phi) velja, če in samo, če vsaka igra v (Pi (G_M (phi), / sigma_0)) zmaga za Player (0). O igri (G_M (phi)) je mogoče razmišljati kot o razpravi med dvema igralcema, eden od njih (Player (0)) pa želi dokazati, da je v tem primeru (phi) medtem ko želi drugi (Player (1)) pokazati, da (phi) ni tako.

Kot v primeru logike prvega reda in neodvisne prijazne logike sta tudi v igri za nepopolne informacije za logiko odvisnosti pozicije igre pari ((theta, s)), kjer je (theta) primerek podformule (phi) (to je, da se večkratni dogodki istega izraza kot podformule (phi) upoštevajo ločeno) in (s) je spremenljivka dodeljena za model (M). [1] Začetni položaj je ((phi, / prazen niz)), kjer je (prazna garnitura) prazna dodelitev; in nedeterministična strategija (sigma_0) za Player (0) za vsako ločitev in eksistencialno količinsko določitev izbere enega ali več naslednikov trenutnega položaja v skladu z naslednjimi pravili:

  • Če je trenutni položaj v obliki ((psi / lor / theta, s)), so njegovi nasledniki ((psi, s)) in ((theta, s));
  • Če je trenutni položaj v obliki ((obstaja v / psi, s)), so njegovi nasledniki vsi položaji ((psi, s ')) z (s' / sim_v s).

Podobno sta naslednika ((psi / land / theta, s)) ((psi, s)) in ((theta, s)) ter nasledniki ((forall v / psi, s)) so vsi položaji oblike ((psi, s ')) za (s' / sim_v s); vendar strategija za igralca (0) ne more določiti naslednika za te pozicije, saj se predpostavlja, da igralec (1) izbere, kateri položaj jim sledi.

Zaporedje pozicij (prekrivanje / rho = / rho_0 / rho_1 / ldots / rho_n) je predvajanje (G_M (phi)), če in samo če

  1. (rho_0 = (phi, / prazna garnitura));
  2. Za vse (i = 1 / ldots n) je (rho_ {i}) naslednik (rho_ {i-1}).

Če nadalje (rho_ {i + 1} v / sigma_0 (rho_i)) kadar koli (rho_i) ustreza ločitvi ali eksistencialnemu kvantifikatorju, rečemo, da (prekriva / rho) spoštuje strategija (sigma_0); in kot rečeno, zapišemo (Pi (G_M (phi), / sigma_0)) za nabor vseh iger nad (G_M (phi)), ki upoštevajo (sigma_0).

Pravimo, da je strategija (sigma_0) zmagovalna, če se vsaka igra (prekriva / rho), ki se konča na položaju ((alfa, s)), kjer je (alfa) prvo- Dobesedni vrstni red je tak, da dodelitev (s) izpolnjuje (alfa) v običajnem pomenu Tarške semantike. Atomi odvisnosti - in igre, ki se končajo v atomih odvisnosti - niso pomembne za odločanje, ali bo določena strategija zmagala. Vendar se uporabljajo za določitev, ali je določena strategija enotna:

Pogoj enotnosti

Strategija (sigma_0) za (G_M (phi)) je enotna, če imata dve predlogi (prekrivanje / rho, / prekrivanje / gama / in / Pi (G_M (phi), / sigma_0)) ki se končata na dveh položajih ((eqord (x_1 / ldots x_n, y), s)), ((eqord (x_1 / ldots x_n, y), s ')) za isti primerek atoma odvisnosti (eqord (x_1 / ldots x_n, y)) imamo to

(textrm {Če} s (x_1) ldots s (x_n) = s '(x_1) ldots s' (x_n) textrm {potem} s (y) = s '(y).)

Potem lahko resnico v teoretični semantiki iger določimo na naslednji način:

Resnica v teoretični semantiki iger:

Stavek (phi) velja v modelu (M) (glede na teoretično semantiko igre), če in samo, če ima igralec (0) enotno zmagovalno strategijo v (G_M (phi)).

Lahko se pokaže, da je ta pojem enak pojmu resnice v timski semantiki. Pravzaprav lahko pokažemo več kot to. Če se za katero koli ekipo (X) in formulo (phi) igra (G_ {M, X} (phi)) igra kot (G_M (phi)), vendar z začetni položaj, izbran naključno za vsako predvajanje iz ({(phi, s): s / v X }), potem velja naslednje:

Ekvivalenca GTS in timske semantike:

Formula (phi) izpolnjuje ekipa (X) (glede na model (M)), če in samo, če ima igralec (0) enotno zmagovalna strategija v (G_ {M, X} (phi)).

Ta rezultat kot stran razjasni, zakaj timska semantika logike odvisnosti izpolnjuje prazno nastavljeno lastnost in lastnost zapiranja navzdol. Če je (X = / prazen niz), potem je vsaka strategija za predvajalnika (0) v (G_ {M, X} (phi)) trivijalno zmagovalna in enotna; in če je (X / podseteq Y), potem je vsaka enotna zmagovalna strategija za igralca (0) v (G_ {M, X} (phi)) tudi enotna zmagovalna strategija za igralca (0) v (G_ {M, Y} (phi)).

3. Lastnosti

3.1 ekspresivnost

Po odvisnosti logika odvisnosti je enakovredna eksistencialnemu fragmentu (Sigma_1 ^ 1) logike drugega reda. Natančneje je mogoče dokazati (Väänänen 2007a), da

Kazensko enakovredna logika odvisnosti in (Sigma_1 ^ 1):

Za vsak stavek logike odvisnosti (phi) obstaja stavek (Sigma_1 ^ 1) stavek (phi ^ *) tak, da

(tag {6} oznaka {eq: DLESO} M / modeli / phi / Leftrightarrow M / modeli / phi ^ * / textrm {za vse modele} M.)

Podobno velja za vsak stavek (Sigma_1 ^ 1) (phi ^ *) logični stavek odvisnosti (phi), ki ga drži ((ref {eq: DLESO})).

Ker Faginov teorem (Fagin 1974) kaže, da je lastnost končnih modelov mogoče določiti v (Sigma_1 ^ 1), če in samo, če je v polinomskem času prepoznana po neterminertičnem Turingovem stroju (torej če in samo če je v NPTIME), takoj sledi, da

Logika odvisnosti in NPTIME:

Za stavek logike odvisnosti (phi) je razred vseh končnih modelov, ki jo izpolnjujejo, v NPTIME. Poleg tega za kateri koli razred NPTIME (mathcal K) končnih modelov obstaja stavek logike odvisnosti (phi), tako da (M / modeli / phi), če in samo, če (M / in / matematični K).

Druga neposredna posledica enakovrednosti med logiko odvisnosti in (Sigma_1 ^ 1) na ravni stavkov je, da izrek kompaktnosti in izrek Löwenheim-Skolem veljata tudi za logiko odvisnosti (Väänänen 2007a):

Kompaktnost:

Če niz (Phi) logičnih stavkov končne odvisnosti ni zadovoljiv v nobenem modelu, potem nekaj končnih podskup (Phi_0 / subseteq_f / Phi) že ni mogoče izpolniti.

Teorem Löwenheim-Skolem:

Če ima stavek logike odvisnosti neskončen model, potem ima modele vseh neskončnih kardinalnosti.

Vendar pa so zadeve bolj občutljive, ko gre za formule z brezplačnimi spremenljivkami. Potem je mogoče pokazati (Kontinen & Väänänen 2009), da logika odvisnosti ustreza navzdol zaprtemu fragmentu eksistencialne logike drugega reda:

Določljivost ekipe v logiki odvisnosti

Nabor (mathcal X) skupin nad modelom (M) in niz (V) spremenljivk ima obliko ({X: M, X / modeli / phi }) za neko logično formulo odvisnosti (phi) z prostimi spremenljivkami v (V), če in samo če

  1. (mathcal X) ni prazen;
  2. (mathcal X) je navzdol zaprt, to je (Y / podselek X / v / mathcal X / Rightarrow Y / in / mathcal X);
  3. (mathcal X) je (Sigma_1 ^ 1) - določljivo v (M), torej obstaja stavek (Sigma_1 ^ 1) (Psi (R)), nad besediščem (M) plus nov (| V |) - simbol relacije (R), tako da

    [X / v / mathcal X / textrm {če in samo, če} M, / textrm {Rel} (X) modeli / Psi (R))

    kjer je (textrm {Rel} (X)) razmerje (| V |) - arry ({s (V): s / v X }), ki ustreza skupini (X).

3.2 Hierarhije v logiki odvisnosti

V Durand & Kontinen 2012 so preučili učinek omejevanja števila odvisnih spremenljivk odvisnih atomov ali števila univerzalnih kvantifikatorjev. Pokazalo se je, da oba načina definiranja fragmentov logike odvisnosti povzročajo hierarhije:

  • Za vse (k) naj bo (mathcal D (k- / forall)) logika odvisnosti omejena na največ (k) univerzalni kvantifikatorji in naj bo (mathcal D (k-dep)) biti logika odvisnosti, omejena na atome odvisnosti oblike (eqord (vec x, y)) za (| / vec x | / leq k). Potem

    (začeti {poravnati *} mathcal D (k- / forall) & <\ mathcal D (k + 1-dep), \\ / mathcal D (k- / forall) & / leq / mathcal D (k- dep) leq / mathcal D (k + 1 - dep) konec {poravnati *})

    in

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

    glede na izrazno moč stavkov.

3.3 Negacija v logiki odvisnosti

Doslej smo domnevali, da so vsi logični izrazi odvisnosti v normalni obliki negacije in da atomi odvisnosti nikoli niso negativni. Po drugi strani je dodajanje eksplicitnega operaterja negacije jeziku logike odvisnosti nekoliko problematično, ker eksistencialna logika drugega reda ni zaprta pod negacijo. Pravzaprav je "očitno" pravilo negacije

[X / modeli / sim / phi / textrm {če in samo, če} X / ne / modeli / phi)

močno poveča izrazno moč logike odvisnosti in jo razširi na skupinsko logiko (Väänänen 2007a, b), ki je v zelo močnem pomenu enakovredna logiki polnega drugega reda (Kontinen & Nurmi 2009).

Manj močna, "dvojna" negacija (lnot) je mogoče opredeliti v skladu s pravili de Morgana, (lnot (phi / lor (land] psi) equiv (lnot / phi) land (lor] (lnot / psi)) in (lnot (obstaja v (forall v] phi) equiv / forall v (obstaja v] (lnot / phi)), plus zakon dvojne negacije (lnot / lnot / phi / equiv / psi) in pravilo

[X / modeli { lnot / eqord} (vec x, y) textrm {če in samo, če} X = / prazna garnitura)

za negacije atomov odvisnosti (Väänänen 2007a, b). Nastali jezik je izrecno enakovreden logiki odvisnosti brez negacij in opis logike odvisnosti Väänänen 2007a dejansko to negacijo obravnava kot del svojega jezika; vendar, kot je prikazano v Kontinen & Väänänen 2011, so pogoji izpolnjevanja logične formule odvisnosti in njeni negaciji med seboj malo povezani. Natančneje:

Dvojna negacija in logika odvisnosti:

Za katere koli dve logični formuli odvisnosti (phi) in (psi), tako da (phi / land / psi) ni mogoče izpolniti, obstaja formula logike odvisnosti (theta) taka, da

[M, X / modeli / theta / textrm {če in samo, če} M, X / modeli / phi)

in

[M, X / modeli / lnot / theta / textrm {če in samo, če} M, X / modeli / psi)

za vse modele (M) in ekipe (X).

Tako ni mogoče reči ničesar o dvojni negaciji (phi), le da je enakovreden nekakšnemu logičnemu izražanju odvisnosti, ki ga ne zadovolji nobena ekipa, ki zadovoljuje (phi). Ker, kot že rečeno, zakon izključene sredine ne deluje v odvisnostni logiki, to ni zelo informativna lastnost; zlasti lahko v logiki odvisnosti (z dvojno negacijo) najdemo enakovredne izraze z enakovrednimi negacijami, kot sta na primer (x / not = x / land y / not = y) in (lnot / eqord (x, y)).

3.4 Sistemi resnice, veljavnosti in dokazovanja v odvisni logiki

Tako kot neodvisna prijazna logika lahko odvisnostna logika opredeli lastnega operaterja resnice (Väänänen 2007a), torej če imamo za vse formule (phi), da je (lceil / phi / rceil) Gödelsko število (phi) potem lahko najdemo formulo (tau (x)), z (x) kot njeno edino prosto spremenljivko, tako da

[M / modeli / phi / textrm {če in samo, če}} M / modeli / tau (lceil / phi / rceil))

za vse modele (M), ki za naravne številke izpolnjujejo Peanove aksiome. To ni v nasprotju s Tarškim teoremom o nedoločljivosti, ker logika odvisnosti ni zaprta pod nasprotujočo si negacijo.

Težava odločitve, ali je stavek logike odvisnosti veljaven (to je res v vseh modelih), ni aritmetičen in dejansko popoln glede na razred (Pi_2) Hierarhije Levy. Kljub temu je bila raziskana teorija dokazovanja logike odvisnosti. Zlasti v Kontinen & Väänänen 2013 je bil razvit zanesljiv in celovit sistem dokazovanja za problem iskanja posledic teorije logike odvisnosti prvega reda.

4. Različice logike odvisnosti

V tem razdelku bomo na kratko povzeli lastnosti najbolj preučenih različic logike odvisnosti. Obstaja veliko takšnih različic in veliko je bilo narejenega na njihovi razvrstitvi in primerjavi. V tem delu bomo omenili le tiste različice, ki so posebnega pomena zaradi svoje povezanosti z ustrezno logiko odvisnosti.

4.1 Logika neodvisnosti

Namesto da razširi logiko prvega reda z atomi odvisnosti (eqord (vec x, y)), jo neodvisna logika (Grädel & Väänänen 2013) razširi na atome neodvisnosti (vec x / mathop { bot _ { vec z }} vec y), katerih predvidena razlaga je "za vsako možno izbiro (vec z), možni vrednosti (vec x) in (vec y) sta neodvisni" -in z drugimi besedami, glede na katero koli fiksno izbiro (vec z), poznavanje vrednosti, ki jo sprejme (vec x), ne bi posredovalo nobenih informacij o vrednosti, ki jo je sprejel (vec y). To je pojem, ki ima pomemben konceptualni pomen: na primer, morda želimo izraziti, da če šifrirni ključ ne pozna šifrirane različice sporočila, ne vsebuje nobene informacije o ustrezni različici z jasnim besedilom. Če (x) predstavlja šifrirano sporočilo in (y) predstavlja navadno besedilo,potem to ustreza pogoju (x / mathop { bot} y), kjer je (vec z) v tem primeru prazen. Podobno, če (k) predstavlja ključ, potem (x / mathop { bot} k) predstavlja trditev, da ključa ni mogoče sklepati iz šifriranega sporočila; in atom odvisnosti od veznice (eqord (k, x, y)) (ki bo, kot bomo kmalu videli, predstavljen v neodvisni logiki) predstavlja trditev, da je navadno besedilo lahko dekodirano glede na šifrirano sporočilo in ključ.lahko predstavimo v neodvisni logiki) predstavlja trditev, da je navadno besedilo lahko dekodirano glede na šifrirano sporočilo in ključ.lahko predstavimo v neodvisni logiki) predstavlja trditev, da je navadno besedilo lahko dekodirano glede na šifrirano sporočilo in ključ.

Formalno lahko pravilo zadovoljitve atomov neodvisnosti poda na naslednji način:

TS-indep:

(M / models_X / vec x / mathop { bot _ { vec z}} vec y), če in samo, če za vse (s, s '\ v X) z (s (vec z) = s '(vec z)) obstaja (s' '\ v X) z (s' '(vec z \, / vec x) = s (vec {x }, / vec {z})) in (s '' (vec y) = s '(vec y)).

(začni {array} {l | ccc} textbf {dodelitev} & / 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 / konec {matrika})

Logika neodvisnosti je strogo bolj izrazna kot logika odvisnosti: res ji manjka navzdol lastnost zapiranja in atom odvisnosti (eqord (vec x, y)) je enak atomu neodvisnosti (y / mathop { bot_ { vec x}} y). Poleg tega je mogoče tudi prikazati (Galliani in Väänänen 2014), da so atomi, ki so pogojeni neodvisnosti (vec x / mathop { bot _ { vec y}} vec z) pogojeni z brezpogojnimi atomi neodvisnosti (vec x / mathop { bot} vec y).

Po neodvisni logiki je neodvisnost tudi enakovredna eksistencialni logiki drugega reda (Sigma_1 ^ 1); vendar je formularno bolj ekspresiven in v Gallianiju 2012 je bilo prikazano, da lahko zajame vse nepopolne (Sigma_1 ^ 1) lastnosti ekipe, ki jih je mogoče določiti.

4.2 Logika vključevanja

Vključitvena logika (Galliani 2012, Galliani & Hella 2013) razširja logiko prvega reda z vključevalnimi atomi (vec x / subseteq / vec y), kar spominja na vključitvene teorije baz podatkov. Njegova semantika je:

TS-inc:

(M / models_X / vec x / subseteq / vec y), če in samo, če za vse (s / v X) obstaja (s '\ v X), tako da (s (vec x) = s '(vec y)).

(začni {array} {l | cc} textbf {dodelitev} & / mathbf {x_1} & / mathbf {x_2} / \ hline s_0 & 0 & 0 \\ s_1 & 0 & 1 \\ s_2 & 1 & 2 \\ s_3 & 2 & 3 / konec {matrika})

Vključitvena logika je za razliko od logike odvisnosti in neodvisnosti strogo šibkejša od eksistencialne logike drugega reda. V resnici je mogoče prikazati (Galliani & Hella 2013), da je enakovreden pozitivnemu fragmentu največje logike s fiksno točko in zato zajeti PTIME lastnosti modelov nad končno urejenimi modeli. Formulacijsko gledano je vključitvena logika strogo šibkejša od logike neodvisnosti, vendar neprimerljiva z logiko odvisnosti: dejansko pogoji izpolnjevanja njenih formul niso zaprti navzdol, ampak jih zapirajo sindikati v smislu, da

[M, X_i / modeli / phi / forall i / v I / Rightarrow M, / bigcup_i X_i / modeli / phi.)

4.3 Ekipna logika

Ekipna logika (Väänänen 2007a, b; Kontinen & Nurmi 2009) širi logiko odvisnosti, tako da ji doda protislovno negacijo (lnot). Ekspresivno je z logiko polnega drugega reda, tako glede opredelljivosti razredov modelov (Väänänen 2007b) kot glede razredov skupin, ki jih lahko logični izrazi ekipe določijo glede na dani model (Kontinen & Nurmi 2009).

4.4 Intuitionistična logika odvisnosti

Intuitionistična logika odvisnosti (Abramsky & Väänänen 2009; Yang 2013) širi logiko odvisnosti z dodajanjem implikacijskega veznika (phi / rightarrow / psi), katerega pravila zadovoljstva so v timski semantiki navedena s strani

TS - (rightarrow):

(X / modeli / phi / rightarrow / psi), če in samo, če je za vse podvrsti (Y) od (X), če (Y / modeli / phi) nato (Y / modeli / psi).

Ta operater se imenuje "intuicijska implikacija" zaradi podobnosti med njegovo semantiko in operaterjem implikacij v Kripkejevi semantiki intuicijske logike (Kripke 1965). Njegova razlaga v smislu prepričanja je povsem preprosta: če dodelitve v (X) predstavljajo stanje, za katerega neki agent meni, da je mogoče, potem lahko podmnožica (Y) od (X) pomeni rezultat posodobitev prepričanja, v kateri agent zavrača nekatera prej verjetna možna stanja stvari in (phi / rightarrow / psi) stanj, kot vsaka taka posodobitev, ki bi povzročila, da bo zadržano (phi) povzročilo tudi (psi) držati. S tega stališča je to zelo naraven koncept, ki nam omogoča, da opišemo napovedi, kako bi se takšno zastopniško stanje odzivalo na posodobitve prepričanj.

Toda zaradi univerzalnega kvantifikacije drugega reda, ki se implicitno nanaša na njegovo semantiko, ta povezovalec zadostuje za povečanje izrazne zapletenosti logike: zlasti, kot je prikazano v Yang 2013, je vsak stavek logike drugega reda enakovreden nekemu stavku intuicijske odvisnosti logika. Intuitionistična logika odvisnosti ohranja lastnost zapiranja navzdol: če ekipa izpolnjuje intuicijsko logično formulo logike odvisnosti, potem to storijo tudi vse njene podvrste.

4.5 Logika predloga odvisnosti

Doslej obravnavani odvisni in neodvisni atomi izražajo razmerja med možnimi vrednostmi spremenljivk v naboru dodelitev. Vendar pa se enake predstave o odvisnosti in neodvisnosti lahko enako uporabimo tudi pri sami predlogi, kot se to dogaja pri naravnem jezikovnem izražanju, kot je na primer "Ali bo ali ne bo opravil predmeta, odvisno samo od vsebine njegovega zadnjega izpita.".

Logika propozicijske odvisnosti obravnava takšne atome v kontekstu propozicijske logike. Logične skupine odvisnosti predloga so množice ocenjevanja (v) od atomov predloga (p_1 / ldots p_n) do ({T, F }). Njegova semantična pravila - in njihove utemeljitve - zelo zrcalijo semantiko semantike prvega reda in pravilo za atome odvisnosti je

PTS-dep:

(X / modeli / eqord (p_1 / ldots p_n, q)), če in samo, če imata dve oceni (v_1, v_2 / v X), ki se ujemata z vrednostmi (p_1 / ldots p_n) se tudi strinjajo z vrednostjo (q).

Številne različice in posplošitve logike odvisnosti prvega reda je mogoče brez težav spustiti na predlagalno raven: tako je na primer mogoče preučiti lastnosti logike predloga za vključitev, logike predloge ekipe, predloge intuicijske logike odvisnosti in tako naprej.

Medtem ko je logika odvisnosti (prvega reda) strogo bolj izrazna kot logika prvega reda, logika predloga odvisnosti ni bolj ekspresivna kot propozicijska logika, saj izhaja takoj iz dejstva, da so vse propozicijske funkcije izrazite v propozicijski logiki. Obstaja pa tesna povezava med skupinami logike odvisnosti od predloga in informacijskimi stanji radovedne logike (Groenendijk 2009; Ciardelli & Roelofsen 2011), semantični okvir za preučevanje pojma pomena in izmenjave informacij: implikacija radovedne logike je popolnoma enaka tisti, ki jo predlaga intuicijska logika odvisnosti.

Aksiomatizacije za logiko odvisnosti predloga in številne njene razširitve najdete v Yang in Väänänen 2016.

4.6 Modalna logika odvisnosti

Modalna logika odvisnosti (Väänänen 2008) in njene različice razširjajo modalno logiko, tako da ji dodajo iste atome odvisnosti (eqord (p_1 / ldots p_n, q)), ki so že obravnavani v primeru logike odvisnosti od predloga.

Pogoje njegovega zadovoljstva je mogoče opredeliti z različico semantike ekipe, v kateri se ekipe zamenjajo z množicami možnih svetov.

Veliko raziskav je preučilo kompleksnost-teoretične lastnosti te logike, njenih fragmentov in njenih razširitev (Ebbing, Lohmann, & Yang 2011; Ebbing & Lohmann 2012; Lohmann & Vollmer 2013).

5. Uporaba logike odvisnosti

5.1 Logika odvisnosti in teorija baz podatkov

Obstaja neposredna povezava med skupinami semantike ekipe in razmerji, preučenimi v teoriji relacijskih baz podatkov: glede na skupino (X) in nabor spremenljivk (vec v = v_1 / ldots v_k), ki se pojavljajo v njegovih nalogah, mogoče je določiti razmerje (X (vec v) = { langle s (v_1), / ldots, s (v_n) rangle: s / v X }). Poleg tega so atomi odvisnosti, preučeni v logiki odvisnosti, in njene variante analogni - in v mnogih primerih izhajajo iz - odvisnosti, ki se obravnavajo v teoriji baze podatkov, kot so funkcionalne odvisnosti (Väänänen 2007a), večvrednotene odvisnosti (Engström 2012) ter odvisnosti in vključenosti (Galliani 2012). Razmerje med logiko odvisnosti in teorijo baz podatkov ni prispevalo le k nadaljnjemu razvoju logike odvisnosti, ampak tudi k teoriji baze podatkov: na primer,v Hannula & Kontinen 2016 je bilo s preučevanjem podobnega problema v kontekstu timske semantike ugotovljeno končno aksiomatizacijo neomejenega problema implikacij za vključitev, funkcionalno in vgrajeno večvrednoteno teoretično bazo podatkov.

5.2 Logika odvisnosti in reprezentacija prepričanja

Kot smo razpravljali v Yang 2014 in Yang & Väänänen 2016, obstaja tesna povezava med (predlagano) intuicijsko logiko odvisnosti in radovedno logiko (Ciardelli & Roelofsen, 2011), okvir za preučevanje pomena in izmenjave informacij med agenti. Na splošno velja, da odvisni atomi in vezive preučenih v timski semantiki priznavajo naravne interpretacije v smislu prepričanj in posodobitev prepričanj, o čemer smo govorili v Galliani 2015. Trenutno je natančna narava odnosa med takšno logiko in dinamično-eppistemično logiko in njegove različice (Van Ditmarsch, van Der Hoek in Kooi 2007) so v veliki meri neraziskane, vendar obstaja veliko razlogov, da bi sumil na nadaljnje povezave med tema dvema področjema matematične in filozofske logike.

5.3 Logika odvisnosti in Arremov izrek

Teorem Arrowa (Arrow 1950) je močno vpliven rezultat teorije družbene izbire, ki na kratko kaže, da ne obstaja noben volilni sistem (to je noben sistem za pretvorbo uvrstitev posameznih preferenc med alternativami v globalno raven preferenc na družbeni ravni). ki lahko izpolnjujejo tri razumne sondirne pogoje, in sicer

  • Če ima vsak volivec prednost (A) do (B), ima skupina kot celota prednost (A) in (B);
  • Ali ima skupina kot celota prednost (A) do (B) ali obratno, je odvisno izključno od vseh volivčevih preferenc glede (A) in (B), ne pa od njihovih preferenc do drugih možnih alternativ;
  • Noben sam volivec ni diktator, torej preferenc skupine ne določa preferenc nobenega posameznega volivca.

Kot že samo besedilo kaže, drugi in tretji pogoj priznavata naravno branje glede na odvisnost in neodvisnost: v resnici, kot je razvidno iz Pacuit & Yang 2016, je mogoče Arrowov izrek formalizirati v neodvisni logiki in dokazati v ustreznem sistemu naravne dedukcije.

5.4 Kvantna logika moštva in Bellove neenakosti

V Hyttinenu, Paoliniju in Väänänenu 2015 je predstavljena različica predloga logike ekipe, imenovana kvantna logika moštva. V tem formalizmu so ekipe nadomeščene s kvantnimi skupinami, ki se od običajnih skupin predloge logične skupine razlikujejo po tem, da omogočajo, da vrednosti določenih spremenljivk niso določene glede na določene vrednotenje in v tem, da omogočajo več primerov istega vrednotenje (s čimer se doda kvantitativni vidik semantiki ekipe). Nato se določi semantika v kvantnih skupinah za jezik, ki omogoča določitev neenakosti glede verjetnosti dogodkov in zanj je razvit zanesljiv in popoln dokazni sistem; in končno se pokaže, da Bellove neenakosti priznavajo nasprotne primere v teh sistemih,kot to počnejo po napovedih kvantne mehanike in po eksperimentalnih dokazih (Einstein, Podolsky, & Rosen 1935; Bell 1964; Aspect, Grangier, & Roger 1981), medtem ko v klasični različici tega okvira ne držijo.

Bibliografija

  • Abramsky, Samson in Jouko Väänänen, 2009, "Od IF do BI: Zgodba o odvisnosti in ločitvi", Synthese, 167 (2): 207–230. doi: 10.1007 / s11229-008-9415-6
  • Arrow, Kenneth J., 1950, "Težavnost koncepta socialnega varstva", Časopis za politično ekonomijo, str.328–346. doi: 10.1086 / 256963
  • Aspekt, Alain, Philippe Grangier in Gérard Roger, 1981, "Eksperimentalni testi realističnih lokalnih teorij z Belovim teoremom", Fizični pregledi, 47 (7): 460–463. doi: 10.1103 / PhysRevLett.47.460
  • Bell, JS, 1964, "O paradoksu Einstein-Podolsky-Rosen", Fizika, 1 (3): 195–200.
  • Ciardelli, Ivano in Floris Roelofsen, 2011, "Navidezna logika", Časopis za filozofsko logiko, 40 (1): 55–94. doi: 10.1007 / s10992-010-9142-6
  • van Ditmarsch, Hans, Wiebe van der Hoek in Barteld Kooi, 2007, Dynamic Epistemic Logic, (Synthese Library 337), Dordrecht: Springer. doi: 10.1007 / 978-1-4020-5839-4
  • Durand, Arnaud in Juha Kontinen, 2012, “Hierarhije v logiki odvisnosti”, Transakcije ACM o računski logiki (TOCL), 13 (4): 1–21. doi: 10.1145 / 2362355.2362359
  • Ebbing, Johannes in Peter Lohmann, 2012, "Kompleksnost preverjanja modela za logiko odvisnosti od modalitete", SOFSEM 2012: Mednarodna konferenca o trenutnih trendih teorije in prakse računalništva, (Lekcije za računalništvo, 7147), Berlin, Heidelberg: Springer, str. 226–237. doi: 10.1007 / 978-3-642-27660-6_19
  • Ebbing, Johannes, Peter Lohmann in Fan Yang, 2013, "Preverjanje modelov za modalno intuicijsko logiko odvisnosti", Mednarodni simpozij o logiki, jeziku in računanju v Tbilisiju 2011 (Lekcije za računalništvo, 7758), Berlin, Heidelberg: Springer, str. 231–256. doi: 10.1007 / 978-3-642-36976-6_15
  • Einstein, A., B. Podolsky in N. Rosen, 1935, "Ali lahko kvantno-mehanski opis fizične resničnosti štejemo za popolnega?" Fizikalni pregled, 47 (10): 777–780. doi: 10.1103 / PhysRev.47.777
  • Engström, Fredrik, 2012, „Splošni kvantifikatorji v logiki odvisnosti“, Journal of Logic, Language and Information, 21 (3): 299–324. doi: 10.1007 / s10849-012-9162-4
  • Fagin, Ronald, 1974, "Splošni spektri prvega reda in prepoznavni polinomski časi", Kompleksnost računanja (Zbornik 7 SIAM-AMS), Richard M. Karp (ur.), Providence, RI: American Mathematical Society, pp. 27–41.
  • Galliani, Pietro, 2012, “Odvisnosti od vključevanja in izključevanja v timski semantiki - o nekaterih logikah nepopolnih informacij”, Anali čiste in uporabne logike, 163 (1): 68–84. doi: 10.1016 / j.apal.2011.08.005
  • –––, 2015, „Doksastična interpretacija timske semantike“, Logika brez meja: eseji o teoriji kompletov, teoriji modelov, filozofski logiki in filozofiji matematike (Ontos Mathematical Logic, 5), Åsa Hirvonen, Juha Kontinen, Roman Kossak, in Andrés Villaveces (ur.), Berlin, Boston: De Gruyter, str. 167–192. doi: 10.1515 / 9781614516873.167
  • Galliani, Pietro in Lauri Hella, 2013, "Logika vključevanja in logika s fiksno točko", Computer Science Logic 2013 (Leibniz International Proceedings in Informatika (LIPIcs), 23), Dagstuhl, Nemčija: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 281–295. doi: 10.4230 / LIPIcs. CSL.2013.281
  • Galliani, Pietro in Jouko Väänänen, 2014, “O logiki odvisnosti”, v Johan van Benthem o logiki in dinamiki informacij (izjemni prispevki k logiki, 5), Alexandru Baltag in Sonja Smets (ur.), Cham: Springer, str. 101– 119. doi: 10.1007 / 978-3-319-06025-5_4
  • Grädel, Erich in Jouko Väänänen, 2013, „Odvisnost in neodvisnost“, Studia Logica, 101 (2): 399–410. doi: 10.1007 / s11225-013-9479-2
  • Groenendijk, Jeroen, 2009, "Navidezna semantika: dve možnosti za ločitev", v Peter Bosch, David Gabelaia in Jérôme Lang (ur.), Sedmi mednarodni simpozij o jeziku, logiki in računanju v Tbilisiju (zvezek predavanja iz računalništva: letnik 5422), Springer-Verlag, str. 80–94. doi: 10.1007 / 978-3-642-00665-4_8
  • Hannula, Miika in Juha Kontinen, 2016, "Končna aksiomatizacija pogojne neodvisnosti in vključenosti". Informacije in računanje, 249: 121–137. doi: 10.1016 / j.ic.2016.04.001
  • Henkin, Leon, 1961, "Nekaj opomb o neskončno dolgih formulah", Infinitistic Methods (Zbornik simpozija o osnovah matematike, Varšava, 1959), Oxford: Pergamon Press, str. 167–183.
  • Hodges, Wilfrid, 1997, „Sestavljiva semantika za jezik nepopolnih informacij“, Logični vestnik IGPL, 5 (4): 539–563. doi: 10.1093 / jigpal / 5.4.539
  • Hyttinen, Tapani, Gianluca Paolini in Jouko Väänänen, 2015, „Kvantna timska logika in Bell-ove neenakosti“, Pregled simbolične logike, 8 (4): 722–742. doi: 10.1017 / S1755020315000192
  • Kontinen, Juha in Ville Nurmi, 2009, "Ekipna logika in logika drugega reda", v zborniku 16. mednarodne delavnice o logiki, jeziku, informacijah in računanju (Beležke iz računalništva, 5514), Berlin, Heidelberg: Springer, str. 230–241. doi: 10.1007 / 978-3-642-02261-6_19
  • Kontinen, Juha in Jouko Väänänen, 2009, "O določljivosti v logiki odvisnosti", Journal of Logic, Language and Information, 18 (3): 317–332.doi: 10.1007 / s10849-009-9082-0
  • –––, 2011, »Opomba o negaciji v logiki odvisnosti«, Notre Dame Journal of Formal Logic, 52 (1): 55–65. doi: 10.1215 / 00294527-2010-036
  • –––, 2013, „Aksiomatiziranje posledic prvega reda v odvisnosti logike“, Anali čiste in uporabne logike, 164 (11): 1101–1117. doi: 10.1016 / j.apal.2013.05.006
  • Kripke, Saul A., 1965, „Semantična analiza intuicijske logike I“, v formalnih sistemih in rekurzivnih funkcijah: Zbornik osmega logičnega kolokvija, Oxford, julij 1963 (Študije v logiki in temelji matematike, 40), John N. Crossley in Michael AE Dummett (ur.), Severna Holandija, str. 92–130. doi: 10.1016 / S0049-237X (08) 71685-9
  • Lohmann, Peter in Heribert Vollmer, 2013, “Rezultati zapletenosti za logiko modalne odvisnosti”, Studia Logica, 101 (2): 343–366. doi: 10.1007 / s11225-013-9483-6
  • Pacuit, Eric in Fan Yang, 2016, "Odvisnost in neodvisnost v družbeni izbiri: Arremova teorema", v logiki odvisnosti, Samson Abramsky, Juha Kontinen, Jouko Väänänen in Heribert Vollmer (ur.), Dordrecht: Springer, str. 235–260. doi: 10.1007 / 978-3-319-31803-5_11
  • Väänänen, Jouko, 2007a, Logika odvisnosti: nov pristop k neodvisnosti prijazni logiki, (Besedila študentov London Mathematical Society, 70), Cambridge: Cambridge University Press. doi: 10.1017 / CBO9780511611193
  • –––, 2007b, „Ekipna logika“, v Interaktivni logiki: Izbrani prispevki iz delavnice 7. avgusta Avgusta de Morgana (Besedila v logiki in igrah, 1), Johan van Benthem, Dov Gabbay in Benedikt Löwe (ur.), Amsterdam: Amsterdam University Press, str. 281–302.
  • –––, 2008, „Modal Dependence Logic“, Nove perspektive na igre in interakcijo (Besedila v logiki in igrah, 4), Krzysztof R. Apt in Robert van Rooij (ur.), Amsterdam: Amsterdam University Press, str.237– 254.
  • Yang, Fan, 2013, “Izražanje sodb drugega reda v intuicijski logiki odvisnosti”, Studia Logica, 101 (2): 323–342. doi: 10.1007 / s11225-013-9476-5
  • –––, 2014, „O razširitvah in variantah logike odvisnosti: študija intuicijskih povezovalcev v nastavitvi timske semantike“. Doktorska naloga, Univerza v Helsinkih.
  • Yang, Fan in Jouko Väänänen, 2016, "Propozicijska logika odvisnosti", Anali čiste in uporabne logike, 167 (7): 557–589. doi: 10.1016 / j.apal.2016.03.003

Akademska orodja

sep man ikona
sep man ikona
Kako navajati ta vnos.
sep man ikona
sep man ikona
Predogled PDF različice tega vnosa pri Društvu prijateljev SEP.
ikona
ikona
Poiščite to temo vnosa pri projektu Internet Filozofija Ontologija (InPhO).
ikona papirjev phil
ikona papirjev phil
Izboljšana bibliografija za ta vnos pri PhilPapers s povezavami do njegove baze podatkov.

Drugi internetni viri

  • Logika odvisnosti od Wikipedije
  • Predstavitve v akademski kolokvijski odvisnosti logike, Amsterdam, 2014

Priporočena: