Logika Závislosti

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-08-25 04:38

Vstupní navigace

• Obsah příspěvku
• Bibliografie
• Akademické nástroje
• Náhled PDF přátel
• Informace o autorovi a citaci
• Zpět na začátek

Logika závislosti

První publikované čt 23. února 2017

Logika závislosti je rozšíření logiky prvního řádu, která k ní přidává atomy závislosti, tj. Výrazy tvaru (eqord (x_1 / ldots x_n, y)), které tvrdí, že hodnota (y) je funkčně závisí na (jinými slovy, určeno) na hodnotách (x_1 / ldots x_n). Tyto atomy umožňují specifikaci nelineárně uspořádaných závislostních vzorců mezi proměnnými, hodně ve stejném smyslu jako IF-Logic zkrácené kvantifikátory; ale na rozdíl od logiky IF logika závislosti odděluje kvantifikaci od specifikace takových podmínek závislosti / nezávislosti. Hlavní sémantika logiky závislosti, zvaná týmová sémantika, zobecňuje Tarskiho sémantiku tím, že nechá výrazy uspokojit nebo neuspokojit s ohledem na množiny proměnných přiřazení spíše než s ohledem na jednotlivé přiřazení. Tato sémantika předchází datům vývoje logiky závislosti a byla původně vyvinuta Wilfridem Hodgesem v kontextu IF-logiky (Hodges 1997). Existuje také herně-teoretická sémantika pro závislostní logiku, založená na hrách s nedokonalými informacemi a zhruba analogická herní-teoretické sémantice pro nezávislostní logiku (Väänänen 2007a). Sensu stricto, pojem „logika závislosti“odkazuje výhradně na jazyk získaný přidáním výše uvedených atomů funkční závislosti do jazyka logiky prvního řádu; ale termín se také používá v obecnějším smyslu pro odkaz na oblast výzkumu, která studuje vlastnosti logiky získané přidáním různých pojmů závislosti a nezávislosti k logice prvního řádu, jako je logika nezávislosti (Grädel & Väänänen 2013)),intuicionální závislostní logika (Yang 2013) nebo inkluzivní logika (Galliani 2012, Galliani & Hella 2013), nebo dokonce logika rozšiřující další logické rámce o podobné atomy, jako v případě modální závislostní logiky (Väänänen 2008). V tomto článku bude termín „logika závislosti“použit pro označení logiky závislosti a termín „logika závislosti a nezávislosti“bude místo toho použit pro označení jeho variant a zobecnění.a termín „logika závislosti a nezávislosti“bude místo toho používán pro označení jeho variant a zobecnění.a termín „logika závislosti a nezávislosti“bude místo toho používán pro označení jeho variant a zobecnění.

• 1. Závislostní vzorce v logice prvního řádu a její rozšíření

• 2. Sémantika týmu

  2.1 Sémantika herní teorie

• 3. Vlastnosti

  • 3.1 Expresivita
  • 3.2 Hierarchie v logice závislosti
  • 3.3 Negace v logice závislosti
  • 3.4 Systémy pravdy, platnosti a důkazů v logice závislosti

• 4. Varianty logiky závislosti

  • 4.1 Logika nezávislosti
  • 4.2 Logika začlenění
  • 4.3 Týmová logika
  • 4.4 Intuicionální logika závislosti
  • 4.5 Propoziční logika závislosti
  • 4.6 Logická závislostní logika

• 5. Aplikace logiky závislosti

  • 5.1 Logika závislosti a teorie databází
  • 5.2 Logika závislosti a reprezentace víry
  • 5.3 Logika závislosti a Arrowova věta
  • 5.4 Kvantová logika týmu a Bellovy nerovnosti
• Bibliografie
• Akademické nástroje
• Další internetové zdroje
• Související záznamy

1. Závislostní vzorce v logice prvního řádu a její rozšíření

Jednou z funkcí logiky prvního řádu, která odpovídá za velkou expresivitu a použitelnost, je skutečnost, že umožňuje vnoření kvantifikátorů, a tedy umožňuje specifikaci vzorců závislosti mezi kvantifikovanými proměnnými. Vezměme si například (snad falešné) prohlášení, že „každý chlapec miluje dívku, která miluje jiného chlapce“. Lze jej snadno převést do logiky prvního řádu jako

) tag {1} label {eq: boygirl1} begin {zarovnat} & / forall x (boy (x) rightarrow / existuje y (girl (y) land / loves (x, y) land {} & / quad / existuje z (boy (z) land x / not = z / land / loves (y, z))) end {zarovnat})

jehož pravdivý stav je podle Tarského obvyklé sémantiky přesně to, co by člověk očekával: výše uvedený výraz je pravdivý, pokud a pouze v případě, že pro každého chlapce (b) je možné najít dívku (g) a chlapce (b ') tak, že (b) miluje (g) a (g) miluje (b') a (b) a (b ') nejsou stejné. Identita dívky (g) může samozřejmě záviset na identitě prvního chlapce (b) - konec konců, aby byl tento výraz pravdivý, nevyžadujeme, aby byli všichni chlapci zamilovaní do všech dívek- a kromě toho identita druhého chlapce (b ') může záviset na identitě prvního chlapce (b) (protože (b') se musí lišit od (b)) a z identity dívky (g), která (b) miluje. Vzorec závislosti mezi našimi kvantifikovanými proměnnými je tedy následující: (y) závisí na (x),zatímco (z) záleží na (x) a (y). Z syntaktického hlediska se to odráží na skutečnosti, že (existuje y) je v rozsahu (forall x), zatímco (existuje z) je v rozsahu obou (forall x)) a (existuje y).

Rozdíly v závislostních vzorcích mezi operátory mohou být použity k formalizaci důležitých rozdílů, jako je například rozdíl mezi kontinuitou funkce (f)

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

a její jednotná kontinuita

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

nebo, ve větším rozšíření logiky prvního řádu, vyjádřit rozdíl mezi hodnotami De Dicto a De Re (např. „Je možné, že každý člověk je zblázen“) lze chápat buď jako tvrzení, že je to pro každou osobu (p), je možné, že (p) je blázen, (forall x (person (x) rightarrow / Diamond / crazy (x))), nebo prohlašuje, že je možné, že je každý blázen společně, (Diamond / forall x (person (x) rightarrow / crazy (x)))).

Závislostní vzorce mezi kvantifikovanými proměnnými v logice prvního řádu jsou nutně tranzitivní, jak je zřejmé jejich spojením s rozsahem odpovídajících pod-výrazů: pokud (existuje y) je v rozsahu (forall x)) a (existuje z) je v rozsahu (existuje y), pak nutně (existuje z) bude v rozsahu (a tedy závislé na) (forall x). Dále je množina všech kvantifikátorů, v jejichž rozsahu leží nějaké podformule (alfa), lineárně uspořádaná: pokud (alfa) je v rozsahu (Q_1 x_1) a (Q_2 x_2), pak buď / (Q_1 x_1) je v rozsahu (Q_2 x_2) nebo naopak.

To omezuje výrazné možnosti logiky prvního řádu. Předpokládejme například, že chceme změnit naše předchozí tvrzení o chlapcích a dívkách takto: každý chlapec miluje dívku, která miluje jiného chlapce, a tohoto druhého chlapce lze vybrat nezávisle na prvním. Co to znamená, intuitivně řečeno, je dost jednoduché: pro každého chlapce (b) najdeme dívku (g) takovou, že (b) miluje (g), a pro každou takovou dívku můžeme najít chlapce (b ') tak, že (g) miluje (b') a (b / not = b '), a navíc můžeme najít identitu druhého chlapce (b') aniž by věděl, že z (b), pouze na základě identity dívky (g). V některých scénářích to může být stále pravda, například pokud dva chlapci (b_1) a (b_2) milují dvě dívky (g_1) a (g_2),kteří však milují pouze (b_2) a (b_1). Je však snadno vidět, že to není ekvivalentní našemu předchozímu tvrzení: například pokud náš vesmír sestává (jako v (b) výše) ze dvou chlapců (b) a (b ') a dívky (g) a (b) a (b ') oba milují (g), kteří oba milují, potom je naše předchozí tvrzení pravdivé, ale současné je nepravdivé.

Dva scénáře, ve kterých ((ref {eq: boygirl1})) jsou pravdivé. V (a), (z) může být vybráno nezávisle z (x); in (b) to nemůže.

Není však jasné, jak formalizovat tuto podmínku v logice prvního řádu. V podstatě bychom museli upravit ((ref {eq: boygirl1})) tak, aby (z) nebylo v rozsahu (x), a proto na něm nezávisí; stále bychom však chtěli, aby (z) závisel na (y) a (y) na (x). Jak již bylo řečeno, takový model závislosti není v logice prvního řádu realizovatelný. Můžeme se vyhnout problému tím, že se uchýlíme k kvantifikaci vyššího řádu: skutečně je vidět ten výraz

) tag {2} label {boygirl2} begin {zarovnat} & / existuje F / forall x (boy (x) rightarrow / existuje y (girl (y) land / loves (x, y)) land / boy (F (y)) land {} & / quad x / not = F (y) land / loves (y, F (y)))) end {zarovnat})

zachycuje naši zamýšlenou interpretaci, ale pouze za cenu explicitní existenciální kvantifikace nad funkcemi.

Možnou alternativou by bylo rozšíření syntaxe logiky prvního řádu, aby se zrušila omezení vzorců závislosti mezi kvantifikovanými proměnnými. Toto je cesta zvolená logikou větvení kvantifikátoru (Henkin 1961), ve které podmínky pravdy ((ref {boygirl2})) odpovídají podmínkám

) tag {3} label {boygirl3} begin {zarovnat} & / left (begin {smallmatrix} forall x & / existuje y \\ / forall z & / existuje w / end {smallmatrix} right) (boy (x) rightarrow (girl (y) land / loves (x, y) land {} & / quad (y = z / rightarrow (boy (w) land x / not =) w / land / loves (z, w))))), / end {zarovnat})

a logice nezávislosti, ve které ((ref {boygirl2})) je ekvivalentní

) tag {4} label {boygirl4} begin {zarovnat} a / forall x / existuje y (boy (x) rightarrow (girl (y) land / loves (x, y) land (existuje z / x) (boy (z) land {} & / quad x / not = z / land / loves (y, z)))). / end {zarovnat})

Nebudeme zde podrobně vysvětlovat sémantiku těchto dvou formalismů; stačí říci, že v ((ref {boygirl3})) hodnota (w) nezávisí na hodnotách (x) a (y) (ačkoli to může záviset na hodnotě z (z)), protože patří do různých „řádků“komplexního kvantifikátoru (left (begin {smallmatrix} forall x & / existuje y \\ / forall z & / existuje w / end {smallmatrix) } right)), zatímco v ((ref {boygirl4})) hodnota (z) nezávisí na hodnotě (x), protože tato závislost je výslovně „odříznuta“kvantifikátorem ((existuje z / x)).

Jedním rysem společným pro větvení kvantifikátorové logiky a logikou přátelské k nezávislosti, jak vidíme, je to, že neoddělují kvantifikaci proměnných od specifikace nestandardních vzorců závislosti: jako v případě logiky prvního řádu, zda kvantifikovaná Proměnná (v_1) bude nebo nebude záviset na nějaké jiné kvantifikované proměnné (v_2) bude určena příslušnou polohou a formou jejich kvantifikátorů.

Logika závislosti má odlišný přístup k problému rozšíření logiky prvního řádu, aby se reprezentovala ((ref {boygirl2})). Ve srovnání s ((ref {eq: boygirl1})) je jedinou novou podmínkou ta, která uvádí, že hodnota (z) je určena (tj. Funkčně závislá) hodnotou (y); a to odpovídá nové atomové podmínce (eqord (y, z)), nazvané atom závislosti, jehož zamýšlený význam je ten, že (hodnota) (z) je funkcí hodnoty (y)). Na rozdíl od větví logiky kvantifikátoru nebo logiky přátelské k nezávislosti je to podmínka nad hodnotami, které mohou mít (y) a (z), nikoli podmínka chování kvantifikátoru (existuje z): ve skutečnosti není důvod vyžadovat, aby (z) byla vůbec kvantifikovaná proměnná - mohla by to být volná proměnná,nebo nějaký složitý termín zahrnující více proměnných.

V závislosti na logice ((ref {boygirl2})) lze formalizovat jako

) tag {5} label {boygirl5} begin {zarovnat} & / forall x / existuje y / existuje z (eqord (y, z) land (boy (x) rightarrow (girl (y)) land / loves (x, y) rightarrow {} & / quad (boy (z) land x / not = z / land / loves (y, z))))) end {zarovnat})

Pravdivé podmínky ((ref {boygirl2})), ((ref {boygirl3})), ((ref {boygirl4})) a ((ref {boygirl5}))) jsou přesně stejné: jakýkoli model, který splňuje jeden z těchto výrazů (v příslušných jazycích), vyhovuje všem čtyřem. Obecněji, jak uvidíme, expresivní pravomoci existenciální logiky druhého řádu, logiky nezávislé na nezávislosti a logiky závislosti s ohledem na definovatelnost tříd modelů jsou přesně stejné. To však neplatí pro vzorce s volnými proměnnými; a dále, tato logika může být rozšířena a upravena podle výrazně odlišných linií.

2. Sémantika týmu

Sémantika týmu, poprvé vyvinutá Wilfridem Hodgesem v rámci logiky nezávislosti přátelské (Hodges 1997), je zobecněním Tarské sémantiky pro logiku prvního řádu v případě vícenásobného přiřazení prvků proměnným. Sady takových úkolů, nazývaných týmy z historických důvodů, tvoří základní sémantický pojem týmové sémantiky a vzorce jsou uspokojeny nebo nespokojeny s ohledem na ně spíše než s ohledem na jednotlivé úkoly. Vztah mezi týmovou sémantikou a Tarski sémantikou ukazuje následující výsledek, který má závislostní logiku i všechny její varianty prvního řádu:

Konzervativnost:

Vzorec prvního řádu je splněn týmem (X) (ve smyslu týmové sémantiky), pokud a pouze pokud všechny úkoly (s / v X) splňují (ve smyslu Tarski sémantiky).

Obecněji lze týmy chápat jako sady víry, které představují soubor všech států světa (= přiřazení), o nichž někteří agenti věří, že je to možné. Potom tým (X) uspokojí nějaký vzorec (phi) pouze tehdy, pokud (phi) platí, když (X) je sada všech možných stavů; a v tomto případě budeme psát (X / models / phi) (nebo (M, X / models / phi), pokud volba modelu (M) není jasná). V této části prozkoumáme pravidla týmové sémantiky a jejich interpretace z hlediska tohoto principu; pak v další části si probereme, jak to také vychází z nedokonalé informační sémantiky herní sémantiky pro závislostní logiku.

Podmínka pro nové atomy závislosti (eqord (x_1 / ldots x_n, y)), které odpovídají tvrzení, že hodnota (y) je funkcí hodnot (x_1 / ldots x_n), lze snadno pochopit:

TS-dep:

(X / models ~ / eqord (x_1 / ldots x_n, y)) pouze tehdy, pokud existují dvě přiřazení (s_1, s_2 / in X), která se shodují na hodnotách (x_1 / ldots x_n) se také shodují na hodnotě (y).

Předpokládejme například, že (X) je soubor přiřazení tří proměnných (x_1), (x_2) a (y), kde (x_1) představuje státní příslušnost kandidáta pozice, (x_2) představuje jejich skóre (podle vhodné metody hodnocení) a (y) představuje, zda byly přijaty nebo odmítnuty. Pak atom (eqord (x_2, y)) odpovídá tvrzení, že nabídka je určena pouze skóre: pokud dva kandidáti mají stejné skóre, dostanou přesně stejnou nabídku, bez ohledu na jakýkoli jiný faktor. Zvláštní případ atomu závislosti je dán atomy stálosti (eqord (y)), které - podle výše uvedené sémantiky - jsou týmem splněny, pokud a pouze pokud všechna jeho přiřazení souhlasí s hodnotou (y).

) begin {array} {l | ccc} textbf {přiřazení} & / 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})

Tabulka 1: Tým (X), ve kterém (y = x_1 + x_2). Zde (y) je funkce (x_1) a (x_2), a proto (= \! \! (X_1 x_2, y)) platí; však (y) není funkcí samotného (x_1), takže (= \! \! (x_1, y)) nedrží.

Podle stejné interpretace jsou pravidla pro literály a spojky prvního řádu (pro jednoduchost budeme předpokládat, že naše výrazy jsou v negační normální formě; a jak je obvyklé, budeme předpokládat, že negace atomů závislosti nejsou nikdy uspokojeny) jsou snadno odvodit:

TS-lit:

Pro všechny literály prvního řádu (alfa), (X / models / alpha), pokud a pouze pokud pro všechna přiřazení (s / in X), (s / models / alpha) v obvyklém Tarski sémantickém smyslu;

TS - (land):

(X / models / phi / land / psi) pouze tehdy, pokud (X / models / phi) a (X / models / psi).

Je třeba zdůraznit, že, jak již můžeme vidět v těchto pravidlech, zákon vyloučeného středního se nedrží závislostní logiky (stejně jako nedrží nezávislou logiku nezávislosti): například pokud tým (X) obsahuje přiřazení (s) s (s (x) = s (y)) a přiřazení (s ') s (s' (x) not = s '(y)) pak (X / not / models x = y) a (X / not / models x / not = y). V této části v každém případě představíme jazyk logiky závislosti bez explicitního negačního operátora; poté budeme hovořit o důsledcích přidání do svého jazyka.

A co univerzální kvantifikace? Za jakých okolností by měl mít v týmu univerzálně kvantifikovaný výraz (forall v / psi)? Opět si musíme vzpomenout na intuici, podle které tým reprezentuje soubor možných stavů věcí. Pokud chceme vyhodnotit (forall v / psi), s ohledem na to, jaké možné stavy věcí bychom měli vyhodnotit (psi)? Přirozenou odpovědí je, že bychom měli brát v úvahu všechny stavy věcí, které se liší od těch v (X) pouze s ohledem na hodnotu (v). Toto ospravedlňuje následující pravidlo:

TS - (forall):

(X / models / forall v / psi) pouze tehdy, pokud (X [M / v] models / phi), kde (X [M / v]) je množina ({s ': / existuje s / v X / mbox {st} s' / sim_v x })

kde (s '\ sim_v s) znamená, že obě přiřazení (s) a (s') se od sebe liší nejvýše s ohledem na hodnotu proměnné (v).

[X = / begin {array} {l | c} textbf {přiřazení} & x \\ / hline s_0 & 0 \\ s_1 & 1 / end {array} Rightarrow X [M / y] = / begin {array} {l | c | c} textbf {přiřazení} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 \\ s'_3 & 1 & 1 / end {array})

Tabulka 2: (X) a (X [M / y]) v modelu se dvěma prvky (0) a (1).

Podívejme se nyní na disjunkci. Kdy by měl (phi / lor / psi) držet? Abychom na to odpověděli, připomeňme - znovu -, že týmy lze chápat jako soubory možných stavů věcí, a že tedy spojení dvou týmů (Y) a (Z) představuje všechny stavy věcí, které mohou nastane, pokud se jedná o (Y) nebo (Z). Proto pokud jsou obě vzorce (phi) a (psi) uspokojeny sadou týmů ({Y_1 / ldots Y_n, / ldots }) a ({Z_1 / ldots Z_n, / ldots }), jejich disjunkce (phi / lor / psi) by měla být uspokojena sadou týmů ({Y_i / cup Z_j: i, j / in 1, / ldots }) nebo rovnocenně

TS - (lor):

(X / models / phi / lor / psi) pouze tehdy, pokud (X = Y / cup Z) pro dva týmy (Y) a (Z) například (Y / models / phi) a (Z / models / psi).

Zde stojí za zmínku, že obecně nevyžadujeme, aby (Y) a (Z) byly nespojité. Kvůli vlastnostem uzavření směrem dolů, o kterém budeme brzy diskutovat, by tato další podmínka neměla žádný význam pro vlastní sémantiku logiky závislosti; ale v případě určitých rozšíření a variant logiky závislosti by tento dodatečný požadavek byl v rozporu se zásadou lokality, podle níž podmínky uspokojení výrazu závisí pouze na hodnotách proměnných, které se v něm vyskytují zdarma (Galliani 2012).

Je také důležité si uvědomit, že v logice závislosti disjunkce není idempotentní: například (eqord (x, y) lor / eqord (x, y)) není ekvivalentní (eqord (x), y)), a tým je uspokojen (X), a to pouze tehdy, pokud pro každé tři úkoly v (X), které se shodují na (x), alespoň dvě se shodují na (y). To se může zdát poněkud kontraintuitivní; ale je to přímý důsledek skutečnosti, že podle naší interpretace, (eqord (x, y) lor / eqord (x, y)) je třeba chápat jako každý možný stav věcí pochází z jednoho z dvě sady stavů věcí a v obou z nich (y) je funkce (x)”. Protože sjednocení funkcí není obecně funkcí, dochází k malému překvapení, že disjunkce v logice závislosti není indempotentní.

Nakonec uvažujeme případ existenciální kvantifikace. Kdy je výraz (existuje v / psi) uspokojen týmem? Abychom na to odpověděli, můžeme začít tím, že budeme uvažovat o interpretaci restrikčního operátora, který vzhledem k jakémukoli týmu (X) vede k týmu (X _ { backslash v}) získanému odstraněním proměnné (v) (pokud je přítomen) ze všech přiřazení (s / in X) (a poté, protože (X) je množina, sbalením identických přiřazení). To lze chápat jako zapomenutou operaci, jejímž prostřednictvím smažeme veškeré informace o hodnotě (v) - například proto, že to, co jsme věřili o této hodnotě, bylo nespolehlivé nebo protože tato hodnota byla změněna. Nyní předpokládejme, že (X _ { backslash v} = Y _ { backslash v}): pak podle naší interpretaceto znamená, že sady možných stavů věcí reprezentovaných (X) a (Y) nesouhlasí nanejvýš s ohledem na hodnotu (v). Pokud tedy (Y) splňuje podmínku (phi), můžeme říci, že (X) by vyhovovalo (phi), pokud ne pro hodnotu (y), nebo rovnocenně, že (X) vyhovuje (existuje v / psi). Toto ospravedlňuje následující pravidlo:

TS - (existuje):

(X / models / existuje v / psi) pokud a pouze pokud existuje nějaké (Y), přes proměnné (X) a (v), takový že (X _ { backslash v} = Y _ { backslash v}) a (Y / models / psi).

Je snadné ověřit, že tomu tak je, pokud a pouze pokud (Y) má tvar (X [F / y] = {s [a / y]: s / in X, a / in F (s) }) pro některé funkce (F) od přiřazení v (X) k neprázdným sadám prvků našeho modelu.

Zde je třeba zdůraznit, že ve výše uvedené definici není obecně vyžadováno, aby (X) a (Y) obsahovaly stejný počet přiřazení: jediné přiřazení v (X) může dobře odpovídat vícenásobným přiřazení v (Y), a - pokud (v) je proměnná vyskytující se v přiřazeních (X) - jediné přiřazení v (Y) může také odpovídat více přiřazením v (X)).

[X = / begin {array} {l | c} textbf {přiřazení} & x \\ / hline s_0 & 0 \\ s_1 & 1 / end {array} Rightarrow X [F / y] = / begin {array} {l | c | c} textbf {přiřazení} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 / end {array})

Tabulka 3: (X) a (X [F / y]) pro (F (s_0) = {0,1 }), (F (s_1) = {0 })

Odložíme důkladnou diskusi o vlastnostech logiky závislosti na specifikaci její herně-teoretické sémantiky. Uzavíráme však tuto část s následujícími třemi důležitými důsledky výše uvedených pravidel:

Lokalita:

Pokud omezení (X) a (Y) na proměnné vyskytující se volně v (phi) jsou stejná, pak (X / models / phi) pouze tehdy, pokud (Y / modely / phi).

Uzavření dolů:

Pokud (X / models / phi) a (Y / subseteq X), pak (Y / models / phi).

Vlastnost Empty set:

Pokud (emptyset) je tým bez přiřazení, pak (emptyset / models / phi) pro všechny vzorce závislosti logiky (phi).

Princip lokality spolu s principem konzervativnosti zmíněným na začátku této části představuje důležitý „zdravý stav“, který by měla splňovat jakákoli varianta a rozšíření logiky závislosti. Totéž nelze říci o uzavření dolů a vlastnosti prázdné sady, které - jak uvidíme - jsou porušeny variantami logiky závislosti.

Nakonec musíme definovat pravdu logické věty závislosti s ohledem na model. Protože věta nemá žádné volné proměnné, máme na principu lokality najednou, že to buď všechny neprázdné týmy uspokojí, nebo jej nevyhovuje žádný neprázdný tým. To je analogické s případem Tarského sémantiky, ve které je věta splněna všemi proměnnými přiřazeními nebo žádnou z nich. Pravdu tedy můžeme definovat obvyklým způsobem:

Pravda v sémantice týmu:

Věta (phi) platí v modelu (M) pouze tehdy, pokud (M, { emptyset } models / phi), kde ({ emptyset }) je tým obsahující pouze prázdné zadání. V tomto případě píšeme, že (M / models / phi).

2.1 Sémantika herní teorie

Jak již bylo zmíněno, herně-teoretická sémantika pro závislostní logiku je variantou nedokonalé informační sémantiky pro nezávislostní logiku, která je sama adaptací herně-teoretické sémantiky logiky 1. řádu. Odkazujeme čtenáře na Väänänen 2007a pro formální a detailní definici této sémantiky.

V sémantice hry-teoretika, věta (phi) a model (M) být dělán odpovídat (obvykle dva-hráč) hra (G_M (phi)). Pravda je pak definována z hlediska existence výherních strategií pro jednoho z hráčů (kteří se v této práci budou nazývat jednoduše „Player (0)“): jinými slovy, pokud (sigma_0) je (možná nedeterministická) strategie pro hráče (0) a (Pi (G_M (phi), / sigma_0)) je sada všech her, které jsou kompatibilní s (sigma_0), pak (phi) platí pouze tehdy, pokud každá hra v (Pi (G_M (phi), / sigma_0)) vyhrává pro hráče (0)). Je možné uvažovat o hře (G_M (phi)) jako debatu mezi dvěma hráči, z nichž jeden (Player (0)) chce ukázat, že je to tak, že (phi) zatímco druhý (Player (1)) chce ukázat, že tomu tak není (phi).

Stejně jako v případě logiky prvního řádu a logiky nezávislé na nezávislosti, i ve hře s nedokonalou informací pro logiku závislosti jsou pozice hry páry ((theta, s)), kde (theta) je instance podformuláře (phi) (tj. více výskytů stejného výrazu jako podformulář (phi) je třeba posuzovat samostatně) a (s) je přiřazení proměnné nad model (M). ^[1] Počáteční pozice je ((phi, / emptyset)), kde (emptyset) je prázdné přiřazení; a nedeterministická strategie (sigma_0) pro Player (0) vybere pro každou disjunkci a existenciální kvantifikaci jednoho nebo více nástupců aktuální pozice podle následujících pravidel:

• Pokud je aktuální pozice ve tvaru ((psi / lor / theta, s)), jsou jeho nástupci ((psi, s)) a ((theta, s));
• Je-li aktuální pozice ve tvaru ((existuje v / psi, s)), jsou její nástupci všechny pozice ((psi, s ')) s (s' / sim_v s).

Podobně nástupci ((psi / land / theta, s)) jsou ((psi, s)) a ((theta, s)) a nástupci ((forall v / psi, s)) jsou všechny pozice tvaru ((psi, s ')) pro (s' / sim_v s); ale strategie pro hráče (0) nemůže určit nástupce pro tyto pozice, protože se předpokládá, že hráč (1) vybere, která pozice je sleduje.

Posloupnost pozic (overline / rho = / rho_0 / rho_1 / ldots / rho_n) je hra (G_M (phi)) pouze tehdy, pokud

1. (rho_0 = (phi, / emptyset));
2. Pro všechny (i = 1 / ldots n) je (rho_ {i}) nástupcem (rho_ {i-1}).

Pokud dále (rho_ {i + 1} in / sigma_0 (rho_i)), kdy (rho_i) odpovídá disjunku nebo existenciálnímu kvantifikátoru, řekneme, že (overline / rho) respektuje strategie (sigma_0); a jak bylo zmíněno, píšeme (Pi (G_M (phi), / sigma_0)) pro množinu všech přehrání nad (G_M (phi)), které respektují (sigma_0)).

Říkáme, že strategie (sigma_0) vyhrává, pokud každá hra (overline / rho), která končí na pozici ((alfa, s)), kde (alfa) je první - doslovný řád je takový, že přiřazení (s) vyhovuje (alfa) v obvyklém smyslu Tarského sémantiky. Atomy závislosti - a hry, které končí atomy závislosti - nemají význam pro rozhodování, zda daná strategie vyhraje. Používají se však ke stanovení, zda je daná strategie jednotná:

Podmínka rovnoměrnosti

Strategie (sigma_0) pro (G_M (phi)) je stejná, pokud existují dvě hry (overline / rho, / overline / gamma / in / Pi (G_M (phi), / sigma_0))) které končí ve dvou pozicích ((eqord (x_1 / ldots x_n, y), s)), ((eqord (x_1 / ldots x_n, y), s ')) pro stejnou instanci atomu závislosti (eqord (x_1 / ldots x_n, y)) máme

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

Pak můžeme definovat pravdu v herně-teoretické sémantice takto:

Pravda v sémantice teoretické hry:

Věta (phi) platí v modelu (M) (s ohledem na sémantiku herní teorie) pouze tehdy, pokud má hráč (0) jednotnou výherní strategii v (G_M (phi)).

Lze ukázat, že tento pojem je v týmové sémantice ekvivalentní pojmu pravdy. Ve skutečnosti můžeme ukázat více než toto. Pokud pro jakýkoli tým (X) a vzorec (phi) se hra (G_ {M, X} (phi)) hraje jako (G_M (phi)), ale s počáteční pozice vybraná náhodně pro každou hru z ({(phi, s): s / in X }), pak platí následující:

Rovnocennost GTS a sémantika týmu:

Vzorec (phi) je splněn týmem (X) (s ohledem na model (M)) pouze tehdy, pokud má hráč (0) uniformu vítězná strategie v (G_ {M, X} (phi)).

Tento výsledek, stranou, objasňuje, proč týmová sémantika logiky závislosti uspokojuje vlastnost prázdné sady a vlastnost uzavření dolů. Pokud (X = / emptyset), pak každá strategie pro hráče (0) v (G_ {M, X} (phi)) je triviálně výherní a jednotná; a pokud (X / subseteq Y), pak jakákoli jednotná vítězná strategie pro hráče (0) v (G_ {M, X} (phi)) je také jednotnou vítěznou strategií pro hráče (0) v (G_ {M, Y} (phi)).

3. Vlastnosti

3.1 Expresivita

Logika závislosti je ekvivalentní existenciálnímu fragmentu (Sigma_1 ^ 1) logiky druhého řádu. Přesněji lze prokázat (Väänänen 2007a), že

Ekvivalence logiky závislosti a (Sigma_1 ^ 1):

Pro každou závislostní logickou větu (phi) existuje (Sigma_1 ^ 1) věta (phi ^ *) taková, že

) tag {6} label {eq: DLESO} M / models / phi / Leftrightarrow M / models / phi ^ * / textrm {pro všechny modely} M.)

Podobně pro každou (Sigma_1 ^ 1) větu (phi ^ *) existuje logická věta závislosti (phi) taková, že platí ((ref {eq: DLESO})).

Protože Faginova věta (Fagin 1974) ukazuje, že vlastnost konečných modelů je definovatelná v (Sigma_1 ^ 1) tehdy a jen tehdy, pokud je rozpoznatelná v polynomickém čase nedeterministickým Turingovým strojem (tj. Pokud a pouze pokud je v NPTIME), to okamžitě vyplývá

Logika závislosti a NPTIME:

Pro každou závislostní logickou větu (phi) je třída všech konečných modelů, které ji splňují, v NPTIME. Kromě toho pro všechny třídy NPTIME (mathcal K) konečných modelů existuje logická věta závislosti (phi) taková, že (M / models / phi) pouze tehdy, pokud (M / in / matematický K).

Další přímý důsledek ekvivalence logiky závislosti a (Sigma_1 ^ 1) na úrovni vět je, že věta o kompaktnosti a Löwenheimova-Skolemova věta platí i pro logiku závislosti (Väänänen 2007a):

Kompaktnost:

Pokud množina (Phi) logických vět konečných závislostí není v žádném modelu uspokojivá, pak její konečná podmnožina (Phi_0 / subseteq_f / Phi) již není uspokojivá.

Löwenheimova-Skolemova věta:

Pokud má závislostní logická věta nekonečný model, pak má modely všech nekonečných kardinálií.

Věci jsou však delikátnější, pokud jde o vzorce s volnými proměnnými. Pak je možné ukázat (Kontinen & Väänänen 2009), že závislostní logika odpovídá dolů uzavřenému fragmentu existenciální logiky druhého řádu:

Definice týmu v logice závislosti

Soubor (mathcal X) týmů nad modelem (M) a soubor (V) proměnných má tvar ({X: M, X / models) phi }) pro nějakou závislostní logiku vzorce (phi), s volnými proměnnými v (V), pouze a pokud

1. (mathcal X) je neprázdný;
2. (mathcal X) je směrem dolů uzavřeno, tj. (Y / subseteq X / in / mathcal X / Rightarrow Y / in / mathcal X);

3. (mathcal X) je (Sigma_1 ^ 1) - definovatelné v (M), to znamená, že existuje (Sigma_1 ^ 1) věta (Psi (R)), přes slovní zásobu (M) plus nový (| V |) - ary vztahový symbol (R), takže

   [X / in / mathcal X / textrm {if and only if} M, / textrm {Rel} (X) models / Psi (R))

   kde (textrm {Rel} (X)) je (| V |) - ary vztah ({s (V): s / in X }), který odpovídá týmu (X).

3.2 Hierarchie v logice závislosti

V Durand & Kontinen 2012 byl zkoumán účinek omezení počtu závislých proměnných atomů závislosti nebo počtu univerzálních kvantifikátorů. Ukázalo se, že oba tyto způsoby definování fragmentů logiky závislosti vedou ke vzniku hierarchií:

• Pro všechny (k) nechť (mathcal D (k- / forall)) je logika závislosti omezena nanejvýš na (k) univerzální kvantifikátory a nechte (mathcal D (k-dep)) logika závislosti omezená na atomy závislosti ve tvaru (eqord (vec x, y)) pro (| / vec x | / leq k). Pak

  ) begin {align *} mathcal D (k- / forall) & <\ mathcal D (k + 1-dep), \\ / mathcal D (k- / forall) & / leq / mathcal D (k- dep) leq / mathcal D (k + 1 - dep) end {zarovnat *})

  a

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

  s ohledem na expresivní pravomoc vět.

3.3 Negace v logice závislosti

Dosud jsme předpokládali, že všechny logické výrazy závislosti jsou v negační normální formě a že atomy závislosti nejsou nikdy negovány. Přidání explicitního negačního operátoru do logiky závislosti je na druhou stranu poněkud problematické, protože existenciální logika druhého řádu není uzavřena pod negací. Ve skutečnosti platí pravidlo „zřejmé“negace

[X / models / sim / phi / textrm {if and only if} X / not / models / phi)

výrazně zvyšuje expresivní sílu logiky závislosti a rozšiřuje ji na týmovou logiku (Väänänen 2007a, b), což je ve velmi silném smyslu ekvivalentní plné logice druhého řádu (Kontinen & Nurmi 2009).

Méně silnou „duální“negaci (lnot) lze definovat z hlediska de Morganových pravidel, (lnot (phi / lor) land] psi) equiv (lnot / phi) land) lor] (lnot / psi)) a (lnot (existuje v) forall v] phi) equiv / forall v) existuje v] (lnot / phi)), plus zákon dvojité negace (lnot / lnot / phi / equiv / psi) a pravidlo

[X / models { lnot / eqord} (vec x, y) textrm {if and only if} X = / emptyset)

pro negace atomů závislosti (Väänänen 2007a, b). Výsledný jazyk je výslovně ekvivalentem logiky závislosti bez negace a popis logiky závislosti Väänänen 2007a ve skutečnosti považuje tuto negaci za součást svého jazyka; jak je však uvedeno v Kontinen & Väänänen 2011, podmínky spokojenosti vzorce závislosti závislosti a podmínky jeho negace spolu navzájem mají jen malou souvislost. Přesněji:

Logika dvojí negace a závislosti:

Pro libovolné dvě vzorce závislosti logiky (phi) a (psi), že (phi / land / psi) není uspokojivá, existuje logika závislosti (theta) takové

[M, X / models / theta / textrm {if and only if} M, X / models / phi)

a

[M, X / models / lnot / theta / textrm {if and only if} M, X / models / psi)

pro všechny modely (M) a týmy (X).

O duální negaci (phi) tedy nelze obecně říci nic kromě toho, že je ekvivalentní nějakému logickému výrazu závislosti, který není uspokojen žádným týmem, který vyhovuje (phi). Protože, jak již bylo zmíněno, zákon vyloučené střední selhává v závislosti na logice závislosti, nejedná se o příliš informativní vlastnost; zejména je možné najít v logice závislosti (s duální negací) ekvivalentní výrazy s neekvivalentními negacemi, jako například (x / not = x / land y / not = y) a (lnot / eqord (x, y)).

3.4 Systémy pravdy, platnosti a důkazů v logice závislosti

Stejně jako logika závislá na nezávislosti, logika závislosti může definovat svůj vlastní pravý operátor (Väänänen 2007a), to znamená, že pokud pro všechny vzorce (phi) máme, (lceil / phi / rceil) je Gödelovo číslo (phi) pak najdeme vzorec (tau (x)), kde (x) je jeho jediná volná proměnná, takže

[M / models / phi / textrm {if a only if} M / models / tau (lceil / phi / rceil))

pro všechny modely (M), které uspokojí Peanovy axiomy pro přirozená čísla. To není v rozporu s Tarského teorémem nedefinovatelnosti, protože logika závislosti není uzavřena protichůdnou negací.

Problém rozhodování, zda je logická věta závislosti závislá (tj. Platí pro všechny modely), není aritmetický a ve skutečnosti je kompletní s ohledem na třídu (Pi_2) hierarchie Levy. Přesto byla studována teorie důkazů logiky závislosti. Zejména v Kontinen & Väänänen 2013 byl vyvinut zvukový a úplný důkazní systém pro problém nalezení důsledků teorie logiky závislosti prvního řádu.

4. Varianty logiky závislosti

V této části stručně shrneme vlastnosti nejstudovanějších variant logiky závislosti. Mnoho takových variant existuje a bylo mnoho práce na jejich klasifikaci a srovnání. V této práci zmíníme pouze ty varianty, které mají zvláštní význam z důvodu jejich vztahu k logice závislosti.

4.1 Logika nezávislosti

Spíše než rozšíření logiky prvního řádu o atomy závislosti (eqord (vec x, y)), logika nezávislosti (Grädel & Väänänen 2013) ji rozšiřuje o atomy nezávislosti (vec x / mathop { bot _ { vec z }} vec y), jehož zamýšlená interpretace je „pro jakoukoli možnou volbu (vec z), možné hodnoty (vec x) a (vec y) jsou nezávislé” - v Jinými slovy, vzhledem k pevné volbě (vec z) by znalost hodnoty (vec x) neposkytovala žádné informace o hodnotě přijaté (vec y). Jedná se o pojem, který má zásadní koncepční význam: například je možné chtít vyjádřit, že - pokud neznáte šifrovací klíč - vidět zašifrovanou verzi zprávy, nenese žádné informace o odpovídající verzi prostého textu. Pokud (x) představuje zašifrovanou zprávu a (y) představuje zprávu ve formátu prostého textu,pak to odpovídá podmínce (x / mathop { bot} y), kde (vec z) je v tomto případě prázdný. Podobně, pokud (k) představuje klíč, pak (x / mathop { bot} k) představuje tvrzení, že klíč nelze odvodit ze šifrované zprávy; a atom závislosti spojitosti (eqord (k, x, y)) (který, jak brzy uvidíme, může být reprezentován v logice nezávislosti) představuje tvrzení, že zpráva prostého textu může být dekódována s ohledem na zašifrovanou zprávu a klíč.může být reprezentován v logice nezávislosti) představuje tvrzení, že prostá textová zpráva může být dekódována s ohledem na šifrovanou zprávu a klíč.může být reprezentován v logice nezávislosti) představuje tvrzení, že prostá textová zpráva může být dekódována s ohledem na šifrovanou zprávu a klíč.

Formálně lze pravidlo spokojenosti atomů nezávislosti stanovit takto:

TS-indep:

(M / models_X / vec x / mathop { bot _ { vec z}} vec y) pouze tehdy, pokud pro všechny (s, s '\ in X) s (s (vec z) = s '(vec z)) existuje (s' '\ in X) s (s' '(vec z \, / vec x) = s (vec {x }, / vec {z})) a (s '' (vec y) = s '(vec y)).

) begin {array} {l | ccc} textbf {přiřazení} & / 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})

Logika nezávislosti je striktně výraznější než logika závislosti: ve skutečnosti postrádá vlastnost uzavření směrem dolů a atom závislosti (eqord (vec x, y)) je ekvivalentem atomu nezávislosti (y / mathop { bot_ { vec x}} y). Dále lze také ukázat (Galliani & Väänänen 2014), že podmíněné atomy nezávislosti (vec x / mathop { bot _ { vec y}} vec z) lze definovat jako nepodmíněné atomy nezávislosti (vec x / mathop { bot} vec y).

Logika nezávislosti je také ekvivalentní existenciální logice druhého řádu (Sigma_1 ^ 1); ale vzorec je výraznější a v Galliani 2012 se ukázalo, že dokáže zachytit všechny neprázdné (Sigma_1 ^ 1) - definovatelné vlastnosti týmu.

4.2 Logika začlenění

Logika inkluze (Galliani 2012, Galliani & Hella 2013) rozšiřuje logiku prvního řádu o atomy inkluze (vec x / subseteq / vec y), což připomíná závislosti inkluze z teorie databází. Jeho sémantika je:

TS-inc:

(M / models_X / vec x / subseteq / vec y) pokud a pouze pokud pro všechny (s / in X) existuje (s '\ in X) takový, že (s (vec x) = s '(vec y)).

) begin {array} {l | cc} textbf {přiřazení} & / mathbf {x_1} & / mathbf {x_2} / \ hline s_0 & 0 & 0 \\ s_1 & 0 & 1 \\ s_2 & 1 & 2 \\ s_3 & 2 & 3 / end {array})

Na rozdíl od logiky závislosti a nezávislosti je logika inkluze (větahodná) přísně slabší než existenciální logika druhého řádu. Ve skutečnosti lze prokázat (Galliani & Hella 2013), že je ekvivalentem kladného fragmentu největší logiky s pevným bodem, a proto zachycuje vlastnosti PTIME modelů před konečně uspořádanými modely. Logika inkluze je přísně slabší než logika nezávislosti, ale je nesrovnatelná s logikou závislosti: podmínky uspokojivosti jejích vzorců nejsou uzavřeny směrem dolů, ale jsou uzavřeny odbory v tom smyslu, že

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

4.3 Týmová logika

Týmová logika (Väänänen 2007a, b; Kontinen & Nurmi 2009) rozšiřuje logiku závislosti tím, že k ní přidává protichůdnou negaci (lnot). Rovnocenně s plnou logikou druhého řádu, a to jak z hlediska definovatelnosti tříd modelů (Väänänen 2007b), tak s ohledem na třídy týmů, které týmové logické výrazy mohou definovat s ohledem na daný model (Kontinen & Nurmi 2009).

4.4 Intuicionální logika závislosti

Intuitionistická závislostní logika (Abramsky & Väänänen 2009; Yang 2013) rozšiřuje logiku závislosti tím, že přidává implikační spojovací (phi / rightarrow / psi), jejíž pravidla spokojenosti jsou dána týmovou sémantikou

TS - (rightarrow):

(X / models / phi / rightarrow / psi) pouze tehdy, pokud pro všechny podsady (Y) z (X), pokud (Y / models / phi), poté (Y / models / psi).

Tento operátor se nazývá „intuicionální implikace“, protože existuje podobnost mezi jeho sémantikou a operátorem implikace v Kripkeho sémantice pro intuicionální logiku (Kripke 1965). Jeho interpretace z hlediska víry je velmi přímá: pokud přiřazení v (X) reprezentují stavy věcí, které některý agent považuje za možné, pak podskupina (Y) (X) může představovat výsledek aktualizace víry, ve které agent odmítá některé dříve uvěřené možné stavy věcí, a (phi / rightarrow / psi) stavy než jakákoli taková aktualizace, která by způsobila držení (phi), by také způsobila (psi) držet. Z tohoto hlediska je to velmi přirozený koncept, který nám umožňuje popsat předpovědi o tom, jak by celkový stav víry takového agenta reagoval na aktualizace víry.

Avšak vzhledem k univerzální kvantifikaci druhého řádu, která je ve sémantice implikovaná, postačuje tato spojitost k výraznému zvýšení expresivní složitosti logiky: zejména, jak je ukázáno v Yang 2013, jakákoli věta logiky druhého řádu je ekvivalentní nějaké větě intuicionální závislosti logika. Intuitionistická závislostní logika si zachovává vlastnost uzavírání směrem dolů: pokud tým splňuje intuicionální závislostní logickou rovnici, pak udělá všechny své podmnožiny.

4.5 Propoziční logika závislosti

Uvažované atomy závislosti a nezávislosti dosud vyjadřují vztahy mezi možnými hodnotami proměnných v sadě přiřazení. Stejné představy o závislosti a nezávislosti však lze stejně přirozeně aplikovat i na samotnou nabídku, jako je tomu u výrazu v přirozeném jazyce, jako je například „„ Zda bude nebo nebude absolvovat kurz, záleží pouze na obsahu jeho závěrečné zkoušky “..

Propoziční závislostní logika zvažuje takové atomy v kontextu výrokové logiky. Logické týmy prozatímní závislosti jsou sady ocenění (v) od výrokových atomů (p_1 / ldots p_n) do ({T, F }). Jeho sémantická pravidla - a jejich zdůvodnění - velmi úzce odrážejí pravidla sémantiky týmů prvního řádu a pravidlo pro atomy závislosti je

PTS-dep:

(X / models / eqord (p_1 / ldots p_n, q)) pouze tehdy, pokud existují dvě ocenění (v_1, v_2 / in X), která se shodují na hodnotách (p_1 / ldots p_n) také se dohodli na hodnotě (q).

Mnoho variant a zobecnění logiky závislosti prvního řádu lze bez problémů snížit na výrokovou úroveň: například je tedy možné studovat vlastnosti výrokové inkluzivní logiky, výrokové týmové logiky, výrokové intuicionální závislosti a tak dále.

Zatímco logika závislosti prvního řádu je striktně výraznější než logika prvního řádu, logika výrokové závislosti není výraznější než logika výroku, jak to bezprostředně vyplývá ze skutečnosti, že všechny výrokové funkce jsou vyjádřeny v výrokové logice. Existuje však úzký vztah mezi týmy logiky výrokové závislosti a informačními stavy zvídavé logiky (Groenendijk 2009; Ciardelli & Roelofsen 2011), sémantický rámec pro studium pojmu význam a výměna informací: zejména, implikace zvídavé logiky je přesně stejná jako implicitní intuicionální závislostní logika.

Axiomatizace pro logiku výrokové závislosti a mnoho jejích rozšíření najdete v Yang & Väänänen 2016.

4.6 Logická závislostní logika

Logická modální závislost (Väänänen 2008) a její varianty rozšiřují modální logiku přidáním stejných atomů závislosti (eqord (p_1 / ldots p_n, q)) již uvažovaných v případě výrokové logiky závislosti.

Podmínky jeho spokojenosti lze definovat variantou sémantiky týmů, ve které jsou týmy nahrazeny sadami možných světů.

Mnoho výzkumů zkoumalo složitost-teoretické vlastnosti této logiky, jejích fragmentů a jejích rozšíření (Ebbing, Lohmann, & Yang 2011; Ebbing & Lohmann 2012; Lohmann & Vollmer 2013).

5. Aplikace logiky závislosti

5.1 Logika závislosti a teorie databází

Mezi týmy týmové sémantiky a vztahy studovanými v teorii relačních databází existuje přímé spojení: vzhledem k týmu (X) a množině proměnných (vec v = v_1 / ldots v_k), ke kterým dochází v jeho přiřazeních, je možné definovat vztah (X (vec v) = { langle s (v_1), / ldots, s (v_n) rangle: s / in X })). Atomy závislostí studované v závislosti na logice a jejich varianty jsou navíc analogické - a v mnoha případech odvozené - závislostem uvažovaným v teorii databáze, jako jsou funkční závislosti (Väänänen 2007a), vícehodnotové závislosti (Engström 2012) a závislosti na inkluzi a vyloučení. (Galliani 2012). Vztah mezi logikou závislosti a teorií databází přispěl nejen k dalšímu rozvoji logiky závislosti, ale také k teorii databází: například,v Hannula & Kontinen 2016 byla konečná axiomatizace neomezeného implikačního problému pro začlenění, funkční a vestavěné vícehodnotové databázové-teoretické závislosti zjištěna studiem podobného problému v kontextu týmové sémantiky.

5.2 Logika závislosti a reprezentace víry

Jak bylo diskutováno v Yang 2014 a Yang & Väänänen 2016, existuje úzká souvislost mezi (výrokovou) intuicionální závislostní logikou a zvídavou logikou (Ciardelli & Roelofsen, 2011), rámec pro studium významu a výměny informací mezi agenty. Obecněji platí, že atomy závislosti a spojky studované v týmové sémantice připouštějí přirozené interpretace z hlediska stavů víry a aktualizací víry, jak je diskutováno v Galliani 2015. V této době přesná povaha vztahu mezi takovou logikou a dynamicko-epistemickou logikou a jeho varianty (Van Ditmarsch, van Der Hoek a Kooi 2007) jsou do značné míry neprozkoumané, existuje však dostatečný důvod k podezření na další souvislosti mezi těmito dvěma oblastmi matematické a filozofické logiky.

5.3 Logika závislosti a Arrowova věta

Arrowova věta (Arrow 1950) je hluboce ovlivňujícím výsledkem teorie sociální volby, která ve stručnosti ukazuje, že neexistuje žádný hlasovací systém (to znamená, že neexistuje žádný systém pro převod žebříčku individuálních preferencí mezi alternativy do globálního žebříčku preferencí na úrovni společnosti). které mohou splnit tři rozumně znějící podmínky, a to

• Pokud každý volič upřednostňuje (A) na (B), preferuje skupina jako celek (A) a (B);
• Zda skupina jako celek upřednostňuje (A) k (B) nebo naopak, záleží výhradně na preferencích každého voliče ohledně (A) a (B), a nikoli na jejich preferencích týkajících se jiných možných alternativ;
• Žádný volič není diktátorem, to znamená, že preference skupiny nejsou určovány preferencemi každého jednotlivého voliče.

Jak samotné znění naznačuje, druhá a třetí podmínka připouštějí přirozené čtení, pokud jde o závislost a nezávislost: ve skutečnosti, jak je ukázáno v Pacuit & Yang 2016, může být Arrowova věta formalizována v logice nezávislosti a prokázána ve vhodném přirozeném dedukčním systému.

5.4 Kvantová logika týmu a Bellovy nerovnosti

V Hyttinenu, Paolini a Väänänen 2015 je představena varianta výrokové týmové logiky, zvaná kvantová týmová logika. V tomto formalismu jsou týmy nahrazeny kvantovými týmy, které se liší od běžných týmů výrokové týmové logiky tím, že umožňují, aby hodnoty určitých proměnných byly neurčité s ohledem na určitá ocenění, a v tom, že umožňují vícenásobné případy stejné ocenění (čímž se týmová sémantika přidá kvantitativní aspekt). Sémantika je pak definována přes kvantové týmy pro jazyk, který umožňuje specifikaci nerovností týkajících se pravděpodobnosti událostí, a je pro něj vyvinut zvukový a úplný důkazní systém; a konečně je ukázáno, že Bellovy nerovnosti připouštějí v těchto systémech protiklady,jak to dělají podle předpovědí kvantové mechaniky a podle experimentálních důkazů (Einstein, Podolsky, & Rosen 1935; Bell 1964; Aspect, Grangier a Roger 1981), zatímco v klasické verzi tohoto rámce tomu tak není.

Bibliografie

• Abramsky, Samson a Jouko Väänänen, 2009, „Od IF k BI: Příběh závislosti a separace“, Synthese, 167 (2): 207–230. doi: 10,1007 / s11229-008-9415-6
• Arrow, Kenneth J., 1950, „Obtížnost v pojetí sociální péče“, Journal of Political Economy, str. 328–346. doi: 10,106 / 256963
• Aspect, Alain, Philippe Grangier a Gérard Roger, 1981, „Experimentální testy realistických místních teorií pomocí Bellovy věty“, Fyzikálně přehledné dopisy, 47 (7): 460–463. doi: 10,1103 / PhysRevLett.47.460
• Bell, JS, 1964, “Na Einstein-Podolsky-Rosen paradox”, Physics, 1 (3): 195–200.
• Ciardelli, Ivano a 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 a Barteld Kooi, 2007, Dynamic Epistemic Logic, (Synthese Library 337), Dordrecht: Springer. doi: 10,1007 / 978-1-4020-5839-4
• Durand, Arnaud a Juha Kontinen, 2012, „Hierarchie v závislosti na logice“, transakce ACM na výpočetní logice (TOCL), 13 (4): 1–21. doi: 10,1145 / 2362355,2362359
• Ebbing, Johannes a Peter Lohmann, 2012, „Složitost kontroly modelu pro logickou závislost logiky“, SOFSEM 2012: Mezinárodní konference o současných trendech v teorii a praxi informatiky, (přednášky z informatiky, 7147), Berlín, Heidelberg: Springer, str. 226–237. doi: 10,1007 / 978-3-642-27660-6_19
• Ebbing, Johannes, Peter Lohmann a Fan Yang, 2013, „Kontrola modelu pro modulární intuitivní závislostní logiku“, mezinárodní Tbilisi sympozium o logice, jazyce a výpočtech 2011, (Přednášky z počítačových věd, 7758), Berlín, Heidelberg: Springer, str. 231–256. doi: 10,1007 / 978-3-642-36976-6_15
• Einstein, A., B. Podolsky a N. Rosen, 1935: „Lze považovat kvantově-mechanický popis fyzické reality za úplný?“Physical Review, 47 (10): 777–780. doi: 10,1103 / PhysRev.47,777
• Engström, Fredrik, 2012, „Generalizované kvantifikátory v závislosti na logice“, Journal of Logic, Language and Information, 21 (3): 299–324. doi: 10,1007 / s10849-012-9162-4
• Fagin, Ronald, 1974, „Generalizovaná spektra prvního řádu a polynomiální časové rozeznatelné sady“, Složitost výpočtu (SIAM-AMS Proceedings 7), Richard M. Karp (ed.), Providence, RI: American Mathematical Society, pp. 27–41.
• Galliani, Pietro, 2012, „Závislosti v oblasti inkluze a vyloučení v sémantice týmu - na některé logice nedokonalých informací“, Annals of Pure and Applica Logic, 163 (1): 68–84. doi: 10,016 / j.apal.2011.08.005
• ––– 2015, „Doxastická interpretace týmové sémantiky“, Logika bez hranic: Eseje o teorii množin, Teorie modelů, Filozofická logika a Filozofie matematiky (Ontos Matematická logika, 5), Åsa Hirvonen, Juha Kontinen, Roman Kossak, a Andrés Villaveces (eds), Berlín, Boston: De Gruyter, s. 167–192. doi: 10,1515 / 9781614516873,167
• Galliani, Pietro a Lauri Hella, 2013, „Logika začleňování a logika pevných bodů“, Logika informatiky 2013 (Leibniz Mezinárodní řízení v informatice (LIPIcs), 23), Dagstuhl, Německo: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 281–295. doi: 10,4230 / LIPIcs. CSL.2013.281
• Galliani, Pietro a Jouko Väänänen, 2014, „On Dependence Logic“, v Johan van Benthem o logické a informační dynamice (vynikající příspěvky k logice, 5), Alexandru Baltag a Sonja Smets (eds), Cham: Springer, s. 101– 119. doi: 10,1007 / 978-3-319-06025-5_4
• Grädel, Erich a Jouko Väänänen, 2013, „Závislost a nezávislost“, Studia Logica, 101 (2): 399–410. doi: 10,1007 / s11225-013-9479-2
• Groenendijk, Jeroen, 2009, „Inquisitive Sémantika: Dvě možnosti pro disjunkce“, v Peteru Boschovi, Davidovi Gabelaia a Jérôme Langovi (eds), sedmém mezinárodním sympoziu Tbilisi o jazyce, logice a výpočtu (Poznámky k přednášce v informatice: Svazek 5422)), Springer-Verlag, s. 80–94. doi: 10,1007 / 978-3-642-00665-4_8
• Hannula, Miika a Juha Kontinen, 2016, „Konečná axiomatizace podmíněných závislostí a nezávislostí“. Information and Computation, 249: 121–137. doi: 10,016 / j.ic.2016.04.001
• Henkin, Leon, 1961, „Některé poznámky k nekonečně dlouhým formám“, v Infinitistických metodách (Sborník ze sympozia o základech matematiky, Varšava, 1959), Oxford: Pergamon Press, s. 167–183.
• Hodges, Wilfrid, 1997, „Kompoziční sémantika pro jazyk nedokonalých informací“, Logic Journal of IGPL, 5 (4): 539–563. doi: 10,1093 / jigpal / 5,4,539
• Hyttinen, Tapani, Gianluca Paolini a Jouko Väänänen, 2015, „Quantum Team Logic a Bellovy nerovnosti“, Recenze Symbolic Logic, 8 (4): 722–742. doi: 10,017 / S1755020315000192
• Kontinen, Juha a Ville Nurmi, 2009, „Týmová logika a logika druhého řádu“, ve sborníku 16. mezinárodního semináře o logice, jazyce, informacích a výpočtech (přednášky z informatiky, 5514), Berlín, Heidelberg: Springer, str. 230–241. doi: 10,1007 / 978-3-642-02261-6_19
• Kontinen, Juha a Jouko Väänänen, 2009, „O definovatelnosti v závislosti na logice“, Journal of Logic, Language and Information, 18 (3): 317–332.doi: 10.1007 / s10849-009-9082-0
• –––, 2011, „Poznámka k negaci v logice závislosti“, Notre Dame Journal of Formal Logic, 52 (1): 55–65. doi: 10,1215 / 00294527-2010-036
• ––– 2013, „Axiomatizace důsledků prvního řádu v logice závislosti“, Annals of Pure and Applica Logic, 164 (11): 1101–1117. doi: 10,016 / j.apal.2013.05.006
• Kripke, Saul A., 1965, „Sémantická analýza intuitivní logiky I“, ve formálních systémech a rekurzivních funkcích: Sborník z osmého logického kolokvia, Oxford červenec 1963 (Studie logiky a základy matematiky, 40), John N. Crossley a Michael AE Dummett (eds.), Severní Holandsko, s. 92–130. doi: 10,016 / S0049-237X (08) 71685-9
• Lohmann, Peter a Heribert Vollmer, 2013, „Výsledky složitosti pro modální závislostní logiku“, Studia Logica, 101 (2): 343–366. doi: 10,1007 / s11225-013-9483-6
• Pacuit, Eric a Fan Yang, 2016, „Závislost a nezávislost ve společenské volbě: Arrowův teorém“, v závislosti Logic, Samson Abramsky, Juha Kontinen, Jouko Väänänen a Heribert Vollmer (eds), Dordrecht: Springer, p. 235–260. doi: 10,1007 / 978-3-319-31803-5_11
• Väänänen, Jouko, 2007a, Logika závislosti: Nový přístup k logice nezávislosti přátelské, (texty studentů London London Mathematical Society, 70), Cambridge: Cambridge University Press. doi: 10,017 / CBO9780511611193
• –––, 2007b, „Týmová logika“, v interaktivní logice: Vybrané příspěvky ze 7. semináře Augustuse de Morgana (Texty v logice a hrách, 1), Johan van Benthem, Dov Gabbay a Benedikt Löwe (ed.), Amsterdam: Amsterdam University Press, s. 281–302.
• –––, 2008, „Logická závislostní logika“, Nové pohledy na hry a interakce (texty v logice a hrách, 4), Krzysztof R. Apt a Robert van Rooij (eds), Amsterdam: Amsterdam University Press, s. 2337– 254.
• Yang, Fan, 2013, „Vyjádření vět druhého řádu v logice závislosti intuice“, Studia Logica, 101 (2): 323–342. doi: 10,1007 / s11225-013-9476-5
• ––– 2014, „O rozšířeních a variantách logiky závislosti: Studie intuitivních spojiv v nastavení sémantiky týmu“. Doktorská práce, Helsinská univerzita.
• Yang, Fan a Jouko Väänänen, 2016, „Propoziční logika závislosti“, Annals of Pure and Applied Logic, 167 (7): 557–589. doi: 10,016 / j.apal.2016.03.003

Akademické nástroje

	Jak citovat tento záznam.
	Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.
	Vyhledejte toto vstupní téma v projektu Internet Philosophy Ontology Project (InPhO).
	Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje

• Logika závislosti na Wikipedii
• Prezentace v Logic Colloquium Dependence Logic, Amsterdam, 2014