Abhängigkeitslogik

Inhaltsverzeichnis:

Abhängigkeitslogik
Abhängigkeitslogik
Anonim

Eintragsnavigation

  • Eintragsinhalt
  • Literaturverzeichnis
  • Akademische Werkzeuge
  • Freunde PDF Vorschau
  • Autor und Zitierinfo
  • Zurück nach oben

Abhängigkeitslogik

Erstveröffentlichung Do 23. Februar 2017

Die Abhängigkeitslogik ist eine Erweiterung der Logik erster Ordnung, die Abhängigkeitsatome hinzufügt, dh Ausdrücke der Form (eqord (x_1 / ldots x_n, y)), die behaupten, dass der Wert von (y) ist funktional abhängig von (mit anderen Worten bestimmt durch) den Werten von (x_1 / ldots x_n). Diese Atome ermöglichen die Spezifikation nichtlinear geordneter Abhängigkeitsmuster zwischen Variablen, ähnlich im Sinne von IF-Logic-Schrägstrichquantifizierern; Anders als bei der IF-Logik trennt die Abhängigkeitslogik die Quantifizierung von der Spezifikation solcher Abhängigkeits- / Unabhängigkeitsbedingungen. Die Hauptsemantik der Abhängigkeitslogik, die als Teamsemantik bezeichnet wird, verallgemeinert die Semantik von Tarski, indem Ausdrücke in Bezug auf Mengen variabler Zuweisungen und nicht in Bezug auf einzelne Zuweisungen erfüllt oder nicht erfüllt werden. Diese Semantik geht der Entwicklung der eigentlichen Abhängigkeitslogik voraus und wurde ursprünglich von Wilfrid Hodges im Kontext der IF-Logik entwickelt (Hodges 1997). Es gibt auch eine spieltheoretische Semantik für die Abhängigkeitslogik, die auf Spielen unvollständiger Information basiert und in etwa der spieltheoretischen Semantik für die unabhängigkeitsfreundliche Logik entspricht (Väänänen 2007a). Sensu stricto bezieht sich der Begriff "Abhängigkeitslogik" ausschließlich auf die Sprache, die durch Hinzufügen der oben genannten funktionalen Abhängigkeitsatome zur Sprache der Logik erster Ordnung erhalten wird; Der Begriff wird aber auch allgemeiner verwendet, um sich auf den Forschungsbereich zu beziehen, der die Eigenschaften von Logik untersucht, die durch Hinzufügen verschiedener Begriffe von Abhängigkeit und Unabhängigkeit zur Logik erster Ordnung wie der Unabhängigkeitslogik erhalten wird (Grädel & Väänänen 2013)),intuitionistische Abhängigkeitslogik (Yang 2013) oder Inklusionslogik (Galliani 2012, Galliani & Hella 2013) oder sogar solche der Logik, die andere logische Rahmen durch ähnliche Atome erweitern, wie im Fall der modalen Abhängigkeitslogik (Väänänen 2008). In diesem Artikel wird der Begriff "Abhängigkeitslogik" verwendet, um sich auf die eigentliche Abhängigkeitslogik zu beziehen, und der Begriff "Logik der Abhängigkeit und Unabhängigkeit" wird stattdessen verwendet, um sich auf seine Varianten und Verallgemeinerungen zu beziehen.und der Begriff "Logik der Abhängigkeit und Unabhängigkeit" wird stattdessen verwendet, um sich auf seine Varianten und Verallgemeinerungen zu beziehen.und der Begriff "Logik der Abhängigkeit und Unabhängigkeit" wird stattdessen verwendet, um sich auf seine Varianten und Verallgemeinerungen zu beziehen.

  • 1. Abhängigkeitsmuster in der Logik erster Ordnung und ihren Erweiterungen
  • 2. Teamsemantik

    2.1 Spieltheoretische Semantik

  • 3. Eigenschaften

    • 3.1 Ausdruckskraft
    • 3.2 Hierarchien in der Abhängigkeitslogik
    • 3.3 Negation in der Abhängigkeitslogik
    • 3.4 Wahrheits-, Gültigkeits- und Beweissysteme in der Abhängigkeitslogik
  • 4. Varianten der Abhängigkeitslogik

    • 4.1 Unabhängigkeitslogik
    • 4.2 Einschlusslogik
    • 4.3 Teamlogik
    • 4.4 Intuitionistische Abhängigkeitslogik
    • 4.5 Aussagenabhängigkeitslogik
    • 4.6 Modale Abhängigkeitslogik
  • 5. Anwendungen der Abhängigkeitslogik

    • 5.1 Abhängigkeitslogik und Datenbanktheorie
    • 5.2 Abhängigkeitslogik und Glaubensrepräsentation
    • 5.3 Abhängigkeitslogik und Satz von Arrow
    • 5.4 Quantenteamlogik und Bellsche Ungleichungen
  • Literaturverzeichnis
  • Akademische Werkzeuge
  • Andere Internetquellen
  • Verwandte Einträge

1. Abhängigkeitsmuster in der Logik erster Ordnung und ihren Erweiterungen

Ein Merkmal der Logik erster Ordnung, das einen Großteil ihrer Expressivität und Anwendbarkeit ausmacht, ist die Tatsache, dass Quantifizierer verschachtelt werden können und daher die Angabe von Abhängigkeitsmustern zwischen quantifizierten Variablen möglich ist. Betrachten Sie zum Beispiel die (hoffentlich falsche) Aussage, dass „jeder Junge ein Mädchen liebt, das einen anderen Jungen liebt“. Es kann einfach in die Logik erster Ordnung als übersetzt werden

) tag {1} label {eq: boygirl1} begin {align} & / forall x (boy (x) rightarrow / existiert y (girl (y) land / liebt (x, y) Land {} & / quad / existiert z (Junge (z) Land x / nicht = z / Land / liebt (y, z))) end {align})

deren Wahrheitsbedingung nach Tarskis üblicher Semantik genau das ist, was man erwarten würde: Der obige Ausdruck ist genau dann wahr, wenn es für jeden Jungen (b) möglich ist, ein Mädchen (g) und einen Jungen / zu finden (b ') so, dass (b) liebt (g) und (g) liebt (b') und (b) und (b ') sind nicht gleich. Die Identität des Mädchens (g) kann natürlich von der Identität des ersten Jungen (b) abhängen - damit dieser Ausdruck wahr ist, müssen nicht alle Jungen in alle Mädchen verliebt sein. und außerdem kann die Identität des zweiten Jungen (b ') sowohl von der Identität des ersten Jungen (b) abhängen (da (b') sich von (b) unterscheiden muss) und von der Identität des Mädchens (g), das (b) liebt. Das Abhängigkeitsmuster zwischen unseren quantifizierten Variablen ist also wie folgt: (y) hängt von (x) ab,während (z) sowohl von (x) als auch von (y) abhängt. Aus syntaktischer Sicht spiegelt sich dies in der Tatsache wider, dass (existiert y) im Bereich von (forall x) liegt, während (existiert z) im Bereich von beiden (forall x) liegt) und (existiert y).

Unterschiede in den Abhängigkeitsmustern zwischen Operatoren können verwendet werden, um wichtige Unterscheidungen zu formalisieren, wie zum Beispiel die zwischen der Kontinuität einer Funktion (f)

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

und seine einheitliche Kontinuität

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

oder in intensiven Erweiterungen der Logik erster Ordnung, um den Unterschied zwischen De Dicto- und De Re-Lesungen auszudrücken (z. B. "Es ist möglich, dass jede Person verrückt ist", kann entweder so verstanden werden, dass es für jede Person gilt (p)), es ist möglich, dass (p) verrückt ist, (forall x (person (x) rightarrow / Diamond / crazy (x))) oder dass es möglich ist, dass jeder verrückt ist zusammen (Diamond / forall x (person (x) rightarrow / crazy (x)))).

Abhängigkeitsmuster zwischen quantifizierten Variablen in der Logik erster Ordnung sind notwendigerweise transitiv, wie durch ihre Verbindungen mit den Bereichen der entsprechenden Unterausdrücke deutlich wird: Wenn (existiert y) im Bereich von (forall x) liegt) und (existiert z) liegt im Bereich von (existiert y), dann muss (existiert z) im Bereich von (und ist daher abhängig von) (forall x)). Darüber hinaus ist die Menge aller Quantifizierer, in deren Bereich einige Unterformeln (alpha) liegen, linear geordnet: Wenn (alpha) im Bereich von (Q_1 x_1) und (Q_2 x_2) liegt, dann entweder (Q_1 x_1) liegt im Bereich von (Q_2 x_2) oder umgekehrt.

Dies schränkt die Ausdrucksmöglichkeiten der Logik erster Ordnung ein. Nehmen wir zum Beispiel an, wir möchten unsere vorherige Behauptung über Jungen und Mädchen wie folgt ändern: Jeder Junge liebt ein Mädchen, das einen anderen Jungen liebt, und dieser zweite Junge kann unabhängig vom ersten ausgewählt werden. Was dies intuitiv bedeutet, ist einfach genug: Für jeden Jungen (b) können wir ein Mädchen (g) finden, so dass (b) liebt (g), und für jedes solche Mädchen können wir finde einen Jungen (b ') so, dass (g) (b') und (b / not = b ') liebt, und außerdem können wir die Identität des zweiten Jungen (b' finden).) ohne das von (b) zu kennen, allein aufgrund der Identität des Mädchens (g). Dies kann in einigen Szenarien immer noch der Fall sein, beispielsweise wenn zwei Jungen (b_1) und (b_2) jeweils zwei Mädchen (g_1) und (g_2) lieben.die jedoch nur (b_2) bzw. (b_1) lieben. Es ist jedoch leicht zu erkennen, dass es nicht unserer vorherigen Aussage entspricht: Zum Beispiel, wenn unser Universum (wie in (b) oben) aus zwei Jungen (b) und (b ') und einem Mädchen / besteht (g) und (b) und (b ') beide lieben (g), die beide lieben, dann ist unsere vorherige Behauptung wahr, aber die aktuelle ist falsch.

[Zwei ähnliche Figuren, beide Figuren haben die Wörter 'Jungen' und 'Mädchen', die oben durch einen horizontalen Raum getrennt sind. Abbildung (a) hat den Punkt b1 oben links, g1 oben rechts, b2 unten links und g2 unten rechts. Die Pfeile zeigen von g1 nach b1, von b1 nach g2, von g2 nach b2 und von b2 nach g1. Abbildung (b) hat b1 oben links, b2 unten links und g1 in der Mitte rechts. Ein Pfeil zeigt sowohl von und nach b1 und g1 als auch von b2 nach g1.]
[Zwei ähnliche Figuren, beide Figuren haben die Wörter 'Jungen' und 'Mädchen', die oben durch einen horizontalen Raum getrennt sind. Abbildung (a) hat den Punkt b1 oben links, g1 oben rechts, b2 unten links und g2 unten rechts. Die Pfeile zeigen von g1 nach b1, von b1 nach g2, von g2 nach b2 und von b2 nach g1. Abbildung (b) hat b1 oben links, b2 unten links und g1 in der Mitte rechts. Ein Pfeil zeigt sowohl von und nach b1 und g1 als auch von b2 nach g1.]

Zwei Szenarien, in denen ((ref {eq: boygirl1})) wahr ist. In (a) kann (z) unabhängig von (x) gewählt werden; in (b) kann es nicht.

Es ist jedoch nicht klar, wie diese Bedingung in der Logik erster Ordnung formalisiert werden soll. Im Wesentlichen müssten wir ((ref {eq: boygirl1})) so ändern, dass (z) nicht im Bereich von (x) liegt und daher nicht davon abhängt. Wir möchten jedoch weiterhin, dass (z) von (y) und (y) von (x) abhängt. Wie gerade diskutiert, ist ein solches Abhängigkeitsmuster jedoch in der Logik erster Ordnung nicht realisierbar. Wir können das Problem umgehen, indem wir auf eine Quantifizierung höherer Ordnung zurückgreifen: In der Tat kann man sehen, dass der Ausdruck

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

erfasst unsere beabsichtigte Interpretation, jedoch nur auf Kosten einer expliziten existenziellen Quantifizierung über Funktionen.

Eine mögliche Alternative wäre, die Syntax der Logik erster Ordnung zu erweitern, um die Einschränkungen bezüglich der Abhängigkeitsmuster zwischen quantifizierten Variablen aufzuheben. Dies ist der Weg der verzweigten Quantifiziererlogik (Henkin 1961), bei dem die Wahrheitsbedingungen von ((ref {boygirl2})) denen von entsprechen

) tag {3} label {boygirl3} begin {align} & / left (begin {smallmatrix} forall x & / existiert y \\ / forall z & / existiert w / end {smallmatrix} right) (Junge (x) rechter Pfeil (Mädchen (y) Land / liebt (x, y) Land {} & / Quad (y = z / rechter Pfeil (Junge (w) Land x / nicht =) w / land / liebt (z, w))))), / end {align})

und zu einer unabhängigkeitsfreundlichen Logik, in der ((ref {boygirl2})) äquivalent zu ist

) tag {4} label {boygirl4} begin {align} & / forall x / existiert y (boy (x) rightarrow (girl (y) land / liebt (x, y) land (existiert z / x) (boy (z) land {} & / quad x / not = z / land / liebt (y, z))). / end {align})

Wir werden hier keine detaillierte Erklärung der Semantik dieser beiden Formalismen geben; Es genügt zu sagen, dass in ((ref {boygirl3})) der Wert von (w) nicht von den Werten von (x) und (y) abhängt (obwohl er vom Wert abhängen kann von (z)), da sie zu verschiedenen "Zeilen" des komplexen Quantifizierers gehören (left (begin {smallmatrix} forall x & / existiert y \\ / forall z & / existiert w / end {smallmatrix) } right)), während in ((ref {boygirl4})) der Wert von (z) nicht vom Wert von (x) abhängt, da diese Abhängigkeit explizit "weggestrichen" wird. durch den Quantifizierer ((existiert z / x)).

Ein Merkmal, das der Verzweigungsquantifiziererlogik und der unabhängigheitsfreundlichen Logik gemeinsam ist, ist, wie wir sehen können, dass sie die Quantifizierung von Variablen nicht von der Spezifikation von nicht standardmäßigen Abhängigkeitsmustern trennen: wie im Fall der Logik erster Ordnung, ob eine quantifizierte Die Variable (v_1) hängt von einer anderen quantifizierten Variablen ab oder wird nicht von einer anderen quantifizierten Variablen (v_2) abhängen, die durch die jeweilige Position und Form ihrer Quantifizierer bestimmt wird.

Die Abhängigkeitslogik verfolgt einen anderen Ansatz für das Problem der Erweiterung der Logik erster Ordnung, um ((ref {boygirl2})) darzustellen. Im Vergleich zu ((ref {eq: boygirl1})) ist die einzige neuartige Bedingung diejenige, die besagt, dass der Wert von (z) durch den Wert von (dh funktional abhängig von) bestimmt wird (dh funktional abhängig von). y); und dies entspricht einer neuen atomaren Bedingung (eqord (y, z)), die als Abhängigkeitsatom bezeichnet wird und deren beabsichtigte Bedeutung darin besteht, dass (der Wert von) (z) eine Funktion des Werts von (y) ist). Anders als bei der Verzweigungsquantifiziererlogik oder der unabhängigheitsfreundlichen Logik ist dies eine Bedingung für die Werte, die (y) und (z) annehmen können, und keine Bedingung für das Verhalten des Quantifizierers (existiert z): In der Tat gibt es im Allgemeinen keinen Grund zu verlangen, dass (z) überhaupt eine quantifizierte Variable ist - es könnte auch eine freie Variable sein,oder ein komplexer Begriff mit mehreren Variablen.

In der Abhängigkeitslogik kann ((ref {boygirl2})) als formalisiert werden

) tag {5} label {boygirl5} begin {align} & / forall x / existiert y / existiert z (eqord (y, z) land (boy (x) rightarrow (girl (y))) Land / liebt (x, y) rechter Pfeil {} & / quad (Junge (z) Land x / nicht = z / Land / liebt (y, z)))) end {align})

Die Wahrheitsbedingungen von ((ref {boygirl2})), ((ref {boygirl3})), ((ref {boygirl4})) und ((ref {boygirl5})) sind genau gleich: Jedes Modell, das einen dieser Ausdrücke (in den jeweiligen Sprachen) erfüllt, erfüllt alle vier. Wie wir sehen werden, sind die Ausdruckskraft der existenziellen Logik zweiter Ordnung, der unabhängigheitsfreundlichen Logik und der Abhängigkeitslogik in Bezug auf die Definierbarkeit von Modellklassen im Allgemeinen genau gleich. Dies ist jedoch bei Formeln mit freien Variablen nicht der Fall; Darüber hinaus können diese Logiken in deutlich unterschiedlichen Richtungen erweitert und geändert werden.

2. Teamsemantik

Die von Wilfrid Hodges im Kontext der unabhängigkeitsfreundlichen Logik entwickelte Team-Semantik (Hodges 1997) ist eine Verallgemeinerung der Tarski-Semantik für Logik erster Ordnung auf den Fall der Mehrfachzuweisung von Elementen zu Variablen. Sätze solcher Aufgaben, die aus historischen Gründen als Teams bezeichnet werden, bilden den grundlegenden semantischen Begriff der Team-Semantik, und Formeln werden in Bezug auf sie und nicht in Bezug auf einzelne Aufgaben erfüllt oder nicht erfüllt. Der Zusammenhang zwischen Team-Semantik und Tarski-Semantik wird durch das folgende Ergebnis gezeigt, das sowohl in der Abhängigkeitslogik als auch in allen Varianten erster Ordnung gilt:

Konservativität:

Eine Formel erster Ordnung wird von einem Team (X) (im Sinne der Teamsemantik) genau dann erfüllt, wenn alle Zuordnungen (s / in X) sie erfüllen (im Sinne der Tarski-Semantik).

Im Allgemeinen können Teams als Glaubenssätze verstanden werden, die die Menge aller Zustände der Welt (= Aufgaben) darstellen, die ein Agent für möglich hält. Dann erfüllt ein Team (X) genau dann eine Formel (phi), wenn (phi) gilt, wenn (X) die Menge aller möglichen Zustände ist; und in diesem Fall schreiben wir (X / models / phi) (oder (M, X / models / phi), wenn die Wahl des Modells (M) nicht klar ist). In diesem Abschnitt werden wir die Regeln der Teamsemantik und ihre Interpretation im Hinblick auf dieses Prinzip untersuchen. Dann werden wir im nächsten Abschnitt diskutieren, wie es auch aus der spieltheoretischen Semantik unvollständiger Informationen für die Abhängigkeitslogik entsteht.

Die Bedingung für die neuen Abhängigkeitsatome (eqord (x_1 / ldots x_n, y)), die der Aussage entsprechen, dass der Wert von (y) eine Funktion der Werte von (x_1 / ldots x_n / ist)) ist leicht zu verstehen:

TS-dep:

(X / models ~ / eqord (x_1 / ldots x_n, y)) genau dann, wenn zwei Zuordnungen (s_1, s_2 / in X) vorliegen, die mit den Werten von (x_1 / ldots übereinstimmen) x_n) stimmen auch über den Wert von (y) überein.

Angenommen, (X) ist eine Reihe von Zuweisungen über die drei Variablen (x_1), (x_2) und (y), wobei (x_1) die Nationalität eines Kandidaten darstellt Eine Position, (x_2), repräsentiert ihre Punktzahl (gemäß einer geeigneten Bewertungsmethode) und (y) repräsentiert, ob sie akzeptiert oder abgelehnt wurden. Dann entspricht das Atom (eqord (x_2, y)) der Aussage, dass das Angebot allein durch die Punktzahl bestimmt wird: Wenn zwei Kandidaten die gleiche Punktzahl haben, erhalten sie unabhängig von einem anderen Faktor genau das gleiche Angebot. Ein Sonderfall eines Abhängigkeitsatoms sind die Konstanzatome (eqord (y)), die - gemäß der obigen Semantik - von einem Team nur dann erfüllt werden, wenn alle seine Zuordnungen über den Wert von (übereinstimmen y).

) begin {array} {l | ccc} textbf {Zuweisung} & / 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})

Tabelle 1: Ein Team (X), in dem (y = x_1 + x_2). Hier ist (y) eine Funktion von (x_1) und (x_2), und daher gilt (= \! \! (X_1 x_2, y)); (y) ist jedoch keine Funktion von (x_1) allein, daher gilt (= \! \! (x_1, y)) nicht.

Unter der gleichen Interpretation gelten die Regeln für Literale und Konjunktionen erster Ordnung (der Einfachheit halber nehmen wir an, dass unsere Ausdrücke in negativer Normalform vorliegen; und wie üblich wird angenommen, dass die Negationen von Abhängigkeitsatomen niemals erfüllt sind) leicht abzuleiten:

TS-lit:

Für alle Literale erster Ordnung (alpha), (X / models / alpha) genau dann, wenn für alle Zuweisungen (s / in X), (s / models / alpha)) im üblichen Sinne der Tarski-Semantik;

TS - (land):

(X / models / phi / land / psi) genau dann, wenn (X / models / phi) und (X / models / psi).

Es ist darauf hinzuweisen, dass, wie wir bereits anhand dieser Regeln sehen können, das Gesetz der ausgeschlossenen Mitte nicht in der Abhängigkeitslogik gilt (so wie es nicht in der unabhängigkeitsfreundlichen Logik gilt): Zum Beispiel, wenn ein Team (X.) enthält sowohl Zuweisungen (s) mit (s (x) = s (y)) als auch Zuweisungen (s ') mit (s' (x) not = s '(y)) dann (X / nicht / Modelle x = y) und (X / nicht / Modelle x / nicht = y). In diesem Abschnitt werden wir auf jeden Fall die Sprache der Abhängigkeitslogik ohne einen expliziten Negationsoperator vorstellen. dann, später, werden wir die Konsequenzen des Hinzufügens zu seiner Sprache diskutieren.

Was ist mit der universellen Quantifizierung? Unter welchen Umständen sollte ein universell quantifizierter Ausdruck (forall v / psi) in einem Team enthalten sein? Auch hier müssen wir uns an die Intuition erinnern, nach der ein Team eine Reihe möglicher Zustände darstellt. Wenn wir (forall v / psi) bewerten möchten, in Bezug auf welche möglichen Zustände sollten wir (psi) bewerten? Die natürliche Antwort ist, dass wir alle Zustände von Dingen, die sich von denen in (X) unterscheiden, nur in Bezug auf den Wert von (v) berücksichtigen sollten. Dies rechtfertigt die folgende Regel:

TS - (forall):

(X / models / forall v / psi) genau dann, wenn (X [M / v] models / phi), wobei (X [M / v]) ist die Menge ({s ': / existiert s / in X / mbox {st} s' / sim_v x })

wobei (s '\ sim_v s) bedeutet, dass sich die beiden Zuweisungen (s) und (s') höchstens in Bezug auf den Wert der Variablen (v) voneinander unterscheiden.

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

Tabelle 2: (X) und (X [M / y]) in einem Modell mit zwei Elementen (0) und (1).

Betrachten wir nun die Disjunktion. Wann sollte (phi / lor / psi) halten? Um dies zu beantworten, erinnern wir uns noch einmal daran, dass Teams als Mengen möglicher Zustände von Dingen verstanden werden können und dass daher die Vereinigung zweier Teams (Y) und (Z) alle Zustände von Dingen darstellt, die möglich sind treten auf, wenn (Y) oder (Z) der Fall ist. Wenn daher die beiden Formeln (phi) und (psi) durch die Gruppe von Teams ({Y_1 / ldots Y_n, / ldots }) und ({Z_1 / ldots Z_n) erfüllt sind, / ldots }) sollte ihre Disjunktion (phi / lor / psi) durch die Gruppe von Teams ({Y_i / cup Z_j: i, j / in 1, / ldots } erfüllt werden)), oder gleichwertig,

TS - (lor):

(X / models / phi / lor / psi) genau dann, wenn (X = Y / cup Z) für zwei Teams (Y) und (Z) so dass (Y / models / phi) und (Z / models / psi).

An dieser Stelle sei darauf hingewiesen, dass wir im Allgemeinen nicht verlangen, dass (Y) und (Z) disjunkt sind. Aufgrund der Abwärtsschließungseigenschaft, die wir bald diskutieren werden, würde diese zusätzliche Bedingung keinen Unterschied für die Semantik der eigentlichen Abhängigkeitslogik machen; Bei bestimmten Erweiterungen und Varianten der Abhängigkeitslogik würde diese zusätzliche Anforderung jedoch dem Lokalitätsprinzip widersprechen, nach dem die Zufriedenheitsbedingungen eines Ausdrucks nur von den Werten der darin vorkommenden Variablen abhängen (Galliani 2012).

Es ist auch wichtig zu beachten, dass in der Abhängigkeitslogik die Disjunktion nicht idempotent ist: Zum Beispiel ist (eqord (x, y) lor / eqord (x, y)) nicht äquivalent zu (eqord (x), y)), und es wird von einem Team (X) genau dann erfüllt, wenn für jeweils drei Aufgaben in (X), die sich auf (x) einigen, mindestens zwei sich auf (y) einigen.. Dies mag etwas kontraintuitiv erscheinen; aber es ist eine einfache Konsequenz der Tatsache, dass nach unserer Interpretation (eqord (x, y) lor / eqord (x, y)) zu lesen ist als „jeder mögliche Zustand der Dinge kommt von einem von zwei Sätze von Zuständen von Dingen, und in beiden ist (y) eine Funktion von (x)”. Da die Vereinigung von Funktionen im Allgemeinen keine Funktion ist, ist es nicht verwunderlich, dass eine Disjunktion in der Abhängigkeitslogik nicht entschädigend ist.

Schließlich betrachten wir den Fall der existenziellen Quantifizierung. Wann wird der Ausdruck (existiert v / psi) von einem Team erfüllt? Um dies zu beantworten, können wir zunächst die Interpretation des Restriktionsoperators betrachten, die bei jedem Team (X) zu dem Team (X _ { backslash v}) führt, das durch Entfernen der Variablen (v) erhalten wird) (falls vorhanden) aus allen Zuweisungen (s / in X) (und dann, da (X) eine Menge ist, durch Reduzieren identischer Zuweisungen). Dies könnte als eine Vergessensoperation verstanden werden, durch die wir alle Informationen über den Wert von (v) löschen - zum Beispiel, weil das, was wir über diesen Wert glaubten, unzuverlässig war oder weil dieser Wert geändert wurde. Nehmen wir nun an, dass (X _ { backslash v} = Y _ { backslash v}): dann, in unserer Interpretation,Dies bedeutet, dass die Mengen möglicher Zustände von Dingen, die durch (X) und (Y) dargestellt werden, in Bezug auf den Wert von (v) höchstens nicht übereinstimmen. Wenn also (Y) die Bedingung (phi) erfüllt, können wir sagen, dass (X) (phi) erfüllen würde, wenn nicht für den Wert von (y) oder äquivalent, dass (X) erfüllt (existiert v / psi). Dies rechtfertigt die folgende Regel:

TS - (existiert):

(X / Modelle / existiert v / psi) genau dann, wenn es einige (Y) über den Variablen (X) und (v) gibt, so dass (X _ { Backslash v} = Y _ { Backslash v}) und (Y / models / psi).

Es ist einfach zu überprüfen, ob dies genau dann der Fall ist, wenn (Y) die Form (X [F / y] = {s [a / y] hat: s / in X, a / in F. (s) }) für einige Funktionen (F) von Zuweisungen in (X) zu nicht leeren Mengen von Elementen unseres Modells.

An dieser Stelle sei darauf hingewiesen, dass es nach der obigen Definition im Allgemeinen nicht erforderlich ist, dass (X) und (Y) die gleiche Anzahl von Zuweisungen enthalten: Eine einzelne Zuweisung in (X) kann durchaus mehreren entsprechen Zuweisungen in (Y) und - wenn (v) bereits eine Variable ist, die in den Zuweisungen von (X) vorkommt - eine einzelne Zuweisung in (Y) kann auch mehreren Zuweisungen in (X entsprechen).

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

Tabelle 3: (X) und (X [F / y]) für (F (s_0) = {0,1 }), (F (s_1) = {0 })

Wir werden eine eingehende Diskussion der Eigenschaften der Abhängigkeitslogik nach der Spezifikation ihrer spieltheoretischen Semantik verschieben. Wir schließen diesen Abschnitt jedoch mit den folgenden drei wichtigen Konsequenzen der oben angegebenen Regeln ab:

Lokalität:

Wenn die Einschränkungen von (X) und (Y) für die in (phi) frei vorkommenden Variablen gleich sind, dann (X / models / phi) genau dann, wenn (Y / Modelle / phi).

Schließen nach unten:

Wenn (X / models / phi) und (Y / subseteq X), dann (Y / models / phi).

Leere Set-Eigenschaft:

Wenn (Emptyset) das Team ist, das keine Zuweisungen enthält, dann (Emptyset / Models / Phi) für alle Abhängigkeitslogikformeln (Phi).

Das Lokalitätsprinzip bildet zusammen mit dem zu Beginn dieses Abschnitts erwähnten Konservativitätsprinzip eine wichtige „Vernunftbedingung“, die jede Variante und Erweiterung der Abhängigkeitslogik erfüllen sollte. Das Gleiche gilt nicht für die Schließung nach unten und die Eigenschaft der leeren Menge, die - wie wir sehen werden - durch Varianten der Abhängigkeitslogik verletzt werden.

Schließlich müssen wir die Wahrheit eines Abhängigkeitslogiksatzes in Bezug auf ein Modell definieren. Da ein Satz keine freien Variablen hat, haben wir nach dem Lokalitätsprinzip sofort, dass entweder alle nicht leeren Teams ihn erfüllen oder kein nicht leeres Team ihn erfüllt. Dies ist analog zu Tarskis Semantik, bei der ein Satz entweder von allen Variablenzuweisungen oder von keiner von ihnen erfüllt wird. So können wir die Wahrheit auf die übliche Weise definieren:

Wahrheit in der Teamsemantik:

Ein Satz (phi) ist in einem Modell (M) genau dann wahr, wenn (M, { Emptyset } Modelle / phi), wobei ({ Emptyset }) ist das Team, das nur die leere Zuordnung enthält. In diesem Fall schreiben wir das (M / models / phi).

2.1 Spieltheoretische Semantik

Wie bereits erwähnt, ist die spieltheoretische Semantik für die Abhängigkeitslogik eine Variante der Semantik unvollständiger Informationen für die unabhängigkeitsfreundliche Logik, die selbst eine Anpassung der spieltheoretischen Semantik der Logik erster Ordnung darstellt. Wir verweisen den Leser auf Väänänen 2007a für eine formale, detaillierte Definition dieser Semantik.

In der spieltheoretischen Semantik werden ein Satz (phi) und ein Modell (M) so erstellt, dass sie einem Spiel (normalerweise für zwei Spieler) (G_M (phi)) entsprechen. Dann wird die Wahrheit in Bezug auf die Existenz von Gewinnstrategien für einen der Spieler definiert (der in dieser Arbeit einfach als "Spieler (0)" bezeichnet wird): mit anderen Worten, wenn (sigma_0) ist Eine (möglicherweise nicht deterministische) Strategie für Spieler (0) und (Pi (G_M (phi), / sigma_0)) ist die Menge aller Spiele, die mit (sigma_0) dann / kompatibel sind (phi) ist genau dann wahr, wenn jedes Spiel in (Pi (G_M (phi), / sigma_0)) für Player (0) gewinnt. Man kann sich das Spiel (G_M (phi)) als eine Debatte zwischen zwei Spielern vorstellen, von denen einer (Spieler (0)) zeigen möchte, dass es der Fall ist, dass (phi) während der andere (Spieler (1)) zeigen möchte, dass es nicht der Fall ist, dass (phi).

Wie im Fall der Logik erster Ordnung und der unabhängigkeitsfreundlichen Logik sind im Spiel mit unvollkommenen Informationen für die Abhängigkeitslogik die Positionen des Spiels Paare ((theta, s)), wobei (theta) ist Eine Instanz einer Unterformel von (phi) (dh mehrere Vorkommen desselben Ausdrucks wie eine Unterformel von (phi) sind separat zu betrachten) und (s) ist eine variable Zuordnung über die Modell (M). [1] Die Anfangsposition ist ((phi, / Emptyset)), wobei (Emptyset) die leere Zuordnung ist; und eine nicht deterministische Strategie (sigma_0) für Spieler (0) wählt für jede Disjunktion und existenzielle Quantifizierung einen oder mehrere Nachfolger der aktuellen Position gemäß den folgenden Regeln aus:

  • Wenn die aktuelle Position die Form ((psi / lor / theta, s)) hat, sind ihre Nachfolger ((psi, s)) und ((theta, s));
  • Wenn die aktuelle Position die Form ((existiert v / psi, s)) hat, sind ihre Nachfolger alle Positionen ((psi, s ')) mit (s' / sim_v s).

In ähnlicher Weise sind die Nachfolger von ((psi / land / theta, s)) ((psi, s)) und ((theta, s)) und die Nachfolger von (() forall v / psi, s)) sind alle Positionen der Form ((psi, s ')) für (s' / sim_v s); Eine Strategie für Spieler (0) kann jedoch keinen Nachfolger für diese Positionen angeben, da davon ausgegangen wird, dass Spieler (1) wählt, welche Position ihnen folgt.

Eine Folge von Positionen (overline / rho = / rho_0 / rho_1 / ldots / rho_n) ist genau dann ein Spiel von (G_M (phi))

  1. (rho_0 = (phi, / Emptyset));
  2. Für alle (i = 1 / ldots n) ist (rho_ {i}) ein Nachfolger von (rho_ {i-1}).

Wenn außerdem (rho_ {i + 1} in / sigma_0 (rho_i)) immer dann, wenn (rho_i) einer Disjunktion oder einem existenziellen Quantifizierer entspricht, sagen wir, dass (overline / rho) das respektiert Strategie (sigma_0); und wie erwähnt schreiben wir (Pi (G_M (phi), / sigma_0)) für die Menge aller Spiele über (G_M (phi)), die (sigma_0) respektieren.

Wir sagen, dass eine Strategie (sigma_0) gewinnt, wenn jedes Spiel (overline / rho), das an einer Position ((alpha, s)) endet, an der (alpha) eine erste ist. Das Ordnungsliteral ist so, dass die Zuweisung (s) (alpha) im üblichen Sinne der Tarski-Semantik erfüllt. Abhängigkeitsatome - und die Spiele, die in Abhängigkeitsatomen enden - sind für die Entscheidung, ob eine bestimmte Strategie gewinnt, nicht relevant. Sie werden jedoch verwendet, um anzugeben, ob eine bestimmte Strategie einheitlich ist:

Homogenitätsbedingung

Eine Strategie (sigma_0) für (G_M (phi)) ist einheitlich, wenn zwei beliebige Spiele (overline / rho, / overline / gamma / in / Pi (G_M (phi), / sigma_0) gespielt werden)) die an zwei Positionen ((eqord (x_1 / ldots x_n, y), s)), ((eqord (x_1 / ldots x_n, y), s ')) für dieselbe Instanz enden vom Abhängigkeitsatom (eqord (x_1 / ldots x_n, y)) haben wir das

) textrm {Wenn} s (x_1) ldots s (x_n) = s '(x_1) ldots s' (x_n) textrm {dann} s (y) = s '(y).)

Dann können wir die Wahrheit in der spieltheoretischen Semantik wie folgt definieren:

Wahrheit in der spieltheoretischen Semantik:

Ein Satz (phi) ist in einem Modell (M) (in Bezug auf die spieltheoretische Semantik) genau dann wahr, wenn Spieler (0) eine einheitliche Gewinnstrategie hat (G_M (phi)).

Es kann gezeigt werden, dass dieser Begriff dem Begriff der Wahrheit in der Teamsemantik entspricht. In der Tat können wir mehr als das zeigen. Wenn für ein Team (X) und eine Formel (phi) das Spiel (G_ {M, X} (phi)) als (G_M (phi)) gespielt wird, jedoch mit dem Die Ausgangsposition wird zufällig für jedes Spiel aus ({(phi, s): s / in X }) ausgewählt. Dann gilt Folgendes:

Äquivalenz von GTS und Teamsemantik:

Eine Formel (phi) wird von einem Team (X) (in Bezug auf ein Modell (M)) genau dann erfüllt, wenn Spieler (0) eine Uniform hat Gewinnstrategie in (G_ {M, X} (phi)).

Abgesehen davon macht dieses Ergebnis deutlich, warum die Team-Semantik der Abhängigkeitslogik die Eigenschaft der leeren Menge und die Eigenschaft der Schließung nach unten erfüllt. In der Tat, wenn (X = / Emptyset), dann ist jede Strategie für Spieler (0) in (G_ {M, X} (phi)) trivial gewinnend und einheitlich; und wenn (X / subseteq Y), dann ist jede einheitliche Gewinnstrategie für Spieler (0) in (G_ {M, X} (phi)) auch eine einheitliche Gewinnstrategie für Spieler (0) in (G_ {M, Y} (phi)).

3. Eigenschaften

3.1 Ausdruckskraft

Satzmäßig entspricht die Abhängigkeitslogik dem existenziellen Fragment (Sigma_1 ^ 1) der Logik zweiter Ordnung. Genauer gesagt kann nachgewiesen werden (Väänänen 2007a), dass

Satzweise Äquivalenz von Abhängigkeitslogik und (Sigma_1 ^ 1):

Für jeden Abhängigkeitslogiksatz (phi) existiert ein (Sigma_1 ^ 1) Satz (phi ^ *), so dass

) tag {6} label {eq: DLESO} M / models / phi / Leftrightarrow M / models / phi ^ * / textrm {für alle Modelle} M.)

In ähnlicher Weise existiert für jeden (Sigma_1 ^ 1) Satz (phi ^ *) ein Abhängigkeitslogiksatz (phi), so dass ((ref {eq: DLESO})) gilt.

Da Fagins Theorem (Fagin 1974) zeigt, dass eine Eigenschaft endlicher Modelle in (Sigma_1 ^ 1) genau dann definierbar ist, wenn sie in polynomialer Zeit von einer nichtdeterministischen Turing-Maschine erkannt werden kann (dh genau dann, wenn dies der Fall ist) in NPTIME) folgt sofort das

Abhängigkeitslogik und NPTIME:

Für jeden Abhängigkeitslogiksatz (phi) ist die Klasse aller endlichen Modelle, die ihn erfüllen, in NPTIME. Darüber hinaus existiert für jede NPTIME-Klasse (mathcal K) endlicher Modelle ein Abhängigkeitslogiksatz (phi), so dass (M / models / phi) genau dann, wenn (M / in) mathcal K).

Eine weitere direkte Folge der Äquivalenz zwischen Abhängigkeitslogik und (Sigma_1 ^ 1) auf der Ebene der Sätze ist, dass sowohl der Kompaktheitssatz als auch der Löwenheim-Skolem-Satz auch für die Abhängigkeitslogik gelten (Väänänen 2007a):

Kompaktheit:

Wenn eine Menge (Phi) von Logiksätzen mit endlicher Abhängigkeit in keinem Modell erfüllt werden kann, ist eine endliche Teilmenge (Phi_0 / subseteq_f / Phi) davon bereits nicht erfüllt.

Löwenheim-Skolem-Theorem:

Wenn ein Satz der Abhängigkeitslogik ein unendliches Modell hat, dann hat er Modelle aller unendlichen Kardinalitäten.

Bei Formeln mit freien Variablen sind die Dinge jedoch heikler. Dann kann gezeigt werden (Kontinen & Väänänen 2009), dass die Abhängigkeitslogik dem nach unten geschlossenen Fragment der existenziellen Logik zweiter Ordnung entspricht:

Teamdefinierbarkeit in der Abhängigkeitslogik

Eine Menge (mathcal X) von Teams über ein Modell (M) und eine Menge (V) von Variablen hat die Form ({X: M, X / models) phi }) für eine Abhängigkeitslogikformel (phi) mit freien Variablen in (V), genau dann, wenn

  1. (mathcal X) ist nicht leer;
  2. (mathcal X) ist nach unten geschlossen, dh (Y / subseteq X / in / mathcal X / Rightarrow Y / in / mathcal X);
  3. (mathcal X) ist (Sigma_1 ^ 1) - definierbar in (M), dh es existiert ein (Sigma_1 ^ 1) Satz (Psi (R)), über das Vokabular von (M) plus das neue (| V |) - Beziehungssymbol (R), so dass

    [X / in / mathcal X / textrm {genau dann, wenn} M, / textrm {Rel} (X) models / Psi (R))

    Dabei ist (textrm {Rel} (X)) die (| V |) - Beziehung ({s (V): s / in X }), die dem Team (X entspricht).

3.2 Hierarchien in der Abhängigkeitslogik

In Durand & Kontinen 2012 wurde der Effekt der Beschränkung der Anzahl abhängiger Variablen von Abhängigkeitsatomen oder der Anzahl universeller Quantifizierer untersucht. Es wurde gezeigt, dass beide Arten der Definition von Fragmenten der Abhängigkeitslogik zu Hierarchien führen:

  • Für alle (k) sei (mathcal D (k- / forall)) eine Abhängigkeitslogik, die auf höchstens (k) universelle Quantifizierer beschränkt ist, und sei (mathcal D (k-dep)) eine Abhängigkeitslogik sein, die auf Abhängigkeitsatome der Form (eqord (vec x, y)) für (| / vec x | / leq k) beschränkt ist. Dann

    ) 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 {align *})

    und

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

    in Bezug auf die Ausdruckskraft von Sätzen.

3.3 Negation in der Abhängigkeitslogik

Bisher haben wir angenommen, dass alle Ausdrücke der Abhängigkeitslogik in negativer Normalform vorliegen und dass Abhängigkeitsatome niemals negiert werden. Das Hinzufügen eines expliziten Negationsoperators zur Sprache der Abhängigkeitslogik ist andererseits etwas problematisch, da die existenzielle Logik zweiter Ordnung nicht unter Negation geschlossen wird. In der Tat die "offensichtliche" Negationsregel

[X / models / sim / phi / textrm {genau dann, wenn} X / not / models / phi)

erhöht die Ausdruckskraft der Abhängigkeitslogik erheblich und erweitert sie auf die Teamlogik (Väänänen 2007a, b), die in einem sehr starken Sinne der vollständigen Logik zweiter Ordnung entspricht (Kontinen & Nurmi 2009).

Eine weniger starke, "doppelte" Negation (lnot) kann in Bezug auf die Regeln von de Morgan definiert werden: (lnot (phi / lor) land] psi) equiv (lnot / phi) land) lor] (lnot / psi)) und (lnot (existiert v) forall v] phi) equiv / forall v) existiert v] (lnot / phi)) plus die Gesetz der doppelten Verneinung (lnot / lnot / phi / equiv / psi) und die Regel

[X / models { lnot / eqord} (vec x, y) textrm {genau dann, wenn} X = / Emptyset)

für Negationen von Abhängigkeitsatomen (Väänänen 2007a, b). Die resultierende Sprache entspricht ausdrücklich der negationsfreien Abhängigkeitslogik, und tatsächlich betrachtet die Beschreibung der Abhängigkeitslogik von Väänänen 2007a diese Negation als Teil ihrer Sprache; Wie in Kontinen & Väänänen 2011 gezeigt, haben die Zufriedenheitsbedingungen einer Abhängigkeitslogikformel und die ihrer Negation jedoch wenig miteinander zu tun. Etwas präziser:

Doppelte Negations- und Abhängigkeitslogik:

Für zwei beliebige Abhängigkeitslogikformeln (phi) und (psi), so dass (phi / land / psi) nicht erfüllt werden kann, gibt es eine Abhängigkeitslogikformel (Theta) so dass

[M, X / models / theta / textrm {genau dann, wenn} M, X / models / phi)

und

[M, X / models / lnot / theta / textrm {genau dann, wenn} M, X / models / psi)

für alle Modelle (M) und Teams (X).

Daher kann im Allgemeinen nichts über die doppelte Negation von (phi) gesagt werden, außer dass sie einem abhängigen logischen Ausdruck entspricht, der von keinem Team erfüllt wird, das (phi) erfüllt. Da, wie bereits erwähnt, das Gesetz der ausgeschlossenen Mitte in der Abhängigkeitslogik versagt, ist dies keine sehr informative Eigenschaft; Insbesondere ist es möglich, in Abhängigkeitslogik (mit doppelter Negation) äquivalente Ausdrücke mit nicht äquivalenten Negationen zu finden, wie zum Beispiel (x / not = x / land y / not = y) und (lnot / eqord) (x, y)).

3.4 Wahrheits-, Gültigkeits- und Beweissysteme in der Abhängigkeitslogik

Wie die unabhängigkeitsfreundliche Logik kann die Abhängigkeitslogik ihren eigenen Wahrheitsoperator definieren (Väänänen 2007a), dh wenn wir für alle Formeln (phi) haben, dass (lceil / phi / rceil) die Gödel-Zahl von / ist (phi) dann können wir eine Formel (tau (x)) finden, mit (x) als einziger freier Variable, so dass

[M / models / phi / textrm {genau dann, wenn} M / models / tau (lceil / phi / rceil))

für alle Modelle (M), die Peanos Axiome für natürliche Zahlen erfüllen. Dies steht nicht im Widerspruch zu Tarskis Undefinierbarkeitssatz, da die Abhängigkeitslogik nicht unter widersprüchlicher Negation geschlossen wird.

Das Problem der Entscheidung, ob ein Abhängigkeitslogiksatz gültig ist (dh in allen Modellen wahr ist), ist nicht arithmetisch und in Bezug auf die Klasse (Pi_2) der Levy-Hierarchie tatsächlich vollständig. Dennoch wurde die Beweistheorie der Abhängigkeitslogik untersucht. Insbesondere in Kontinen & Väänänen 2013 wurde ein solides und vollständiges Beweissystem für das Problem entwickelt, die Konsequenzen einer Abhängigkeitslogiktheorie erster Ordnung zu finden.

4. Varianten der Abhängigkeitslogik

In diesem Abschnitt werden die Eigenschaften der am besten untersuchten Varianten der Abhängigkeitslogik kurz zusammengefasst. Es gibt viele solcher Varianten, und es wurde viel an ihrer Klassifizierung und ihrem Vergleich gearbeitet. In dieser Arbeit werden nur diejenigen Varianten erwähnt, die aufgrund ihrer Beziehung zur eigentlichen Abhängigkeitslogik von besonderer Bedeutung sind.

4.1 Unabhängigkeitslogik

Anstatt die Logik erster Ordnung um Abhängigkeitsatome (eqord (vec x, y)) zu erweitern, erweitert die Unabhängigkeitslogik (Grädel & Väänänen 2013) sie um Unabhängigkeitsatome (vec x / mathop { bot _ { vec z }} vec y), dessen beabsichtigte Interpretation lautet: "Für jede mögliche Auswahl von (vec z) sind die möglichen Werte von (vec x) und (vec y) unabhängig" -in Mit anderen Worten, bei einer festen Auswahl von (vec z) würde die Kenntnis des von (vec x) angenommenen Werts keine Informationen über den von (vec y) angenommenen Wert liefern. Dies ist ein Begriff von erheblicher konzeptioneller Bedeutung: Beispielsweise möchte man möglicherweise zum Ausdruck bringen, dass die verschlüsselte Version einer Nachricht keine Informationen über die entsprechende Klartextversion enthält, wenn man den Verschlüsselungsschlüssel nicht kennt. Wenn (x) die verschlüsselte Nachricht darstellt und (y) die Nur-Text-Nachricht darstellt,dann entspricht dies der Bedingung (x / mathop { bot} y), wobei (vec z) in diesem Fall leer ist. In ähnlicher Weise repräsentiert (x / mathop { bot} k) die Behauptung, dass der Schlüssel nicht aus der verschlüsselten Nachricht abgeleitet werden kann, wenn (k) den Schlüssel darstellt; und das Konjunktionsabhängigkeitsatom (eqord (k, x, y)) (das, wie wir bald sehen werden, in der Unabhängigkeitslogik dargestellt werden kann) repräsentiert die Behauptung, dass die Klartextnachricht angesichts der verschlüsselten Nachricht decodiert werden kann und der Schlüssel.kann in der Unabhängigkeitslogik dargestellt werden) stellt die Behauptung dar, dass die Klartextnachricht angesichts der verschlüsselten Nachricht und des Schlüssels decodiert werden kann.kann in der Unabhängigkeitslogik dargestellt werden) stellt die Behauptung dar, dass die Klartextnachricht angesichts der verschlüsselten Nachricht und des Schlüssels decodiert werden kann.

Formal kann die Zufriedenheitsregel für Unabhängigkeitsatome wie folgt angegeben werden:

TS-Indep:

(M / models_X / vec x / mathop { bot _ { vec z}} vec y) genau dann, wenn für alle (s, s '\ in X) mit (s (vec z) = s '(vec z)) es existiert ein (s' '\ in X) mit (s' '(vec z \, / vec x) = s (vec {x }, / vec {z})) und (s '' (vec y) = s '(vec y)).

) begin {array} {l | ccc} textbf {Zuweisung} & / 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})

Die Unabhängigkeitslogik ist strikt ausdrucksvoller als die Abhängigkeitslogik: In der Tat fehlt ihr die Eigenschaft der Schließung nach unten, und das Abhängigkeitsatom (eqord (vec x, y)) entspricht dem Unabhängigkeitsatom (y / mathop { bot_) { vec x}} y). Darüber hinaus kann auch gezeigt werden (Galliani & Väänänen 2014), dass konditionierte Unabhängigkeitsatome (vec x / mathop { bot _ { vec y}} vec z) als bedingungslose Unabhängigkeitsatome (definiert werden können) vec x / mathop { bot} vec y).

Satzmäßig entspricht die Unabhängigkeitslogik auch der existenziellen Logik zweiter Ordnung (Sigma_1 ^ 1); Aber formelmäßig ist es ausdrucksvoller und es wurde in Galliani 2012 gezeigt, dass es alle nicht leeren (Sigma_1 ^ 1) - definierbaren Teameigenschaften erfassen kann.

4.2 Einschlusslogik

Die Einschlusslogik (Galliani 2012, Galliani & Hella 2013) erweitert die Logik erster Ordnung um Einschlussatome (vec x / subseteq / vec y), die an die Einschlussabhängigkeiten der Datenbanktheorie erinnern. Seine Semantik ist:

TS-inc:

(M / models_X / vec x / subseteq / vec y) genau dann, wenn für alle (s / in X) ein (s '\ in X) existiert, so dass (s (vec x) = s '(vec y)).

) begin {array} {l | cc} textbf {Zuweisung} & / 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})

Anders als die Abhängigkeits- und Unabhängigkeitslogik ist die Einschlusslogik (satzweise) streng schwächer als die existenzielle Logik zweiter Ordnung. Tatsächlich kann gezeigt werden (Galliani & Hella 2013), dass es dem positiven Fragment der größten Festkomma-Logik entspricht und daher die PTIME-Eigenschaften von Modellen gegenüber Modellen endlicher Ordnung erfasst. In Bezug auf die Formel ist die Inklusionslogik streng schwächer als die Unabhängigkeitslogik, aber mit der Abhängigkeitslogik nicht zu vergleichen: In der Tat sind die Erfüllbarkeitsbedingungen ihrer Formeln nicht nach unten geschlossen, sondern sie werden von Gewerkschaften in dem Sinne geschlossen, dass

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

4.3 Teamlogik

Die Teamlogik (Väänänen 2007a, b; Kontinen & Nurmi 2009) erweitert die Abhängigkeitslogik, indem sie eine widersprüchliche Negation (lnot) hinzufügt. Es ist äqui-expressiv mit vollständiger Logik zweiter Ordnung, sowohl in Bezug auf die Definierbarkeit von Modellklassen (Väänänen 2007b) als auch in Bezug auf die Klassen von Teams, die Teamlogik-Ausdrücke in Bezug auf ein bestimmtes Modell definieren können (Kontinen & Nurmi 2009)..

4.4 Intuitionistische Abhängigkeitslogik

Intuitionistische Abhängigkeitslogik (Abramsky & Väänänen 2009; Yang 2013) erweitert die Abhängigkeitslogik um einen Implikationskonnektiv (phi / rightarrow / psi), dessen Zufriedenheitsregeln in der Teamsemantik von angegeben werden

TS - (rightarrow):

(X / models / phi / rightarrow / psi) genau dann, wenn für alle Teilmengen (Y) von (X), wenn (Y / models / phi) dann (Y / models / psi).

Dieser Operator wird wegen der Ähnlichkeit zwischen seiner Semantik und der des Implikationsoperators in Kripkes Semantik für intuitionistische Logik als "intuitionistische Implikation" bezeichnet (Kripke 1965). Seine Interpretation in Bezug auf den Glauben ist recht einfach: Wenn die Zuweisungen in (X) die Zustände von Dingen darstellen, die ein Agent für möglich hält, kann eine Teilmenge (Y) von (X) das Ergebnis von a darstellen Glaubensaktualisierung, bei der der Agent einige zuvor angenommene mögliche Zustände ablehnt, und (phi / rightarrow / psi) Zustände als jede solche Aktualisierung, die dazu führen würde, dass (phi) gehalten wird, würde auch (psi / verursachen)) halten. Unter diesem Gesichtspunkt ist dies ein sehr natürliches Konzept, das es uns ermöglicht, Vorhersagen darüber zu beschreiben, wie der allgemeine Glaubenszustand eines solchen Agenten auf Glaubensaktualisierungen reagieren würde.

Aufgrund der universellen Quantifizierung zweiter Ordnung, die in ihrer Semantik impliziert ist, reicht dieser Zusammenhang jedoch aus, um die Ausdruckskomplexität der Logik erheblich zu erhöhen: Insbesondere, wie in Yang 2013 gezeigt, entspricht jeder Satz der Logik zweiter Ordnung einem Satz intuitionistischer Abhängigkeit Logik. Die intuitionistische Abhängigkeitslogik behält die Eigenschaft der Schließung nach unten bei: Wenn ein Team eine intuitionistische Abhängigkeitslogikformel erfüllt, tun dies auch alle seine Teilmengen.

4.5 Aussagenabhängigkeitslogik

Die bisher betrachteten Abhängigkeits- und Unabhängigkeitsatome drücken Beziehungen zwischen den möglichen Werten von Variablen in einer Reihe von Zuordnungen aus. Die gleichen Vorstellungen von Abhängigkeit und Unabhängigkeit können jedoch ebenso natürlich auf den Vorschlag selbst angewendet werden, wie dies im Ausdruck natürlicher Sprache der Fall ist, wie zum Beispiel „Ob er den Kurs bestehen wird oder nicht, hängt nur vom Inhalt seiner Abschlussprüfung ab“..

Aussagenabhängigkeitslogik betrachtet solche Atome im Kontext der Satzlogik. Propositional Dependence Logic Teams sind Sätze von Bewertungen (v) von Propositional Atoms (p_1 / ldots p_n) bis ({T, F }). Seine semantischen Regeln - und ihre Rechtfertigungen - spiegeln sehr genau die der Team-Semantik erster Ordnung wider, und die Regel für Abhängigkeitsatome lautet

PTS-dep:

(X / models / eqord (p_1 / ldots p_n, q)) genau dann, wenn zwei Bewertungen (v_1, v_2 / in X) vorliegen, die mit den Werten von (p_1 / ldots p_n übereinstimmen)) stimme auch dem Wert von (q) zu.

Viele der Varianten und Verallgemeinerungen der Abhängigkeitslogik erster Ordnung können problemlos auf die Propositionsebene gesenkt werden: So ist es beispielsweise möglich, die Eigenschaften der Propositional Inclusion Logic, der Propositional Team Logic, der Propositional Intuitionistic Dependence Logic usw. zu untersuchen.

Während die Abhängigkeitslogik (erster Ordnung) streng ausdrucksvoller ist als die Logik erster Ordnung, ist die Satzabhängigkeitslogik nicht ausdrucksvoller als die Satzlogik, da sich unmittelbar aus der Tatsache ergibt, dass alle Satzfunktionen in der Satzlogik ausdrückbar sind. Es besteht jedoch eine enge Beziehung zwischen den Teams der Aussagenabhängigkeitslogik und den Informationszuständen der neugierigen Logik (Groenendijk 2009; Ciardelli & Roelofsen 2011), einem semantischen Rahmen für die Untersuchung des Begriffs von Bedeutung und Informationsaustausch: insbesondere Die Implikation der neugierigen Logik ist genau die gleiche wie die der aussagekräftigen intuitionistischen Abhängigkeitslogik.

Axiomatisierungen für die Aussagenabhängigkeitslogik und viele ihrer Erweiterungen finden sich in Yang & Väänänen 2016.

4.6 Modale Abhängigkeitslogik

Die Modalabhängigkeitslogik (Väänänen 2008) und ihre Varianten erweitern die Modallogik, indem sie dieselben Abhängigkeitsatome (eqord (p_1 / ldots p_n, q)) hinzufügen, die bereits im Fall der Aussagenabhängigkeitslogik berücksichtigt wurden.

Seine Zufriedenheitsbedingungen können durch eine Variante der Teamsemantik definiert werden, bei der Teams durch Sätze möglicher Welten ersetzt werden.

Viel Forschung hat die komplexitätstheoretischen Eigenschaften dieser Logik, ihrer Fragmente und ihrer Erweiterungen untersucht (Ebbing, Lohmann & Yang 2011; Ebbing & Lohmann 2012; Lohmann & Vollmer 2013).

5. Anwendungen der Abhängigkeitslogik

5.1 Abhängigkeitslogik und Datenbanktheorie

Es gibt eine direkte Verbindung zwischen den Teams der Teamsemantik und den in der relationalen Datenbanktheorie untersuchten Beziehungen: Wenn ein Team (X) und ein Tupel von Variablen (vec v = v_1 / ldots v_k) in seinen Aufgaben vorkommen, Es ist möglich, die Beziehung (X (vec v) = { langle s (v_1), / ldots, s (v_n) rangle: s / in X }) zu definieren. Darüber hinaus sind die in der Abhängigkeitslogik und ihren Varianten untersuchten Abhängigkeitsatome analog zu und in vielen Fällen abgeleitet von Abhängigkeiten, die in der Datenbanktheorie berücksichtigt werden, wie funktionale Abhängigkeiten (Väänänen 2007a), mehrwertige Abhängigkeiten (Engström 2012) sowie Einschluss- und Ausschlussabhängigkeiten (Galliani 2012). Die Beziehung zwischen Abhängigkeitslogik und Datenbanktheorie trug nicht nur zur Weiterentwicklung der Abhängigkeitslogik bei, sondern auch zur Entwicklung der Datenbanktheorie: zum Beispiel:In Hannula & Kontinen 2016 wurde eine endliche Axiomatisierung des uneingeschränkten Implikationsproblems für inklusionsbezogene, funktionale und eingebettete mehrwertige datenbanktheoretische Abhängigkeiten durch die Untersuchung eines ähnlichen Problems im Kontext der Teamsemantik gefunden.

5.2 Abhängigkeitslogik und Glaubensrepräsentation

Wie in Yang 2014 und Yang & Väänänen 2016 diskutiert, besteht ein enger Zusammenhang zwischen (propositionaler) intuitionistischer Abhängigkeitslogik und neugieriger Logik (Ciardelli & Roelofsen, 2011), einem Rahmen für die Untersuchung der Bedeutung und des Informationsaustauschs zwischen Agenten. Im Allgemeinen lassen die in Team-Semantik untersuchten Abhängigkeitsatome und Konnektiva natürliche Interpretationen in Bezug auf Glaubenszustände und Glaubensaktualisierungen zu, wie in Galliani 2015 erörtert. Zu diesem Zeitpunkt ist die genaue Art der Beziehung zwischen solchen Logiken und dynamisch-epistemischer Logik und seine Varianten (Van Ditmarsch, van Der Hoek & Kooi 2007) sind weitgehend unerforscht, aber es gibt genügend Grund, weitere Verbindungen zwischen diesen beiden Bereichen der mathematischen und philosophischen Logik zu vermuten.

5.3 Abhängigkeitslogik und Satz von Arrow

Der Satz von Arrow (Arrow 1950) ist ein zutiefst einflussreiches Ergebnis der Theorie der sozialen Wahl, das kurz gesagt zeigt, dass kein Abstimmungssystem (dh kein System zur Umwandlung von Rankings individueller Präferenzen zwischen Alternativen in ein globales Präferenzranking auf gesellschaftlicher Ebene) existiert das kann drei vernünftig klingende Bedingungen erfüllen, nämlich

  • Wenn jeder Wähler (A) gegenüber (B) bevorzugt, bevorzugt die gesamte Gruppe (A) und (B);
  • Ob die Gruppe als Ganzes (A) gegenüber (B) bevorzugt oder umgekehrt, hängt ausschließlich von den Präferenzen jedes Wählers in Bezug auf (A) und (B) ab und nicht von ihren Präferenzen in Bezug auf andere mögliche Alternativen.
  • Kein einzelner Wähler ist ein Diktator, dh die Präferenzen der Gruppe werden nicht durch die Präferenzen eines einzelnen Wählers bestimmt.

Wie der Wortlaut selbst nahelegt, lassen die zweite und dritte Bedingung eine natürliche Lesart in Bezug auf Abhängigkeit und Unabhängigkeit zu: Wie in Pacuit & Yang 2016 gezeigt, kann der Satz von Arrow in der Unabhängigkeitslogik formalisiert und in einem geeigneten natürlichen Deduktionssystem bewiesen werden.

5.4 Quantenteamlogik und Bellsche Ungleichungen

In Hyttinen, Paolini & Väänänen 2015 wird eine Variante der Satzteamlogik vorgestellt, die als Quantenteamlogik bezeichnet wird. In diesem Formalismus werden Teams durch Quantenteams ersetzt, die sich von den normalen Teams der Aussagen-Team-Logik dadurch unterscheiden, dass sie zulassen, dass die Werte bestimmter Variablen in Bezug auf bestimmte Bewertungen unbestimmt sind, und dass sie mehrere Instanzen derselben zulassen Bewertung (wodurch der Team-Semantik ein quantitativer Aspekt hinzugefügt wird). Anschließend wird über Quantenteams eine Semantik für eine Sprache definiert, die die Spezifizierung von Ungleichungen hinsichtlich der Wahrscheinlichkeiten von Ereignissen ermöglicht, und es wird ein solides und vollständiges Beweissystem dafür entwickelt. und schließlich wird gezeigt, dass Bellsche Ungleichungen Gegenbeispiele in diesen Systemen zulassen,wie sie es nach den Vorhersagen der Quantenmechanik und nach experimentellen Beweisen tun (Einstein, Podolsky & Rosen 1935; Bell 1964; Aspect, Grangier & Roger 1981), während sie dies in der klassischen Version dieses Rahmens nicht tun.

Literaturverzeichnis

  • Abramsky, Samson und Jouko Väänänen, 2009, „Vom IF zum BI: Eine Geschichte von Abhängigkeit und Trennung“, Synthese, 167 (2): 207–230. doi: 10.1007 / s11229-008-9415-6
  • Arrow, Kenneth J., 1950, „Eine Schwierigkeit im Konzept der sozialen Wohlfahrt“, The Journal of Political Economy, S. 328–346. doi: 10.1086 / 256963
  • Aspect, Alain, Philippe Grangier und Gérard Roger, 1981, „Experimentelle Tests realistischer lokaler Theorien über den Bellschen Satz“, Physical Review Letters, 47 (7): 460–463. doi: 10.1103 / PhysRevLett.47.460
  • Bell, JS, 1964, „Über das Einstein-Podolsky-Rosen-Paradoxon“, Physics, 1 (3): 195–200.
  • Ciardelli, Ivano und 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 und Barteld Kooi, 2007, Dynamic Epistemic Logic, (Synthesebibliothek 337), Dordrecht: Springer. doi: 10.1007 / 978-1-4020-5839-4
  • Durand, Arnaud und Juha Kontinen, 2012, „Hierarchien in der Abhängigkeitslogik“, ACM Transactions on Computational Logic (TOCL), 13 (4): 1–21. doi: 10.1145 / 2362355.2362359
  • Ebbing, Johannes und Peter Lohmann, 2012, „Komplexität der Modellprüfung für modale Abhängigkeitslogik“, SOFSEM 2012: Internationale Konferenz über aktuelle Trends in Theorie und Praxis der Informatik, (Lecture Notes in Computer Science, 7147), Berlin, Heidelberg: Springer, S. 226–237. doi: 10.1007 / 978-3-642-27660-6_19
  • Ebbing, Johannes, Peter Lohmann und Fan Yang, 2013, „Modellprüfung für modale intuitionistische Abhängigkeitslogik“, Internationales Tiflis-Symposium für Logik, Sprache und Berechnung 2011, (Lecture Notes in Computer Science, 7758), Berlin, Heidelberg: Springer S. 231–256. doi: 10.1007 / 978-3-642-36976-6_15
  • Einstein, A., B. Podolsky und N. Rosen, 1935, "Kann die quantenmechanische Beschreibung der physikalischen Realität als vollständig angesehen werden?" Physical Review, 47 (10): 777–780. doi: 10.1103 / PhysRev.47.777
  • Engström, Fredrik, 2012, „Generalisierte Quantifizierer in der Abhängigkeitslogik“, Journal of Logic, Language and Information, 21 (3): 299–324. doi: 10.1007 / s10849-012-9162-4
  • Fagin, Ronald, 1974, "Verallgemeinerte Spektren erster Ordnung und erkennbare Mengen in Polynomzeit", Komplexität der Berechnung (SIAM-AMS Proceedings 7), Richard M. Karp (Hrsg.), Providence, RI: American Mathematical Society, pp. 27–41.
  • Galliani, Pietro, 2012, „Einschluss- und Ausschlussabhängigkeiten in der Teamsemantik - von einigen Logiken unvollständiger Informationen“, Annals of Pure and Applied Logic, 163 (1): 68–84. doi: 10.1016 / j.apal.2011.08.005
  • –––, 2015, „Die doxastische Interpretation der Teamsemantik“, Logik ohne Grenzen: Aufsätze zur Mengenlehre, Modelltheorie, Philosophische Logik und Philosophie der Mathematik (Ontos Mathematical Logic, 5), Åsa Hirvonen, Juha Kontinen, Roman Kossak, und Andrés Villaveces (Hrsg.), Berlin, Boston: De Gruyter, S. 167–192. doi: 10.1515 / 9781614516873.167
  • Galliani, Pietro und Lauri Hella, 2013, „Inklusionslogik und Festpunktlogik“, Informatiklogik 2013 (Leibniz International Proceedings in Informatics (LIPIcs), 23), Dagstuhl, Deutschland: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, pp. 281–295. doi: 10.4230 / LIPIcs. CSL.2013.281
  • Galliani, Pietro und Jouko Väänänen, 2014, „Über Abhängigkeitslogik“, in Johan van Benthem über Logik und Informationsdynamik (Herausragende Beiträge zur Logik, 5), Alexandru Baltag und Sonja Smets (Hrsg.), Cham: Springer, S. 101– 119. doi: 10.1007 / 978-3-319-06025-5_4
  • Grädel, Erich und Jouko Väänänen, 2013, „Abhängigkeit und Unabhängigkeit“, Studia Logica, 101 (2): 399–410. doi: 10.1007 / s11225-013-9479-2
  • Groenendijk, Jeroen, 2009, „Neugierige Semantik: Zwei Möglichkeiten der Disjunktion“, in Peter Bosch, David Gabelaia und Jérôme Lang (Hrsg.), Siebtes internationales Tiflis-Symposium über Sprache, Logik und Berechnung (Lecture Notes in Computer Science: Band 5422)), Springer-Verlag, S. 80–94. doi: 10.1007 / 978-3-642-00665-4_8
  • Hannula, Miika und Juha Kontinen, 2016, „Eine endliche Axiomatisierung bedingter Unabhängigkeit und Inklusionsabhängigkeiten“. Information and Computation, 249: 121–137. doi: 10.1016 / j.ic.2016.04.001
  • Henkin, Leon, 1961, „Einige Bemerkungen zu unendlich langen Formeln“, in Infinitistic Methods (Proceedings of the Symposium on the Foundations of Mathematics, Warschau, 1959), Oxford: Pergamon Press, S. 167–183.
  • Hodges, Wilfrid, 1997, „Kompositionssemantik für eine Sprache unvollkommener Informationen“, Logic Journal of the IGPL, 5 (4): 539–563. doi: 10.1093 / jigpal / 5.4.539
  • Hyttinen, Tapani, Gianluca Paolini und Jouko Väänänen, 2015, „Quantum Team Logic and Bell's Inequalities“, The Review of Symbolic Logic, 8 (4): 722–742. doi: 10.1017 / S1755020315000192
  • Kontinen, Juha und Ville Nurmi, 2009, „Teamlogik und Logik zweiter Ordnung“, in Proceedings des 16. Internationalen Workshops zu Logik, Sprache, Information und Berechnung (Lecture Notes in Computer Science, 5514), Berlin, Heidelberg: Springer S. 230–241. doi: 10.1007 / 978-3-642-02261-6_19
  • Kontinen, Juha und Jouko Väänänen, 2009, „Über Definierbarkeit in der Abhängigkeitslogik“, Journal of Logic, Language and Information, 18 (3): 317–332.doi: 10.1007 / s10849-009-9082-0
  • –––, 2011, „Eine Bemerkung zur Negation in der Abhängigkeitslogik“, Notre Dame Journal of Formal Logic, 52 (1): 55–65. doi: 10.1215 / 00294527-2010-036
  • –––, 2013, „Axiomatisierung von Konsequenzen erster Ordnung in der Abhängigkeitslogik“, Annals of Pure and Applied Logic, 164 (11): 1101–1117. doi: 10.1016 / j.apal.2013.05.006
  • Kripke, Saul A., 1965, "Semantical Analysis of Intuitionistic Logic I", in formalen Systemen und rekursiven Funktionen: Proceedings of the Eighth Logic Colloquium, Oxford, Juli 1963 (Studies in Logic and the Foundations of Mathematics, 40), John N. Crossley und Michael AE Dummett (Hrsg.), Nordholland, S. 92–130. doi: 10.1016 / S0049-237X (08) 71685-9
  • Lohmann, Peter und Heribert Vollmer, 2013, „Komplexitätsergebnisse für die Modalabhängigkeitslogik“, Studia Logica, 101 (2): 343–366. doi: 10.1007 / s11225-013-9483-6
  • Pacuit, Eric und Fan Yang, 2016, „Abhängigkeit und Unabhängigkeit in der sozialen Wahl: Theorem von Arrow“, in Dependence Logic, Samson Abramsky, Juha Kontinen, Jouko Väänänen und Heribert Vollmer (Hrsg.), Dordrecht: Springer, S. 235–260. doi: 10.1007 / 978-3-319-31803-5_11
  • Väänänen, Jouko, 2007a, Abhängigkeitslogik: Ein neuer Ansatz zur unabhängigkeitsfreundlichen Logik, (Studententexte der London Mathematical Society, 70), Cambridge: Cambridge University Press. doi: 10.1017 / CBO9780511611193
  • –––, 2007b, „Team Logic“, in Interactive Logic: Ausgewählte Artikel aus dem 7. Augustus de Morgan Workshop (Texte in Logik und Spielen, 1), Johan van Benthem, Dov Gabbay und Benedikt Löwe (Hrsg.), Amsterdam: Amsterdam University Press, S. 281–302.
  • –––, 2008, „Modal Dependence Logic“, Neue Perspektiven für Spiele und Interaktion (Texte in Logik und Spielen, 4), Krzysztof R. Apt und Robert van Rooij (Hrsg.), Amsterdam: Amsterdam University Press, S. 237– 254.
  • Yang, Fan, 2013, „Sätze zweiter Ordnung in intuitionistischer Abhängigkeitslogik ausdrücken“, Studia Logica, 101 (2): 323–342. doi: 10.1007 / s11225-013-9476-5
  • –––, 2014, „Über Erweiterungen und Varianten der Abhängigkeitslogik: Eine Studie über intuitionistische Konnektiva in der Team-Semantik-Umgebung“. Doktorarbeit, Universität Helsinki.
  • Yang, Fan und Jouko Väänänen, 2016, „Aussagenlogik der Abhängigkeit“, Annals of Pure and Applied Logic, 167 (7): 557–589. doi: 10.1016 / j.apal.2016.03.003

Akademische Werkzeuge

Sep Mann Symbol
Sep Mann Symbol
Wie man diesen Eintrag zitiert.
Sep Mann Symbol
Sep Mann Symbol
Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
Inpho-Symbol
Inpho-Symbol
Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
Phil Papers Ikone
Phil Papers Ikone
Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

  • Abhängigkeitslogik auf Wikipedia
  • Präsentationen in Academy Colloquium Dependence Logic, Amsterdam, 2014