Sõltuvusloogika

Sisukord:

Sõltuvusloogika
Sõltuvusloogika
Anonim

Sisenemise navigeerimine

  • Sissesõidu sisu
  • Bibliograafia
  • Akadeemilised tööriistad
  • Sõprade PDF-i eelvaade
  • Teave autori ja tsitaadi kohta
  • Tagasi üles

Sõltuvusloogika

Esmakordselt avaldatud 23. veebruaril 2017

Sõltuvusloogika on esimese järgu loogika laiendus, mis lisab sellele sõltuvuse aatomeid, st vormi (eqord (x_1 / ldots x_n, y)) avaldisi, mis väidavad, et (y) väärtus on funktsionaalselt sõltuv (teisisõnu, määratud) väärtustega (x_1 / ldots x_n). Need aatomid võimaldavad mittelineaarselt järjestatud sõltuvusmustrite täpsustamist muutujate vahel, mis on samas mõttes IF-Logicu kaldkriipsutega; kuid erinevalt IF-loogikast eraldab sõltuvusloogika kvantifitseerimise selliste sõltuvuse / sõltumatuse tingimuste täpsustamisest. Sõltuvusloogika peamine semantika, mida nimetatakse meeskonna semantikaks, üldistab Tarski semantikat, lastes avaldistel olla rahul või mitte rahul olla pigem muutuva ülesande komplektide kui üksikute ülesannete osas. See semantika eelneb sõltuvusloogika tegelikule arengule ja selle töötas algselt välja Wilfrid Hodges IF-loogika kontekstis (Hodges 1997). Samuti on olemas sõltuvusloogika mänguteoreetiline semantika, mis põhineb ebatäiusliku teabe mängudel ja on umbes analoogne iseseisvussõbraliku loogika mänguteoreetilise semantikaga (Väänänen 2007a). Sensu stricto, termin „sõltuvusloogika” tähistab eranditult keelt, mis saadakse ülalnimetatud funktsionaalsete sõltuvuse aatomite lisamisel esimese astme loogika keelde. kuid seda terminit kasutatakse ka üldisemas tähenduses uurimisvaldkonnale, kus uuritakse loogika omadusi, mis on saadud, lisades esimese järjekorra loogikale erinevad sõltuvuse ja sõltumatuse mõisted, näiteks iseseisvusloogika (Grädel & Väänänen 2013),intuitsiooniline sõltuvusloogika (Yang 2013) või kaasamisloogika (Galliani 2012, Galliani & Hella 2013) või isegi loogika need, mis laiendavad sarnaseid aatomeid kasutades muid loogilisi raamistikke, nagu modaalsõltuvuse loogika puhul (Väänänen 2008). Selles artiklis kasutatakse mõistet “sõltuvusloogika” just nimelt sõltuvusloogikaks ning selle “variantide ja üldistuste” tähistamiseks kasutatakse terminit “sõltuvuse ja sõltumatuse loogika”.ning terminit „sõltuvuse ja sõltumatuse loogika” kasutatakse selle variantide ja üldistuste tähistamiseks.ning terminit „sõltuvuse ja sõltumatuse loogika” kasutatakse selle variantide ja üldistuste tähistamiseks.

  • 1. Sõltuvusmustrid esimese järjekorra loogikas ja selle laiendites
  • 2. Meeskonna semantika

    2.1 Mänguteoreetiline semantika

  • 3. Omadused

    • 3.1 Ekspressiivsus
    • 3.2 Sõltuvusloogika hierarhiad
    • 3.3 Eitus sõltuvusloogikas
    • 3.4 Tõe-, kehtivus- ja tõestussüsteemid sõltuvusloogikas
  • 4. Sõltuvusloogika variandid

    • 4.1 Iseseisvusloogika
    • 4.2 Kaasamise loogika
    • 4.3 Meeskonna loogika
    • 4.4 Intuitionistlik sõltuvusloogika
    • 4.5 Propositsiooniline sõltuvusloogika
    • 4.6 Modaalsõltuvuse loogika
  • 5. Sõltuvusloogika rakendused

    • 5.1 Sõltuvusloogika ja andmebaasi teooria
    • 5.2 Sõltuvusloogika ja veendumuste kujutamine
    • 5.3 Sõltuvusloogika ja Nooli teoreem
    • 5.4 Kvantmeeskonna loogika ja Belli ebavõrdsus
  • Bibliograafia
  • Akadeemilised tööriistad
  • Muud Interneti-ressursid
  • Seotud kirjed

1. Sõltuvusmustrid esimese järjekorra loogikas ja selle laiendites

Esmajärgulise loogika üks omadusi, mis moodustab suure osa selle ekspressiivsusest ja rakendatavusest, on asjaolu, et see võimaldab kvantifitseerijaid pesastada ja seega võimaldab täpsustada kvantifitseeritavate muutujate vahelist sõltuvusmustrit. Mõelge näiteks (loodetavasti valele) väitele, et “iga poiss armastab mõnda tüdrukut, kes armastab mõnda teist poissi”. Seda saab otse tõlkida esimese astme loogikaks

) silt {1} silt {eq: boygirl1} algab {joondamine} ja / xforall x (poiss (x) parempoolne nool / eksisteerib y (tüdruk (y) maa / armastab (x, y) maa {} & / quad / eksisteerib z (poiss (z) maa x / not = z / maa / armastab (y, z)))) lõpp {joondus})

kelle tõelisus, vastavalt Tarski tavapärasele semantikale, on täpselt selline, mida võiks eeldada: ülaltoodud väljend vastab tõele ainult siis, kui iga poisi jaoks on võimalik leida tüdruk (g) ja poiss (b ') selliselt, et (b) armastab (g) ja (g) armastab (b') ning (b) ja (b ') pole samad. Tüdruku identiteet (g) võib muidugi sõltuda esimese poisi isikust (b) - selle väljenduse tõesuse tagamiseks ei nõua me, et kõik poisid oleksid armunud kõikidesse tüdrukutesse - ja peale selle võib teise poisi identiteet (b ') sõltuda nii esimese poisi identiteedist (b) (kuna (b') peab erinema (b)) ja alates tüdruku (g), keda (b) armastab, identiteedist. Seega on meie kvantifitseeritud muutujate sõltuvusmuster järgmine: (y) sõltub (x),samas (z) sõltub nii (x) kui ka ((y)). Süntaktilisest aspektist peegeldub see asjaolus, et (eksisteerib y) kuulub (forall x), samas kui (eksisteerib z) on mõlema (forall x) ja (eksisteerib y).

Operaatorite sõltuvusmustrite erinevusi saab kasutada oluliste eristuste vormistamiseks, näiteks funktsiooni järjepidevuse vaheliseks muutmiseks (f)

) forall x / forall / epsilon / eksisteerib / delta / forall x '(| x - x' | <\ delta / paremnool | f (x) - f (x ') | <\ epsilon))

ja selle ühtlane järjepidevus

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

või esimese astme loogika intentsionaalsetes laiendites väljendada erinevust De Dicto ja De Re näitude vahel (nt “Igal inimesel on võimalik hulluks minna” võib mõista nii, et see väidab, et see on iga inimese jaoks (p), on võimalik, et (p) on hull, (jätkub x (inimene (x) parempoolne nool / Teemant / hull (x))) või kui väide, et on võimalik, et kõik on hullud koos, (Diamond / forall x (inimene (x) paremnool / hull (x)))).

Esimese astme loogika kvantifitseeritud muutujate vahelised sõltuvusmustrid on tingimata mööduvad, kuna seda näitab nende seos vastavate alamlausete ulatusega: kui (eksisteerib y) on (forall x) ja (eksisteerib z) on (eksisteerib y) ulatuses, siis ilmtingimata (eksisteerib z) on (forall x). Lisaks on kõigi kvantifikaatorite komplekt, mille ulatuses mõni alamvorm (alpha) asub, lineaarselt järjestatud: kui (alpha) on (Q_1 x_1) ja (Q_2 x_2), siis kas (Q_1 x_1) kuulub ulatusse (Q_2 x_2) või vastupidi.

See piirab esimese järjekorra loogika ekspressiivseid võimalusi. Näiteks oletagem, et soovime muuta oma varasemat väidet poiste ja tüdrukute kohta järgmiselt: iga poiss armastab mõnda tüdrukut, kes armastab mõnda teist poissi, ja selle teise poisi saab iseseisvalt valida. Mida see intuitiivselt öeldes tähendab, on piisavalt lihtne: iga poisi jaoks (b) võime leida tüdruku (g) nii, et (b) armastaks (g), ja iga sellise tüdruku jaoks leida poiss (b ') selline, et (g) armastaks (b') ja (b / not = b '), ja lisaks sellele võime leida teise poisi identiteedi (b') teadmata sellest, et (b), ainult tüdruku (g) identiteedi alusel. Mõnes stsenaariumis võib see siiski tõsi olla, näiteks kui kaks poissi (b_1) ja (b_2) armastavad vastavalt kahte tüdrukut (g_1) ja (g_2),kes aga armastavad vastavalt ainult vastavalt (b_2) ja (b_1). Siiski on hõlpsasti näha, et see pole samaväärne meie varasema väitega: näiteks kui meie universum koosneb (nagu ülaltoodud punktis b) kahest poisist (b) ja (b ') ja tüdrukust (g) ja (b) ja (b ') mõlemad armastavad (g), kes armastavad mõlemat, siis on meie eelmine väide tõene, kuid praegune on vale.

[kaks sarnast joonist, mõlemal joonisel on ülaosas horisontaalse tühikuga eraldatud sõnad 'poisid' ja 'tüdrukud'. Joonisel (a) on punkt b1 vasakus ülanurgas, g1 paremas ülanurgas, b2 vasakus alanurgas ja g2 paremas alanurgas. Nooled suunavad punktidesse g1 kuni b1, alates b1 kuni g2, alates g2 kuni b2 ja b2 kuni g1. Joonisel (b) on vasakul ülaservas b1, vasakus alanurgas b2, paremas keskel g1. Nool osutab punktidele b1 ja g1 ning punktidele b1 ja g1 ja sarnaselt punktidele b2 kuni g1.]
[kaks sarnast joonist, mõlemal joonisel on ülaosas horisontaalse tühikuga eraldatud sõnad 'poisid' ja 'tüdrukud'. Joonisel (a) on punkt b1 vasakus ülanurgas, g1 paremas ülanurgas, b2 vasakus alanurgas ja g2 paremas alanurgas. Nooled suunavad punktidesse g1 kuni b1, alates b1 kuni g2, alates g2 kuni b2 ja b2 kuni g1. Joonisel (b) on vasakul ülaservas b1, vasakus alanurgas b2, paremas keskel g1. Nool osutab punktidele b1 ja g1 ning punktidele b1 ja g1 ja sarnaselt punktidele b2 kuni g1.]

Kaks stsenaariumi, milles ((ref {eq: boygirl1})) on tõene. Punktis a võib (z) valida sõltumatult hulgast (x); punktis b seda ei saa.

Kuid pole selge, kuidas seda tingimust esimese järjekorra loogikas vormistada. Sisuliselt peaksime muutma ((ref {eq: boygirl1})) nii, et (z) ei kuuluks (x) ja seega ei sõltu sellest; siiski tahaksime, et (z) sõltuks (y) ja (y) (x) -st. Nagu just arutatud, pole selline sõltuvusmuster siiski esimese astme loogikas realiseeritav. Saame probleemist kõrvale hiilida kõrgema järgu kvantifitseerimise abil: tõepoolest on näha seda väljendit

) silt {2} silt {boygirl2} alusta {joonda} ja / eksisteerib F / forall x (poiss (x) parempoolne nool / eksisteerib y (tüdruk (y) maa / armastab (x, y) maa / poiss (F (y)) maa {} & / quad x / not = F (y) land / armastab (y, F (y)))) end {joondada})

hõlmab meie kavandatud tõlgendust, kuid ainult funktsioonide eksistentsiaalse kvantifitseerimise hinnaga.

Võimalik alternatiiv oleks laiendada esimese järgu loogika süntaksit, et kaotada kvantifitseeritud muutujate vahelise sõltuvuse mustrite piirangud. Sellel teel kulgeb hargneva kvantifikaatori loogika (Henkin 1961), kus ((ref {boygirl2})) tõetingimused vastavad

) silt {3} silt {boygirl3} alusta {joonda} ja / vasakule (alusta {smallmatrix} forall x & / eksisteerib y \\ / forall z & / eksisteerib w / end {smallmatrix} paremal) (poiss (x) parempoolne nool (tüdruk (y) maa / armastab (x, y) maa {} & / quad (y = z / parempoolne nool (poiss (w) maa x / not = w / land / armastab (z, w)))))), / end {joonda})

ja sõltumatussõbralikule loogikale, milles ((ref {boygirl2})) on samaväärne

) silt {4} silt {boygirl4} alusta {joonduma} ja / xforall x / eksisteerib y (poiss (x) parempoolne nool (tüdruk (y) maa / armastab (x, y) maa (olemas z / x) (poiss (z) maa {} & / quad x / not = z / maa / armastab (y, z))))). / lõpp {joonda})

Me ei anna siin üksikasjalikku selgitust nende kahe formalismi semantika kohta; piisab, kui öelda, et ((ref {boygirl3})) väärtus (w) ei sõltu (x) ja (y) väärtustest (kuigi see võib sõltuda väärtusest (z)), kuna nad kuuluvad keeruka kvantifikaatori erinevatesse „ridadesse” (vasakul (algavad {smallmatrix} forall x & / eksisteerib y \\ / forall z & / eksisteerib w / end {smallmatrix } paremal)), samas kui ((ref {boygirl4})) ei sõltu (z) väärtus (x) väärtusest, kuna see sõltuvus on otseses mõttes "vähendatud" kvantifikaatori abil ((olemas z / x)).

Nagu näeme, on hargnevale kvantifikaatorloogikale ja sõltumatussõbralikule loogikale ühine tunnus see, et need ei eralda muutujate kvantifitseerimist mittestandardsete sõltuvusmustrite spetsifikatsioonist: nagu esimese astme loogika puhul, kas kvantifitseeritud muutuja (v_1) sõltub või ei sõltu mõnest teisest kvantifitseeritavast muutujast (v_2), mis määratakse nende kvantifikaatorite vastava positsiooni ja vormi järgi.

Sõltuvusloogika esindab teistsugust lähenemist esimese järgu loogika laiendamise probleemile ((ref {boygirl2})). Võrreldes ((ref {eq: boygirl1})), on ainus uudne tingimus see, mis väidab, et (z) väärtus määratakse (st funktsionaalselt sõltub) väärtusest (y); ja see vastab uuele aatomi tingimusele (eqord (y, z)), mida nimetatakse sõltuvusaatomiks, mille kavandatud tähendus on, et (väärtus) (z) on funktsiooni väärtusest (y). Erinevalt hargneva kvantifikaatori loogika või sõltumatussõbraliku loogika juhtumitest on see tingimus väärtuste üle, mida (y) ja (z) võib võtta, mitte tingimus kvantitaatori käitumise kohta ((eksisteerib z)): tõepoolest, üldiselt pole põhjust nõuda, et (z) oleks üldse kvantifitseeritud muutuja - see võib olla hoopis vaba muutuja,või mõni keerukas termin, mis hõlmab mitut muutujat.

Sõltuvusloogikas saab ((ref {boygirl2})) vormistada kujul

) silt {5} silt {boygirl5} alusta {joonda} ja / forall x / eksisteerib y / eksisteerib z (eqord (y, z) maa (poiss (x) parempoolne nool (tüdruk (y)) maa / armastab (x, y) parempoolne nool {} & / quad (poiss (z) maa x / not = z / maa / armastab (y, z))))) lõpp {joondus})

((Ref {boygirl2})), ((ref {boygirl3})), ((ref {boygirl4})) ja ((ref {boygirl5}) tõetingimused) on täpselt samad: iga mudel, mis rahuldab ühte neist väljenditest (vastavates keeltes), vastab kõigile neljale. Üldisemalt, nagu näeme, on eksistentsiaalse teise järgu loogika, sõltumatussõbraliku loogika ja sõltuvusloogika väljendusjõud mudeliklasside määratletavuse osas täpselt samad. See ei kehti aga vabade muutujatega valemite puhul; ja lisaks saab neid loogikaid laiendada ja muuta märkimisväärselt erinevate joonte järgi.

2. Meeskonna semantika

Meeskonna semantika, mille Wilfrid Hodges arendas esmakordselt välja iseseisvuse sõbraliku loogika kontekstis (Hodges 1997), on Tarski esimese astme loogika semantika üldistus juhul, kui muutujatele on mitu elementi määratud. Selliste ülesannete komplektid, mida ajaloolistel põhjustel nimetatakse meeskondadeks, moodustavad meeskonna semantika põhilise semantilise idee ja valemid on rahul või ei rahuldu nende, mitte üksikute ülesannete osas. Seost meeskonna semantika ja Tarski semantika vahel näitab järgmine tulemus, mis hoiab sõltuvusloogikat ja kõiki selle esimese järgu variante:

Konservatiivsus:

meeskond (X) (meeskonna semantika tähenduses) rahuldab esimese järgu valemi ainult siis, kui kõik ülesanded (X-is X) vastavad sellele (Tarski semantika tähenduses).

Üldisemalt võib meeskondi mõista kui veendumuste kogumeid, mis esindavad kõigi maailma olekute kogumit (= ülesandeid), mida mõni agent peab võimalikuks. Siis vastab meeskond (X) mõnele valemile (phi) ainult siis, kui (phi) kehtib siis, kui (X) on kõigi võimalike olekute kogum; ja sel juhul kirjutame (X / mudelid / phi) (või (M, X / mudelid / phi), kui mudeli (M) valik pole selge). Selles osas uurime meeskonna semantika reegleid ja nende tõlgendamist selle põhimõtte osas; siis arutame järgmises osas, kuidas see tuleneb ka sõltuvusloogika ebatäiuslikust infomängust-teoreetilisest semantikast.

Uute sõltuvusaatomite (eqord (x_1 / ldots x_n, y)) tingimus, mis vastavad väitele, et (y) väärtus on funktsiooni (x_1 / ldots x_n), on kergesti mõistetav:

TS-dep:

(X / mudelid ~ / eqord (x_1 / ldots x_n, y)) siis ja ainult siis, kui mõni teine ülesanne (s_1, s_2 / X-is), mis lepivad kokku (x_1 / ldots väärtused x_n) lepivad kokku ka (y) väärtuses.

Oletagem näiteks, et (X) on kolme muutuja (x_1), (x_2) ja (y) ülesannete kogum, kus (x_1) tähistab kandidaadi kodakondsust positsioon, (x_2) tähistab nende tulemust (vastavalt sobivale hindamismeetodile) ja (y) tähistab seda, kas nad aktsepteeriti või lükati tagasi. Siis vastab aatom (eqord (x_2, y)) väitele, et pakkumise määrab ainult skoor: kui kahel kandidaadil on ühesugune skoor, saavad nad täpselt sama pakkumise, sõltumata muust tegurist. Sõltuvuse aatomi erijuhu annavad püsivuse aatomid (eqord (y)), mille meeskond rahuldab vastavalt ülaltoodud semantikale ainult siis, kui kõik tema ülesanded lepivad kokku (y).

) alusta {massiiv} {l | ccc} textbf {loovutamine} & / 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})

Tabel 1: meeskond (X), kus (y = x_1 + x_2). Siin (y) on funktsioonide (x_1) ja (x_2) funktsioon, seega (= \! \! (X_1 x_2, y)) kehtib; aga (y) ei ole funktsiooni (x_1) üksi, nii et (= \! \! (x_1, y)) ei kehti.

Sama tõlgenduse kohaselt kehtivad esimese astme litraatide ja sidesõnade reeglid (lihtsuse huvides eeldame, et meie avaldised on eitus normaalses vormis; ja nagu tavaliselt, eeldame, et sõltuvusaatomite negatiivid pole kunagi täidetud). lihtne tuletada:

TS-valgustatud:

kõigi esimese järgu litrite (alpha), (X / mudelid / alpha) jaoks ja ainult siis, kui kõigi ülesannete jaoks (s / X-is), (s / mudelid / alpha) Tarski semantika tavamõistes;

TS - (maa):

(X / mudelid / phi / maa / psi) siis ja ainult siis, kui (X / mudelid / phi) ja (X / mudelid / psi).

Väärib märkimist, et nagu nende reeglite järgi juba näeme, ei pea välistatud keskosa seadus sõltuvusloogikat (samamoodi nagu see ei kehti iseseisvuse sõbralikus loogikas): näiteks kui meeskond (X) sisaldab nii ülesandeid (s) koos (s (x) = s (y)) kui ka ülesandeid (s ') koos (s' (x) not = s '(y)) siis (X / ei / mudelid x = y) ja (X / ei / mudelid x / ei = y). Igal juhul tutvustame selles jaotises sõltuvusloogika keelt ilma selge eitusoperaatorita; siis arutame hiljem selle keelele lisamise tagajärgi.

Aga universaalne kvantifitseerimine? Millistel asjaoludel peaks meeskonnas olema üldtunnustatud väljend (forall v / psi)? Jällegi peame meenutama intuitsiooni, mille kohaselt meeskond esindab asjade võimalikke olekuid. Kui soovime hinnata (forall v / psi), siis milliste võimalike olekute suhtes peaksime hindama (psi)? Loomulik vastus on, et peaksime arvestama kõigi asjadega, mis erinevad (X) omadest, ainult väärtuse (v) osas. See õigustab järgmist reeglit:

TS - (forall):

(X / mudelid / forall v / psi) ainult siis, kui (X [M / v] mudelid / phi), kus (X [M / v]) on komplekt ({s ': / eksisteerib s / kaustas X / mbox {st} s' / sim_v x })

kus (s '\ sim_v s) tähendab, et kaks ülesannet (s) ja (s') erinevad üksteisest kõige rohkem muutuja (v) väärtuse osas.

[X = / alga {massiiv} {l | c} textbf {assignment} & x \\ / hline s_0 & 0 \\ s_1 & 1 / end {array} Rightarrow X [M / y] = / alga {massiiv} {l | c | c} textbf {loovutamine} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 \\ s'_3 & 1 & 1 / lõpp {array})

Tabel 2: (X) ja (X [M / y]) kahe elemendiga mudelites (0) ja (1).

Mõelgem nüüd disjunktsioonile. Millal peaks (phi / lor / psi) käes hoidma? Sellele vastuseks tuletagem veel kord meelde, et meeskondi võib mõista võimalike olekute kogumina ja seetõttu esindab kahe meeskonna (Y) ja (Z) liit kõiki asju, mis võivad ilmneda juhul, kui on tegemist näiteks Y (Y) või (Z) -ga. Seega, kui meeskondade komplekt rahuldab kaks valemit (phi) ja (psi), siis ({Y_1 / ldots Y_n, / ldots }) ja ({Z_1 / ldots Z_n, / ldots }), nende disjunktsiooni (phi / lor / psi) peaks rahuldama meeskondade komplekt ({Y_i / cup Z_j: i, j / in 1, / ldots }) või samaväärselt

TS - (lor):

(X / mudelid / phi / lor / psi) ainult siis, kui (X = Y / tass Z) kahe võistkonna jaoks (Y) ja (Z) näiteks (Y / mudelid / phi) ja (Z / mudelid / psi).

Siinkohal tasub rõhutada, et me ei nõua üldiselt, et (Y) ja (Z) oleksid teineteisest lahus. Allapoole jääva sulgemisomaduse tõttu, mida me varsti arutame, ei muudaks see lisatingimus sõltuvusloogika semantilist tähendust; kuid sõltuvusloogika teatud laiendite ja variantide puhul oleks see lisanõue vastuolus lokaalsuse põhimõttega, mille kohaselt avalduse rahuldamise tingimused sõltuvad ainult selles vabalt esinevate muutujate väärtustest (Galliani 2012).

Samuti on oluline märkida, et sõltuvusloogikas pole disjunktsioon idempotentne: näiteks (eqord (x, y) lor / eqord (x, y)) ei ole samaväärne (eqord (x), y)), ja meeskond (X) on sellega rahul ja ainult siis, kui iga (3) jaotuses (X) kokku lepitud kolme ülesande osas on vähemalt kaks kokku leppinud (y). See võib tunduda pisut intuitiivne; kuid see on otsekohene tagajärg tõsiasjale, et meie tõlgenduse kohaselt tuleb (eqord (x, y) lor / eqord (x, y)) lugeda nii, nagu “asjade kõik võimalikud seisundid tulenevad ühest kaks asjade olekukomplekti ja mõlemas (y) on funktsiooni (x)”. Kuna funktsioonide liit ei ole üldiselt funktsioon, on väike üllatus, et sõltuvusloogika lahutamine ei ole ilmne.

Lõpuks vaatleme eksistentsiaalse kvantifitseerimise juhtumit. Millal meeskond rahuldab väljendit (on olemas v / psi)? Sellele vastamiseks võime kõigepealt kaaluda piiranguoperaatori tõlgendamist, mis annab meeskonna (X) korral tulemuseks muutuja (v) saamiseks meeskonna (X _ { tagasilöögi v}).) (kui see on olemas) kõigist ülesannetest (s / X-is) (ja kuna (X) on komplekt, ahendage identsed ülesanded). Seda võib mõista kui unustamistoimingut, mille käigus kustutame kogu teabe väärtuse (v) kohta - näiteks seetõttu, et see, mida me selle väärtuse kohta uskusime, oli ebausaldusväärne või selle väärtuse muutmise tõttu. Oletagem nüüd, et (X _ { kaldkriips v} = Y _ { kaldkriips v}): siis meie tõlgendusessee tähendab, et asjade võimalike olekute kogumid, mida tähistavad (X) ja (Y), ei ühti kõige enam väärtusega (v). Seega, kui (Y) vastab tingimusele (phi), võime öelda, et (X) vastab (phi), kui mitte väärtusele (y), või samaväärselt, see (X) vastab (eksisteerib v / psi). See õigustab järgmist reeglit:

TS - (on olemas):

(X / mudelid / eksisteerib v / psi) muutujate (X) ja (v) kohal siis ja ainult siis, kui mõni (Y) on olemas, nii, et (X _ { kaldkriips v} = Y _ { kaldkriips v}) ja (Y / mudelid / psi).

On lihtne kontrollida, kas see on nii ja ainult siis, kui (Y) on kujul (X [F / y] = {s [a / y]: s / X-is, a / F-s (s) }) mõne funktsiooni (F) jaoks alates määramistest (X) kuni mudeli elementide mittekomplektideni.

Siinkohal tasub rõhutada, et ülaltoodud määratlus ei nõua üldiselt, et (X) ja (Y) sisaldaks sama arvu ülesandeid: (X) üks ülesanne võib samamoodi vastata mitmele ülesanded jaotises (Y) ja -kui (v) on juba muutuja, mis ilmneb (X) määramisel - (Y) üks ülesanne võib vastata ka mitmele ülesandele jaotises (X).

[X = / alga {massiiv} {l | c} textbf {loovutamine} & x \\ / hline s_0 & 0 \\ s_1 & 1 / end {array} Rightarrow X [F / y] = / alga {massiiv} {l | c | c} textbf {loovutamine} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 / end {array})

Tabel 3: (X) ja (X [F / y]) jaoks (F (s_0) = {0,1 }), (F (s_1) = {0 })

Lükkame sõltuvusloogika omaduste põhjaliku arutelu edasi pärast selle mängu-teoreetilise semantika täpsustamist. Selle lõigu järeldame siiski ülaltoodud reeglite kolmest olulisest tagajärjest:

Paikkond:

Kui rakenduses (phi) vabalt esinevate muutujate (X) ja (Y) piirangud on samad, siis (X / mudelid / phi) siis ja ainult siis, kui (Y / mudelid / phi).

Allapoole sulgemine:

kui (X / mudelid / phi) ja (Y / subseteq X), siis (Y / mudelid / phi).

Tühi komplekti omadus:

kui (emptyset) on meeskond, millel pole ühtegi määramist, siis (emptyset / mudelid / phi) kõigi sõltuvusloogika valemite (phi) jaoks.

Asukohapõhimõte koos selle jaotise alguses mainitud konservatiivsuse põhimõttega on oluline “mõistlikkuse tingimus”, millele sõltuvusloogika iga variant ja laiendus peaks vastama. Sama ei saa öelda allapoole sulgemise ja tühja seatud omaduse kohta, mida - nagu näeme - rikutakse sõltuvusloogika variantidega.

Lõpuks peame määratlema sõltuvusloogika lause tõesuse mudeli suhtes. Kuna lausel pole vabu muutujaid, on lokaalsuse põhimõtte kohaselt korraga nii, et kas kõik mittevabad meeskonnad vastavad sellele või mitte ükski mittevaba meeskond ei rahulda seda. See on analoogne Tarski semantika juhtumiga, kus lauset rahuldavad kas kõik muutuvad ülesanded või mitte ükski neist. Seega saame tõde määratleda tavalisel viisil:

Tõde meeskonna semantikas:

lause (phi) on mudelis (M) tõene ainult siis ja ainult siis, kui (M, { emptyset } mudelid / phi), kus ({ emptyset }) on meeskond, mis sisaldab ainult tühja ülesannet. Sel juhul kirjutame selle (M / mudelid / phi).

2.1 Mänguteoreetiline semantika

Nagu mainitud, on sõltuvusloogika mänguteoreetiline semantika sõltumatussõbraliku loogika ebatäiusliku teabe semantika variant, mis on iseenesest esimese järgu loogika mänguteoreetilise semantika kohandamine. Selle semantika ametliku ja üksikasjaliku määratluse saamiseks viitame lugejale Väänänen 2007a.

Mänguteoreetilises semantikas tehakse lause (phi) ja mudel (M) vastavaks (tavaliselt kahe mängijaga) mängule (G_M (phi)). Siis määratletakse tõde ühe mängija võitmisstrateegiate olemasolul (keda selles töös nimetatakse lihtsalt mängijaks (mängijaks (0))): teisisõnu, kui (sigma_0) on (võib-olla mittedeterministlik) strateegia mängija (0) ja (Pi (G_M (phi), / sigma_0)) on kõigi näidendite kogum, mis ühildub rakendusega (sigma_0), siis (phi) on tõsi siis ja ainult siis, kui iga (Pi (G_M (phi), / sigma_0)) mäng võidab Player (0). Mängu (G_M (phi)) on võimalik mõelda kui kahe mängija vahelist arutelu, kellest üks (mängija (0)) soovib näidata, et (phi) samal ajal kui teine (mängija (1)) soovib näidata, et see pole nii (phi).

Nagu esimese astme loogika ja sõltumatussõbraliku loogika puhul, on ka sõltuvusloogika ebatäiusliku infomängu korral mängu positsioonid paaris ((teeta, s)), kus (teeta) on (phi) alamvormi eksemplar (see tähendab, et (phi) alamvormiga sama avaldise mitu esinemist tuleb vaadelda eraldi) ja (s) on muutuv omistamine mudel (M). [1] Algpositsioon on ((phi, / emptyset)), kus (emptyset) on tühi ülesanne; ja mittedeterministlik strateegia (sigma_0) mängija (0) jaoks valib iga disjunktsiooni ja eksistentsiaalse kvantifitseerimise jaoks ühe või mitu praeguse positsiooni järgijat vastavalt järgmistele reeglitele:

  • Kui praegune positsioon on kujul ((psi / lor / teeta, s)), siis on selle järglased ((psi, s)) ja ((teeta, s));
  • Kui praegune asukoht on kujul ((eksisteerib v / psi, s)), siis on selle järglased kõik positsioonid ((psi, s ')) koos (s' / sim_v s).

Samamoodi on ((psi / maa / teeta, s)) pärijad ((psi, s)) ja ((teeta, s)) ning ((forall v / psi, s)) on kõik vormi positsioonid ((psi, s ')) (s' / sim_v s) jaoks; kuid mängija (0) strateegia ei saa nendele positsioonidele järeltulijat määrata, kuna eeldatakse, et mängija (1) valib, milline positsioon neid järgib.

Positsioonide jada (ületükk / rho = / rho_0 / rho_1 / ldots / rho_n) on (G_M (phi)) esitus siis ja ainult siis, kui

  1. (rho_0 = (phi, / emptyset));
  2. Kõigi (i = 1 / ldots n) korral on (rho_ {i}) järgijale (rho_ {i-1}).

Kui peale selle (rho_ {i + 1} in / sigma_0 (rho_i)), kui (rho_i) vastab disjunktsioonile või eksistentsiaalsele kvantitatiivile, siis ütleme, et (overline / rho) austab strateegia (sigma_0); ja nagu mainitud, kirjutame (Pi (G_M (phi), / sigma_0)) kõigi (G_M (phi)) ülemängude jaoks, mis austavad (sigma_0).

Me ütleme, et strateegia (sigma_0) võidab, kui iga mäng (ülejooneline / rho), mis lõpeb positsiooniga ((alpha, s)), kus (alpha) on esimene, järjekorranumber on selline, et ülesanne (s) rahuldab (alfa) Tarski semantika tavapärases tähenduses. Sõltuvusaatomitel - ja näidenditel, mis lõpevad sõltuvusaatomitega - pole tähtsust otsustamisel, kas antud strateegia võidab. Neid kasutatakse aga selleks, et täpsustada, kas antud strateegia on ühtne:

Ühtsuse tingimus

(G_M (phi)) strateegia (sigma_0) on ühtne, kui mõni neist mängib (ülejooneline / rho, / ülekülg / gamma / sisse-Pi (G_M (phi), / sigma_0)), mis lõpevad kahes positsioonis ((eqord (x_1 / ldots x_n, y), s)), ((eqord (x_1 / ldots x_n, y), s ')) sama eksemplari jaoks sõltuvusaatomi (eqord (x_1 / ldots x_n, y)) meil on see

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

Siis saame mängu teoreetilises semantikas tõe määratleda järgmiselt:

Tõde mänguteoreetilises semantikas:

lause (phi) vastab mudelis (M) (mänguteoreetilise semantika osas) ainult siis, kui mängijal (0) on ühtne võidustrateegia (G_M (phi)).

Võib näidata, et see mõiste on võrdne tõe mõistega meeskonna semantikas. Tegelikult saame näidata midagi enamat. Kui mis tahes meeskonna (X) ja valemi (phi) korral mängitakse mängu (G_ {M, X} (phi)) kui (G_M (phi)), kuid iga mängu jaoks juhuslikult valitud algpositsioon alates ({(phi, s: s / sisse X }), siis kehtib järgmine:

GTS ja meeskonna semantika ekvivalentsus:

meeskond (X) (mudeli suhtes (M)) rahuldab valemi (phi) ainult siis, kui mängijal (0) on ühtne võitmisstrateegia rakenduses (G_ {M, X} (phi)).

See tulemus kõrvaldab selgelt, miks sõltuvusloogika meeskonna semantika rahuldab tühja seatud omadust ja allapoole suunatud sulgemisomadust. Tõepoolest, kui (X = / emptyset), siis on iga mängija (0) strateegia rakenduses (G_ {M, X} (phi)) triviaalselt võidetav ja ühtne; ja kui (X / subseteq Y), on iga mängija (0) ühtne võidustrateegia rakenduses (G_ {M, X} (phi)) ka mängija (0) ühtne võidustrateegia. asukohas (G_ {M, Y} (phi)).

3. Omadused

3.1 Ekspressiivsus

Lausetepõhine sõltuvusloogika on samaväärne teise järgu loogika eksistentsiaalse fragmendiga (Sigma_1 ^ 1). Täpsemalt saab tõestada (Väänänen 2007a), et

Sõltuvusloogika ja (Sigma_1 ^ 1) lausetepõhine ekvivalents:

iga sõltuvusloogika lause (phi) jaoks on olemas (Sigma_1 ^ 1) lause (phi ^ *) selline () silt {6} silt {eq: DLESO} M / mudelid / phi / Leftrightarrow M / mudelid / phi ^ * / textrm {kõigile mudelitele} M.]

Samamoodi on iga (Sigma_1 ^ 1) lause (phi ^ *) jaoks sõltuvusloogika lause (phi), mida ((ref {eq: DLESO})) peab.

Kuna Fagini teoreem (Fagin 1974) näitab, et piiritletud mudelite omadus on defineeritav (Sigma_1 ^ 1) siis ja ainult siis, kui see on polünoomi ajal tuvastatav mittedeterministliku Turingi masina abil (see tähendab siis ja ainult siis, kui see on NPTIME-s), järeldub sellest kohe

Sõltuvusloogika ja NPTIME: mis

tahes sõltuvusloogikalause (phi) korral on NPTIME-s kõigi seda rahuldavate piiratud mudelite klass. Lisaks on lõplike mudelite NPTIME-klassi (matemaatiline K) jaoks olemas selline sõltuvusloogika lause (phi), et (M / mudelid / phi) ainult siis, kui (M / in / matemaatiline K).

Sõltuvusloogika ja (Sigma_1 ^ 1) samaväärsuse teine otsene tagajärg lausete tasandil on see, et kompaktsuse teoreem ja Löwenheim-Skolemi teoreem vastavad ka sõltuvusloogikale (Väänänen 2007a):

Kompaktsus:

kui piiratud sõltuvusloogika lausete komplekt (Phi) pole üheski mudelis rahuldav, siis pole selle mõni piiratud alamhulk (Phi_0 / subseteq_f / Phi) juba rahuldatav.

Löwenheim-Skolemi teoreem:

Kui sõltuvusloogika lausel on lõpmatu mudel, siis on sellel kõigi lõpmatute kardinaalsuste mudelid.

Kuid vabade muutujatega valemite puhul on asjad delikaatsemad. Siis on võimalik näidata (Kontinen & Väänänen 2009), et sõltuvusloogika vastab eksistentsiaalse teise järgu loogika allapoole suletud fragmendile:

Meeskondade määratletavus sõltuvusloogikas

Mudeli (M) ja muutujate hulga (V) meeskondade komplekt (matemaatiline X) on kujul ({X: M, X / mudelid / phi }) mõne sõltuvusloogika valemi (phi) jaoks koos vabade muutujatega (V), ainult siis, kui

  1. (matemaatiline X) on tühi;
  2. (matemaatiline X) on allapoole suletud, see tähendab, (Y / subseteq X / in / mathcal X / parempoolne nool Y / \ matemaatikas X);
  3. (matemaatiline X) on (Sigma_1 ^ 1) - defineeritav rakenduses (M), see tähendab, et on olemas (Sigma_1 ^ 1) lause (Psi (R)), (M) sõnavara ja uue (| V |) - ary seose sümboli (R) üle nii, et

    [X / in / mathcal X / textrm {ainult siis, kui} M, / textrm {Rel} (X) mudelid / Psi (R))

    kus (textrm {Rel} (X)) on (| V |) - ary relatsioon ({s (V): s / in X }), mis vastab meeskonnale (X).

3.2 Sõltuvusloogika hierarhiad

Ajakirjas Durand & Kontinen 2012 uuriti sõltuvuse aatomite sõltuvate muutujate arvu või universaalsete kvantifikaatorite arvu piiramise mõju. Näidati, et mõlemad need sõltuvusloogika fragmentide määratlemise viisid tekitavad hierarhia:

  • Kõigi (k) puhul olgu (matemaatiline D (k- / forall)) sõltuvusloogika piiratud maksimaalselt (k) universaalsete kvantifikaatoritega ja las (matemaatiline D (k-dep)) olema sõltuvusloogika, mis piirdub vormi (eqord (vec x, y)) sõltuvusaatomitega (| / vec x | / leq k) sõltuvusaatomite osas. Siis

    ) alusta {joonda *} matemaatiline D (k- / forall) ja <\ matemaatiline D (k + 1-dep), \\ / matemaatiline D (k- / forall) & / leq / matemaatiline D (k- dep) leq / matemaatiline D (k + 1 - dep) lõpeta {joonda *})

    ja

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

    lausete väljendusjõu suhtes.

3.3 Eitus sõltuvusloogikas

Siiani eeldasime, et kõik sõltuvuse loogikaväljendid on eitus normaalses vormis ja sõltuvuse aatomeid pole kunagi eitada. Teisest küljest on selgesõnalise eitusoperaatori lisamine sõltuvusloogika keelde mõnevõrra problemaatiline, kuna eksistentsiaalse teise astme loogika pole eituse all suletud. Tõepoolest, “ilmse” eituse reegel

[X / mudelid / sim / phi / textrm {ainult siis, kui} X / ei / mudelid / phi)

suurendab oluliselt sõltuvusloogika ekspressiivset jõudu, laiendades seda meeskonnaloogikale (Väänänen 2007a, b), mis väga tugevas mõttes on võrdne täieliku teise järgu loogikaga (Kontinen & Nurmi 2009).

Vähem tugevat, "kahekordset" eitust (ei saa) saab määratleda de Morgani reeglite järgi, (lnot (phi / lor) land] psi) equiv (lnot / phi) land) lor] (lnot / psi)) ja (lnot (eksisteerib v) forall v] phi) equiv / forall v) pastāv v] (lnot / phi)), pluss topelt eituse seadused (lnot / lnot / phi / equiv / psi) ja reegel

[X / mudelid { ei ole / eqord} (vec x, y) textrm {ainult siis, kui} X = / emptyset)

sõltuvusaatomite eituse jaoks (Väänänen 2007a, b). Saadud keel on ekspressiivselt ekvivalentne eitusvaba sõltuvusloogikaga ja tegelikult peab Väänänen 2007a sõltuvusloogika kirjeldus seda eitust oma keele osaks; aga nagu nähtub Kontinen & Väänänen 2011, on sõltuvusloogika valemi ja selle eituse rahulolu tingimused üksteisega vähe seotud. Täpsemalt:

Kahekordne eitus ja sõltuvusloogika: mis

tahes kahe sõltuvusloogika valemi (phi) ja (psi) korral, nii et (phi / maa / psi) pole rahuldatav, eksisteerib sõltuvusloogika valem (teeta) selline, et

[M, X / mudelid / theta / textrm {ainult siis, kui} M, X / mudelid / phi)

ja

[M, X / mudelid / ei ole / teeta / textrm {ainult siis, kui} M, X / mudelid / psi)

kõigi mudelite (M) ja meeskondade (X) jaoks.

Seega ei saa (phi) kahese eituse kohta üldiselt midagi öelda, välja arvatud see, et see võrdub mõne sõltuvusloogika avaldisega, mida ei rahulda ükski meeskond, kes rahuldab (phi). Kuna, nagu juba mainitud, tõrjutud keskosa seadus ei sõltu sõltuvusloogikast, pole see väga informatiivne omadus; eriti on sõltuvusloogikast (kahesuguse eituse korral) võimalik leida ekvivalentsete negatiividega samaväärseid avaldisi, näiteks näiteks (x / not = x / maa y / not = y) ja (lnot / eqord (x, y)).

3.4 Tõe-, kehtivus- ja tõestussüsteemid sõltuvusloogikas

Nagu sõltumatuse sõbralik loogika, võib sõltuvusloogika määratleda ka oma tõeoperaatori (Väänänen 2007a), st kui kõigi valemite (phi) korral on meil (lceil / phi / rceil) Gödeli arv (phi), siis leiame valemi (tau (x)), mille ainus vaba muutuja on (x), nii et

[M / mudelid / phi / textrm {ainult siis, kui} M / mudelid / tau (lceil / phi / rceil))

kõigi mudelite (M) jaoks, mis vastavad Peano aksioomidele naturaalarvude korral. See ei ole vastuolus Tarski määratlematuse teoreemiga, sest sõltuvusloogika ei ole vastuolulise eituse tingimustes suletud.

Sõltuvusloogika lause kehtivuse (see tähendab, et tõsi on kõigis mudelites) kehtivuse otsustamise probleem ei ole aritmeetiline ja on Levy hierarhia klassi ((Pi_2)) osas tegelikult täielik. Sellest hoolimata on uuritud sõltuvusloogika tõestusteooriat. Eelkõige on Kontinen & Väänänen 2013 välja töötatud usaldusväärne ja täielik tõestussüsteem sõltuvusloogika teooria esimese järgu tagajärgede leidmise probleemiks.

4. Sõltuvusloogika variandid

Selles osas võtame lühidalt kokku sõltuvusloogika enim uuritud variantide omadused. Selliseid variante on palju ning nende klassifitseerimise ja võrdlemise nimel on palju vaeva nähtud. Selles töös nimetame ainult neid variante, millel on eriline tähtsus nende seose tõttu tegeliku sõltuvusloogikaga.

4.1 Iseseisvusloogika

Esimese astme loogika sõltuvuse aatomitega (eqord (vec x, y)) laiendamise asemel laiendab iseseisvusloogika (Grädel & Väänänen 2013) seda iseseisvuse aatomitega (vec x / mathop { bot _ { vec z }} vec y), mille kavandatud tõlgendus on „(vec z) mis tahes võimaliku valiku korral, (vec x) ja (vec y) võimalikud väärtused on sõltumatud” - Teisisõnu, arvestades (vec z) mis tahes fikseeritud valikut, ei anna (vec x) võetud väärtuse teadmine mingit teavet (vec y) võetud väärtuse kohta. See on olulise kontseptuaalse tähtsusega mõiste: näiteks võiksite väljendada, et kui krüptimisvõtit ei teata, siis sõnumi krüptitud versiooni nägemine ei sisalda teavet vastava selge teksti versiooni kohta. Kui (x) tähistab krüptitud sõnumit ja (y) tähistab tavalist teksti,siis vastab see tingimusele (x / mathop { bot} y), kus (vec z) on sel juhul tühi. Samamoodi, kui (k) tähistab võtit, siis (x / mathop { bot} k) tähistab väidet, et võtit ei saa krüptitud sõnumist järeldada; ja konjunktsioonisõltuvuse aatom (eqord (k, x, y)) (mida, nagu näeme varsti, saab esindada iseseisvusloogikas) tähistab väidet, et lihttekstisõnumit saab krüpteeritud sõnumi korral dekodeerida ja võti.saab esitada sõltumatuse loogikas) esindab väidet, et lihttekstisõnumit saab krüptitud teate ja võtme korral dekodeerida.saab esitada sõltumatuse loogikas) esindab väidet, et lihttekstisõnumit saab krüptitud teate ja võtme korral dekodeerida.

Formaalselt saab sõltumatuse aatomite rahuldamise reegli anda järgmiselt:

TS-indep:

(M / mudelid_X / vec x / mathop { bot _ { vec z}} vec y) ainult siis, kui kõigi (s, s '\ X-is) koos (s (vec z) = s '(vec z)) eksisteerib (s' '\ X-is), kus (s' '(vec z \, / vec x) = s (vec {x }, / vec {z})) ja (s '' (vec y) = s '(vec y)).

) alusta {massiiv} {l | ccc} textbf {loovutamine} & / 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})

Sõltumatusloogika on rangelt väljendusrikkam kui sõltuvusloogika: tõepoolest, sellel puudub allapoole suunatud sulgumisomadus ja sõltuvusaatom (eqord (vec x, y)) on samaväärne iseseisvuse aatomiga (y / mathop { bot_ { vec x}} y). Lisaks saab näidata ka (Galliani & Väänänen 2014), et konditsioneeritud iseseisvuse aatomeid (vec x / mathop { bot _ { vec y}} vec z) saab määratleda tingimusteta sõltumatuse aatomite (vec x / mathop { bot} vec y).

Lausetepõhine sõltumatuse loogika on samaväärne eksistentsiaalse teise järgu loogikaga (Sigma_1 ^ 1); kuid valemit arvestades on see väljendusrikas ja Galliani 2012 näitas, et see võib hõlmata kõiki mittevajalikke ((Sigma_1 ^ 1)) - määratletavaid meeskonna atribuute.

4.2 Kaasamise loogika

Kaasamise loogika (Galliani 2012, Galliani & Hella 2013) laiendab esimese astme loogikat kaasamise aatomitega (vec x / subseteq / vec y), meenutades andmebaasiteooria kaasamise sõltuvusi. Selle semantika on:

TS-inc:

(M / mudelid_X / vec x / subseteq / vec y) siis ja ainult siis, kui kõigi (s / X-is) jaoks on olemas (s '\ in X) selline, et (s (vec x) = s '(vec y)).

) alusta {massiiv} {l | cc} textbf {loovutamine} & / mathbf {x_1} & / mathbf {x_2} / \ hline s_0 & 0 & 0 \\ s_1 & 0 & 1 \\ s_2 & 1 & 2 \\ s_3 & 2 & 3 / lõpp {array})

Erinevalt sõltuvus- ja iseseisvusloogikast on kaasamise loogika (lausetepõhine) rangelt nõrgem kui eksistentsiaalne teise järgu loogika. Tegelikult saab näidata (Galliani ja Hella 2013), et see on võrdne suurima fikseeritud punkti loogika positiivse fragmendiga ja seetõttu lüüa mudelite PTIME omadused üle piiratud järjestatud mudelite. Valemi mõttes on kaasamise loogika rangelt nõrgem kui sõltumatuse loogika, kuid võrreldamatu sõltuvusloogikaga: tõepoolest, selle valemi rahuldatavuse tingimused pole allapoole suletud, vaid need on ametiühingute poolt suletud selles mõttes, et

[M, X_i / mudelid / phi / Forall i / I / Rightarrow M, / bigcup_i X_i / mudelid / phi.)

4.3 Meeskonna loogika

Meeskondlik loogika (Väänänen 2007a, b; Kontinen & Nurmi 2009) laiendab sõltuvusloogikat, lisades sellele vastuolulise eituse (lnot). See on võrdselt ekspressiivne täieliku teise järgu loogikaga, seda nii mudeliklasside määratletavuse osas (Väänänen 2007b) kui ka võistkonnaklasside osas, mida meeskonna loogikaväljendid saavad antud mudeli suhtes määratleda (Kontinen & Nurmi 2009)..

4.4 Intuitionistlik sõltuvusloogika

Intuitionistlik sõltuvusloogika (Abramsky & Väänänen 2009; Yang 2013) laiendab sõltuvusloogikat, lisades sellele implikatsioonilise ühendussüsteemi (phi / rightarrow / psi), mille rahulolu reeglid on meeskonna semantikas antud

TS - (parempoolne nool):

(X / mudelid / phi / parem nool / psi) ainult siis, kui kõigi (X) kõigi alamhulkade (Y) korral, kui (Y / mudelid / phi), siis (Y / mudelid / psi).

Seda operaatorit nimetatakse "intuitionistlikuks implikatsiooniks", kuna tema semantika ja Kripke intuitiivse loogika semantilisuse implikatsioonioperaatori sarnasus on sama (Kripke 1965). Selle tõlgendamine veendumuste osas on üsna sirgjooneline: kui (X) ülesanded tähistavad asja olekuid, mida mõni agent peab võimalikuks, võib (X) alamhulk (Y) esindada veendumuste värskendus, milles agent lükkab tagasi mõne varem arvatava võimaliku asja oleku ja (phi / rightarrow / psi) oleku, kui selline värskendus, mis põhjustab (phi) hoidmist, põhjustaks ka (psi) hoidma. Sellest vaatenurgast on see väga loomulik kontseptsioon, mis võimaldab meil kirjeldada ennustusi selle kohta, kuidas sellise agendi üldine veendumusseisund uskumuste ajakohastamisele reageerib.

Teise astme universaalse kvantitatiivse kvantitatiivsuse määramise tõttu selle semantikas piisab sellest ühendusest loogika ekspressiivse keerukuse oluliseks suurendamiseks: eriti, nagu Yang 2013 on näidanud, on teise astme loogika iga lause samaväärne mõne intuitiivse sõltuvuse lausega. loogika. Intuitionistlik sõltuvusloogika säilitab sulgemisomadused allapoole: kui meeskond rahuldab intuitsioonistliku sõltuvusloogika valemi, siis tehke seda ka kõigi selle alamhulkade puhul.

4.5 Propositsiooniline sõltuvusloogika

Siiani vaadeldud sõltuvuse ja iseseisvuse aatomid väljendavad seoseid muutuste võimalike väärtuste vahel ülesandekomplektis. Samu sõltuvuse ja sõltumatuse mõisteid saab võrdselt loomulikult kohaldada ka väidete suhtes, kuna see juhtub loomulikus keeleväljenduses, näiteks näiteks „See, kas ta kursuse läbib või mitte, sõltub ainult tema lõpueksami sisust“.

Propozicionaalne sõltuvusloogika arvestab selliseid aatomeid propositsioonilise loogika kontekstis. Propositsionaalse sõltuvuse loogikatiimid on väärtuskomplektid (v) algsest aatomist (p_1 / ldots p_n) kuni ({T, F }). Selle semantilised reeglid ja nende põhjendused peegeldavad väga täpselt esimese järgu meeskonna semantilisi reegleid ja sõltuvuse aatomite reegel on

PTS-dep:

(X / mudelid / eqord (p_1 / ldd p_n, q)) siis ja ainult siis, kui on kaks väärtust (v_1, v_2 / X-is), mis lepivad kokku (p_1 / ldots p_n väärtuses) leppige kokku ka (q) väärtus.

Paljusid esimese astme sõltuvusloogika variante ja üldistusi saab ilma raskusteta madalamale viia algsel tasemel: seega on näiteks võimalik uurida propositsioonilise kaasamise loogika, propositsioonilise meeskonna loogika, propositsioonilise intuitsioonilise sõltuvusloogika omadusi jne..

Kui (esimese astme) sõltuvusloogika on rangelt ekspressiivsem kui esimese astme loogika, siis propositsiooniline sõltuvusloogika ei ole ekspressiivsem kui propositsiooniline loogika, kuna see tuleneb vahetult asjaolust, et kõik propositsioonifunktsioonid on propositsiooniloogikas väljendatavad. Esialgse sõltuvusloogika meeskondade ja uudishimuliku loogika teabe olekute vahel on siiski tihe seos (Groenendijk 2009; Ciardelli & Roelofsen 2011), tähenduse mõiste uurimise ja teabevahetuse semantiline raamistik: eriti, uudishimuliku loogika tähendus on täpselt sama, mis propositsioonilise intuitionistliku sõltuvusloogika loogikal.

Jaotusliku sõltuvusloogika ja paljude selle laiendite aksiomatizations leiate Yang & Väänänen 2016.

4.6 Modaalsõltuvuse loogika

Modaalsõltuvuse loogika (Väänänen 2008) ja selle variandid laiendavad modaalset loogikat, lisades sellele samad sõltuvuse aatomid (eqord (p_1 / ldots p_n, q)), mida juba käsitletakse propositsioonilise sõltuvusloogika puhul.

Selle rahulolu tingimusi saab määratleda meeskonna semantika variandi abil, milles meeskonnad asendatakse võimalike maailmade komplektidega.

Palju uuritud on selle loogika, selle fragmentide ja laiendite keerukus-teoreetilisi omadusi (Ebbing, Lohmann, & Yang 2011; Ebbing & Lohmann 2012; Lohmann & Vollmer 2013).

5. Sõltuvusloogika rakendused

5.1 Sõltuvusloogika ja andmebaasi teooria

Meeskonna semantika meeskondade ja relatsiooniandmebaasi teoorias uuritud suhete vahel on otsene seos: antud meeskond (X) ja selle ülesannetes esinevate muutujate hulk (vec v = v_1 / ldots v_k), on võimalik määratleda seos (X (vec v) = { langle s (v_1), / ldots, s (v_n) rangle: s / in X }). Lisaks sellele on sõltuvusloogikas uuritud sõltuvusaatomid ja selle variandid analoogsed andmebaasiteoorias käsitletavate sõltuvustega - ja paljudel juhtudel tuletatud neist - nagu funktsionaalsed sõltuvused (Väänänen 2007a), mitmeväärtusega sõltuvused (Engström 2012) ning kaasamise ja välistamise sõltuvused. (Galliani 2012). Sõltuvusloogika ja andmebaasiteooria vaheline seos ei aidanud mitte ainult sõltuvusloogika, vaid ka andmebaasi teooria edasiarendamisel: näiteksaastal Hannula & Kontinen 2016 leiti kaasamise, funktsionaalsete ja manustatud mitmeväärtusega andmebaasi-teoreetiliste sõltuvuste piiramatu implikatsiooni probleemi aksiomatization sarnase probleemi uurimisega meeskonna semantika kontekstis.

5.2 Sõltuvusloogika ja veendumuste kujutamine

Nagu Yang 2014 ja Yang & Väänänen 2016 on arutanud, eksisteerib tihe seos (ettepanekualuse) intuitsioonilise sõltuvusloogika ja uudishimuliku loogika vahel (Ciardelli & Roelofsen, 2011), mis on tähenduse uurimise ja agentide vahelise teabevahetuse raamistik. Üldisemalt võttes võimaldavad meeskonna semantikas uuritud sõltuvusaatomid ja -ühendused loomulikke tõlgendusi uskumuse olekute ja uskumuste värskenduste osas, nagu käsitleti ajakirjas Galliani 2015. Sel ajal on sellise loogika ja dünaamilise-episteemilise loogika vahelise seose täpne olemus olemas. ja selle variandid (Van Ditmarsch, van Der Hoek, & Kooi 2007) on suures osas uurimata, kuid on piisavalt põhjust arvata edasisi seoseid nende kahe matemaatilise ja filosoofilise loogika valdkonna vahel.

5.3 Sõltuvusloogika ja Nooli teoreem

Arrow teoreem (Arrow 1950) on sügavalt mõjuv sotsiaalse valiku teooria tulemus, mis lühidalt näitab, et puudub hääletussüsteem (see tähendab, et puudub süsteem alternatiivide individuaalsete eelistuste paremusjärjestuse teisendamiseks globaalseks, ühiskondlikul tasemel eelistuste edetabeliks). mis vastavad kõigile kolmele mõistlikule tingimusele, nimelt

  • Kui iga valija eelistab (A) kui (B), siis eelistab kogu rühm tervikuna (A) ja (B);
  • Kas rühm tervikuna eelistab (A) kuni (B) või vastupidi, sõltub ainult iga valija eelistustest seoses (A) ja (B), mitte nende eelistustega muude võimalike alternatiivide osas;
  • Ükski valija pole diktaator, see tähendab, et rühma eelistusi ei määra ühegi valija eelistused.

Nagu sõnastus ise soovitab, tunnistab teine ja kolmas tingimus loomulikku lugemist sõltuvuse ja sõltumatuse osas: tegelikult, nagu nähtub Pacuit & Yang 2016, saab Arrow teoreemi vormistada iseseisvusloogikas ja tõestada sobivas naturaalses deduktsioonisüsteemis.

5.4 Kvantmeeskonna loogika ja Belli ebavõrdsus

Hyttinenis, Paolinis ja Väänänen 2015 tutvustatakse meeskondliku loogika varianti, mida nimetatakse kvantmeeskonna loogikaks. Selles formaalsuses asendatakse meeskonnad kvantmeeskondadega, mis erinevad tavalise meeskonnaloogilise meeskonna loogikaga meeskondadest selle poolest, et need võimaldavad teatud muutujate väärtuste määramatust teatud väärtuste suhtes määratleda ja võimaldavad sama variatsiooni mitu eksemplari. hindamine (lisades seega meeskonna semantikale kvantitatiivse aspekti). Seejärel määratletakse kvantmeeskondade abil keele semantika, mis võimaldab täpsustada sündmuste tõenäosusega seotud ebavõrdsust, ja selle jaoks on välja töötatud kindel ja täielik tõestussüsteem; ja lõpuks näidatakse, et Belli ebavõrdsus tunnistab selles süsteemis ka teisi näiteid,nagu nad teevad kvantmehaanika ennustuste ja eksperimentaalsete tõendite kohaselt (Einstein, Podolsky ja Rosen 1935; Bell 1964; Aspect, Grangier, & Roger 1981), samas kui selle raamistiku klassikalises versioonis nad seda ei tee.

Bibliograafia

  • Abramsky, Simson ja Jouko Väänänen, 2009, “IF-st BI-ni: lugu sõltuvusest ja eraldumisest”, Synthese, 167 (2): 207–230. doi: 10.1007 / s11229-008-9415-6
  • Arrow, Kenneth J., 1950, “Raskus sotsiaalse heaolu kontseptsioonis”, ajakiri Political Economy, lk.328–346. doi: 10.1086 / 256963
  • Aspect, Alain, Philippe Grangier ja Gérard Roger, 1981, “Realistlike kohalike teooriate eksperimentaalsed testid Belli teoreemi kaudu”, Physical Review Letters, 47 (7): 460–463. doi: 10.1103 / PhysRevLett.47.460
  • Bell, JS, 1964, “Einsteini-Podolsky-Roseni paradoksil”, füüsika, 1 (3): 195–200.
  • Ciardelli, Ivano ja Floris Roelofsen, 2011, “Inquisitive Logic”, Journal of Philosophical Logic, 40 (1): 55–94. doi: 10.1007 / s10992-010-9142-6
  • van Ditmarsch, Hans, Wiebe van der Hoek ja Barteld Kooi, 2007, Dynamic Epistemic Logic, (Synthese'i raamatukogu 337), Dordrecht: Springer. doi: 10.1007 / 978-1-4020-5839-4
  • Durand, Arnaud ja Juha Kontinen, 2012, “Hierarhiad sõltuvusloogikas”, ACM-i tehingud arvutusloogikal (TOCL), 13 (4): 1–21. doi: 10.1145 / 2362355.2362359
  • Ebbing, Johannes ja Peter Lohmann, 2012, “Modaalsõltuvuse loogika mudeli kontrollimise keerukus”, SOFSEM 2012: Arvutiteaduse teooria ja praktika praeguste suundumuste rahvusvaheline konverents (arvutiteaduse loengute märkused, 7147), Berliin, Heidelberg: Springer, lk 226–237. doi: 10.1007 / 978-3-642-27660-6_19
  • Ebbing, Johannes, Peter Lohmann ja Fan Yang, 2013, “Modaalse intuitsioonilise sõltuvuse loogika mudeli kontrollimine”, rahvusvaheline Thbilisi loogika, keele ja arvutamise sümpoosion 2011 (arvutiteaduse loengute märkused, 7758), Berliin, Heidelberg: Springer, lk 231–256. doi: 10.1007 / 978-3-642-36976-6_15
  • Einstein, A., B. Podolsky ja N. Rosen, 1935, “Kas füüsilise reaalsuse kvantmehaanilist kirjeldust võib pidada täielikuks?” Füüsiline ülevaade, 47 (10): 777–780. doi: 10.1103 / PhysRev.47.777
  • Engström, Fredrik, 2012, “Üldistatud kvantifikaatorid sõltuvusloogikas”, ajakiri Logic, Language and Information, 21 (3): 299–324. doi: 10.1007 / s10849-012-9162-4
  • Fagin, Ronald, 1974, “Üldistatud esimese astme spektrid ja polünoomiajal tuvastatavad komplektid”, arvutamise keerukus (SIAM-AMS Proceedings 7), Richard M. Karp (toim.), Providence, RI: American Mathematical Society, lk. 27. – 41.
  • Galliani, Pietro, 2012, „Kaasamise ja välistamise sõltuvused meeskonna semantikas - ebatäiusliku teabe mõnel loogikal”, Annals of Pure and Applied Logic, 163 (1): 68–84. doi: 10.1016 / j.apal.2011.08.005
  • –––, 2015, „Meeskonnasemantika doksastiline tõlgendus“, piirideta loogika: esseed komplektiteooriast, mudeliteooriast, filosoofilisest loogikast ja matemaatika filosoofiast (Ontos Mathematical Logic, 5), Åsa Hirvonen, Juha Kontinen, Roman Kossak, ja Andrés Villaveces (toim), Berliin, Boston: De Gruyter, lk 167–192. doi: 10.1515 / 9781614516873.167
  • Galliani, Pietro ja Lauri Hella, 2013, “Kaasamise loogika ja fikseeritud punkti loogika”, arvutiteaduse loogika 2013 (Leibniz International Proceedings in Informatics (LIPIcs), 23), Dagstuhl, Saksamaa: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, lk. 281–295. doi: 10.4230 / LIPIcs. CSL.2013.281
  • Galliani, Pietro ja Jouko Väänänen, 2014, “Sõltuvusloogikast”, Johan van Benthemis loogikast ja infodünaamikast (silmapaistvad kaastööd loogikale, 5), Alexandru Baltag ja Sonja Smets (toim), Cham: Springer, lk 101–10. 119. doi: 10.1007 / 978-3-319-06025-5_4
  • Grädel, Erich ja Jouko Väänänen, 2013, “Sõltuvus ja iseseisvus”, Studia Logica, 101 (2): 399–410. doi: 10.1007 / s11225-013-9479-2
  • Groenendijk, Jeroen, 2009, „Huvitav semantika: kaks disjunktsiooni võimalust“, Peter Bosch, David Gabelaia ja Jérôme Lang (toim), seitsmes rahvusvaheline Tbilisi keele, loogika ja arvutamise sümpoosion (arvutiteaduse loengute märkused: 542. köide)), Springer-Verlag, lk 80–94. doi: 10.1007 / 978-3-642-00665-4_8
  • Hannula, Miika ja Juha Kontinen, 2016, “Tingimusliku iseseisvuse ja kaasamise sõltuvuste lõplik aksiomatization”. Teave ja arvutused, 249: 121–137. doi: 10.1016 / j.ic.2016.04.001
  • Henkin, Leon, 1961, “Mõned märkused lõputult pikkade valemite kohta”, infinitistic Methods (Proceedings of the Symposium on the Mathematics Foundations, Varssavi, 1959), Oxford: Pergamon Press, lk 167–183.
  • Hodges, Wilfrid, 1997, “Kompositsiooniline semantika ebatäiusliku teabe keele jaoks”, IGPLi loogikaajakiri, 5 (4): 539–563. doi: 10.1093 / jigpal / 5.4.539
  • Hyttinen, Tapani, Gianluca Paolini ja Jouko Väänänen, 2015, “Quantum Team Logic and Bell's Unqualities”, The Review of Symbolic Logic, 8 (4): 722–742. doi: 10.1017 / S1755020315000192
  • Kontinen, Juha ja Ville Nurmi, 2009, “Meeskonna loogika ja teise järgu loogika”, loogika, keele, teabe ja arvutamise 16. rahvusvahelise seminari (loengumärkused arvutiteaduses, 5514), Berliin, Heidelberg: Springer, lk 230–241. doi: 10.1007 / 978-3-642-02261-6_19
  • Kontinen, Juha ja Jouko Väänänen, 2009, “Sõltuvusloogika määratletavuse kohta”, ajakiri Logic, Language and Information, 18 (3): 317–332.doi: 10.1007 / s10849-009-9082-0
  • –––, 2011, „Märkus eitusest sõltuvuse loogikas”, Notre Dame Journal of Formal Logic, 52 (1): 55–65. doi: 10.1215 / 00294527-2010-036
  • ––– 2013, “Esimese astme tagajärgede aksiomatiziseerimine sõltuvusloogikas”, Annals of Pure and Applied Logic, 164 (11): 1101–1117. doi: 10.1016 / j.apal.2013.05.006
  • Kripke, Saul A., 1965, “Intuitionistliku loogika semantiline analüüs I”, formaalsetes süsteemides ja rekursiivsetes funktsioonides: kaheksanda loogikakollokviumi toimetused, Oxford, juuli 1963 (uurimused loogikast ja matemaatika alused, 40), John N. Crossley ja Michael AE Dummett (toim), Põhja-Holland, lk 92–130. doi: 10.1016 / S0049-237X (08) 71685-9
  • Lohmann, Peter ja Heribert Vollmer, 2013, “Modaalsõltuvuse loogika keerukustulemused”, Studia Logica, 101 (2): 343–366. doi: 10.1007 / s11225-013-9483-6
  • Pacuit, Eric ja Fan Yang, 2016, “Sõltuvus ja sõltumatus ühiskondlikus valikus: Arrow’s Theorem”, sõltuvusloogikas, Samson Abramsky, Juha Kontinen, Jouko Väänänen ja Heribert Vollmer (toim), Dordrecht: Springer, lk 235–260. doi: 10.1007 / 978-3-319-31803-5_11
  • Väänänen, Jouko, 2007a, Sõltuvusloogika: uus lähenemisviis iseseisvussõbralikule loogikale (Londoni Matemaatika Seltsi õpilaste tekstid, 70), Cambridge: Cambridge University Press. doi: 10.1017 / CBO9780511611193
  • ––– 2007b, „Meeskonna loogika“, interaktiivses loogikas: valitud artiklid 7. augusti de Morgani õpitoast (loogika ja mängude tekstid, 1), Johan van Benthem, Dov Gabbay ja Benedikt Löwe (toim), Amsterdam: Amsterdam University Press, lk 281–302.
  • –––, 2008, „Modaalsest sõltuvusloogika”, uued mängude ja koostoime vaatenurgad (loogika ja mängude tekstid, 4), Krzysztof R. Apt ja Robert van Rooij (toim), Amsterdam: Amsterdam University Press, lk 237–23 254.
  • Yang, Fan, 2013, “Teise järgu lausete väljendamine intuitsioonilises sõltuvusloogikas”, Studia Logica, 101 (2): 323–342. doi: 10.1007 / s11225-013-9476-5
  • ––– 2014, „Sõltuvusloogika laiendamistest ja variantidest: intuitiivsete ühenduste uurimine meeskonnasemantika seadistamisel“. PhD lõputöö, Helsingi ülikool.
  • Yang, Fan ja Jouko Väänänen, 2016, “Sõltuvuse propositsiooniline loogika”, Puhta ja rakendatud loogika ajakirjad, 167 (7): 557–589. doi: 10.1016 / j.apal.2016.03.003

Akadeemilised tööriistad

sep mehe ikoon
sep mehe ikoon
Kuidas seda sissekannet tsiteerida.
sep mehe ikoon
sep mehe ikoon
Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.
info ikoon
info ikoon
Otsige seda sisenemisteema Interneti-filosoofia ontoloogiaprojektilt (InPhO).
phil paberite ikoon
phil paberite ikoon
Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.

Muud Interneti-ressursid

  • Sõltuvusloogika Vikipeedias
  • Ettekanded akadeemia kollokviumi sõltuvusloogikas, Amsterdam, 2014