Логика на зависимостта

2023 Автор: Noah Black | [email protected]. Последно модифициран: 2023-08-25 04:38

Навигация за влизане

• Съдържание за участие
• библиография
• Академични инструменти
• Friends PDF Preview
• Информация за автора и цитирането
• Върнете се в началото

Логика на зависимостта

За първи път публикуван на 23 февруари 2017 г.

Логиката на зависимостта е разширение на логиката от първи ред, която добавя към нея атоми на зависимост, тоест изрази от формата (eqord (x_1 / ldots x_n, y)), които твърдят, че стойността на (y) е функционално зависими от (с други думи, определени от) стойностите на (x_1 / ldots x_n). Тези атоми позволяват уточняване на нелинейно подредени модели на зависимост между променливи, почти в същия смисъл на нарязаните количествено-количествени коефициенти на IF-Logic; но, различно от IF-логиката, логиката на зависимостта отделя количественото определяне от спецификацията на такива условия на зависимост / независимост. Основната семантика на логиката на зависимостта, наречена екипна семантика, обобщава семантиката на Тарски, като позволява изразите да бъдат удовлетворени или не удовлетворени по отношение на набори от променливи задания, а не по отношение на единични задачи. Тази семантика предопределя самото развитие на логиката на зависимостта и първоначално е разработена от Уилфрид Ходжес в контекста на IF-логиката (Hodges 1997). Съществува също игрово-теоретична семантика за логиката на зависимостта, базирана на игри с несъвършена информация и приблизително аналогична на игрово-теоретичната семантика за благоприятна за независимостта логика (Väänänen 2007a). Sensu stricto, терминът „логика на зависимостта“се отнася изключително до езика, получен чрез добавяне на гореспоменатите атоми на функционалната зависимост към езика на логиката от първи ред; но терминът се използва също в по-общ смисъл, за да се отнася до областта на изследване, която изучава свойствата на логиките, получени чрез добавяне на различни понятия за зависимост и независимост към логиката от първи ред, като логиката за независимост (Grädel & Väänänen 2013),интуиционистична логика на зависимостта (Yang 2013) или логика на включване (Galliani 2012, Galliani & Hella 2013) или дори тези на логиката, разширяващи други логически рамки чрез подобни атоми, както в случая на логиката на модалната зависимост (Väänänen 2008). В тази статия терминът „логика на зависимостта“ще се използва за обозначаване на съответната логика на зависимостта, а терминът „логика на зависимостта и независимостта“ще се използва за обозначаване на нейните варианти и обобщения.и терминът „логика на зависимостта и независимостта“вместо това ще се използва за обозначаване на нейните варианти и обобщения.и терминът „логика на зависимостта и независимостта“вместо това ще се използва за обозначаване на нейните варианти и обобщения.

• 1. Моделите на зависимост в логиката от първи ред и нейните разширения

• 2. Екипна семантика

  2.1 Игрово-теоретична семантика

• 3. Свойства

  • 3.1 Експресивност
  • 3.2 Йерархии в логиката на зависимостта
  • 3.3 Отрицание в логиката на зависимостта
  • 3.4 Системи за истина, валидност и доказателство в логиката на зависимостта

• 4. Варианти на логиката на зависимостта

  • 4.1 Логика на независимостта
  • 4.2 Логика на включване
  • 4.3 Екип на логиката
  • 4.4 Интуиционистка логика на зависимостта
  • 4.5 Логика на предложената зависимост
  • 4.6 Логика на модалната зависимост

• 5. Приложения на логиката на зависимостта

  • 5.1 Логика на зависимостта и теория на базата данни
  • 5.2 Логика на зависимостта и представяне на убеждения
  • 5.3 Логика на зависимостта и теорема на Стрела
  • 5.4 Квантова логика на екипа и неравенствата на Бел
• библиография
• Академични инструменти
• Други интернет ресурси
• Свързани записи

1. Моделите на зависимост в логиката от първи ред и нейните разширения

Една особеност на логиката от първи ред, която отчита голяма част от своята експресивност и приложимост, е фактът, че тя позволява да бъдат вложени количествени средства и следователно позволява да се уточни моделите на зависимост между количествено променливите. Помислете например за (надяваме се, невярно) твърдение, че „всяко момче обича някое момиче, което обича друго момче“. Тя може да бъде директно преведена в логика от първи ред като

) етикет {1} етикет {eq: boygirl1} начало {подравняване} & / forall x (boy (x) rightarrow / съществува y (момиче (y) земя / обича (x, y) земя {} & / quad / съществува z (boy (z) land x / not = z / land / обича (y, z)))) end {align})

чието условие за истинност, според обичайната семантика на Тарски, е точно това, което човек би очаквал: горният израз е верен, ако и само ако за всяко момче (b) е възможно да се намери момиче (g) и момче (b '), така че (b) обича (g) и (g) обича (b') и (b) и (b ') не са едно и също. Самоличността на момичето (g) може, разбира се, да зависи от самоличността на първото момче (b) - в края на краищата, за да е вярно този израз, не се изисква всички момчета да са влюбени във всички момичета- и освен това, идентичността на второто момче (b ') може да зависи както от идентичността на първото момче (b) (тъй като (b') трябва да е различно от (b)) и от самоличността на момичето (g), което (b) обича. Така че моделът на зависимост между нашите количествено променливи е следният: (y) зависи от (x),докато (z) зависи и от (x), и (y). От синтактична гледна точка това се отразява от факта, че (съществува y) е в обхвата на (forall x), докато (съществува z) е в обхвата на двете (forall x) и (съществува y).

Разликите в моделите на зависимост между операторите могат да се използват за формализиране на важни разграничения, като например тази между непрекъснатостта на функция (f)

) forall x / forall / epsilon / съществува / delta / forall x '(| x - x' | <\ delta / rightarrow | f (x) - f (x ') | <\ epsilon))

и равномерната му приемственост

) forall / epsilon / съществува / delta / forall x / forall x '(| x - x' | <\ delta / rightarrow | f (x) - f (x ') | <\ epsilon))

или, в интензивни разширения на логиката от първи ред, да се изрази разликата между показанията на De Dicto и De Re (напр. „Възможно е всеки човек да е луд“може да се разбира или като заявява, че това е за всеки човек (p), възможно е (p) да е луд, (forall x (person (x) rightarrow / Diamond / crazy (x))) или като заявява, че е възможно всички да са луди заедно, (Diamond / forall x (person (x) rightarrow / crazy (x)))).

Моделите на зависимост между количествено определени променливи в логиката от първи ред са непременно транзитивни, тъй като това става очевидно от връзките им с обхвата на съответните под-изрази: ако (съществува y) е в обхвата на (forall x) и (съществува z) е в обхвата на (съществува y), тогава задължително (съществува z) ще бъде в обхвата на (и следователно, зависи от) (forall x). Освен това, наборът от всички квантори, в чийто обхват се намира някаква подформула (alpha), е линейно подреден: ако (alpha) е в обхвата на (Q_1 x_1) и (Q_2 x_2), тогава или (Q_1 x_1) е в обхвата на (Q_2 x_2), или обратно.

Това ограничава изразителните възможности на логиката от първи ред. Например, нека предположим, че искаме да изменяме предишното си твърдение за момчета и момичета по следния начин: всяко момче обича някое момиче, което обича друго момче, а това второ момче може да бъде избрано независимо на първото. Интуитивно казано това означава, че е достатъчно просто: за всяко момче (b) можем да намерим момиче (g) такова, че (b) обича (g), а за всяко такова момиче можем намери момче (b ') такова, че (g) обича (b') и (b / not = b '), и освен това можем да открием самоличността на второто момче (b') без да знае това на (b) въз основа на самоличността на момичето (g). Това все още може да е вярно в някои сценарии, като например, ако две момчета (b_1) и (b_2) обичат съответно две момичета (g_1) и (g_2),които обаче обичат само (b_2) и (b_1) съответно. Обаче лесно се вижда, че то не е еквивалентно на предишното ни твърдение: например, ако нашата Вселена се състои (както в б) по-горе) от две момчета (b) и (b ') и момиче (g) и (b) и (b ') и двете обичат (g), който обича и двете, тогава предишното ни твърдение е вярно, но настоящото е невярно.

Два сценария, в които ((ref {eq: boygirl1})) е истина. В (a) (z) може да бъде избран независимо от (x); в б) не може.

Не е ясно обаче как да формализираме това условие по логика от първи ред. По същество ще трябва да модифицираме ((ref {eq: boygirl1})), така че (z) да не е в обхвата на (x), и следователно не зависи от него; все пак бихме искали (z) да зависи от (y) и (y) от (x). Както току-що беше обсъдено обаче, такъв модел на зависимост не може да се осъществи по логика от първи ред. Можем да заобиколим въпроса, като прибягваме до количествено определяне на по-висок ред: наистина може да се види, че изразът

) етикет {2} етикет {boygirl2} започнем {подравнявам} & / съществува F / forall x (boy (x) rightarrow / съществува y (girl (y) land / loves (x, y) land / boy (F (y)) land {} & / quad x / not = F (y) land / обича (y, F (y)))) end {align})

улавя намерената ни интерпретация, но само с цената на изричното екзистенциално количествено определяне на функциите.

Възможна алтернатива би била разширяването на синтаксиса на логиката от първи ред, за да се премахнат ограниченията относно моделите на зависимост между количествено променливите. Това е маршрутът, взет от логиката на количествено разклонение (Henkin 1961), в който условията за истинност на ((ref {boygirl2})) отговарят на тези на

) етикет {3} етикет {boygirl3} начало {подравняване} & / наляво (започнем {smallmatrix} forall x & / съществува y \\ / forall z & / съществува w / end {smallmatrix} вдясно) (boy (x) rightarrow (момиче (y) земя / обича (x, y) земя {} & / quad (y = z / rightarrow (boy (w) land x / not = w / land / обича (z, w))))), / end {align})

и към логиката на независимостта, в която ((ref {boygirl2})) е еквивалентна на

) етикет {4} етикет {boygirl4} започнем {подравняване} & / forall x / съществува y (boy (x) rightarrow (girl (y) land / loves (x, y) land (съществува z / x) (boy (z) land {} & / quad x / not = z / land / обича (y, z)))). / end {align})

Тук няма да даваме подробно обяснение на семантиката на тези два формализма; достатъчно е да се каже, че в ((ref {boygirl3})) стойността на (w) не зависи от стойностите на (x) и (y) (въпреки че може да зависи от стойността на (z)), тъй като те принадлежат към различни "редове" на сложния количествен елемент (вляво (започва {smallmatrix} forall x & / съществува y \\ / forall z & / съществува w / end {smallmatrix } право)), докато в ((ref {boygirl4})) стойността на (z) не зависи от стойността на (x), тъй като тази зависимост е изрично „намалена“чрез количествения елемент ((съществува z / x)).

Една особеност, обща за логиката на разклоняване на количествените фактори и логиката, благоприятна за независимостта, както виждаме, е, че те не разделят количественото определяне на променливите от спецификацията на нестандартните модели на зависимост: както в случая на логиката от първи ред, дали количествено определена променлива (v_1) ще зависи или не зависи от някаква друга количествена променлива (v_2) ще се определя от съответната позиция и форма на техните количествени характеристики.

Логиката на зависимостта приема различен подход към проблема с разширяването на логиката от първи ред, за да се представи ((ref {boygirl2})). В сравнение с ((ref {eq: boygirl1})), единственото ново условие е това, което заявява, че стойността на (z) се определя от (тоест, функционално зависима от) стойността на (у); и това съответства на ново атомно условие (eqord (y, z)), наречено атом на зависимост, чието предназначение е, че (стойността на) (z) е функция на стойността на (y). За разлика от случаите на разклоняваща се количествена логика или логика, подходяща за независимостта, това е условие за стойностите, които могат да приемат (y) и (z), а не условие за поведението на количествения елемент (съществува z): наистина няма принципно причина да се изисква, че (z) изобщо е количествена променлива - може вместо това да е безплатна променлива,или някакъв сложен термин, включващ множество променливи.

В зависимост от логиката, ((ref {boygirl2})) може да бъде формализиран като

) маркер {5} етикет {boygirl5} започнем {подравнявам} & / forall x / съществува y / съществува z (eqord (y, z) land (boy (x) rightarrow (girl (y) land / обича (x, y) rightarrow {} & / quad (boy (z) land x / not = z / land / loves (y, z))))) end {align})

Условията за истинност на ((ref {boygirl2})), ((ref {boygirl3})), ((ref {boygirl4})) и ((ref {boygirl5})) са абсолютно еднакви: всеки модел, който удовлетворява един от тези изрази (на съответните езици), отговаря на всичките четири. По-общо, както ще видим, изразителните сили на екзистенциалната логика от втори ред, логиката на независимостта и логиката на зависимостта по отношение на дефинируемостта на класовете модели са абсолютно еднакви. Това обаче не е така за формули с безплатни променливи; и освен това, тези логики могат да бъдат разширени и модифицирани по очевидно различни линии.

2. Екипна семантика

Екипната семантика, разработена за първи път от Уилфрид Ходжес в контекста на логиката, свързана с независимостта (Hodges 1997), е обобщение на семантиката на Тарски за логика от първи ред към случая на множество присвояване на елементи на променливи. Наборите от такива задачи, наречени екипи по исторически причини, представляват основното семантично понятие за семантиката на екипа и формулите са удовлетворени или не са удовлетворени по отношение на тях, а не по отношение на единични задачи. Връзката между семантиката на екипа и семантиката на Тарски е показана от следния резултат, който се държи в логиката на зависимост, както и във всичките му варианти от първия ред:

Консервативност:

Формулата от първи ред се удовлетворява от екип (X) (по смисъла на семантиката на екипа), ако и само ако всички задачи (s / в X) го удовлетворяват (в смисъла на семантика на Тарски).

По-общо, отборите могат да се разбират като групи от вярвания, представляващи набора от всички състояния на света (= задания), които някой агент смята за възможни. Тогава екип (X) ще задоволи някаква формула (phi), ако и само ако (phi) има значение, когато (X) е множеството от всички възможни състояния; и в този случай ще напишем (X / модели / phi) (или (M, X / модели / phi), ако изборът на модела (M) не е ясен). В този раздел ще разгледаме правилата на семантиката на екипа и тяхната интерпретация по отношение на този принцип; след това в следващия раздел ще обсъдим как тя възниква също от несъвършената информационно-теоретична игра-семантика за логиката на зависимостта.

Условието за новите атоми на зависимост (eqord (x_1 / ldots x_n, y)), които съответстват на твърдението, че стойността на (y) е функция на стойностите на (x_1 / ldots x_n), лесно се разбира:

TS-dep:

(X / модели ~ / eqord (x_1 / ldots x_n, y)), ако и само ако има две задачи (s_1, s_2 / в X), които са съгласни със стойностите на (x_1 / ldots x_n) също се съгласяват за стойността на (y).

Например, да предположим, че (X) е набор от задания над трите променливи (x_1), (x_2) и (y), където (x_1) представлява националността на кандидат за позиция, (x_2) представлява резултата им (според подходящ метод за оценка) и (y) представлява дали са приети или отхвърлени. Тогава atom (eqord (x_2, y)) съответства на твърдението, че офертата се определя само от резултата: ако двама кандидати имат една и съща оценка, те ще получат абсолютно една и съща оферта, независимо от всеки друг фактор. Специален случай на атом на зависимостта е даден от атомите на постоянството (eqord (y)), които - според горната семантика - са удовлетворени от екип, ако и само ако всичките му задачи са съгласни със стойността на (у).

) започнем {масив} {l | ccc} textbf {назначение} & / 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 {масив})

Таблица 1: Екип (X), в който (y = x_1 + x_2). Тук (y) е функция от (x_1) и (x_2), и следователно (= \! \! (X_1 x_2, y)) има; обаче, (y) не е функция само от (x_1), така че (= \! \! (x_1, y)) не се задържа.

При същата интерпретация правилата за литерали и съединения от първи ред (за простота ще приемем, че нашите изрази са в нормална форма на отрицание; и, както е обичайно, ще приемем, че отрицанията на атомите на зависимостта никога не са удовлетворени) са лесно да се получи:

TS-lit:

За всички литерали от първи ред (alpha), (X / модели / алфа), ако и само ако за всички задачи (s / в X), (s / модели / alpha) в обичайния смисъл на Тарски семантика;

TS - (land):

(X / модели / phi / земя / psi), ако и само ако (X / модели / phi) и (X / модели / psi).

Заслужава да се отбележи, че както вече можем да видим по тези правила, законът на изключената среда не се държи в логиката на зависимостта (точно както не се държи в логиката на приятелската независимост): например, ако екип (X) съдържа както задания (s) с (s (x) = s (y)), така и задания (s ') с (s' (x) not = s '(y)) след това (X / не / модели x = y) и (X / не / модели х / не = у). В този раздел, във всеки случай, ще представим езика на логиката на зависимостта без изричен оператор на отрицание; тогава по-късно ще обсъдим последствията от добавянето му към езика му.

Ами универсалното количествено определяне? При какви обстоятелства трябва да има универсално количествено изражение (forall v / psi) в екип? Отново трябва да си припомним интуицията, според която екип представлява набор от възможни състояния на нещата. Ако искаме да оценим (forall v / psi), по отношение на кои възможни състояния на нещата трябва да оценим (psi)? Естественият отговор е, че трябва да разгледаме всички състояния на нещата, които се различават от тези в (X) само по отношение на стойността на (v). Това обосновава следното правило:

TS - (forall):

(X / модели / forall v / psi), ако и само ако (X [M / v] модели / phi), където (X [M / v]) е множеството ({s ': / съществува s / в X / mbox {st} s' / sim_v x })

където (s '\ sim_v s) означава, че двете задачи (s) и (s') се различават най-много по отношение на стойността на променливата (v).

[X = / започнем {масив} {l | c} textbf {назначение} & x \\ / hline s_0 & 0 \\ s_1 & 1 / край {array} Rightarrow X [M / y] = / start {array} {l | в | c} textbf {присвояване} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 \\ s'_3 & 1 & 1 / край {масив})

Таблица 2: (X) и (X [M / y]) в модел с два елемента (0) и (1).

Нека сега помислим за дизъюнкция. Кога трябва да се задържи (phi / lor / psi)? За да отговорим на това, нека отново припомним, че отборите могат да бъдат разбрани като групи от възможни състояния на нещата и следователно обединението на два отбора (Y) и (Z) представлява всички състояния на нещата, които могат да възникват, ако случаят е (Y) или (Z). Следователно, ако двете формули (phi) и (psi) са удовлетворени от множеството от отбори ({Y_1 / ldots Y_n, / ldots }) и ({Z_1 / ldots Z_n, / ldots }), съответно тяхното разделяне (phi / lor / psi) трябва да бъде удовлетворено от множеството отбори ({Y_i / cup Z_j: i, j / in 1, / ldots }) или, еквивалентно,

TS - (lor):

(X / модели / phi / lor / psi), ако и само ако (X = Y / cup Z) за два отбора (Y) и (Z) такива, че (Y / модели / phi) и (Z / модели / psi).

Тук си струва да се отбележи, че по принцип не се изисква, че (Y) и (Z) са разединени. Поради свойството за затваряне надолу, за което ще обсъдим скоро, това допълнително условие няма да има значение за правилната семантика на логиката на зависимостта; но в случай на някои разширения и варианти на логиката на зависимостта, това допълнително изискване би противоречало на принципа за локалност, според който условията за удовлетвореност на един израз зависят само от стойностите на променливите, които се срещат в него (Galliani 2012).

Важно е също да се отбележи, че в логиката на зависимостта дизъюнкцията не е идпотентна: например, (eqord (x, y) lor / eqord (x, y)) не е еквивалентно на (eqord (x, y)) и той е удовлетворен от екип (X), ако и само ако за всеки три задания в (X), които се съгласяват (x), най-малко две са съгласни (y), Това може да изглежда донякъде контраинтуитивно; но е пряка последица от факта, че според нашето тълкуване (eqord (x, y) lor / eqord (x, y)) трябва да се чете като всяко възможно състояние на нещата идва от едно от две групи състояния на нещата и в двете двете (y) е функция на (x)”. Тъй като обединението на функции по принцип не е функция, изненадва се малко, че дизъюнцията в логиката на зависимостта не е безспорна.

И накрая, ние разглеждаме случая на екзистенциалното количествено определяне. Кога изразът (съществува v / psi) е удовлетворен от екип? За да отговорим на това, може да започнем с разглеждане на интерпретацията на ограничителния оператор, която, като се има предвид всеки отбор (X), води до отбора (X _ { обратна черта v}), получен чрез премахване на променливата (v) (ако има) от всички задачи (s / в X) (и след това, тъй като (X) е набор, като се свиват идентични задачи). Това може да се разбере като операция за забравяне, чрез която изтриваме цялата информация за стойността на (v) - например, защото това, което вярвахме за тази стойност, е ненадеждно или защото тази стойност е променена. Нека сега предположим, че (X _ { backslash v} = Y _ { backslash v}): тогава в нашата интерпретация,това означава, че множествата от възможни състояния на неща, представени от (X) и (Y), не са съгласни най-много по отношение на стойността на (v). Следователно, ако (Y) удовлетворява условието (phi), можем да кажем, че (X) би удовлетворил (phi), ако не за стойността на (y), или, еквивалентно, че (X) удовлетворява (съществува v / psi). Това обосновава следното правило:

TS - (съществува):

(X / модели / съществува v / psi), ако и само ако има някои (Y), над променливите на (X) и (v), такива, че (X _ { обратна черта v} = Y _ { обратна черта v}) и (Y / модели / psi).

Направо е да се потвърди, че това е така, ако и само ако (Y) е във формата (X [F / y] = {s [a / y]: s / в X, a / в F (s) }) за някаква функция (F) от задания в (X) до непразни набори от елементи от нашия модел.

Тук си струва да се отбележи, че обикновено не се изисква от горното определение, че (X) и (Y) съдържат един и същ брой задания: една задача в (X) може да съответства на множество заданията в (Y), и-ако (v) вече е променлива, възникваща в заданията на (X) - едно задание в (Y) може също да съответства на множество задания в (X).

[X = / започнем {масив} {l | c} textbf {назначение} & x \\ / hline s_0 & 0 \\ s_1 & 1 / край {array} Rightarrow X [F / y] = / start {array} {l | в | c} textbf {назначение} & x & y \\ / hline s'_0 & 0 & 0 \\ s'_1 & 0 & 1 \\ s'_2 & 1 & 0 / край {масив})

Таблица 3: (X) и (X [F / y]) за (F (s_0) = {0,1 }), (F (s_1) = {0 })

Ще отложим задълбочена дискусия за свойствата на логиката на зависимостта след уточняване на нейната игрово-теоретична семантика. Този раздел обаче завършваме със следните три важни последици от горепосочените правила:

Находище:

Ако ограниченията на (X) и (Y) за променливите, които се срещат свободно в (phi), са същите, тогава (X / модели / phi), ако и само ако (Y / модели / phi).

Затваряне надолу:

Ако (X / модели / phi) и (Y / подсеквент X), тогава (Y / модели / фи).

Свойство на празния набор:

Ако (emptyset) е екипът, който не съдържа задания, тогава (emptyset / models / phi) за всички логически формули на зависимост (phi).

Принципът за локалност, заедно с принципа на консервативност, споменат в началото на този раздел, представлява важно „здравословно условие“, на което всеки вариант и разширяване на логиката на зависимост трябва да отговаря. Същото не може да се каже за затварянето надолу и за празното зададено свойство, което - както ще видим - се нарушава от варианти на логиката на зависимост.

И накрая, ние трябва да определим истинността на логическото изречение на зависимост по отношение на модел. Тъй като изречението няма свободни променливи, по принципа на местоположението имаме веднага, че или всички непразни екипи го удовлетворяват, или никой непразен екип не го удовлетворява. Това е аналогично на семантиката на Тарски, в която едно изречение е удовлетворено или от всички задачи на променливи, или от нито едно от тях. По този начин можем да определим истината по обичайния начин:

Истина в семантиката на екипа:

Изречение (phi) е вярно в модел (M), ако и само ако (M, { празен набор } модели / phi), където ({ emptyset }) е екипът, съдържащ само празното задание. В този случай пишем, че (M / модели / phi).

2.1 Игрово-теоретична семантика

Както бе споменато, игрово-теоретичната семантика за логиката на зависимостта е вариант на несъвършената информационна семантика за благоприятна за независимостта логика, която сама по себе си е адаптация на игрово-теоретичната семантика на логиката от първи ред. Препращаме читателя към Väänänen 2007a за официално, подробно определение на тази семантика.

В теоретично-теоретичната семантика, изречение (phi) и модел (M) са направени, за да съответстват на (обикновено двама играчи) игра (G_M (phi)). Тогава истината се определя от гледна точка на съществуването на печеливши стратегии за един от играчите (който в тази работа ще бъде наречен просто „Играч (0)”): с други думи, ако (sigma_0) е a (вероятно недетерминирана) стратегия за Player (0) и (Pi (G_M (phi), / sigma_0)) е съвкупността от всички игра, които са съвместими с (sigma_0), тогава (phi) е вярно, ако и само ако всяка игра в (Pi (G_M (phi), / sigma_0)) печели за Играч (0). Възможно е да се мисли за играта (G_M (phi)) като дебат между двама играчи, единият от които (Играч (0)) желае да демонстрира, че случаят е, че (phi) докато другият (Играч (1)) желае да докаже, че не е така (phi).

Както в случая с логиката от първи ред и логиката на благото на независимостта, в несъвършената информационна игра за логиката на зависимостта позициите на играта са двойки ((theta, s)), където (theta) е екземпляр на подформула на (phi) (тоест множество събития от един и същ израз като подформула на (phi) трябва да се разглеждат отделно) и (s) е присвояване на променлива над модел (M). ^[1] Първоначалната позиция е ((phi, / празен набор)), където (празен набор) е празното задание; и недетерминирана стратегия (sigma_0) за Играч (0) избира за всяко разстройство и екзистенциално количествено определяне един или повече приемници на текущата позиция в съответствие със следните правила:

• Ако текущата позиция е във формата ((psi / lor / theta, s)), то нейните приемници са ((psi, s)) и ((theta, s));
• Ако текущата позиция е във формата ((съществува v / psi, s)), то нейните наследници са всички позиции ((psi, s ')) с (s' / sim_v s).

По същия начин наследниците на ((psi / land / theta, s)) са ((psi, s)) и ((theta, s)), и наследниците на ((forall v / psi, s)) са всички позиции на формата ((psi, s ')) за (s' / sim_v s); но стратегия за Играч (0) не може да посочи приемник за тези позиции, тъй като се приема, че Играч (1) избира коя позиция да ги следва.

Поредица от позиции (overline / rho = / rho_0 / rho_1 / ldots / rho_n) е игра на (G_M (phi)), ако и само ако

1. (rho_0 = (phi, / празен набор));
2. За всички (i = 1 / ldots n) (rho_ {i}) е наследник на (rho_ {i-1}).

Ако освен това (rho_ {i + 1} в / sigma_0 (rho_i)) винаги, когато (rho_i) съответства на дизъюнкция или екзистенциален количествен показател, казваме, че (overline / rho) спазва стратегия (sigma_0); и както споменахме, пишем (Pi (G_M (phi), / sigma_0)) за множеството от всички възпроизведения на (G_M (phi)), които зачитат (sigma_0).

Казваме, че стратегия (sigma_0) печели, ако всяка игра (overline / rho), която завършва в позиция ((alpha, s)), където (alpha) е първо- Буквалната поръчка е такава, че заданието (s) удовлетворява (alpha) в обичайния смисъл на семантиката на Тарски. Атомите на зависимостта - и играта, която завършва в атомите на зависимост - нямат значение за вземане на решение дали дадена стратегия печели. Те обаче се използват за определяне дали дадена стратегия е еднаква:

Условие за

униформа Стратегия (sigma_0) за (G_M (phi)) е равномерна, ако има две играи (overline / rho, / overline / gamma / in / Pi (G_M (phi), / sigma_0)) които завършват на две позиции ((eqord (x_1 / ldots x_n, y), s)), ((eqord (x_1 / ldots x_n, y), s ')) за същия екземпляр на атома на зависимост (eqord (x_1 / ldots x_n, y)) имаме това

) textrm {Ако} s (x_1) ldots s (x_n) = s '(x_1) ldots s' (x_n) textrm {тогава} s (y) = s '(y).)

Тогава можем да определим истината в игрово-теоретичната семантика, както следва:

Истината в игрово-теоретичната семантика:

Изречение (phi) е вярно в модел (M) (по отношение на теоретичната игра на семантиката), ако и само ако Играч (0) има еднаква печеливша стратегия в (G_M (Фи)).

Може да се покаже, че това понятие е еквивалентно на понятието истина в отборната семантика. Всъщност можем да покажем повече от това. Ако за всеки отбор (X) и формула (phi) играта (G_ {M, X} (phi)) се играе като (G_M (phi)), но с първоначална позиция, избрана на случаен принцип за всяка игра от ({(phi, s): s / в X }), след това се извършва следното:

Еквивалентност на GTS и отборната семантика:

Формула (phi) се удовлетворява от екип (X) (по отношение на модел (M)), ако и само ако Player (0) има униформа печеливша стратегия в (G_ {M, X} (phi)).

Този резултат като настрана прави ясно защо семантиката на екипа на логиката на зависимост удовлетворява свойството празно зададено и свойството за затваряне надолу. Всъщност, ако (X = / празен набор), тогава всяка стратегия за Играч (0) в (G_ {M, X} (phi)) е тривиално печеливша и еднаква; и ако (X / subseteq Y), то всяка еднаква печеливша стратегия за Играч (0) в (G_ {M, X} (phi)) също е еднаква печеливша стратегия за Играч (0) в (G_ {M, Y} (phi)).

3. Свойства

3.1 Експресивност

Логиката на зависимостта от изречението е еквивалентна на екзистенциалния фрагмент (Sigma_1 ^ 1) на логиката от втори ред. По-точно може да се докаже (Väänänen 2007a), че това

Изравнителна еквивалентност на логиката на зависимостта и (Sigma_1 ^ 1):

За всяко логическо изречение на зависимост (phi) съществува изречение (Sigma_1 ^ 1) (phi ^ *) такова, че

) етикет {6} етикет {eq: DLESO} M / models / phi / Leftrightarrow M / models / phi ^ * / textrm {за всички модели} M.)

По подобен начин за всяко изречение (Sigma_1 ^ 1) (phi ^ *) съществува логическо изречение на зависимост (phi) такова, че ((ref {eq: DLESO})) е в сила.

Тъй като теоремата на Фагин (Fagin 1974) показва, че свойството на крайните модели може да се дефинира в (Sigma_1 ^ 1), ако и само ако е разпознаваемо в полиномно време от недетерминирана машина на Тюринг (тоест, ако и само ако е в NPTIME), следва веднага това

Логика на зависимостта и NPTIME:

За всяко изречение за логика на зависимост (phi), класът на всички крайни модели, които я удовлетворяват, е в NPTIME. Освен това, за всеки клас NPTIME (mathcal K) на крайните модели съществува логическо изречение на зависимост (phi), така че (M / модели / phi), ако и само ако (M / в / математика К).

Друго пряко следствие от еквивалентността между логиката на зависимостта и (Sigma_1 ^ 1) на нивото на изреченията е, че теоремата за компактност и теоремата на Левенхайм-Сколем имат значение и за логиката на зависимостта (Väänänen 2007a):

Компактност:

Ако съвкупност (Phi) от логически изречения с ограничена зависимост не е удовлетворима при нито един модел, тогава някои крайни подмножества (Phi_0 / subseteq_f / Phi) от него вече не са изпълними.

Теорема на Льовенхайм-Сколем:

Ако логичното изречение за зависимост има безкраен модел, то то има модели на всички безкрайни кардиналности.

Въпросите обаче са по-деликатни, когато става дума за формули с безплатни променливи. Тогава е възможно да се покаже (Kontinen & Väänänen 2009), че логиката на зависимостта съответства на затворения надолу фрагмент от екзистенциалната логика от втори ред:

Определеност на отбора в зависимост от логиката

Набор (mathcal X) на отбори над модел (M) и набор (V) от променливи е във формата ({X: M, X / модели / phi }) за някаква логическа формула на зависимост (phi), с безплатни променливи в (V), ако и само ако

1. (mathcal X) не е празно;
2. (mathcal X) е затворена надолу, тоест (Y / subseteq X / в / mathcal X / Rightarrow Y / in / mathcal X);

3. (mathcal X) е (Sigma_1 ^ 1) - дефинируем в (M), тоест съществува изречение (Sigma_1 ^ 1) (Psi (R)), над речника на (M) плюс новия (| V |) - символ на връзката (R), така че

   [X / в / mathcal X / textrm {ако и само ако} M, / textrm {Rel} (X) модели / Psi (R))

   където (textrm {Rel} (X)) е отношението (| V |) - ар / {s (V): s / в X }), което съответства на екипа (X).

3.2 Йерархии в логиката на зависимостта

В Durand & Kontinen 2012 беше изследван ефектът от ограничаване на броя на зависимите променливи на атомите на зависимостта или броя на универсалните количествени характеристики. Показано е, че и двата начина за определяне на фрагменти от логиката на зависимост пораждат йерархии:

• За всички (k), нека (mathcal D (k- / forall)) е логика на зависимостта, ограничена до най-много (k) универсални квантори и нека (mathcal D (k-dep)) бъде логиката на зависимостта, ограничена до атоми на зависимост от формата (eqord (vec x, y)) за (| / vec x | / leq k). Тогава

  ) начало {подравняване *} 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 {align *})

  и

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

  по отношение на изразителната сила на изреченията.

3.3 Отрицание в логиката на зависимостта

Досега ние приехме, че всички логически изрази на зависимост са в нормална форма на отрицание и че атомите на зависимостта никога не се отричат. Добавянето на изричен оператор на отрицание към езика на логиката на зависимостта, от друга страна, е донякъде проблематично поради факта, че екзистенциалната логика от втори ред не е затворена под отрицание. Всъщност правилото за „очевидно“отрицание

[X / модели / sim / phi / textrm {ако и само ако} X / не / модели / phi)

значително увеличава изразителната сила на логиката на зависимостта, разширявайки я до логиката на екипа (Väänänen 2007a, b), която в много силен смисъл е еквивалентна на логиката на пълен втори ред (Kontinen & Nurmi 2009).

По-малко силно, "двойно" отрицание (lnot) може да се дефинира по отношение на правилата на де Морган, (lnot (phi / lor) land] psi) equiv (lnot / phi) land) lor] (lnot / psi)) и (lnot (съществува v) forall v] phi) equiv / forall v) съществува v] (lnot / phi)), плюс закон на двойно отрицание (lnot / lnot / phi / equiv / psi) и правилото

[X / модели { lnot / eqord} (vec x, y) textrm {ако и само ако} X = / празен набор)

за отрицания на атомите на зависимостта (Väänänen 2007a, b). Полученият език е експресивно еквивалентен на логиката на зависимостта без отрицание и всъщност описанието на логиката на зависимостта на Väänänen 2007a разглежда това отрицание като част от неговия език; обаче, както е показано в Kontinen & Väänänen 2011, условията за удовлетворяване на формулата на логиката на зависимостта и тези на нейното отрицание нямат малка връзка помежду си. По-точно:

Двойна логика на отрицание и зависимост:

За всякакви две логически формули на зависимост (phi) и (psi), така че (phi / земя / psi) не е удовлетворима, съществува формула на логика на зависимост (theta) такъв, че

[M, X / модели / theta / textrm {ако и само ако} M, X / модели / phi)

и

[M, X / модели / lnot / theta / textrm {ако и само ако} M, X / модели / psi)

за всички модели (M) и екипи (X).

По този начин, нищо общо не може да се каже за двойното отрицание на (phi), освен че е еквивалентно на някакъв логически израз на зависимост, който не е удовлетворен от никой екип, който удовлетворява (phi). Тъй като, както вече беше споменато, законът на изключената средна се проваля в логиката на зависимостта, това не е много информативно свойство; по-специално е възможно в логиката на зависимостта (с двойно отрицание) да се намерят еквивалентни изрази с нееквивалентни отрицания, като например (x / not = x / land y / not = y) и (lnot / eqord (х, у)).

3.4 Системи за истина, валидност и доказателство в логиката на зависимостта

Подобно на логиката за независимост, логиката на зависимостта може да определи своя оператор на истината (Väänänen 2007a), тоест ако за всички формули (phi) имаме, че (lceil / phi / rceil) е числото на Gödel от (phi) тогава можем да намерим формула (tau (x)), като (x) е единствената й свободна променлива, така че

[M / модели / phi / textrm {ако и само ако} M / models / tau (lceil / phi / rceil))

за всички модели (M), които отговарят на аксиомите на Peano за естествени числа. Това не е в противоречие с теоремата за неопределимост на Тарски, защото логиката на зависимостта не е затворена при противоречиво отрицание.

Проблемът с решението дали логичното изречение за зависимост е валидно (тоест е вярно във всички модели) е неаритметично и всъщност пълно с клас (Pi_2) на йерархията на Леви. Независимо от това, доказаната теория на логиката на зависимостта е изучена. По-специално, в Kontinen & Väänänen 2013 е разработена стабилна и пълна система за доказателство за проблема с намирането на последиците от първия ред на теорията на логиката на зависимостта.

4. Варианти на логиката на зависимостта

В този раздел ще обобщим накратко свойствата на най-изследваните варианти на логиката на зависимостта. Съществуват много такива варианти и е направена много работа по тяхното класифициране и сравнение. В тази работа ще споменем само онези варианти, които имат особено значение поради връзката им с правилната логика на зависимостта.

4.1 Логика на независимостта

Вместо да разширява логиката от първи ред с атоми на зависимост (eqord (vec x, y)), логиката за независимост (Grädel & Väänänen 2013) я разширява с атоми за независимост (vec x / mathop { bot _ { vec z }} vec y), чиято намерена интерпретация е "за всеки възможен избор на (vec z), възможните стойности (vec x) и (vec y) са независими" -в други думи, предвид всеки фиксиран избор на (vec z), знаейки стойността, взета от (vec x), няма да предаде информация за стойността, взета от (vec y). Това е понятие със значително концептуално значение: например, човек може да иска да изрази това - ако човек не познава ключа за криптиране - виждането на криптирана версия на съобщение не носи информация за съответната версия с ясен текст. Ако (x) представлява шифрованото съобщение и (y) представлява обикновения текст,тогава това съответства на условието (x / mathop { bot} y), където (vec z) в този случай е празно. По същия начин, ако (k) представлява ключа, тогава (x / mathop { bot} k) представлява твърдението, че ключът не може да бъде изведен от шифрованото съобщение; и атомът на конюнктната зависимост (eqord (k, x, y)) (който, както скоро ще видим, може да бъде представен в логиката за независимост) представлява твърдението, че обикновеното текстово съобщение може да бъде декодирано, като се има предвид криптираното съобщение и ключът.може да бъде представена в логиката за независимост) представлява твърдението, че обикновеното текстово съобщение може да бъде декодирано, като се има предвид криптираното съобщение и ключа.може да бъде представена в логиката за независимост) представлява твърдението, че обикновеното текстово съобщение може да бъде декодирано, като се има предвид криптираното съобщение и ключа.

Формално правилото за удовлетворяване на атомите за независимост може да бъде дадено по следния начин:

TS-indep:

(M / models_X / vec x / mathop { bot _ { vec z}} vec y), ако и само ако за всички (s, s '\ в X) с (s (vec z) = s '(vec z)) съществува (s' '\ в X) с (s' '(vec z \, / vec x) = s (vec {x }, / vec {z})) и (s '' (vec y) = s '(vec y)).

) започнем {масив} {l | ccc} textbf {назначение} & / 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 / край {масив})

Логиката на независимостта е строго по-изразителна от логиката на зависимостта: наистина, тя няма свойството за затваряне надолу и атомът на зависимост (eqord (vec x, y)) е еквивалентен на атома на независимостта (y / mathop { bot_ { vec x}} y). Освен това може също да се покаже (Galliani & Väänänen 2014), че атомите за независимост на обусловеността (vec x / mathop { bot _ { vec y}} vec z) могат да бъдат дефинирани по отношение на безусловната независимост на атомите (vec x / mathop { bot} vec y).

Логиката за независимост по отношение на изречението също е еквивалентна на екзистенциалната логика от втори ред (Sigma_1 ^ 1); но по отношение на формулата, тя е по-изразителна и беше показано в Galliani 2012, че може да заснеме всички непразни (Sigma_1 ^ 1) - определящи свойства на екипа.

4.2 Логика на включване

Логиката на включване (Galliani 2012, Galliani & Hella 2013) разширява логиката от първи ред с включване на атоми (vec x / subseteq / vec y), напомняща зависимостите за включване на теорията на базата данни. Неговата семантика е:

TS-inc:

(M / models_X / vec x / subseteq / vec y), ако и само ако за всички (s / в X) съществува (s '\ в X) такъв, че (s (vec x) = s '(vec y)).

) започнем {масив} {l | cc} textbf {назначение} & / mathbf {x_1} & / mathbf {x_2} / \ hline s_0 & 0 & 0 \\ s_1 & 0 & 1 \\ s_2 & 1 & 2 \\ s_3 & 2 & 3 / край {масив})

За разлика от логиката на зависимостта и независимостта, логиката на включване е (измислена от изреченията) строго по-слаба от екзистенциалната логика от втори ред. Всъщност може да се покаже (Galliani & Hella 2013), че е еквивалентен на положителния фрагмент от най-голямата логика с фиксирана точка, и следователно, за улавяне на PTIME свойствата на моделите върху крайно подредени модели. Логично включващата логика е строго по-слаба от логиката на независимостта, но несъпоставима с логиката на зависимостта: наистина условията за удовлетворяване на нейните формули не са затворени надолу, а са затворени от съюзи в смисъл, че

[M, X_i / модели / phi / forall i / в I / Rightarrow M, / bigcup_i X_i / модели / phi.)

4.3 Екип на логиката

Екипътната логика (Väänänen 2007a, b; Kontinen & Nurmi 2009) разширява логиката на зависимостта, като добавя към нея противоречиво отрицание (lnot). Той е равноекспресивен с пълна логика от втори ред, както по отношение на дефинируемостта на класовете от модели (Väänänen 2007b), така и по отношение на класовете от екипи, които логическите изрази на екипа могат да определят по отношение на даден модел (Kontinen & Nurmi 2009),

4.4 Интуиционистка логика на зависимостта

Интуиционистичната логика на зависимостта (Abramsky & Väänänen 2009; Yang 2013) разширява логиката на зависимостта, като добавя импликационен съединител (phi / rightarrow / psi), чиито правила за удовлетвореност са дадени в семантиката на екипа от

TS - (rightarrow):

(X / модели / phi / rightarrow / psi), ако и само ако за всички подмножества (Y) от (X), ако (Y / модели / phi) тогава (Y / модели / psi).

Този оператор е наречен „интуиционистичен импликация“поради сходството между неговата семантика и оператора на импликация в семантиката на интуиционистичната логика на Крипке (Kripke 1965). Интерпретацията му от гледна точка на вярата е доста проста: ако заданията в (X) представляват състояния на нещо, което някой агент счита за възможно, тогава подмножество (Y) от (X) може да представлява резултата от a актуализация на убежденията, в която агентът отхвърля някои по-рано вярвани възможни състояния на нещата и (phi / rightarrow / psi) състояния, отколкото всяка подобна актуализация, която би довела до задържане на (phi), също би довело до (psi) да задържа. От тази гледна точка това е съвсем естествено понятие, което ни позволява да опишем прогнозите за това как цялостното състояние на убеждение на такъв агент би реагирало на актуализациите на убежденията.

Въпреки това, поради универсалното количествено определяне от втори ред, имплицитно в неговата семантика, този съединител е достатъчен да увеличи значително изразителната сложност на логиката: по-специално, както е показано в Ян 2013, всяко изречение от втори ред логика е еквивалентно на някакво изречение на интуиционистична зависимост логика. Интуиционистичната логика на зависимост запазва свойството за затваряне надолу: ако екипът удовлетворява формулата на логиката на интуиционистичната зависимост, тогава правят това и всичките му подмножества.

4.5 Логика на предложената зависимост

Разгледаните дотук атоми на зависимост и независимост изразяват връзки между възможните стойности на променливи в набор от задания. Едни и същи представи за зависимост и независимост обаче могат да бъдат еднакво естествено да се приложат и към самото предложение, както се случва в естествения израз на езика, като например „Дали ще премине курса или не, зависи само от съдържанието на последния му изпит“, Логиката на предложената зависимост разглежда такива атоми в контекста на логиката на предложението. Логическите екипи на предложената зависимост са набори от оценки (v) от предложения атоми (p_1 / ldots p_n) до ({T, F }). Неговите семантични правила - и техните оправдания - отразяват много отблизо тези на семантиката на екипа от първи ред и правилото за атомите на зависимостта е

PTS-dep:

(X / models / eqord (p_1 / ldots p_n, q)), ако и само ако има две оценки (v_1, v_2 / в X), които са съгласни със стойностите на (p_1 / ldots p_n) също се съгласяват за стойността на (q).

Много от вариантите и обобщенията на логиката на зависимостта от първи ред могат да бъдат спуснати до предложеното ниво без никакви затруднения: по този начин, например, е възможно да се изучат свойствата на логиката на предложението за включване, логиката на предложенията на екипа, логиката на предложената интуиционистка зависимост и т.н., Докато логиката на зависимостта (първи ред) е строго по-изразителна от логиката от първи ред, логиката на предложената зависимост не е по-изразителна от предложената логика, тъй като това следва веднага от факта, че всички предложения на функции са изразителни в предложениевата логика. Съществува обаче тясна връзка между екипите на логиката на предложената зависимост и информационните състояния на любознателната логика (Groenendijk 2009; Ciardelli & Roelofsen 2011), семантична рамка за изследване на понятието смисъл и обмен на информация: по-специално, въздействието на любознателната логика е точно същото като на предложената интуиционистка логика на зависимостта.

Аксиоматизации за логиката на предложената зависимост и много от нейните разширения могат да бъдат намерени в Yang & Väänänen 2016.

4.6 Логика на модалната зависимост

Логиката на модалната зависимост (Väänänen 2008) и нейните варианти разширяват модалната логика, като добавят към нея същите атоми на зависимост (eqord (p_1 / ldots p_n, q)), които вече са разгледани в случай на логика на предложението за зависимост.

Условията му за удовлетвореност могат да бъдат определени чрез вариант на семантиката на екипа, в който отборите се заменят от набори от възможни светове.

Много изследвания изследват сложно-теоретичните свойства на тази логика, на нейните фрагменти и нейните разширения (Ebbing, Lohmann, & Yang 2011; Ebbing & Lohmann 2012; Lohmann & Vollmer 2013).

5. Приложения на логиката на зависимостта

5.1 Логика на зависимостта и теория на базата данни

Съществува пряка връзка между отборите от семантиката на екипа и отношенията, изучени в теорията на релационната база данни: като се даде екип (X) и набор от променливи (vec v = v_1 / ldots v_k), възникващи в неговите задачи, възможно е да се определи отношението (X (vec v) = { langle s (v_1), / ldots, s (v_n) rangle: s / в X }). Освен това атомите на зависимост, изучавани в логиката на зависимостта и нейните варианти, са аналогични на - и в много случаи, извлечени от - зависимости, разглеждани в теорията на базата данни като функционални зависимости (Väänänen 2007a), многозначни зависимости (Engström 2012) и зависимости за включване и изключване (Galliani 2012). Връзката между логиката на зависимостта и теорията на базата данни допринесе не само за по-нататъшното развитие на логиката на зависимостта, но и за теорията на базата данни: например,в Hannula & Kontinen 2016 беше открита ограничена аксиоматизация на проблема с неограничените импликации за включване, функционални и вградени многозначни теоретични зависимости от бази данни чрез изследване на подобен проблем в контекста на семантиката на екипа.

5.2 Логика на зависимостта и представяне на убеждения

Както беше обсъдено в Yang 2014 и Yang & Väänänen 2016, съществува тясна връзка между (предлагащата) интуиционистка логика на зависимостта и любознателната логика (Ciardelli & Roelofsen, 2011), рамка за изследване на значението и обмена на информация между агентите. По-общо, атомите на зависимостта и съединителите на изследваните в екипната семантика допускат естествени интерпретации по отношение на състоянията на вярата и актуализациите на убежденията, както беше обсъдено в Galliani 2015. По това време точното естество на връзката между такава логика и динамично-епистемичната логика и неговите варианти (Van Ditmarsch, van Der Hoek, & Kooi 2007) са до голяма степен неизследвани, но има достатъчно причини да се подозира по-нататъшни връзки между тези две области на математическата и философската логика.

5.3 Логика на зависимостта и теорема на Стрела

Теоремата на Arrow (Arrow 1950) е дълбоко влиятелен резултат от теорията за социалния избор, която накратко показва, че не съществува система за гласуване (тоест няма система за преобразуване на класиране на индивидуалните предпочитания между алтернативите в глобално класиране на предпочитания на обществено ниво). които могат да отговарят на три разумни звукови условия, а именно

• Ако всеки избирател предпочита (A) до (B), групата като цяло предпочита (A) и (B);
• Дали групата като цяло предпочита (A) до (B) или обратно, зависи изключително от предпочитанията на всеки избирател относно (A) и (B), а не от техните предпочитания по отношение на други възможни алтернативи;
• Нито един избирател не е диктатор, тоест предпочитанията на групата не се определят от предпочитанията на всеки един избирател.

Както подсказва самата формулировка, второто и третото условие допускат естествен прочит по отношение на зависимост и независимост: всъщност, както е показано в Pacuit & Yang 2016, теоремата на Arrow може да бъде формализирана в логиката на независимостта и да се докаже в подходяща естествена дедукционна система.

5.4 Квантова логика на екипа и неравенствата на Бел

В Hyttinen, Paolini и Väänänen 2015 се въвежда вариант на предложената отборна логика, наречен квантова екипна логика. В този формализъм екипите се заместват от квантови екипи, които се различават от обикновените екипи от логика на предложенията на екипа по това, че позволяват стойностите на определени променливи да бъдат неопределени по отношение на определени оценки и по това, че позволяват множество случаи на една и съща оценка (по този начин добавя количествен аспект към семантиката на екипа). След това се определя семантика над квантовите екипи за език, който позволява да се уточни неравенството по отношение на вероятностите от събития и за него е разработена стабилна и цялостна система за доказване; и накрая е показано, че неравенствата на Бел признават контрапримери в тази система,както правят според прогнозите на квантовата механика и според експерименталните доказателства (Айнщайн, Подолски и Росен 1935; Бел 1964; Аспект, Гранже и Роджър 1981), докато те не го правят в класическата версия на тази рамка.

библиография

• Абрамски, Самсон и Джоко Ваянен, 2009, „От IF до BI: Приказка за зависимостта и раздялата“, Synthese, 167 (2): 207–230. Дой: 10.1007 / s11229-008-9415-6
• Arrow, Kenneth J., 1950, „Трудност в концепцията за социално благополучие“, The Journal of Political Economy, pp.328–346. DOI: 10.1086 / 256963
• Аспект, Ален, Филип Гранже и Джерард Роджър, 1981, „Експериментални тестове на реалистични локални теории чрез теоремата на Бел“, Писма за физически преглед, 47 (7): 460–463. Дой: 10.1103 / PhysRevLett.47.460
• Bell, JS, 1964, „За парадокса на Айнщайн-Подолски-Розен“, Физика, 1 (3): 195–200.
• Ciardelli, Ivano и Floris Roelofsen, 2011, „Инквизитивна логика“, сп. „Философска логика“, 40 (1): 55–94. Дой: 10.1007 / s10992-010-9142-6
• van Ditmarsch, Hans, Wiebe van der Hoek и Barteld Kooi, 2007, Dynamic Epistemic Logic, (Synthese Library 337), Dordrecht: Springer. DOI: 10.1007 / 978-1-4020-5839-4
• Durand, Arnaud и Juha Kontinen, 2012, “Йерархии в логиката на зависимостта”, ACM транзакции по изчислителна логика (TOCL), 13 (4): 1–21. DOI: 10.1145 / 2,362,355.2362359
• Ebbing, Johannes и Peter Lohmann, 2012, „Сложност на проверката на модела за логика на модалната зависимост“, SOFSEM 2012: Международна конференция за актуалните тенденции в теорията и практиката на компютърните науки, (Бележки от лекции по компютърни науки, 7147), Берлин, Хайделберг: Спрингер, стр. 226-237. DOI: 10.1007 / 978-3-642-27660-6_19
• Ebbing, Johannes, Peter Lohmann и Fan Yang, 2013, „Проверка на модела за мода на интуиционистичната логика на зависимостта“, Международен симпозиум по логика, език и изчисления в Тбилиси 2011, (Бележки от лекции по компютърни науки, 7758), Берлин, Хайделберг: Springer, стр. 231–256. DOI: 10.1007 / 978-3-642-36976-6_15
• Айнщайн, А., Б. Подолски и Н. Росен, 1935, „Може ли квантово-механичното описание на физическата реалност да се счита за завършено?“Физически преглед, 47 (10): 777–780. Дой: 10.1103 / PhysRev.47.777
• Engström, Fredrik, 2012, „Обобщени квантори в логиката на зависимостта“, Journal of Logic, Language and Information, 21 (3): 299–324. Дой: 10.1007 / s10849-012-9162-4
• Фагин, Роналд, 1974, „Генерализирани спектри от първи ред и разпознаваеми полиномиални времена“, сложност на изчисленията (SIAM-AMS Proceedings 7), Ричард М. Карп (съст.), Провиденс, RI: Американско математическо дружество, стр. 27-41.
• Galliani, Pietro, 2012, „Зависимости на включване и изключване в семантиката на екипа - върху някои логики на несъвършена информация“, Анали на чистата и приложна логика, 163 (1): 68–84. Дой: 10.1016 / j.apal.2011.08.005
• –––, 2015, „Доксастичното тълкуване на отборната семантика“, Логика без граници: есета за теория на множествата, теория на модела, философска логика и философия на математиката (Ontos Mathematical Logic, 5), Åsa Hirvonen, Juha Kontinen, Roman Kossak, и Andrés Villaveces (eds), Берлин, Бостън: De Gruyter, стр. 167–192. DOI: 10.1515 / 9,781,614,516,873.167
• Galliani, Pietro and Lauri Hella, 2013, „Логика на включване и логика с фиксирана точка”, Computer Science Logic 2013 (Leibniz International Proceedings in Informatika (LIPIcs), 23), Dagstuhl, Германия: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 281-295. Дой: 10.4230 / LIPIcs. CSL.2013.281
• Галиани, Пиетро и Джоко Ваянен, 2014, „На логиката на зависимостта”, в Йохан ван Бентхем за логиката и динамиката на информацията (изключителни приноси към логиката, 5), Александру Балтаг и Соня Сметс (редактори), Cham: Springer, стр. 101– 119. DOI: 10.1007 / 978-3-319-06025-5_4
• Grädel, Erich и Jouko Väänänen, 2013, „Зависимост и независимост“, Studia Logica, 101 (2): 399–410. Дой: 10.1007 / s11225-013-9479-2
• Groenendijk, Jeroen, 2009 г., „Инквизитивна семантика: две възможности за разединение”, в Peter Bosch, David Gabelaia, & Jérôme Lang (eds), Седми международен симпозиум по език, логика и изчисления в Тбилиси (Бележки от лекции по компютърни науки: Том 5422), Springer-Verlag, с. 80–94. DOI: 10.1007 / 978-3-642-00665-4_8
• Ханула, Мийка и Юха Континен, 2016, „Крайна аксиоматизация на условната независимост и зависимостите за включване“. Информация и изчисления, 249: 121–137. Дой: 10.1016 / j.ic.2016.04.001
• Хенкин, Леон, 1961 г., „Някои забележки за безкрайно дълги формули“, в „Безкрайни методи“(Proceedings of the Symposium on the основи на математиката, Варшава, 1959 г.), Oxford: Pergamon Press, стр. 167–183.
• Hodges, Wilfrid, 1997, „Композиционна семантика за език на несъвършена информация“, Logic Journal of IGPL, 5 (4): 539–563. DOI: 10.1093 / jigpal / 5.4.539
• Hyttinen, Tapani, Gianluca Paolini и Jouko Väänänen, 2015, “Quantum Team Logic and Bell's Neaqalities”, Прегледът на символичната логика, 8 (4): 722–742. Дой: 10.1017 / S1755020315000192
• Kontinen, Juha и Ville Nurmi, 2009, „Екипна логика и логика от втори ред“, в сборника на 16-ия международен семинар по логика, език, информация и изчисления (Бележки от лекции по компютърни науки, 5514), Берлин, Хайделберг: Спрингер, стр. 230–241. DOI: 10.1007 / 978-3-642-02261-6_19
• Kontinen, Juha и Jouko Väänänen, 2009, „За дефинируемостта в логиката на зависимостта“, сп. „Логика, език и информация“, 18 (3): 317–332.doi: 10.1007 / s10849-009-9082-0
• –––, 2011 г., „Забележка за отрицанието в логиката на зависимостта“, сп. Notre Dame of Formal Logic, 52 (1): 55–65. DOI: 10.1215 / 00294527-2010-036
• –––, 2013, „Аксиоматизиране на последствията от първи ред в логиката на зависимостта”, Анали на чистата и приложна логика, 164 (11): 1101–1117. Дой: 10.1016 / j.apal.2013.05.006
• Kripke, Saul A., 1965, „Семантичен анализ на интуиционистичната логика I“, във формални системи и рекурсивни функции: Proceedings of the Восьми логически колоквиум, Оксфорд, юли 1963 (изследвания в областта на логиката и основите на математиката, 40), John N. Crossley и Michael AE Dummett (ред.), Северна Холандия, стр. 92–130. DOI: 10.1016 / S0049-237X (08) 71685-9
• Lohmann, Peter и Heribert Vollmer, 2013, „Резултати от сложността за логика на модалната зависимост“, Studia Logica, 101 (2): 343–366. Дой: 10.1007 / s11225-013-9483-6
• Пакуит, Ерик и Фен Ян, 2016, „Зависимостта и независимостта в социалния избор: Теоремата на стрелата“, в „Логика на зависимостта“, Самсон Абрамски, Юха Континен, Джоко Ваянен и Хериберт Волмер (редактори), Дордрехт: Спрингер, стр. 235-260, DOI: 10.1007 / 978-3-319-31803-5_11
• Väänänen, Jouko, 2007a, Логика на зависимостта: Нов подход към логиката за приятелска независимост, (Текстове на студентите в Лондонското математическо общество, 70), Кеймбридж: Cambridge University Press. Дой: 10.1017 / CBO9780511611193
• –––, 2007b, „Екипна логика“, в „Интерактивна логика“: Избрани доклади от седма работилница „Август де Морган“(Текстове в логиката и игрите, 1), Йохан ван Бентхем, Дов Габай и Бенедикт Льове (ред.), Амстердам: Amsterdam University Press, стр. 281–302.
• –––, 2008, „Логика на модната зависимост”, Нови перспективи за игри и взаимодействие (Текстове в логиката и игрите, 4), Krzysztof R. Apt и Robert van Rooij (eds), Амстердам: Amsterdam University Press, стр.237– 254.
• Yang, Fan, 2013, „Изразяване на присъди от втори ред в интуиционистичната логика на зависимостта“, Studia Logica, 101 (2): 323–342. Дой: 10.1007 / s11225-013-9476-5
• –––, 2014, „За разширенията и вариантите на логиката на зависимостта: изследване на интуиционистичните съединители в настройката на екипната семантика“. Докторска дисертация, Университет в Хелзинки.
• Yang, Fan и Jouko Väänänen, 2016, „Логика на предложената зависимост“, Анали на чистата и приложна логика, 167 (7): 557–589. Дой: 10.1016 / j.apal.2016.03.003

Академични инструменти

	Как да цитирам този запис.
	Вижте PDF версията на този запис в Дружеството на приятелите на SEP.
	Разгледайте тази тема за вписване в интернет философския онтологичен проект (InPhO).
	Подобрена библиография за този запис в PhilPapers, с връзки към неговата база данни.

Други интернет ресурси

• Логика на зависимостта от Wikipedia
• Презентации в академичната колоквиумна логика на зависимостта, Амстердам, 2014 г.