Logika závislosti - Dependence logic

Logika závislosti je logický formalismus, vytvořený Jouko Väänänen,^[1] který dodává atomy závislosti do jazyka logika prvního řádu. Atom závislosti je výrazem formy ${ displaystyle = ! ! (t_ {1} ldots t_ {n})}$ , kde ${ displaystyle t_ {1} ldots t_ {n}}$ jsou výrazy a odpovídají tvrzení, že hodnota ${ displaystyle t_ {n}}$ je funkčně závislé na hodnotách ${ displaystyle t_ {1} ldots t_ {n-1}}$ .

Logika závislosti je a logika nedokonalých informací, jako logika kvantifikátoru větvení nebo logika vstřícná k nezávislosti: jinými slovy, jeho herní teoretická sémantika lze získat z logiky prvního řádu omezením dostupnosti informací pro hráče, což umožňuje nelineárně uspořádané vzorce závislosti a nezávislosti mezi proměnnými. Logika závislosti se však od těchto logik liší tím, že odděluje pojmy závislosti a nezávislosti od pojmu kvantifikace.

Syntax

Syntax logiky závislosti je rozšířením syntaxe logiky prvního řádu. Pro pevné podpis σ = (S_func, S_rel, ar), sada všech dobře vytvořených logických vzorců závislostí je definována podle následujících pravidel:

Podmínky

Jsou definovány pojmy v logice závislosti přesně jako v logice prvního řádu.

Atomové vzorce

V logice závislosti existují tři typy atomových vzorců:

A relační atom je výrazem formy ${ displaystyle Rt_ {1} ldots t_ {n}}$ pro jakýkoli n-ary vztah ${ displaystyle ! R}$ v našem podpisu a pro jakoukoli n-uple podmínek ${ displaystyle t_ {1} ldots t_ {n}}$ ;
An atom rovnosti je výrazem formy ${ displaystyle t_ {1} = t_ {2}}$ , pro jakékoli dva termíny ${ displaystyle t_ {1}}$ a ${ displaystyle t_ {2}}$ ;
A atom závislosti je výrazem formy ${ displaystyle = ! ! (t_ {1} ldots t_ {n})}$ , pro všechny ${ displaystyle n in mathbb {N}}$ a pro všechny n-uple podmínek ${ displaystyle t_ {1} ldots t_ {n}}$ .

Nic jiného není atomový vzorec logiky závislosti.

Rovněž se nazývají relační atomy a atomy rovnosti atomy prvního řádu.

Složité vzorce a věty

Pro pevný podpis σ je sada všech vzorců ${ displaystyle phi}$ logiky závislosti a jejich příslušných sad volných proměnných ${ displaystyle { mbox {zdarma}} ( phi)}$ jsou definovány takto:

Libovolný atomový vzorec ${ displaystyle phi}$ je vzorec a ${ displaystyle { mbox {zdarma}} ( phi)}$ je sada všech proměnných vyskytujících se v něm;
Li ${ displaystyle phi}$ je vzorec, tak je ${ displaystyle lnot phi}$ a ${ displaystyle { mbox {Free}} ( lnot phi) = { mbox {Free}} ( phi)}$ ;
Li ${ displaystyle phi}$ a ${ displaystyle psi}$ jsou vzorce, tak je ${ displaystyle phi vee psi}$ a ${ displaystyle { mbox {Free}} ( phi vee psi) = { mbox {Free}} ( phi) cup { mbox {Free}} ( psi)}$ ;
Li ${ displaystyle phi}$ je vzorec a ${ displaystyle x}$ je proměnná, ${ displaystyle existuje x phi}$ je také vzorec a ${ displaystyle { mbox {zdarma}} ( existuje v phi) = { mbox {zdarma}} ( phi) zpětné lomítko {v }}$ .

Nic není logickým vzorcem závislosti, pokud to nelze získat pomocí konečného počtu aplikací těchto čtyř pravidel.

Vzorec ${ displaystyle phi}$ takhle ${ displaystyle { mbox {Free}} ( phi) = emptyset}$ je věta logiky závislosti.

Konjunkce a univerzální kvantifikace

Ve výše uvedené prezentaci syntaxe logiky závislostí, spojky a univerzální kvantifikace nejsou považovány za primitivní operátory; spíše jsou definovány z hlediska disjunkce a negace a existenční kvantifikace respektive prostřednictvím De Morganovy zákony.

Proto, ${ displaystyle phi klín psi}$ je bráno jako zkratka pro ${ Displaystyle lnot ( lnot phi vee lnot psi)}$ , a ${ displaystyle forall x phi}$ je bráno jako zkratka pro ${ displaystyle lnot ( existuje x ( lnot phi))}$ .

Sémantika

The týmová sémantika pro logiku závislosti je varianta Wilfrid Hodges "kompoziční sémantika pro Logika IF.^[2]^[3] Existují ekvivalentní herně teoretická sémantika logiky závislosti, a to jak z hlediska nedokonalé informační hry a co se týče dokonalých informačních her.

Týmy

Nechat ${ displaystyle ! { mathcal {A}} = (A, sigma, I)}$ být struktura prvního řádu a nechte ${ displaystyle V = {v_ {1} ldots v_ {n} }}$ být konečnou sadou proměnných. Pak tým skončil A s doménou $PROTI$ je soubor úkolů A s doménou $PROTI$ , tj. soubor funkcí $μ$ z $PROTI$ na $A$ .

Může být užitečné si představit takový tým jako a relace databáze s atributy ${ displaystyle v_ {1} ldots v_ {n}}$ a pouze s jedním datovým typem odpovídajícím doméně $A$ struktury: například pokud tým $X$ skládá se ze čtyř úkolů ${ displaystyle ! mu _ {1} ldots mu _ {4}}$ s doménou ${ displaystyle ! {v_ {1}, v_ {2}, v_ {3} }}$ pak to může představovat jako vztah

{ displaystyle { begin {array} {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 {pole}}}

Pozitivní a negativní spokojenost

Týmovou sémantiku lze definovat z hlediska dvou vztahů ${ displaystyle { mathcal {T}}}$ a ${ displaystyle { mathcal {C}}}$ mezi strukturami, týmy a vzorci.

Vzhledem ke struktuře ${ displaystyle { mathcal {A}}}$ , tým ${ displaystyle X}$ a logický vzorec závislosti ${ displaystyle phi}$ jehož volné proměnné jsou obsaženy v doméně ${ displaystyle X}$ , pokud ${ displaystyle ({ mathcal {A}}, X, phi) v { mathcal {T}}}$ říkáme to ${ displaystyle X}$ je trumf pro ${ displaystyle phi}$ v ${ displaystyle { mathcal {A}}}$ a my to píšeme ${ displaystyle { mathcal {A}} modely _ {X} ^ {+} phi}$ ; a analogicky, pokud ${ displaystyle ({ mathcal {A}}, X, phi) v { mathcal {C}}}$ říkáme to ${ displaystyle X}$ je cotrump pro ${ displaystyle phi}$ v ${ displaystyle { mathcal {A}}}$ a my to píšeme ${ displaystyle { mathcal {A}} modely _ {X} ^ {-} phi}$ .

Li ${ displaystyle { mathcal {A}} modely _ {X} ^ {+} phi}$ lze to také říci ${ displaystyle phi}$ je pozitivně spokojen podle ${ displaystyle X}$ v ${ displaystyle { mathcal {A}}}$ , a pokud místo toho ${ displaystyle { mathcal {A}} modely _ {X} ^ {-} phi}$ dá se to říct ${ displaystyle phi}$ je negativně spokojen podle ${ displaystyle X}$ v ${ displaystyle { mathcal {A}}}$ .

Nutnost samostatně posoudit pozitivní a negativní spokojenost je důsledkem skutečnosti, že v logice závislosti, stejně jako v logice větvící kvantifikátory nebo v Logika IF, zákon vyloučeného středu neplatí; alternativně lze předpokládat, že všechny vzorce jsou v negační normální formě, pomocí De Morganových vztahů k definování univerzální kvantifikace a konjunkce z existenční kvantifikace a disjunkce, a uvažovat pouze o pozitivní spokojenosti.

Dostal trest ${ displaystyle phi}$ , říkáme to ${ displaystyle phi}$ je skutečný v ${ displaystyle { mathcal {A}}}$ kdyby a jen kdyby ${ displaystyle { mathcal {A}} modely _ { { prázdná sada }} ^ {+} phi}$ , a my to říkáme ${ displaystyle phi}$ je Nepravdivé v ${ displaystyle { mathcal {A}}}$ kdyby a jen kdyby ${ displaystyle { mathcal {A}} modely _ { { prázdná sada }} ^ {-} phi}$ .

Sémantická pravidla

Pokud jde o případ Alfred Tarski Vztah uspokojivosti pro vzorce prvního řádu, pozitivní a negativní vztahy uspokojivosti týmové sémantiky pro logiku závislosti jsou definovány strukturální indukce přes vzorce jazyka. Protože operátor negace zaměňuje pozitivní a negativní uspokojivost, odpovídají obě indukce ${ displaystyle ! models ^ {+}}$ a ${ displaystyle ! models ^ {-}}$ je třeba provést současně:

Pozitivní uspokojivost

${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} Rt_ {1} ldots t_ {n}}$ $! { mathcal A} models _ {X} ^ {+} Rt_ {1} ldots t_ {n}$ kdyby a jen kdyby
1. ${ displaystyle ! R}$ je symbol n-ary v podpisu ${ displaystyle ! { mathcal {A}}}$ ;
2. Všechny proměnné vyskytující se v podmínkách ${ displaystyle ! t_ {1} ldots t_ {n}}$ jsou v doméně ${ displaystyle ! X}$ ;
3. Pro každý úkol ${ displaystyle ! mu v X}$ , vyhodnocení n-tice ${ displaystyle ! (t_ {1} ldots t_ {n})}$ podle ${ displaystyle ! mu}$ je ve výkladu ${ displaystyle ! R}$ v ${ displaystyle ! { mathcal {A}}}$ ;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} t_ {1} = t_ {2}}$ $! { mathcal A} models _ {X} ^ {+} t_ {1} = t_ {2}$ kdyby a jen kdyby
1. Všechny proměnné vyskytující se v podmínkách ${ displaystyle ! t_ {1}}$ a ${ displaystyle ! t_ {2}}$ jsou v doméně ${ displaystyle ! X}$ ;
2. Pro každý úkol ${ displaystyle ! mu v X}$ , hodnocení ${ displaystyle ! t_ {1}}$ a ${ displaystyle ! t_ {2}}$ podle ${ displaystyle ! { mathcal {A}}}$ jsou stejní;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} = ! ! (t_ {1} ldots t_ {n})}$ jen a jen pokud nějaké dva úkoly ${ displaystyle ! s, s v X}$ jehož hodnocení n-tice ${ displaystyle ! (t_ {1} ldots t_ {n-1})}$ shodně přiřadit stejnou hodnotu ${ displaystyle ! t_ {n}}$ ;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} lnot phi}$ kdyby a jen kdyby ${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} phi}$ ;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} phi vee psi}$ $! { mathcal A} models _ {X} ^ {+} phi vee psi$ jen tehdy, pokud existují týmy ${ displaystyle ! Y}$ $! Y$ a ${ displaystyle ! Z}$ $! Z$ takhle
1. ${ displaystyle X = Y cup Z}$ '
2. ${ displaystyle ! { mathcal {A}} modely _ {Y} ^ {+} phi}$ ;
3. ${ displaystyle ! { mathcal {A}} modely _ {Z} ^ {+} psi}$ ;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} existuje x phi}$ právě když existuje funkce ${ displaystyle ! F}$ z ${ displaystyle ! X}$ do domény ${ displaystyle ! { mathcal {A}}}$ takhle ${ displaystyle ! { mathcal {A}} modely _ {X [F / x]} ^ {+} phi}$ , kde ${ displaystyle ! X [F / x] = {s [F (s) / x]: s v X }}$ .

Negativní uspokojivost

${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} Rt_ {1} ldots t_ {n}}$ $! { mathcal A} models _ {X} ^ {-} Rt_ {1} ldots t_ {n}$ kdyby a jen kdyby
1. ${ displaystyle ! R}$ je symbol n-ary v podpisu ${ displaystyle ! { mathcal {A}}}$ ;
2. Všechny proměnné vyskytující se v podmínkách ${ displaystyle ! t_ {1} ldots t_ {n}}$ jsou v doméně ${ displaystyle ! X}$ ;
3. Pro každý úkol ${ displaystyle ! mu v X}$ , vyhodnocení n-tice ${ displaystyle ! (t_ {1} ldots t_ {n})}$ podle ${ displaystyle ! mu}$ není ve výkladu ${ displaystyle ! R}$ v ${ displaystyle ! { mathcal {A}}}$ ;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} t_ {1} = t_ {2}}$ $! { mathcal A} models _ {X} ^ {-} t_ {1} = t_ {2}$ kdyby a jen kdyby
1. Všechny proměnné vyskytující se v podmínkách ${ displaystyle ! t_ {1}}$ a ${ displaystyle ! t_ {2}}$ jsou v doméně ${ displaystyle ! X}$ ;
2. Pro každý úkol ${ displaystyle ! mu v X}$ , hodnocení ${ displaystyle ! t_ {1}}$ a ${ displaystyle ! t_ {2}}$ podle ${ displaystyle ! { mathcal {A}}}$ jsou rozdílní;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} = ! ! (t_ {1} ldots t_ {n})}$ kdyby a jen kdyby ${ displaystyle ! X}$ je prázdný tým;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} lnot phi}$ kdyby a jen kdyby ${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} phi}$ ;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} phi vee psi}$ kdyby a jen kdyby ${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} phi}$ a ${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} psi}$ ;
${ displaystyle ! { mathcal {A}} modely _ {X} ^ {-} existuje x phi}$ kdyby a jen kdyby ${ displaystyle ! { mathcal {A}} modely _ {X [A / x]} ^ {-} phi}$ , kde ${ displaystyle ! X [A / x] = {s [m / x]: s v A }}$ a ${ displaystyle ! A}$ je doménou ${ displaystyle ! { mathcal {A}}}$ .

Logika závislosti a další logiky

Logika závislosti a logika prvního řádu

Logika závislosti je a konzervativní rozšíření logiky prvního řádu:^[4] jinými slovy pro každou větu prvního řádu ${ displaystyle ! phi}$ a struktura ${ displaystyle ! { mathcal {A}}}$ máme to ${ displaystyle ! { mathcal {A}} modely _ { { emptyset }} ^ {+} phi}$ kdyby a jen kdyby ${ displaystyle ! phi}$ je pravda v ${ displaystyle ! { mathcal {A}}}$ podle obvyklé sémantiky prvního řádu. Navíc pro každou první objednávku vzorec ${ displaystyle ! phi}$ , ${ displaystyle ! { mathcal {A}} modely _ {X} ^ {+} phi}$ jen a jen pokud jsou všechny úkoly ${ displaystyle ! mu v X}$ uspokojit ${ displaystyle ! phi}$ v ${ displaystyle ! { mathcal {A}}}$ podle obvyklé sémantiky prvního řádu.

Logika závislosti je však přísně expresivnější než logika prvního řádu:^[5] například věta

{ displaystyle ! existuje z forall x_ {1} forall x_ {2} existuje y_ {1} existuje y_ {2} (= ! ! (x_ {1}, y_ {1}) klín = ! ! (x_ {2}, y_ {2}) klín (x_ {1} = x_ {2} leftrightarrow y_ {1} = y_ {2}) klín y_ {1} ne = z)}

platí v modelu ${ displaystyle { mathcal {A}}}$ právě tehdy, je-li doména tohoto modelu nekonečná, i když žádný vzorec prvního řádu ${ displaystyle ! phi}$ má tuto vlastnost.

Logika závislosti a logika druhého řádu

Každá logická věta závislosti je ekvivalentní nějaké větě v existenciálním fragmentu logiky druhého řádu,^[6] to znamená na nějakou větu druhého řádu tohoto formuláře

{ displaystyle ! existuje R_ {1} ldots existuje R_ {n} psi (R_ {1} ldots R_ {n})}

kde ${ displaystyle psi (R_ {1} ldots R_ {n})}$ neobsahuje kvantifikátory druhého řádu. Naopak každá věta druhého řádu ve výše uvedené formě je ekvivalentní nějaké logické větě závislosti.^[7]

Pokud jde o otevřené vzorce, logika závislosti odpovídá dolů monotónnímu fragmentu existenciální logiky druhého řádu v tom smyslu, že neprázdná třída týmů je definovatelná pomocí vzorce logiky závislosti právě tehdy, pokud je odpovídající třída vztahů dolů monotónní a definovatelná existenciálním vzorcem druhého řádu.^[8]

Logika závislosti a větvící kvantifikátory

Kvantifikátory větvení jsou vyjádřitelné z hlediska atomů závislosti: například výraz

{ displaystyle (Q_ {H} x_ {1}, x_ {2}, y_ {1}, y_ {2}) phi (x_ {1}, x_ {2}, y_ {1}, y_ {2} ) equiv { begin {pmatrix} forall x_ {1} existuje y_ {1} forall x_ {2} existuje y_ {2} end {pmatrix}} phi (x_ {1}, x_ {2}, y_ {1}, y_ {2})}

je ekvivalentní logické větě závislosti ${ displaystyle forall x_ {1} existuje y_ {1} forall x_ {2} existuje y_ {2} (= ! ! (x_ {1}, y_ {1}) wedge = ! ! (x_ {2}, y_ {2}) klín phi)}$ , v tom smyslu, že první výraz je v modelu pravdivý právě tehdy, pokud je druhý výraz pravdivý.

Naopak, jakákoli věta logiky závislosti je ekvivalentní nějaké větě v logice větvících kvantifikátorů, protože všechny existenční věty druhého řádu jsou vyjádřitelné v logice větvících kvantifikátorů.^[9]^[10]

Logika závislosti a logika IF

Jakákoli logická věta závislosti je logicky ekvivalentní nějaké logické větě IF a naopak.^[11]

Problém je však jemnější, pokud jde o otevřené vzorce. Překlady mezi logikou IF a logickými vzorci závislosti a naopak existují, pokud je doména týmu pevná: jinými slovy pro všechny sady proměnných ${ displaystyle ! V = {v_ {1} ldots v_ {n} }}$ a všechny logické vzorce IF ${ displaystyle ! phi}$ s volnými proměnnými v ${ displaystyle ! V}$ existuje logický vzorec závislosti ${ displaystyle ! phi ^ {D}}$ takhle

{ displaystyle { mathcal {A}} modely _ {X} ^ {+} phi Leftrightarrow { mathcal {A}} modely _ {X} ^ {+} phi ^ {D}}

pro všechny struktury ${ displaystyle { mathcal {A}}}$ a pro všechny týmy ${ displaystyle ! X}$ s doménou ${ displaystyle ! V}$ a naopak pro každý logický vzorec závislosti ${ displaystyle ! psi}$ s volnými proměnnými v ${ displaystyle ! V}$ existuje logický vzorec IF ${ displaystyle ! psi ^ {I}}$ takhle

{ displaystyle { mathcal {A}} modely _ {X} ^ {+} psi Leftrightarrow { mathcal {A}} modely _ {X} ^ {+} psi ^ {I}}

pro všechny struktury ${ displaystyle { mathcal {A}}}$ a pro všechny týmy ${ displaystyle ! X}$ s doménou ${ displaystyle ! V}$ . Tyto překlady nemohou být kompoziční.^[12]

Vlastnosti

Logické vzorce závislosti jsou dolů zavřený: pokud ${ displaystyle { mathcal {A}} modely _ {X} phi}$ a ${ displaystyle Y subseteq X}$ pak ${ displaystyle { mathcal {A}} modely _ {Y} psi}$ . Navíc prázdný tým (ale ne tým obsahující prázdné zadání) splňuje všechny vzorce logiky závislostí, kladně i záporně.

Zákon vyloučeného středu selže v logice závislosti: například vzorec ${ displaystyle existuje y (= ! ! (y) klín y = x)}$ tým není pozitivně ani negativně spokojen ${ displaystyle X = {(x: 0), (x: 1) }}$ . Disjunkce navíc není idempotivní a nerozdává se po spojení.^[13]

Oba věta o kompaktnosti a Löwenheim-Skolemova věta platí pro logiku závislosti. Craigova interpolační věta také platí, ale vzhledem k povaze negace v logice závislosti, v mírně upravené formulaci: pokud dva vzorce logiky závislosti ${ displaystyle phi}$ a ${ displaystyle psi}$ jsou rozporuplný, to znamená, že nikdy neplatí, že obojí ${ displaystyle phi}$ a ${ displaystyle psi}$ držet ve stejném modelu, pak existuje a první objednávka věta ${ displaystyle theta}$ ve společném jazyce dvou vět takové, že ${ displaystyle phi}$ naznačuje ${ displaystyle theta}$ a ${ displaystyle theta}$ je v rozporu s ${ displaystyle psi}$ .^[14]

Jako logika IF,^[15] Logika závislosti může definovat vlastní operátor pravdy:^[16] přesněji existuje vzorec ${ displaystyle tau (x)}$ tak, že za každou větu ${ displaystyle phi}$ logiky závislosti a všech modelů ${ displaystyle { mathcal {M}} _ { omega}}$ které uspokojí Peanoovy axiomy, pokud ${ displaystyle ' phi'}$ je Gödelovo číslo z ${ displaystyle phi}$ pak

{ displaystyle { mathcal {M}} _ { omega} modely _ { { emptyset }} ^ {+} ! phi}

kdyby a jen kdyby

{ displaystyle { mathcal {M}} _ { omega} modely _ { { emptyset }} ^ {+} tau (' phi').}

To není v rozporu Tarskiho věta o nedefinovatelnosti, protože negace logiky závislosti není obvyklá protichůdná.

Složitost

Jako důsledek Faginova věta, vlastnosti konečných struktur definovatelných v logice závislosti přesně odpovídají vlastnostem NP. Dále Durand a Kontinen ukázali, že omezení počtu univerzálních kvantifikátorů nebo arity závislých atomů ve větách vede k hierarchickým větám s ohledem na expresivní sílu.^[17]

Problém nekonzistence logiky závislosti je semidecidable, a ve skutečnosti ekvivalentní problému nekonzistence pro logiku prvního řádu. Rozhodovací problém pro logiku závislosti však neníaritmetický, a je ve skutečnosti úplná s ohledem na ${ displaystyle Pi _ {2}}$ třída Levy hierarchie.^[18]

Varianty a rozšíření

Týmová logika

Týmová logika^[19] rozšiřuje logiku závislosti o a rozporuplná negace ${ displaystyle sim ! ! phi}$ . Jeho expresivní síla je ekvivalentní plné logice druhého řádu.^[20]

Logika modální závislosti

Atom závislosti nebo jeho vhodnou variantu lze přidat do jazyka modální logika, tedy získání logika modální závislosti.^[21]^[22]^[23]

Logika intuitivní závislosti

Logice závislosti chybí implikace. The intuicionistické implikace ${ displaystyle phi rightarrow psi}$ , jehož název je odvozen z podobnosti mezi jeho definicí a implikací intuicionistická logika, lze definovat takto:^[24]

{ displaystyle ! { mathcal {A}} modely _ {X} phi rightarrow psi}

jen a jen pro všechny

{ displaystyle Y subseteq X}

takhle

{ displaystyle { mathcal {A}} modely _ {Y} phi}

to platí

{ displaystyle { mathcal {A}} modely _ {Y} psi}

.

Logika intuitivní závislosti, tj. Logika závislosti doplněná intuitivní implikací, je ekvivalentní logice druhého řádu.^[25]

Logika nezávislosti

Namísto atomů závislosti se logika nezávislosti prvního řádu přidává k jazyku atomů logické nezávislosti prvního řádu ${ displaystyle { vec {t_ {1}}} bot _ { vec {t_ {3}}} { vec {t_ {2}}}}$ kde ${ displaystyle { vec {t_ {1}}}}$ , ${ displaystyle { vec {t_ {2}}}}$ a ${ displaystyle { vec {t_ {3}}}}$ jsou n-tice pojmů. Sémantika těchto atomů je definována následovně:

{ displaystyle { mathcal {A}} modely _ {X} { vec {t_ {1}}} bot _ { vec {t_ {3}}} { vec {t_ {2}}}}

jen a jen pro všechny

{ displaystyle s, s ' v X}

s

{ displaystyle { vec {t_ {3}}} langle s rangle = { vec {t_ {3}}} langle s ' rangle}

tady existuje

{ displaystyle s '' v X}

takhle

{ 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}

a

{ displaystyle { vec {t_ {2}}} langle s ' rangle = { vec {t_ {2}}} langle s' rangle}

.

Logika nezávislosti odpovídá existenciální logice druhého řádu v tom smyslu, že neprázdná třída týmů je definovatelná logickým vzorcem nezávislosti právě tehdy, pokud je odpovídající třída vztahů definovatelná existenčním vzorcem druhého řádu.^[26] Proto je na úrovni otevřených vzorců logika nezávislosti přísně silnější v expresivní síle než logika závislosti. Na úrovni vět jsou však tyto logiky rovnocenné.^[27]

Logika začlenění / vyloučení

Logika inkluze / exkluze rozšiřuje logiku prvního řádu o atomy inkluze ${ displaystyle { vec {t_ {1}}} subseteq { vec {t_ {2}}}}$ a vylučovací atomy ${ displaystyle { vec {t_ {1}}} střední { vec {t_ {2}}}}$ kde v obou vzorcích ${ displaystyle { vec {t_ {1}}}}$ a ${ displaystyle { vec {t_ {2}}}}$ jsou termínové n-tice stejné délky. Sémantika těchto atomů je definována následovně:

${ displaystyle { mathcal {A}} modely _ {X} { vec {t_ {1}}} subseteq { vec {t_ {2}}}}$ jen a jen pro všechny ${ displaystyle s v X}$ tady existuje ${ displaystyle s ' v X}$ takhle ${ displaystyle { vec {t_ {1}}} langle s rangle = { vec {t_ {2}}} langle s ' rangle}$ ;
${ displaystyle { mathcal {A}} modely _ {X} { vec {t_ {1}}} střední { vec {t_ {2}}}}$ jen a jen pro všechny ${ displaystyle s, s ' v X}$ to platí ${ displaystyle { vec {t_ {1}}} langle s rangle neq { vec {t_ {2}}} langle s ' rangle}$ .

Logika zahrnutí / vyloučení má stejnou expresivní sílu jako logika nezávislosti, a to již na úrovni otevřených vzorců.^[28] Logika inkluze a logika vyloučení jsou získány přidáním pouze inkluzních atomů nebo vylučovacích atomů k logice prvního řádu. Inklusní logické věty odpovídají v expresivní síle největším logickým větám s pevným bodem; proto logika zahrnutí zachycuje (nejméně) logiku s pevným bodem na konečných modelech a PTIME nad konečně seřazenými modely.^[29] Logika vyloučení zase odpovídá logice závislosti v expresivní síle.^[30]

Zobecněné kvantifikátory

Dalším způsobem rozšíření logiky závislosti je přidání některých zobecněných kvantifikátorů do jazyka logiky závislosti. Velmi nedávno došlo k nějaké studii logiky závislosti s monotónními generalizovanými kvantifikátory^[31] a logika závislosti s určitým většinovým kvantifikátorem, což vede k nové popisné složitosti charakterizaci hierarchie počítání.^[32]

Viz také

Poznámky

Reference

Abramsky, Samson a Väänänen, Jouko (2009), „From IF to BI“. Synthese 167 (2): 207–230.
Durand, Arnaud; Ebbing Johannes; Kontinen, Juha a Vollmer Heribert (2011), 'Logika závislosti s většinovým kvantifikátorem '. FSTTCS 2011: 252-263.
Durand, Arnaud a Kontinen, Juha, 'Hierarchie v logice závislostí^{[trvalý mrtvý odkaz ]}'. Zobrazí se transakce ACM ve výpočetní logice.
Enderton, Herbert B. (1970), „Konečné částečně objednané kvantifikátory“. Z. Math. Logik Grundlagen Math., 16: 393–397.
Engström, Fredrik, 'Zobecněné kvantifikátory v logice závislosti '. Časopis logiky, jazyka a informací.
Galliani, Pietro (2012), 'Zahrnutí a vyloučení v sémantice týmu - na některých logikách nedokonalých informací '. Annals of Pure and Applied Logic 163 (1): 68-84.
Galliani, Pietro a Hella, Lauri (2013), 'Logika začlenění a logika pevného bodu '. Proceedings of Computer Science Logic 2013 (CSL 2013), Leibniz International Proceedings in Informatics (LIPIcs) 23, 281-295.
Grädel, Erich a Väänänen, Jouko, 'Závislost a nezávislost '. Studia Logica, objevit se.
Hintikka, Jaakko (2002), 'Principy matematiky znovu ', ISBN 978-0-521-62498-5.
Hodges, Wilfride (1997), 'Kompoziční sémantika pro jazyk nedokonalých informací '. Časopis IGPL 5: 539–563.
Kontinen, Juha a Nurmi, Ville (2009), „Team Logic and Second-Order Logic“. v Logika, jazyk, informace a výpočet, str. 230–241.
Kontinen, Juha a Väänänen, Jouko (2009), „O definovatelnosti v logice závislosti“. Journal of Logic, Language and Information 18 (3): 317–332.
Kontinen, Juha a Väänänen, Jouko (2009), 'Poznámka k negaci logiky závislosti '. Notre Dame Journal of Formal Logic, 52 (1): 55-65, 2011.
Lohmann, Peter and Vollmer, Heribert (2010), „Complexity Results for Modal Dependence Logic“. v Přednášky z informatiky, str. 411–425.
Sevenster, Merlijn (2009), 'Modelově teoretické a výpočetní vlastnosti logiky závislosti na modálu '. Journal of Logic and Computation 19 (6): 1157–1173.
Väänänen, Jouko (2007), 'Logika závislosti - nový přístup k logice přátelské k nezávislosti ', ISBN 978-0-521-87659-9.
Väänänen, Jouko (2008), 'Logika modální závislosti '. Nové perspektivy v logice a interakci, s. 237–254.
Walkoe, Wilbur J. (1970), „Konečná částečně objednaná kvantifikace '. Journal of Symbolic Logic, 35: 535–575.
Yang, Fan (2010), „Vyjadřování vět druhého řádu v logice intuitivní závislosti“. Závislost a nezávislost v logickém řízení, s. 118–132.

externí odkazy

[1] Väänänen 2007

[2] Hodges 1997

[3] Väänänen 2007, §3.2

[4] Väänänen 2007, §3.2

[5] Väänänen 2007, §4

[6] Väänänen 2007, bod 6.1

[7] Väänänen 2007, bod 6.3

[8] Kontinen a Väänänen 2009

[9] Enderton 1970

[10] Walkoe 1970

[11] Väänänen 2007, §3.6

[12] Kontinen a Väänänen 2009 bis

[13] Väänänen 2007, §3

[14] Väänänen 2007, bod 6.2

[15] Hintikka 2002

[16] Väänänen 2007, bod 6.4

[17] Durand a Kontinen

[18] Väänänen 2007, §7

[19] Väänänen 2007, § 8

[20] Kontinen a Nurmi 2009

[21] Sevenster 2009

[22] Väänänen 2008

[23] Lohmann a Vollmer 2010

[24] Abramsky a Väänänen 2009

[25] Yang 2010

[26] Galliani 2012

[27] Grädel a Väänänen

[28] Galliani 2012

[29] Galliani a Hella 2013

[30] Galliani 2012

[31] Engström

[32] Durand, Ebbing, Kontinen, Vollmer 2011

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]