Logika zależności

Logika zależności to formalizm logiczny stworzony przez Jouko Väänänena , który dodaje atomy zależności do języka logiki pierwszego rzędu . Atom zależności jest wyrażeniem postaci ${\ Displaystyle = \! \! (t_ {1} \ ldots t_ {n})}$ , gdzie ${\ displaystyle t_ { 1} \ ldots t_ {n}}$ są wyrazami i odpowiadają stwierdzeniu, że wartość ${\ displaystyle t_ {n}}$ jest funkcjonalnie zależna od wartości ${\ displaystyle t_ { 1}\ldots t_{n-1}}$ .

Logika zależności jest logiką niedoskonałych informacji, jak logika rozgałęzionych kwantyfikatorów lub logika niezależna : innymi słowy, jej semantykę teorii gier można uzyskać z logiki pierwszego rzędu, ograniczając dostępność informacji dla graczy, umożliwiając w ten sposób nieliniowo uporządkowane wzorce zależności i niezależności między zmiennymi. Jednak logika zależności różni się od tych logik tym, że oddziela pojęcia zależności i niezależności od pojęcia kwantyfikacji.

Składnia

Składnia logiki zależności jest rozszerzeniem składni logiki pierwszego rzędu. Dla ustalonej sygnatury σ = ( S _func , S _rel , ar) zbiór wszystkich prawidłowo sformułowanych formuł logicznych zależności jest definiowany według następujących zasad:

Warunki

Terminy w logice zależności są definiowane dokładnie tak samo jak w logice pierwszego rzędu .

Formuły atomowe

Istnieją trzy rodzaje formuł atomowych w logice zależności:

1. Atom relacyjny $dla$ wyrażeniem postaci $w$ dowolnej n-arnej relacji naszej sygnaturze terminów ${\ Displaystyle t_ {1} \ ldots t_ {n}}$ ;
2. Atom równości jest wyrażeniem postaci ${\ displaystyle t_ {1} = t_ {2}}$ , dla dowolnych dwóch terminów ${\ displaystyle t_ {1}}$ i ${\ displaystyle t_ { 2}}$ ;
3. Atom zależności jest wyrażeniem postaci ${\ Displaystyle = \! \! (t_ {1} \ ldots t_ {n})}$ dla dowolnego ${\ displaystyle n \ w \mathbb {N}}$ i dla dowolnego n- wielu terminów ${\ Displaystyle t_ {1} \ ldots t_ {n}}$ .

Nic innego nie jest atomową formułą logiki zależności.

Atomy relacyjne i równościowe są również nazywane atomami pierwszego rzędu .

Złożone formuły i zdania

W przypadku podpisu stałego σ zbiór wszystkich formuł ${\ displaystyle \ phi$$}$ im zestawów wolnych zmiennych są zdefiniowane jako co następuje:

1. Każda formuła atomowa $jest$ , a $jest$ wszystkich występujących w
2. ϕ ${\ Displaystyle \ phi}$ jest formułą, więc jest $\ phi )={\mbox{Wolny}}(\phi)}$$\$ Displaystyle ;
3. ϕ $\ Displaystyle \ phi}$ i ${\ Displaystyle \ psi}$ są formułami, więc jest ${\ Displaystyle \ phi \ vee \ psi}$ i ${\ Displaystyle {\ mbox {wolny}} (\ phi \ vee \ psi) = {\ mbox {wolny}} (\ phi) \ puchar {\ mbox {wolny}} (\ psi)}$ ;
4. Jeśli $formułą$ i ${\ Displaystyle {\ mbox {wolny}} (\ istnieje v \ phi) = {\ mbox {wolny}} (\ phi) \ ukośnik odwrotny \ {v \}}$ zmienną formułą $)$$($ .

Nic nie jest formułą logiki zależności, jeśli nie można tego uzyskać poprzez skończoną liczbę zastosowań tych czterech reguł.

Formuła taka, że $Displaystyle {\ mbox {Free}} (\ phi) = \ emptyset}$$\$ zdaniem logiki zależności.

Kwantyfikacja koniunkcyjna i uniwersalna

W powyższym przedstawieniu składni logiki zależności koniunkcja i kwantyfikacja uniwersalna nie są traktowane jako operatory pierwotne; są one raczej definiowane odpowiednio w kategoriach dysjunkcji i negacji oraz kwantyfikacji egzystencjalnej za pomocą praw De Morgana .

Dlatego $\ phi \ klin \$${$${\ Displaystyle \ forall x \ phi}$ skrót i jest traktowany jako skrót dla ${\ Displaystyle \ lnot (\ istnieje x (\ lnot \ phi))}$ .

Semantyka

Semantyka zespołowa dla logiki zależności jest odmianą semantyki kompozycyjnej Wilfrida Hodgesa dla logiki IF . Istnieją równoważne semantyki teorii gier dla logiki zależności, zarówno pod względem niedoskonałych gier informacyjnych , jak i doskonałych gier informacyjnych.

Zespoły

Niech ${\ Displaystyle {\ mathcal {A}} = (A, \ sigma, ja)}$ będzie strukturą pierwszego rzędu i niech ${\ Displaystyle V=\{v_{1}\ldots v_{n}\}}$ będzie skończonym zbiorem zmiennych. Wtedy zespół nad A o dziedzinie V jest zbiorem przypisań nad A o dziedzinie V , czyli zbiorem funkcji μ od V do A .

Pomocne może być zwizualizowanie takiego zespołu jako relacji bazy danych z atrybutami i tylko jednym typem danych, odpowiadającym domenie A struktury: ${\ displaystyle v_ {1} \ ldots v_ {n}}$ na przykład, jeśli zespół X składa ${1} \ ldots \ mu _$ z czterech zadań z domeną ${v_{1},v_{2},v_{3}\}}$$Displaystyle \ mu$ to można to przedstawić jako relację

${\ Displaystyle {\ rozpocząć {tablica} {c| ccc} &v_{1}&v_{2}&v_{3}\\\hline \mu _{1}&\mu _{1}(v_{1})&\mu _{1}(v_{2})&\ mu _{1}(v_{3})\\\mu _{2}&\mu _{2}(v_{1})&\mu _{2}(v_{2})&\mu _{ 2}(v_{3})\\\mu _{3}&\mu _{3}(v_{1})&\mu _{3}(v_{2})&\mu _{3}( v_{3})\\\mu_{4}&\mu_{4}(v_{1})&\mu_{4}(v_{2})&\mu_{4}(v_{3} })\end{tablica}}}$

Satysfakcja pozytywna i negatywna

$zespołu można$ w kategoriach dwóch relacji i między strukturami, zespołami i $.$

$pod$ uwagę strukturę , zespół nad nią i formułę logiki zależności $,$ której wolne zmienne $displaystyle X}$ zawarte w domenie $displaystyle X}$${$ , jeśli ${\ Displaystyle ({\ mathcal {A}}, X, \ phi) \ w {\ mathcal {T}}}$ mówimy, że ${\ Displaystyle X}$ jest atutem dla $i piszemy$ , że ZA $\ Displaystyle {\ mathcal$${X} ^{+}\phi}$ ; i analogicznie, jeśli mówimy, że jest ${C}}}$$mathcal$ ϕ $mathcal {A}} \ modele _ {X} ^ {-}\phi}$$\ Displaystyle \ phi}$ w $-$ X ϕ { .

Jeśli można również powiedzieć, że jest pozytywnie spełniony przez ${\ mathcal {A}} \ modele _ {X} ^ {+}$$Displaystyle$$} }$ w ${\ Displaystyle {\ mathcal {A}}}$ i jeśli zamiast tego można powiedzieć, że ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} \ phi}$${\ Displaystyle \ phi}$ jest negatywnie spełniony przez ${\ Displaystyle X}$ w ${\ Displaystyle {\ mathcal {A}}}$ .

Konieczność oddzielnego rozpatrywania satysfakcji pozytywnej i negatywnej wynika z faktu, że w logice zależności, podobnie jak w logice kwantyfikatorów rozgałęzionych czy w logice IF , nie obowiązuje prawo wyłączonego środka ; alternatywnie można założyć, że wszystkie formuły są w postaci normalnej negacji , używając relacji De Morgana w celu zdefiniowania uniwersalnej kwantyfikacji i koniunkcji odpowiednio z kwantyfikacji egzystencjalnej i alternatywy, i rozważyć samą satysfakcję pozytywną.

$,$ zdanie mówimy, że ${A}} \ modele _ {\ {\ pusty zbiór \}} ^ {+} \ phi}$ prawdziwe w ZA $\$$Displaystyle {\ mathcal {A}}}$ wtedy i tylko wtedy, gdy ${\ Displaystyle {\$${\ displaystyle {\ mathcal {A} }}$$i$ mówimy, że jest fałszem w wtedy i tylko wtedy, gdy ${\ Displaystyle {\ mathcal {A}} \ modele _ {\ {\ pusty zbiór \}} ^ {-} \ phi}$ .

Reguły semantyczne

Jeśli chodzi o przypadek relacji spełnialności Alfreda Tarskiego dla formuł pierwszego rzędu, pozytywne i negatywne relacje spełnialności semantyki zespołowej dla logiki zależności są definiowane przez indukcję strukturalną po formułach języka. Ponieważ operator negacji zamienia dodatnią i ujemną spełnialność, dwie indukcje odpowiadające i ⊨ $\ displaystyle \ modele ^ {-}}$ muszą być wykonane jednocześnie: ${\ displaystyle \ modele ^ {+}} }$

Pozytywna spełnialność

1. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} Rt_ {1} \ ldots t_ {n}}$ wtedy i tylko wtedy, gdy
   1. ${\ Displaystyle R}$ jest n-arnym symbolem w podpisie ZA $\ Displaystyle {\ mathcal {A}}}$ ;
   2. $Wszystkie$ zmienne występujące w terminach w dziedzinie ${\ displaystyle t_ {1} \ ldots t_ {n}}$ ;
   3. Dla każdego zadania ocena krotki $t$$\ Displaystyle (t_ {1} \ ldots t_ {n})}$ μ $displaystyle \mu}$ jest w interpretacji w ZA $\ Displaystyle {$$mathcal {A}}}$ ;
2. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} t_ {1} = t_ {2}}$ wtedy i tylko wtedy, gdy
   1. $t_ {1}$ w terminach i $displaystyle$ w dziedzinie $}$ ;
   2. Dla każdego zadania $X}$${\ Displaystyle$$t_ {2}} zgodnie z t 1 {\ displaystyle {\$ mathcal { displaystyle $\ mu \$ są takie same;
3. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} = \! \! (t_ {1} \ ldots t_ {n})}$ wtedy i tylko wtedy, gdy dowolne dwa przypisania ${\ Displaystyle s, s' \ in X}$ , których oceny krotki ${\ Displaystyle (t_ {1} \ ldots t_ { n-1})}$ zbiegają się przypisać tę samą wartość do ${\ displaystyle t_ {n}}$ ;
4. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} \ lnot \ phi}$ wtedy i tylko wtedy, gdy ${\ Displaystyle {\ mathcal {A}} \modele _{X}^{-}\phi}$ ;
5. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} \ phi \ vee \ psi}$ wtedy i tylko wtedy, gdy istnieją zespoły ${\ Displaystyle Y}$ i ${ \displaystyle Z}$ takie, że
   1. ${\ Displaystyle X = Y \ kubek Z}$ '
   2. ${\ Displaystyle {\ mathcal {A}} \ modele _ {Y} ^ {+} \ phi}$ ;
   3. ${\ Displaystyle {\ mathcal {A}} \ modele _ {Z} ^ {+} \ psi}$ ;
6. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} \ istnieje x \ phi}$ wtedy i tylko wtedy, gdy istnieje funkcja ${\ displaystyle F}$ z ${ \ Displaystyle X}$ do domeny takiej, że ZA $} \ modele _ {X [F / x]} ^ {+} \ phi}$$Displaystyle$ , gdzie ${\ Displaystyle X [F / x] = \ {s [F ( s)/x]:s\w X\}}$ .

Negatywna spełnialność

1. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} Rt_ {1} \ ldots t_ {n}}$ wtedy i tylko wtedy, gdy
   1. ${\ Displaystyle R}$ jest n-arnym symbolem w podpisie ZA $\ Displaystyle {\ mathcal {A}}}$ ;
   2. $Wszystkie$ zmienne występujące w terminach w dziedzinie ${\ displaystyle t_ {1} \ ldots t_ {n}}$ ;
   3. Dla każdego zadania ocena krotki $t$$\ Displaystyle (t_ {1} \ ldots t_ {n})}$$displaystyle \mu}$ { nie jest w interpretacji w ZA $\ Displaystyle {$$mathcal {A}}}$ ;
2. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} t_ {1} = t_ {2}}$ wtedy i tylko wtedy, gdy
   1. $t_ {1}$ w terminach i $displaystyle$ w dziedzinie $}$ ;
   2. Dla każdego zadania $mathcal$ i ${\ displaystyle t_$${2}}$ zgodnie z $A}}}$ \ displaystyle $\ mathcal {\ displaystyle {\ displaystyle {\$ są różne;
3. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} = \! \! (t_ {1} \ ldots t_ {n})}$$pustym$ i tylko wtedy, gdy jest zespołem;
4. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} \ lnot \ phi}$ wtedy i tylko wtedy, gdy ${\ Displaystyle {\ mathcal {A}} \modele _{X}^{+}\phi}$ ;
5. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} \ phi \ vee \ psi}$ wtedy i tylko wtedy, gdy ${\ Displaystyle {\ mathcal { A}} \ modele _ {X} ^ {-} \ phi}$ i ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} \ psi}$ ;
6. ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {-} \ istnieje x \ phi}$ wtedy i tylko wtedy, gdy ${\ Displaystyle {\ mathcal {A}} \ modele _ {X [A / x]} ^ {-} \ phi}$ , gdzie $\w A\}}$${\ Displaystyle X [A/x]=\{s[m/x]:$$\$ i jest domeną ZA $displaystyle {\mathcal {A}}}$ .

Logika zależności i inne logiki

Logika zależności i logika pierwszego rzędu

Logika zależności jest $\ modele _ {\ {\ pusty zbiór \}} ^ {+} \ phi}$ rozszerzeniem logiki pierwszego rzędu: innymi słowy, dla każdego zdania pierwszego $struktury$ mamy to $}$${\ Displaystyle {\ mathcal {A}}}$$wtedy$ i tylko wtedy, gdy jest prawdziwe w zgodnie ze zwykłą semantyką pierwszego rzędu. Ponadto, dla dowolnego wzoru pierwszego rzędu , ${\ mathcal {A}} \ modele _ {X} ^ {+} \ phi}$$Displaystyle$ wtedy i tylko wtedy, gdy wszystkie $.$ zgodnie zwykłą $semantyką$$_$ _

Jednak logika zależności jest zdecydowanie bardziej wyrazista niż logika pierwszego rzędu: na przykład zdanie

${\ Displaystyle \ istnieje z \ forall x_ {1} \ forall x_ {2} \ istnieje y_ {1} \ istnieje y_ {2} (= \! \! (x_ {1}, y_ {1}) \ klin =\!\!(x_{2},y_{2})\klin (x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\klin y_{1}\not = z)}$

jest prawdziwe w modelu $tej$$,$ gdy dziedzina tego modelu jest nieskończona, mimo że żadna formuła pierwszego rzędu nie właściwości.

Logika zależności i logika drugiego rzędu

Każde zdanie logiki zależności jest równoważne jakiemuś zdaniu we fragmencie egzystencjalnym logiki drugiego rzędu, czyli jakiemuś zdaniu drugiego rzędu postaci

${\ Displaystyle \ istnieje R_ {1} \ ldots \ istnieje R_ {n} \ psi (R_ {1} \ ldots R_ {n})}$

gdzie ${\ Displaystyle \ psi (R_ {1} \ ldots R_ {n})}$ nie zawiera kwantyfikatorów drugiego rzędu. I odwrotnie, każde zdanie drugiego rzędu w powyższej postaci jest równoważne jakiemuś zdaniu logiki zależności.

Jeśli chodzi o formuły otwarte, logika zależności odpowiada skierowanemu w dół monotonicznemu fragmentowi egzystencjalnej logiki drugiego rzędu w tym sensie, że niepusta klasa zespołów jest definiowalna za pomocą formuły logiki zależności wtedy i tylko wtedy, gdy odpowiadająca jej klasa relacji jest monotoniczna w dół i definiowalna przez egzystencjalną formułę drugiego rzędu.

Logika zależności i kwantyfikatory rozgałęziające

Kwantyfikatory rozgałęziające można wyrazić za pomocą atomów zależności: na przykład wyrażenie

${\ Displaystyle (Q_ {H} x_ {1}, x_ {2}, y_ {1}, y_ {2}) \ fi (x_ {1}, x_ {2}, y_ {1},y_{2})\equiv {\begin{pmatrix}\forall x_{1}\exists y_{1}\\\forall x_{2}\exists y_{2}\end{pmatrix}}\ fi (x_{1},x_{2},y_{1},y_{2})}$

jest równoważne ze zdaniem logiki zależności ${\ Displaystyle \ forall x_ {1} \ istnieje y_{1}\forall x_{2}\istnieje y_{2}(=\!\!(x_{1},y_{1})\klin =\!\!(x_{2},y_{2 })\wedge \phi )}$ , w tym sensie, że pierwsze wyrażenie jest prawdziwe w modelu wtedy i tylko wtedy, gdy drugie wyrażenie jest prawdziwe.

I odwrotnie, każde zdanie logiki zależności jest równoważne jakiemuś zdaniu w logice rozgałęzionych kwantyfikatorów, ponieważ wszystkie egzystencjalne zdania drugiego rzędu są wyrażalne w logice rozgałęzionych kwantyfikatorów.

Logika zależności i logika JEŻELI

Każde zdanie logiczne zależności jest logicznie równoważne jakiemuś zdaniu logicznemu JEŻELI i odwrotnie.

Problem jest jednak bardziej subtelny, jeśli chodzi o formuły otwarte. Tłumaczenia między logiką JEŻELI a formułami logiki zależności i odwrotnie, istnieją tak długo, jak długo domena zespołu jest ustalona: innymi słowy, dla wszystkich zestawów zmiennych $ldots v_ {n} \}}$${\ displaystyle V = \ { v_ {1}$${$ i wszystkie formuły logiczne JEŻELI $istnieje$ wolnymi zmiennymi w formuła logiczna zależności $D}}$${\ displaystyle \ phi ^$ takie, że

${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} \ phi \ Leftrightarrow {\ mathcal {A}} \ modele _ {X} ^ {+}\fi ^{D}}$

dla wszystkich struktur $dla$$wszystkich$$zespołów$ z domeną odwrotnie, dla każdej formuły logicznej $z$ wolne zmienne w $​​ψ$ formuła logiczna JEŻELI taka, że $\ displaystyle \ psi ^ {I}}$

${\ Displaystyle {\ mathcal {A}} \ modele _ {X} ^ {+} \ psi \ Strzałka w lewo {\ mathcal {A}} \ modele _ {X} ^ {+}\psi ^{I}}$

$\$ struktur i dla wszystkich zespołów z domeną $\ displaystyle {$$displaystyle V}$ . Tłumaczenia te nie mogą być kompozycyjne.

Nieruchomości

Formuły logiki zależności są domknięte w dół : jeśli i $\ Displaystyle Y \ subseteq X} to ZA ⊨ X ϕ {\ Displaystyle {\ mathcal {A}$$\$ modele $} styl wyświetlania {\ mathcal {A}} \ modele _ {Y} \ psi}$ . Ponadto pusty zespół (ale nie zespół zawierający puste zadanie) spełnia wszystkie formuły logiki zależności, zarówno pozytywnie, jak i negatywnie.

Prawo wyłączonego środka zawodzi w logice zależności: na przykład formuła ${\ Displaystyle \ istnieje y (= \! \! (y) \ klin y = x)}$ nie jest ani pozytywnie, ani negatywnie zadowolony przez zespół ${\ Displaystyle X = \ {(x: 0), (x: 1) \}}$ . Ponadto dysjunkcja nie jest idempotentna i nie rozkłada się na koniunkcję.

Zarówno twierdzenie o zwartości, jak i twierdzenie Löwenheima-Skolema są prawdziwe dla logiki zależności. Twierdzenie Craiga o interpolacji również obowiązuje , ale ze względu $na$ naturę negacji w logice zależności, w nieco zmodyfikowanym sformułowaniu: jeśli dwie formuły logiki zależności $,$ to znaczy nigdy nie jest tak, że oba i ${\ displaystyle$$\ psi}$ trzymają się tego samego modelu, wtedy istnieje zdanie pierwszego rzędu we wspólnym języku obu zdań ${\ displaystyle \ theta$ takie, że $}$ i jest sprzeczne z $displaystyle$${$$teta$ .

$​​dla$$:$ dokładniej istnieje formuła taka, zdania zależności i modele , które spełniają $aksjomaty Peano$ , jeśli jest liczbą Gödla ${\ displaystyle \ phi},$ a następnie ${\ displaystyle '\ phi$

${\ Displaystyle {\ mathcal {M}} _ {\ omega} \ modele _ {\ {\ pusty zbiór \}} ^ {+} \! \ phi} wtedy i tylko wtedy,$ gdy ${\ Displaystyle {\ mathcal {M}} _ {\ omega} \ modele _ {\ {\ pusty zbiór \}} ^ {+} \ tau („\ phi”).}$

Nie jest to sprzeczne z twierdzeniem Tarskiego o niedefiniowalności , ponieważ negacja logiki zależności nie jest zwykłą sprzecznością.

Złożoność

W konsekwencji twierdzenia Fagina , własności struktur skończonych definiowalnych w logice zależności odpowiadają dokładnie właściwościom NP. Ponadto Durand i Kontinen wykazali, że ograniczenie liczby kwantyfikatorów uniwersalnych lub liczby atomów zależności w zdaniach prowadzi do twierdzeń o hierarchii w odniesieniu do siły wyrazu.

Problem niespójności logiki zależności jest półrozstrzygalny iw rzeczywistości równoważny problemowi niespójności dla logiki pierwszego rzędu. $arytmetyczny$ problem decyzyjny dla logiki zależności nie jest rzeczywistości jest kompletny w odniesieniu do klasy hierarchii Levy'ego .

Warianty i rozszerzenia

Logika zespołu

Logika zespołowa rozszerza logikę zależności o sprzeczną negację ${\ Displaystyle \ sim \! \! \ phi}$ . Jego siła wyrazu jest równoważna mocy pełnej logiki drugiego rzędu.

Logika zależności modalnej

Atom zależności lub jego odpowiedni wariant można dodać do języka logiki modalnej , uzyskując w ten sposób logikę zależności modalnej .

Intuicjonistyczna logika zależności

W tej chwili logika zależności nie ma implikacji. Implikacja intuicjonistyczna , której nazwa wywodzi się z podobieństwa między jej definicją a implikacją logiki intuicjonistycznej , można zdefiniować w następujący sposób: ${\ displaystyle \ phi \ rightarrow \ psi}$

${\ Displaystyle {\ mathcal {A}} \ modele _ {X} \ phi \ rightarrow \ psi}$ wtedy i tylko wtedy, gdy dla wszystkich ${\ Displaystyle Y \ subseteq X}$ takie, że ${\ Displaystyle {\ mathcal {A}} \ modele _ {Y} \ phi}$ utrzymuje, że ZA ${\ Displaystyle {\ mathcal {A}} \ modele _ {Y} \ psi$ .

Intuicjonistyczna logika zależności, czyli logika zależności uzupełniona implikacją intuicjonistyczną, jest równoważna logice drugiego rzędu.

Logika niezależności

Zamiast atomów zależności, logika niezależności dodaje do języka logiki pierwszego rzędu atomy niezależności ${\ Displaystyle {\ vec {t_ {1}}} \ bot _ {\ vec {t_ { 3}} {\ vec {t_ {2}}}}$ gdzie ${\ Displaystyle {\ vec {t_ {1}}}}$ , ${\ Displaystyle {\ vec {t_ {2}}} }$ i ${\ Displaystyle {\ vec {t_ {3}}}}$ to krotki terminów. Semantyka tych atomów jest zdefiniowana następująco:

${\ Displaystyle {\ mathcal {A}} \ modele _ {X} {\ vec {t_ {1}}} \ bot _ {\ vec {t_ {3} }} {\ vec {t_ {2}}}}$ wtedy i tylko wtedy, gdy dla wszystkich ${\ Displaystyle s, s '\ w X}$ z ${\ Displaystyle {\ vec {t_ {3}}} \ langle s \ rangle = {\ vec {t_ {3}}} \ langle s' \ rangle} istnieje s ″ ∈$ X $'' \ w X}$ takie, że ${\ Displaystyle {\ vec {t_ {3}}} \ langle s '' \ rangle = {\ vec {t_ {3}}} \ langle s \ rangle}$ , ${\ Displaystyle {\ vec {t_ {1}}} \ langle s '' \ rangle = {\ vec {t_ {1} }} \ langle s \ rangle}$ i ${\ Displaystyle {\ vec {t_ {2}}} \ langle s'' \ rangle = {\ vec {t_ {2}}}\langle s'\rangle }$ .

Logika niezależności odpowiada egzystencjalnej logice drugiego rzędu w tym sensie, że niepusta klasa zespołów jest definiowalna za pomocą formuły logiki niezależności wtedy i tylko wtedy, gdy odpowiednia klasa relacji jest definiowalna za pomocą egzystencjalnej formuły drugiego rzędu. Dlatego na poziomie formuł otwartych logika niezależności jest zdecydowanie silniejsza pod względem siły wyrazu niż logika zależności. Jednak na poziomie zdań logiki te są równoważne.

Logika włączania/wyłączania

Logika włączenia / wyłączenia rozszerza logikę pierwszego rzędu o atomy inkluzji i ${\ Displaystyle {\ vec {t_ {1}}} \ mid {\ vec {t_ {2}}}}$ wykluczenia $t_ {1}}} \ subseteq {\ vec {t_ {2}}}}$ gdzie w obu wzorach ${\ Displaystyle {\ vec {t_ {1}} }}$$terminów$ są o tej samej długości Semantyka tych atomów jest zdefiniowana następująco:

• ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} {\ vec {t_ {1}}} \ subseteq {\ vec {t_ {2}}}}$ jeśli $takie$ tylko wtedy, gdy dla wszystkich istnieje ${\ Displaystyle s \ w X}$ , $Displaystyle {\vec {t_{1}}}\langle s\rangle ={\vec {t_{2}}}\langle s'\rangle }$ ;
• ${\ Displaystyle {\ mathcal {A}} \ modele _ {X} {\ vec {t_ {1}}} \ mid {\ vec {t_ {2}}}}$ jeśli i tylko wtedy, gdy dla wszystkich ${\ Displaystyle s, s' \ w X}$ to utrzymuje, że ${\ Displaystyle {\ vec {t_ {1} }}\langle s\rangle \neq {\vec {t_{2}}}\langle s'\rangle }$ .

Logika włączania/wyłączania ma taką samą siłę wyrazu jak logika niezależności, już na poziomie formuł otwartych. Logika inkluzji i logika wykluczenia są uzyskiwane przez dodanie odpowiednio tylko atomów inkluzji lub atomów wykluczenia do logiki pierwszego rzędu. Zdania logiki inkluzyjnej odpowiadają pod względem siły wyrazu największym zdaniom logiki punktu stałego; stąd logika inkluzji przechwytuje (najmniejszą) logikę punktu stałego w modelach skończonych i PTIME w skończonych modelach uporządkowanych. Z kolei logika wykluczania odpowiada logice zależności w mocy ekspresyjnej.

Uogólnione kwantyfikatory

Innym sposobem rozszerzenia logiki zależności jest dodanie do języka logiki zależności pewnych uogólnionych kwantyfikatorów. Całkiem niedawno przeprowadzono badania logiki zależności z monotonicznymi uogólnionymi kwantyfikatorami i logiką zależności z pewnym kwantyfikatorem większościowym, co doprowadziło do nowej opisowej charakterystyki złożoności hierarchii liczenia.

Zobacz też

• Semantyka gry
• Kwantyfikator rozgałęziający
• Logika przyjazna niezależności

Notatki

• Abramsky, Samson i Väänänen, Jouko (2009), „Od JEŚLI do BI”. Synteza 167 (2): 207–230.
• Durand, Arnaud; Ebbing Johannes; Kontinen, Juha i Vollmer Heribert (2011), „ Logika zależności z kwantyfikatorem większościowym ”. FSTCS 2011: 252-263.
• Durand, Arnaud i Kontinen, Juha, „ Hierarchie w logice zależności ”. Transakcje ACM w logice obliczeniowej, 2012.
• Enderton, Herbert B. (1970), „Skończone kwantyfikatory częściowo uporządkowane”. Z. Matematyka. Logik Grundlagen Math., 16: 393–397.
• Engström, Fredrik, „ Uogólnione kwantyfikatory w logice zależności ”. Pojawi się Journal of Logic, Language and Information.
• Galliani, Pietro (2012), „ Włączanie i wyłączanie w semantyce zespołowej - o niektórych logikach niedoskonałych informacji ”. Roczniki czystej i stosowanej logiki 163 (1): 68-84.
• Galliani, Pietro i Hella, Lauri (2013), „ Logika włączenia i logika punktu stałego ”. Proceedings of Computer Science Logic 2013 (CSL 2013), Leibniz International Proceedings in Informatics (LIPIcs) 23, 281-295.
• Grädel, Erich i Väänänen, Jouko, „ Zależność i niezależność ”. Studia Logica, aby się pojawić.
•   Hintikka, Jaakko (2002), „ Zrewidowane zasady matematyki ”, ISBN 978-0-521-62498-5 .
• Hodges, Wilfrid (1997), „ Semantyka kompozycyjna dla języka niedoskonałych informacji ”. Dziennik IGPL 5: 539–563.
• Kontinen, Juha i Nurmi, Ville (2009), „Logika zespołowa i logika drugiego rzędu”. W logice, języku, informacjach i obliczeniach , s. 230–241.
• Kontinen, Juha i Väänänen, Jouko (2009), „O definiowalności w logice zależności”. Journal of Logic, Language and Information 18 (3): 317–332.
• Kontinen, Juha i Väänänen, Jouko (2009), „ Uwaga o negacji logiki zależności ”. Notre Dame Journal of Formal Logic, 52(1):55-65, 2011.
• Lohmann, Peter i Vollmer, Heribert (2010), „Wyniki złożoności dla logiki zależności modalnych”. W notatkach z wykładów z informatyki , s. 411–425.
• Sevenster, Merlijn (2009), „ Teoretyczne modele i właściwości obliczeniowe modalnej logiki zależności ”. Journal of Logic and Computation 19 (6): 1157–1173.
•   Väänänen, Jouko (2007), „ Logika zależności - nowe podejście do logiki przyjaznej niezależności ”, ISBN 978-0-521-87659-9 .
• Väänänen, Jouko (2008), „ Modalna logika zależności ”. Nowe perspektywy w logice i interakcji, s. 237–254.
• Walkoe, Wilbur J. (1970), „Skończona częściowo uporządkowana kwantyfikacja ”. Journal of Symbolic Logic, 35: 535–575.
• Yang, Fan (2010), „Wyrażanie zdań drugiego rzędu w intuicjonistycznej logice zależności”. Zależność i niezależność w postępowaniu logicznym, s. 118–132.

Linki zewnętrzne

• Galliani, Pietro. „Logika zależności” . W Zalta, Edward N. (red.). Stanford Encyklopedia filozofii .
• Specjalne wydanie Studia Logica na temat „Zależności i niezależności w logice” , zawierające szereg artykułów na temat logiki zależności
• Prezentacje w Academy Colloquium Dependence Logic, Amsterdam, 2014