Lógica De Dependência

Índice:

Lógica De Dependência
Lógica De Dependência

Vídeo: Lógica De Dependência

Vídeo: Lógica De Dependência
Vídeo: LÓGICA de la DEPENDENCIA | #CitandoA Bertrand Badie 2024, Março
Anonim

Navegação de entrada

  • Conteúdo da Entrada
  • Bibliografia
  • Ferramentas Acadêmicas
  • Pré-visualização do Friends PDF
  • Informações sobre autor e citação
  • De volta ao topo

Lógica de Dependência

Publicado pela primeira vez em 2017-02-23

A lógica de dependência é uma extensão da lógica de primeira ordem que adiciona átomos de dependência, ou seja, expressões da forma (eqord (x_1 / ldots x_n, y)) que afirma que o valor de (y) é funcionalmente dependente (em outras palavras, determinado por) dos valores de (x_1 / ldots x_n). Esses átomos permitem a especificação de padrões de dependência não linearmente ordenados entre variáveis, muito no mesmo sentido dos quantificadores IF-Logic cortados; mas, diferentemente da lógica IF, a lógica de dependência separa a quantificação da especificação de tais condições de dependência / independência. A principal semântica da lógica de dependência, chamada semântica de equipe, generaliza a semântica de Tarski, permitindo que as expressões sejam satisfeitas ou não com relação a conjuntos de atribuições de variáveis, e não com relação a atribuições únicas. Essa semântica antecede o desenvolvimento da lógica de dependência propriamente dita e foi originalmente desenvolvida por Wilfrid Hodges no contexto da lógica IF (Hodges 1997). Também existe uma semântica da teoria dos jogos para a lógica da dependência, baseada em jogos de informações imperfeitas e aproximadamente análoga à semântica da teoria dos jogos da lógica favorável à independência (Väänänen 2007a). Sensu stricto, o termo “lógica de dependência” refere-se exclusivamente à linguagem obtida pela adição dos átomos de dependência funcional acima mencionados à linguagem da lógica de primeira ordem; mas o termo também é usado, em um sentido mais geral, para se referir à área de pesquisa que estuda as propriedades das lógicas obtidas adicionando várias noções de dependência e independência à lógica de primeira ordem, como a lógica de independência (Grädel & Väänänen 2013),lógica de dependência intuicionista (Yang 2013) ou lógica de inclusão (Galliani 2012, Galliani & Hella 2013), ou mesmo as da lógica que estendem outras estruturas lógicas através de átomos semelhantes, como no caso da lógica de dependência modal (Väänänen 2008). Neste artigo, o termo "lógica de dependência" será usado para se referir à lógica de dependência propriamente dita, e o termo "lógicas de dependência e independência" será usado para se referir a suas variantes e generalizações.e o termo “lógicas de dependência e independência” será usado para se referir a suas variantes e generalizações.e o termo “lógicas de dependência e independência” será usado para se referir a suas variantes e generalizações.

  • 1. Padrões de dependência na lógica de primeira ordem e suas extensões
  • 2. Semântica de equipe

    2.1 Semântica teórica dos jogos

  • 3. Propriedades

    • 3.1 Expressividade
    • 3.2 Hierarquias na lógica de dependência
    • 3.3 Negação na lógica da dependência
    • 3.4 Sistemas de verdade, validade e prova na lógica da dependência
  • 4. Variantes da lógica de dependência

    • 4.1 Lógica da Independência
    • 4.2 Lógica de inclusão
    • 4.3 Lógica da equipe
    • 4.4 Lógica de dependência intuicionista
    • 4.5 Lógica de dependência proposicional
    • 4.6 Lógica de dependência modal
  • 5. Aplicações da lógica de dependência

    • 5.1 Lógica de dependência e teoria de banco de dados
    • 5.2 Lógica de dependência e representação de crenças
    • 5.3 Lógica de dependência e teorema de Arrow
    • 5.4 Lógica quântica de equipe e desigualdades de Bell
  • Bibliografia
  • Ferramentas Acadêmicas
  • Outros recursos da Internet
  • Entradas Relacionadas

1. Padrões de dependência na lógica de primeira ordem e suas extensões

Uma característica da lógica de primeira ordem, responsável por grande parte de sua expressividade e aplicabilidade, é o fato de permitir que os quantificadores sejam aninhados e, portanto, permite a especificação de padrões de dependência entre variáveis quantificadas. Considere, por exemplo, a afirmação (esperançosamente falsa) de que "todo garoto ama uma garota que ama outro garoto". Ele pode ser diretamente traduzido para a lógica de primeira ordem como

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

cuja condição de verdade, de acordo com a semântica usual de Tarski, é precisamente o que se esperaria: a expressão acima é verdadeira se, e somente se, para todo garoto (b) for possível encontrar uma garota (g) e um garoto (b ') de modo que (b) ame (g) e (g) ame (b') e (b) e (b ') não sejam os mesmos. A identidade da garota (g) pode, é claro, depender da identidade do primeiro garoto (b) - afinal, para que essa expressão seja verdadeira, não exigimos que todos os garotos estejam apaixonados por todas as garotas. e, além disso, a identidade do segundo garoto (b ') pode depender tanto da identidade do primeiro garoto (b) (já que (b') deve ser diferente de (b)) e a partir da identidade da garota que (b) ama. Portanto, o padrão de dependência entre nossas variáveis quantificadas é o seguinte: (y) depende de (x),enquanto (z) depende de (x) e (y). De uma perspectiva sintática, isso se reflete no fato de que (existe y) está no escopo de (forall x) enquanto (existe z) está no escopo de ambos (forall x) e (existe y).

Diferenças nos padrões de dependência entre operadores podem ser usadas para formalizar distinções importantes, como, por exemplo, a entre a continuidade de uma função (f)

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

e sua continuidade uniforme

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

ou, em extensões intensionais da lógica de primeira ordem, para expressar a diferença entre as leituras de De Dicto e De Re (por exemplo, “É possível que toda pessoa fique louca” pode ser entendida como afirmando que é para todas as pessoas (p), é possível que (p) seja louco, (forall x (person (x) rightarrow / Diamond / crazy (x))) ou afirmando que é possível que todos estejam loucos juntos, (Diamond / forall x (person (x) rightarrow / crazy (x)))).

Os padrões de dependência entre variáveis quantificadas na lógica de primeira ordem são necessariamente transitivos, como é evidenciado por suas conexões com os escopos das subexpressões correspondentes: se (existir y) estiver no escopo de (forall x) e (existe z) está no escopo de (existe y), então necessariamente (existe z) estará no escopo de (e, portanto, depende de) (forall x) Além disso, o conjunto de todos os quantificadores em cujo escopo está parte de alguma sub-fórmula (alpha) é ordenado linearmente: se (alpha) está no escopo de (Q_1 x_1) e (Q_2 x_2), então (Q_1 x_1) está no escopo de (Q_2 x_2) ou vice-versa.

Isso limita as possibilidades expressivas da lógica de primeira ordem. Por exemplo, suponhamos que desejamos alterar nossa afirmação anterior sobre meninos e meninas da seguinte forma: todo garoto ama uma garota que ama outro garoto, e esse segundo garoto pode ser escolhido independentemente no primeiro. O que isso significa, intuitivamente falando, é bastante simples: para todo garoto (b), podemos encontrar uma garota (g), tal que (b) ama (g), e para toda garota que pudermos encontre um menino (b ') tal que (g) ame (b') e (b / not = b ') e, além disso, podemos encontrar a identidade do segundo menino (b') sem saber o de (b), com base na identidade da garota (g) sozinha. Isso ainda pode ser verdade em alguns cenários, como, por exemplo, se dois meninos (b_1) e (b_2) amam, respectivamente, duas meninas (g_1) e (g_2),que, no entanto, amam apenas (b_2) e (b_1), respectivamente. No entanto, é fácil ver que isso não é equivalente à nossa afirmação anterior: por exemplo, se nosso universo consiste (como em (b) acima) de dois meninos (b) e (b ') e uma menina (g) e (b) e (b ') ambos amam (g) que ama os dois, então nossa afirmação anterior é verdadeira, mas a atual é falsa.

[duas figuras semelhantes, ambas as figuras têm as palavras 'Meninos' e 'Meninas' separadas por espaço horizontal no topo. A figura (a) tem o ponto b1 no canto superior esquerdo, g1 no canto superior direito, b2 no canto inferior esquerdo e g2 no canto inferior direito. As setas apontam de g1 para b1, de b1 para g2, de g2 para b2 e b2 para g1. A figura (b) tem b1 no canto superior esquerdo, b2 no canto inferior esquerdo, g1 no meio direito. Uma seta aponta de e para b1 e g1 e da mesma forma de b2 para g1.]
[duas figuras semelhantes, ambas as figuras têm as palavras 'Meninos' e 'Meninas' separadas por espaço horizontal no topo. A figura (a) tem o ponto b1 no canto superior esquerdo, g1 no canto superior direito, b2 no canto inferior esquerdo e g2 no canto inferior direito. As setas apontam de g1 para b1, de b1 para g2, de g2 para b2 e b2 para g1. A figura (b) tem b1 no canto superior esquerdo, b2 no canto inferior esquerdo, g1 no meio direito. Uma seta aponta de e para b1 e g1 e da mesma forma de b2 para g1.]

Dois cenários nos quais ((ref {eq: boygirl1})) é verdadeiro. Em (a), (z) pode ser escolhido independentemente de (x); em (b), não pode.

No entanto, não está claro como formalizar essa condição na lógica de primeira ordem. Em essência, precisaríamos modificar ((ref {eq: boygirl1})) para que (z) não esteja no escopo de (x) e, portanto, não dependa disso; no entanto, ainda queremos que (z) dependa de (y) e (y) de (x). Como acabamos de discutir, entretanto, esse padrão de dependência não é realizável na lógica de primeira ordem. Podemos contornar o problema recorrendo à quantificação de ordem superior: de fato, pode-se ver que a expressão

(tag {2} label {boygirl2} begin {align} e / existe F / forall x (boy (x) rightarrow / existe y (girl (y) land / loves (x, y) terra / menino (F (y)) terra {} & / quad x / not = F (y) terra / amores (y, F (y)))) end {align})

captura nossa interpretação pretendida, mas apenas ao custo da quantificação existencial explícita sobre as funções.

Uma alternativa possível seria expandir a sintaxe da lógica de primeira ordem, a fim de levantar as restrições sobre os padrões de dependência entre variáveis quantificadas. Essa é a rota adotada pela lógica quantificadora ramificada (Henkin 1961), na qual as condições de verdade de ((ref {boygirl2})) correspondem às de

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

e à lógica favorável à independência, na qual ((ref {boygirl2})) é equivalente a

(tag {4} label {boygirl4} begin {align} e / forall x / existe y (boy (x) rightarrow (garota (y) land / amores (x, y) land / \ existe z / x) (boy (z) land {} & / quad x / not = z / land / loves (y, z)))). / end {align})

Não daremos aqui uma explicação detalhada da semântica desses dois formalismos; basta dizer que em ((ref {boygirl3})) o valor de (w) não depende dos valores de (x) e (y) (embora possa depender do valor de (z)), pois pertencem a diferentes “linhas” do quantificador complexo (left (begin {smallmatrix} forall x & / existe y \\ / forall z & / existe w / end {smallmatrix } right)), enquanto em ((ref {boygirl4})) o valor de (z) não depende do valor de (x), porque essa dependência é explicitamente "cortada" pelo quantificador ((existe z / x)).

Uma característica comum à lógica quantificadora ramificada e à lógica amigável à independência, como podemos ver, é que elas não separam a quantificação de variáveis da especificação de padrões de dependência não-padrão: como no caso da lógica de primeira ordem, seja uma quantificada A variável (v_1) dependerá ou não de alguma outra variável quantificada (v_2) será determinada pela respectiva posição e forma de seus quantificadores.

A lógica de dependência adota uma abordagem diferente para o problema de estender a lógica de primeira ordem para representar ((ref {boygirl2})). Comparada com ((ref {eq: boygirl1})), a única condição nova é a que afirma que o valor de (z) é determinado por (ou seja, depende funcionalmente) do valor de (y); e isso corresponde a uma nova condição atômica (eqord (y, z)), chamada átomo de dependência, cujo significado pretendido é que (o valor de) (z) seja uma função do valor de (y). Diferentemente dos casos de lógica quantificadora ramificada ou lógica amigável à independência, essa é uma condição sobre os valores que (y) e (z) podem assumir, não uma condição sobre o comportamento do quantificador (existe z): na verdade, geralmente não há motivos para exigir que (z) seja uma variável quantificada - ela pode muito bem ser uma variável livre,ou algum termo complexo que envolva múltiplas variáveis.

Na lógica da dependência, ((ref {boygirl2})) pode ser formalizado como

(tag {5} label {boygirl5} begin {align} e / forall x / existe y / existe z (eqord (y, z) land (boy (x) rightarrow (girl (y) land / loves (x, y) rightarrow {} & / quad (boy (z) land x / not = z / land / loves (y, z))))) fim {alinhar})

As condições de verdade de ((ref {boygirl2})), ((ref {boygirl3})), ((ref {boygirl4})) e ((ref {boygirl5})) são precisamente os mesmos: qualquer modelo que satisfaça uma dessas expressões (nos respectivos idiomas) satisfaz todas as quatro. Em geral, como veremos, os poderes expressivos da lógica existencial de segunda ordem, lógica amigável à independência e lógica da dependência em relação à definibilidade das classes de modelos são precisamente os mesmos. Este não é, no entanto, o caso de fórmulas com variáveis livres; e, além disso, essas lógicas podem ser estendidas e modificadas ao longo de linhas marcadamente diferentes.

2. Semântica de equipe

A semântica de equipe, desenvolvida pela primeira vez por Wilfrid Hodges no contexto da lógica amigável à independência (Hodges, 1997), é uma generalização da semântica de Tarski para a lógica de primeira ordem no caso de várias atribuições de elementos a variáveis. Conjuntos de tais atribuições, chamados de equipes por razões históricas, constituem a noção semântica fundamental da semântica de equipes, e as fórmulas são satisfeitas ou não com relação a elas e não com designações únicas. A conexão entre a semântica da equipe e a semântica de Tarski é mostrada pelo seguinte resultado, que é válido na lógica de dependência e em todas as suas variantes de primeira ordem:

Conservatividade:

Uma fórmula de primeira ordem é satisfeita por uma equipe (X) (no sentido da semântica da equipe) se e somente se todas as atribuições (s / em X) a satisfizerem (no sentido da semântica de Tarski).

Em geral, as equipes podem ser entendidas como conjuntos de crenças, representando o conjunto de todos os estados do mundo (= atribuições) que algum agente acredita ser possível. Então uma equipe (X) satisfará alguma fórmula (phi) se, e somente se (phi) for mantida quando (X) for o conjunto de todos os estados possíveis; e, neste caso, escreveremos (X / models / phi) (ou (M, X / models / phi) se a escolha do modelo (M) não for clara). Nesta seção, examinaremos as regras da semântica da equipe e sua interpretação em termos desse princípio; então, na próxima seção, discutiremos como ela também surge da semântica da teoria dos jogos com informações imperfeitas para a lógica da dependência.

A condição para os novos átomos de dependência (eqord (x_1 / ldots x_n, y)), que correspondem à afirmação de que o valor de (y) é uma função dos valores de (x_1 / ldots x_n), é facilmente entendido:

TS-dep:

(X / modelos ~ / eqord (x_1 / ldots x_n, y)) se e somente se houver duas atribuições (s_1, s_2 / em X) que concordam com os valores de (x_1 / ldots x_n) também concorda com o valor de (y).

Por exemplo, suponha que (X) seja um conjunto de atribuições sobre as três variáveis (x_1), (x_2) e (y), em que (x_1) representa a nacionalidade de um candidato para uma posição, (x_2) representa sua pontuação (de acordo com um método de avaliação adequado) e (y) representa se eles foram aceitos ou rejeitados. Então o átomo (eqord (x_2, y)) corresponde à afirmação de que a oferta é determinada apenas pela pontuação: se dois candidatos tiverem a mesma pontuação, receberão exatamente a mesma oferta, independentemente de qualquer outro fator. Um caso especial de átomo de dependência é dado pelos átomos de constância (eqord (y)), que - conforme a semântica acima - são satisfeitos por uma equipe se e somente se todas as suas atribuições concordarem com o valor de (y).

(begin {array} {l | ccc} textbf {atribuição} & / 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})

Tabela 1: Uma equipe (X) na qual (y = x_1 + x_2). Aqui (y) é uma função de (x_1) e (x_2) e, portanto, (= \! \! (X_1 x_2, y)) é válida; no entanto, (y) não é uma função de (x_1) sozinho, portanto (= \! \! (x_1, y)) não é válido.

Sob a mesma interpretação, as regras para literais de primeira ordem e conjunções (por simplicidade, assumiremos que nossas expressões estão na forma normal de negação; e, como é habitual, assumiremos que as negações dos átomos de dependência nunca são satisfeitas) são fácil de derivar:

TS-lit:

para todos os literais de primeira ordem (alpha), (X / models / alpha) se e somente se para todas as atribuições (s / em X), (s / models / alpha) no sentido semântico usual de Tarski;

TS - (land):

(X / models / phi / land / psi) se e somente se (X / models / phi) e (X / models / psi).

Vale ressaltar que, como já podemos ver por essas regras, a lei do meio excluído não se aplica à lógica de dependência (assim como não se aplica à lógica amigável à independência): por exemplo, se uma equipe (X) contém as atribuições (s) com (s (x) = s (y)) e as atribuições (s ') com (s' (x) not = s '(y)) então (X / not / models x = y) e (X / not / models x / not = y). Nesta seção, em qualquer caso, apresentaremos a linguagem da lógica de dependência sem um operador de negação explícito; depois, discutiremos as consequências de adicioná-lo ao seu idioma.

E a quantificação universal? Em que circunstâncias uma expressão universalmente quantificada (forall v / psi) deve conter uma equipe? Novamente, devemos lembrar a intuição segundo a qual uma equipe representa um conjunto de possíveis estados de coisas. Se desejamos avaliar (forall v / psi), com relação a quais possíveis estados de coisas devemos avaliar (psi)? A resposta natural é que devemos considerar todos os estados de coisas que diferem daqueles em (X) apenas com relação ao valor de (v). Isso justifica a seguinte regra:

TS - (forall):

(X / models / forall v / psi) se e somente se (X [M / v] models / phi), onde (X [M / v]) é o conjunto ({s ': / existe s / na X / mbox {st} s' / sim_v x })

onde (s '\ sim_v s) significa que as duas atribuições (s) e (s') diferem uma da outra no máximo em relação ao valor da variável (v).

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

Tabela 2: (X) e (X [M / y]) em um modelo com dois elementos (0) e (1).

Vamos agora considerar a disjunção. Quando deve (phi / lor / psi) aguentar? Para responder a isso, lembremos, mais uma vez, que as equipes podem ser entendidas como conjuntos de possíveis estados de coisas e que, portanto, a união de duas equipes (Y) e (Z) representa todos os estados de coisas que podem ocorrer se (Y) ou (Z) for o caso. Portanto, se as duas fórmulas (phi) e (psi) forem atendidas pelo conjunto de equipes ({Y_1 / ldots Y_n, / ldots }) e ({Z_1 / ldots Z_n, / ldots }), respectivamente, sua disjunção (phi / lor / psi) deve ser satisfeita pelo conjunto de equipes ({Y_i / cup Z_j: i, j / in 1, / ldots }), ou equivalente,

TS - (lor):

(X / models / phi / lor / psi) se e somente se (X = Y / cup Z) para duas equipes (Y) e (Z) tal que (Y / models / phi) e (Z / models / psi).

Vale ressaltar aqui que não exigimos, em geral, que (Y) e (Z) sejam disjuntos. Devido à propriedade de fechamento descendente, que discutiremos em breve, essa condição adicional não faria diferença para a semântica da lógica de dependência; mas, no caso de certas extensões e variantes da lógica da dependência, esse requisito adicional entraria em conflito com o princípio da localidade, segundo o qual as condições de satisfação de uma expressão dependem apenas dos valores das variáveis que ocorrem livres nela (Galliani 2012).

Também é importante observar que, na lógica da dependência, a disjunção não é idempotente: por exemplo, (eqord (x, y) lor / eqord (x, y)) não é equivalente a (eqord (x, y)) e é satisfeita por uma equipe (X) se e somente se a cada três atribuições em (X) que concordam com (x) pelo menos duas concordam com (y). Isso pode parecer um pouco contra-intuitivo; mas é uma conseqüência direta do fato de que, sob nossa interpretação, (eqord (x, y) lor / eqord (x, y)) deve ser lido como “todo estado possível de coisas provém de um dois conjuntos de estados de coisas e em ambos (y) é uma função de (x)”. Como a união de funções não é, em geral, uma função, surpreende que a disjunção na lógica da dependência não seja indempotente.

Finalmente, consideramos o caso da quantificação existencial. Quando a expressão (existe v / psi) é satisfeita por uma equipe? Para responder a isso, podemos começar considerando a interpretação do operador de restrição que, dada qualquer equipe (X), resulta na equipe (X _ { barra invertida v}) obtida com a remoção da variável (v) (se presente) de todas as atribuições (s / em X) (e depois, como (X) é um conjunto, recolhendo atribuições idênticas). Isso pode ser entendido como uma operação de esquecimento, através da qual excluímos todas as informações sobre o valor de (v) - por exemplo, porque o que acreditávamos sobre esse valor não era confiável ou porque esse valor foi alterado. Agora, suponha que (X _ { barra invertida v} = Y _ { barra invertida v}): então, em nossa interpretação,isso significa que os conjuntos de possíveis estados de coisas representados por (X) e (Y) discordam no máximo em relação ao valor de (v). Assim, se (Y) satisfaz a condição (phi), podemos dizer que (X) satisfaria (phi) se não fosse o valor de (y) ou, equivalente, que (X) satisfaz (existe v / psi). Isso justifica a seguinte regra:

TS - (existe):

(X / modelos / existe v / psi) se e somente se houver algum (Y), sobre as variáveis de (X) e (v), tal que (X _ { barra invertida v} = Y _ { barra invertida v}) e (Y / modelos / psi).

É fácil verificar se esse é o caso se e somente se (Y) tiver a forma (X [F / a] = {s [a / a]: s / em X, a / em F (s) }) para alguma função (F) de atribuições em (X) a conjuntos de elementos não vazios de nosso modelo.

Vale ressaltar aqui que, em geral, não é exigido pela definição acima que (X) e (Y) contenham o mesmo número de atribuições: uma única atribuição em (X) pode muito bem corresponder a múltiplos atribuições em (Y) e -se (v) já é uma variável que ocorre nas atribuições de (X) - uma única atribuição em (Y) também pode corresponder a várias atribuições em (X).

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

Tabela 3: (X) e (X [F / y]) para (F (s_0) = {0,1 }), (F (s_1) = {0 })

Adiaremos uma discussão aprofundada das propriedades da lógica da dependência para depois da especificação de sua semântica da teoria dos jogos. No entanto, concluímos esta seção com as três consequências importantes a seguir das regras mencionadas acima:

Localidade:

Se as restrições de (X) e (Y) para as variáveis que ocorrem livres em (phi) forem as mesmas, então (X / models / phi) se e somente se (Y / modelos / phi).

Fechamento para baixo:

Se (X / models / phi) e (Y / subseteq X) então (Y / models / phi).

Propriedade do conjunto vazio:

se (emptyset) for a equipe que não contém atribuições, (emptyset / models / phi) para todas as fórmulas de lógica de dependência (phi).

O princípio da localidade, juntamente com o princípio da conservatividade mencionado no início desta seção, constitui uma importante “condição de sanidade” que qualquer variação e extensão da lógica de dependência deve satisfazer. O mesmo não pode ser dito sobre o fechamento descendente e a propriedade set vazia, que, como veremos, é violada por variantes da lógica de dependência.

Finalmente, precisamos definir a verdade de uma sentença lógica de dependência em relação a um modelo. Como uma sentença não possui variáveis livres, pelo princípio da localidade, temos de imediato que todas as equipes não vazias a satisfazem ou nenhuma equipe não vazia a satisfaz. Isso é análogo ao caso da semântica de Tarski, em que uma sentença é satisfeita por todas as atribuições de variáveis ou por nenhuma delas. Assim, podemos definir a verdade da maneira usual:

Verdade na semântica da equipe:

uma frase (phi) é verdadeira em um modelo (M) se e somente se (M, { emptyset } models / phi), onde ({ emptyset }) é a equipe que contém apenas a atribuição vazia. Nesse caso, escrevemos isso (M / models / phi).

2.1 Semântica teórica dos jogos

Como mencionado, a semântica da teoria dos jogos para a lógica da dependência é uma variante da semântica de informações imperfeitas para a lógica favorável à independência, que é ela própria uma adaptação da semântica da teoria dos jogos da lógica de primeira ordem. Referimos o leitor a Väänänen 2007a para uma definição formal e detalhada dessa semântica.

Na semântica da teoria dos jogos, uma sentença (phi) e um modelo (M) são feitos para corresponder a um jogo (geralmente para dois jogadores) (G_M (phi)). Então a verdade é definida em termos da existência de estratégias vencedoras para um dos jogadores (que, neste trabalho, será chamado simplesmente de "Jogador (0)"): em outras palavras, se (sigma_0) for uma estratégia (possivelmente não determinística) para Player (0) e (Pi (G_M (phi), / sigma_0)) é o conjunto de todas as jogadas compatíveis com (sigma_0) e depois (phi) é verdadeiro se e somente se todas as jogadas em (Pi (G_M (phi), / sigma_0)) estiverem vencendo para o jogador (0). É possível pensar no jogo (G_M (phi)) como um debate entre dois jogadores, um dos quais (Player (0)) deseja demonstrar que é esse o caso (phi) enquanto o outro (Jogador (1)) deseja demonstrar que não é esse o caso (phi).

Como no caso da lógica de primeira ordem e da lógica favorável à independência, no jogo de informações imperfeitas para a lógica de dependência, as posições do jogo são pares ((theta, s)), onde (theta) é uma instância de uma sub-fórmula de (phi) (ou seja, múltiplas ocorrências da mesma expressão que uma sub-fórmula de (phi) deve ser considerada separadamente) e (s) é uma atribuição variável sobre o modelo (M). [1] A posição inicial é ((phi, / emptyset)), onde (emptyset) é a atribuição vazia; e uma estratégia não determinística (sigma_0) para Player (0) seleciona, para cada disjunção e quantificação existencial, um ou mais sucessores da posição atual de acordo com as seguintes regras:

  • Se a posição atual é da forma ((psi / lor / theta, s)), seus sucessores são ((psi, s)) e ((theta, s));
  • Se a posição atual tiver a forma ((existe v / psi, s)), seus sucessores serão todas as posições ((psi, s ')) com (s' / sim_v s).

Da mesma forma, os sucessores de ((psi / land / theta, s)) são ((psi, s)) e ((theta, s)) e os sucessores de ((forall v / psi, s)) são todas as posições da forma ((psi, s ')) para (s' / sim_v s); mas uma estratégia para o Player (0) não pode especificar um sucessor para essas posições, pois supõe-se que o Player (1) escolha qual posição as segue.

Uma sequência de posições (overline / rho = / rho_0 / rho_1 / ldots / rho_n) é uma jogada de (G_M (phi)) se e somente se

  1. (rho_0 = (phi, / conjunto vazio));
  2. Para todos (i = 1 / ldots n), (rho_ {i}) é um sucessor de (rho_ {i-1}).

Se além disso (rho_ {i + 1} in / sigma_0 (rho_i)) sempre que (rho_i) corresponda a uma disjunção ou a um quantificador existencial, dizemos que (overline / rho) respeita o estratégia (sigma_0); e, como mencionado, escrevemos (Pi (G_M (phi), / sigma_0)) para o conjunto de todas as jogadas sobre (G_M (phi)) que respeitam (sigma_0).

Dizemos que uma estratégia (sigma_0) está ganhando se toda jogada (overline / rho) que termina em uma posição ((alpha, s)) onde (alpha) é a primeira literal de ordem é tal que a atribuição (s) satisfaz (alpha) no sentido usual da semântica de Tarski. Átomos de dependência - e as jogadas que terminam em átomos de dependência - não têm relevância para decidir se uma determinada estratégia está ganhando. No entanto, eles são usados para especificar se uma determinada estratégia é uniforme:

Condição de uniformidade

Uma estratégia (sigma_0) para (G_M (phi)) é uniforme se houver duas jogadas (overline / rho, / overline / gamma / in / Pi (G_M (phi), / sigma_0)) que terminam em duas posições ((eqord (x_1 / ldots x_n, y), s)), ((eqord (x_1 / ldots x_n, y), s ')) para a mesma instância do átomo de dependência (eqord (x_1 / ldots x_n, y)) temos esse

(textrm {Se} s (x_1) ldots s (x_n) = s '(x_1) ldots s' (x_n) textrm {então} s (y) = s '(y).)

Então, podemos definir a verdade na semântica da teoria dos jogos da seguinte maneira:

Verdade na semântica da teoria dos jogos:

Uma frase (phi) é verdadeira em um modelo (M) (com relação à semântica da teoria dos jogos) se e somente se o Player (0) tiver uma estratégia de vitória uniforme em (G_M (phi)).

Pode-se mostrar que essa noção é equivalente à noção de verdade na semântica da equipe. De fato, podemos mostrar mais do que isso. Se, para qualquer equipe (X) e fórmula (phi), o jogo (G_ {M, X} (phi)) for jogado como (G_M (phi)), mas com o posição inicial escolhida aleatoriamente para cada jogada de ({(phi, s): s / em X }), o seguinte é válido:

Equivalência de GTS e semântica da equipe:

Uma fórmula (phi) é satisfeita por uma equipe (X) (com relação a um modelo (M)) se e somente se o jogador (0) tiver uniforme estratégia vencedora em (G_ {M, X} (phi)).

Esse resultado, como um aparte, deixa claro por que a semântica da equipe da lógica de dependência satisfaz a propriedade de conjunto vazia e a propriedade de fechamento para baixo. De fato, se (X = / emptyset), então toda estratégia para o Jogador (0) em (G_ {M, X} (phi)) é trivialmente vencedora e uniforme; e se (X / subseteq Y), qualquer estratégia de vitória uniforme para o Player (0) em (G_ {M, X} (phi)) também é uma estratégia de vitória uniforme para o Player (0) em (G_ {M, Y} (phi)).

3. Propriedades

3.1 Expressividade

Em termos de sentenças, a lógica de dependência é equivalente ao fragmento existencial (Sigma_1 ^ 1) da lógica de segunda ordem. Mais precisamente, pode-se provar (Väänänen 2007a) que

Equivalência em termos de sentença da lógica de dependência e (Sigma_1 ^ 1):

para cada sentença da lógica de dependência (phi) existe uma (Sigma_1 ^ 1) sentença (phi ^ *) de modo que

(tag {6} label {eq: DLESO} M / models / phi / Leftrightarrow M / models / phi ^ * / textrm {para todos os modelos} M.)

Da mesma forma, para cada (Sigma_1 ^ 1) sentença (phi ^ *) existe uma sentença lógica de dependência (phi) tal que ((ref {eq: DLESO})) é válida.

Como o Teorema de Fagin (Fagin 1974) mostra que uma propriedade de modelos finitos é definível em (Sigma_1 ^ 1) se e somente se for reconhecível no tempo polinomial por uma máquina de Turing não determinística (isto é, se e somente se for em NPTIME), segue-se imediatamente que

Lógica de dependência e NPTIME:

Para qualquer sentença lógica de dependência (phi), a classe de todos os modelos finitos que a satisfazem está em NPTIME. Além disso, para qualquer classe NPTIME (mathcal K) de modelos finitos, existe uma frase lógica de dependência (phi) tal que (M / models / phi) se e somente se (M / in / mathcal K).

Outra conseqüência direta da equivalência entre lógica de dependência e (Sigma_1 ^ 1) no nível das sentenças é que o teorema da compactação e o teorema de Löwenheim-Skolem também se aplicam à lógica da dependência (Väänänen 2007a):

Compacidade:

Se um conjunto (Phi) de sentenças de lógica de dependência finita não é satisfatório em nenhum modelo, algum subconjunto finito (Phi_0 / subseteq_f / Phi) já não é satisfatório.

Teorema de Löwenheim-Skolem:

Se uma sentença lógica de dependência possui um modelo infinito, possui modelos de todas as cardinalidades infinitas.

No entanto, os assuntos são mais delicados quando se trata de fórmulas com variáveis livres. Então é possível mostrar (Kontinen & Väänänen 2009) que a lógica de dependência corresponde ao fragmento fechado para baixo da lógica existencial de segunda ordem:

Definibilidade da equipe na lógica de dependência

Um conjunto (mathcal X) de equipes sobre um modelo (M) e um conjunto (V) de variáveis tem a forma ({X: M, X / models / phi }) para alguma fórmula lógica de dependência (phi), com variáveis livres em (V), se e somente se

  1. (mathcal X) não é vazio;
  2. (mathcal X) está fechado para baixo, ou seja, (Y / subseteq X / em / mathcal X / Rightarrow Y / em / mathcal X);
  3. (mathcal X) é (Sigma_1 ^ 1) - definível em (M), ou seja, existe uma (Sigma_1 ^ 1) frase (Psi (R)), sobre o vocabulário (M) mais o novo símbolo de relação (| V |) - ário (R), de modo que

    [X / in / mathcal X / textrm {se e somente se} M, / textrm {Rel} (X) modelos / Psi (R))

    onde (textrm {Rel} (X)) é a relação (| V |) - ária ({s (V): s / em X }) que corresponde à equipe (X).

3.2 Hierarquias na lógica de dependência

Em Durand & Kontinen 2012, foi examinado o efeito de restringir o número de variáveis dependentes de átomos de dependência ou o número de quantificadores universais. Foi demonstrado que essas duas formas de definir fragmentos da lógica de dependência dão origem a hierarquias:

  • Para todos (k), seja (mathcal D (k- / forall)) a lógica de dependência restrita a no máximo (k) quantificadores universais e let (mathcal D (k-dep)) seja lógica de dependência restrita a átomos de dependência no formato (eqord (vec x, y)) para (| / vec x | / leq k). Então

    (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 *})

    e

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

    no que diz respeito ao poder expressivo das sentenças.

3.3 Negação na lógica da dependência

Até agora, assumimos que todas as expressões lógicas de dependência estão na forma normal de negação e que os átomos de dependência nunca são negados. Adicionar um operador de negação explícito à linguagem da lógica de dependência, por outro lado, é um tanto problemático, devido ao fato de que a lógica existencial de segunda ordem não é fechada sob negação. De fato, a regra de negação "óbvia"

[X / models / sim / phi / textrm {se e somente se} X / not / models / phi)

aumenta muito o poder expressivo da lógica da dependência, estendendo-o à lógica da equipe (Väänänen 2007a, b), que é, em um sentido muito forte, equivalente à lógica de segunda ordem completa (Kontinen & Nurmi 2009).

Uma negação "dupla" menos forte (lnot) pode ser definida em termos das regras de Morgan, (lnot (phi / lor (land] psi) equiv (lnot / phi) land (lor] (lnot / psi)) e (lnot (existe v (forall v] phi) equiv / forall v (existe v] (lnot / phi)), mais o lei da dupla negação (lnot / lnot / phi / equiv / psi) e a regra

[X / models { lnot / eqord} (vec x, y) textrm {se e somente se} X = / emptyset)

para negações de átomos de dependência (Väänänen 2007a, b). A linguagem resultante é expressivamente equivalente à lógica de dependência sem negação e, de fato, a descrição da lógica de dependência de Väänänen 2007a considera essa negação como parte de sua linguagem; no entanto, como mostrado em Kontinen & Väänänen 2011, as condições de satisfação de uma fórmula lógica de dependência e as de sua negação têm pouca conexão entre si. Mais precisamente:

Lógica dupla de negação e dependência:

para quaisquer duas fórmulas lógicas de dependência (phi) e (psi) tais que (phi / land / psi) não sejam satisfatórias, existe uma fórmula de lógica de dependência (theta) tal que

[M, X / models / theta / textrm {se e somente se} M, X / models / phi)

e

[M, X / models / não / theta / textrm {se e somente se} M, X / models / psi)

para todos os modelos (M) e equipes (X).

Assim, nada em geral pode ser dito sobre a dupla negação de (phi), exceto que é equivalente a alguma expressão lógica de dependência que não é satisfeita por nenhuma equipe que satisfaça (phi). Como, como já mencionado, a lei do meio excluído falha na lógica da dependência, essa não é uma propriedade muito informativa; em particular, é possível encontrar na lógica de dependência (com dupla negação) expressões equivalentes com negações não equivalentes, como por exemplo (x / not = x / land y / not = y) e (lnot / eqord (x, y)).

3.4 Sistemas de verdade, validade e prova na lógica da dependência

Como a lógica amigável à independência, a lógica da dependência pode definir seu próprio operador de verdade (Väänänen 2007a), isto é, se para todas as fórmulas (phi) tivermos que (lceil / phi / rceil) é o número de Gödel de (phi), podemos encontrar uma fórmula (tau (x)), com (x) como sua única variável livre, de modo que

[M / models / phi / textrm {se e somente se} M / models / tau (lceil / phi / rceil))

para todos os modelos (M) que satisfazem os axiomas de Peano para números naturais. Isso não está em contradição com o teorema da indefinibilidade de Tarski, porque a lógica da dependência não é fechada sob negação contraditória.

O problema de decidir se uma sentença lógica de dependência é válida (ou seja, verdadeira em todos os modelos) é não aritmético e, de fato, completo com relação à classe (Pi_2) da hierarquia de Levy. No entanto, a teoria da prova da lógica da dependência foi estudada. Em particular, em Kontinen & Väänänen 2013, um sistema de prova completo e sólido foi desenvolvido para o problema de encontrar as consequências de primeira ordem de uma teoria da lógica de dependência.

4. Variantes da lógica de dependência

Nesta seção, resumiremos brevemente as propriedades das variantes mais estudadas da lógica de dependência. Existem muitas dessas variantes e muito trabalho foi feito em sua classificação e comparação. Neste trabalho, mencionaremos apenas as variantes que têm significado especial por causa de sua relação com a lógica de dependência propriamente dita.

4.1 Lógica da Independência

Em vez de estender a lógica de primeira ordem com átomos de dependência (eqord (vec x, y)), a lógica da independência (Grädel & Väänänen 2013) a estende com átomos de independência (vec x / mathop { bot _ { vec z }} vec y), cuja interpretação pretendida é "para qualquer opção possível de (vec z), os valores possíveis de (vec x) e (vec y) são independentes" -em por outras palavras, dada qualquer opção fixa de (vec z), o conhecimento do valor obtido por (vec x) não transmitiria nenhuma informação sobre o valor obtido por (vec y). Essa é uma noção de importância conceitual significativa: por exemplo, pode-se querer expressar que, se não se conhece a chave de criptografia, ver a versão criptografada de uma mensagem não traz informações sobre a versão em texto não criptografado correspondente. Se (x) representa a mensagem criptografada e (y) representa a mensagem em texto sem formatação,então isso corresponde à condição (x / mathop { bot} y), onde (vec z) nesse caso está vazio. Da mesma forma, se (k) representa a chave, (x / mathop { bot} k) representa a alegação de que a chave não pode ser inferida a partir da mensagem criptografada; e a dependência conjunta atom (eqord (k, x, y)) (que, como veremos em breve, pode ser representada na lógica da independência) representa a alegação de que a mensagem de texto sem formatação pode ser decodificada, dada a mensagem criptografada e a chavepode ser representado na lógica da independência) representa a alegação de que a mensagem de texto sem formatação pode ser decodificada, dada a mensagem criptografada e a chave.pode ser representado na lógica da independência) representa a alegação de que a mensagem de texto sem formatação pode ser decodificada, dada a mensagem criptografada e a chave.

Formalmente, a regra de satisfação para os átomos de independência pode ser dada da seguinte maneira:

TS-indep:

(M / models_X / v x x mathop { bot _ { vec z}} v y) se e somente se for para todos (s, s '\ em X) com (s (vec z) = s '(vec z)) existe um (s' '\ em X) com (s' '(vec z \, / vec x) = s (vec {x }, / vec {z})) e (s '' (vec y) = s '(vec y)).

(begin {array} {l | ccc} textbf {atribuição} & / mathbf {x_1} & / mathbf {x_2} & / mathbf {x_3} / \ hline s_0 & 0 & 0 & 0 / 0 s_1 & 0 & 1 & 1 \\ s_2 & 1 & 0 & 1 \\ s_3 & 1 & 1 & 0 / end {array})

A lógica da independência é estritamente mais expressiva que a lógica da dependência: na verdade, ela não possui a propriedade de fechamento para baixo, e o átomo de dependência (eqord (vec x, y)) é equivalente ao átomo de independência (y / mathop { bot_ { vec x}} y). Além disso, também pode ser demonstrado (Galliani & Väänänen 2014) que átomos de independência condicionados (vec x / mathop { bot _ { vec y}} vec z) podem ser definidos em termos de átomos de independência incondicional (vec x / mathop { bot} vec y).

Em termos de sentença, a lógica de independência também é equivalente à lógica existencial de segunda ordem (Sigma_1 ^ 1); mas em termos de fórmula, é mais expressivo e foi mostrado na Galliani 2012 que ele pode capturar todas as propriedades de equipe definíveis não vazias (Sigma_1 ^ 1).

4.2 Lógica de inclusão

A lógica de inclusão (Galliani 2012, Galliani & Hella 2013) estende a lógica de primeira ordem com átomos de inclusão (vec x / subseteq / vec y), remanescente das dependências de inclusão da teoria de banco de dados. Sua semântica é:

TS-inc:

(M / models_X / v x x subseteq / v y) se e somente se para todos (s / em X) existir um (s '\ em X) tal que (s (vec x) = s '(vec y)).

(begin {array} {l | cc} textbf {atribuição} & / mathbf {x_1} & / mathbf {x_2} / \ hline s_0 & 0 & 0 / 0 \\ s_1 & 0 & 1 \\ s_2 & 1 & 2 \\ s_3 & 2 & 3 / final {matriz})

Diferentemente da lógica de dependência e independência, a lógica de inclusão é (em termos de sentenças) estritamente mais fraca que a lógica existencial de segunda ordem. De fato, pode ser demonstrado (Galliani & Hella 2013) como equivalente ao fragmento positivo da maior lógica de ponto fixo e, portanto, capturar propriedades PTIME de modelos sobre modelos finitos ordenados. Em termos de fórmula, a lógica de inclusão é estritamente mais fraca que a lógica da independência, mas incomparável com a lógica da dependência: de fato, as condições de satisfação de suas fórmulas não são fechadas para baixo, mas são fechadas por sindicatos no sentido de que

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

4.3 Lógica da equipe

A lógica da equipe (Väänänen 2007a, b; Kontinen & Nurmi 2009) estende a lógica da dependência, adicionando a ela uma negação contraditória (lnot). É equi-expressivo com lógica de segunda ordem completa, tanto em termos de definibilidade de classes de modelos (Väänänen 2007b) quanto em relação às classes de equipes que expressões lógicas de equipe podem definir em relação a um determinado modelo (Kontinen & Nurmi 2009).

4.4 Lógica de dependência intuicionista

A lógica da dependência intuicionista (Abramsky & Väänänen 2009; Yang 2013) estende a lógica da dependência adicionando uma implicação conectiva (phi / rightarrow / psi), cujas regras de satisfação são dadas na semântica da equipe por

TS - (rightarrow):

(X / models / phi / rightarrow / psi) se e somente se para todos os subconjuntos (Y) de (X), se (Y / models / phi) então (Y / models / psi).

Esse operador é chamado de "implicação intuicionista", devido à semelhança entre sua semântica e a do operador de implicação na semântica de Kripke para a lógica intuicionista (Kripke, 1965). Sua interpretação em termos de crença é bastante direta: se as atribuições em (X) representam os estados que um agente acredita ser possível, um subconjunto (Y) de (X) pode representar o resultado de um uma atualização de crença na qual o agente rejeita alguns estados possíveis anteriormente considerados e (phi / rightarrow / psi) afirma que qualquer atualização que faria com que (phi) permanecesse também causaria (psi) segurar. Desse ponto de vista, esse é um conceito muito natural que nos permite descrever previsões sobre como o estado geral de crença de um agente reagiria às atualizações de crenças.

No entanto, devido à quantificação universal de segunda ordem implícita em sua semântica, esse conectivo é suficiente para aumentar bastante a complexidade expressiva da lógica: em particular, como mostrado em Yang 2013, qualquer sentença de lógica de segunda ordem é equivalente a alguma sentença de dependência intuicionista lógica. A lógica de dependência intuicionista mantém a propriedade de fechamento para baixo: se uma equipe satisfaz uma fórmula de lógica de dependência intuicionista, o mesmo ocorre com todos os seus subconjuntos.

4.5 Lógica de dependência proposicional

Os átomos de dependência e independência considerados até agora expressam relações entre os possíveis valores de variáveis em um conjunto de atribuições. No entanto, as mesmas noções de dependência e independência podem ser igualmente naturalmente aplicadas à proposição, como ocorre na expressão da linguagem natural, como por exemplo: "Se ele vai ou não passar no curso depende apenas do conteúdo de seu exame final".

A lógica de dependência proposicional considera esses átomos no contexto da lógica proposicional. As equipes de lógica de dependência proposicional são conjuntos de avaliações (v) de átomos proposicionais (p_1 / pontos p_n) a ({T, F }). Suas regras semânticas - e suas justificativas - refletem muito de perto as da semântica de equipe de primeira ordem, e a regra para átomos de dependência é

PTS-dep:

(X / models / eqord (p_1 / ldots p_n, q)) se e somente se houver duas avaliações (v_1, v_2 / em X) que concordam com os valores de (p_1 / ldots p_n) também concorda com o valor de (q).

Muitas das variantes e generalizações da lógica de dependência de primeira ordem podem ser reduzidas ao nível proposicional sem nenhuma dificuldade: assim, por exemplo, é possível estudar as propriedades da lógica de inclusão proposicional, lógica da equipe proposicional, lógica da dependência intuicionista proposicional e assim por diante..

Enquanto a lógica de dependência (de primeira ordem) é estritamente mais expressiva que a lógica de primeira ordem, a lógica de dependência proposicional não é mais expressiva que a lógica proposicional, pois decorre imediatamente do fato de que todas as funções proposicionais são expressáveis na lógica proposicional. Existe, no entanto, uma estreita relação entre as equipes de lógica de dependência proposicional e os estados de informação da lógica inquisitiva (Groenendijk 2009; Ciardelli & Roelofsen 2011), uma estrutura semântica para o estudo da noção de significado e troca de informações: em particular, a implicação da lógica inquisitiva é exatamente a mesma da lógica da dependência intuicionista proposicional.

Axiomatizações para lógica de dependência proposicional e muitas de suas extensões podem ser encontradas em Yang & Väänänen 2016.

4.6 Lógica de dependência modal

A lógica de dependência modal (Väänänen 2008) e suas variantes estendem a lógica modal adicionando a ela os mesmos átomos de dependência (eqord (p_1 / ldots p_n, q)) já considerados no caso da lógica de dependência proposicional.

Suas condições de satisfação podem ser definidas através de uma variante da semântica de equipes, na qual as equipes são substituídas por conjuntos de mundos possíveis.

Muita pesquisa investigou as propriedades teóricas da complexidade dessa lógica, de seus fragmentos e suas extensões (Ebbing, Lohmann & Yang 2011; Ebbing & Lohmann 2012; Lohmann & Vollmer 2013).

5. Aplicações da lógica de dependência

5.1 Lógica de dependência e teoria de banco de dados

Existe uma conexão direta entre as equipes da semântica de equipes e as relações estudadas na teoria dos bancos de dados relacionais: dada uma equipe (X) e uma tupla de variáveis (vec v = v_1 / ldots v_k) ocorrendo em suas atribuições, é possível definir a relação (X (vec v) = { langle s (v_1), / ldots, s (v_n) rangle: s / em X }). Além disso, os átomos de dependência estudados na lógica de dependência e suas variantes são análogos a - e, em muitos casos, derivados de - dependências consideradas na teoria de bancos de dados, como dependências funcionais (Väänänen 2007a), dependências com vários valores (Engström 2012) e dependências de inclusão e exclusão (Galliani 2012). A relação entre lógica de dependência e teoria de banco de dados contribuiu não apenas para o desenvolvimento posterior da lógica de dependência, mas também para a teoria de banco de dados: por exemplo,em Hannula & Kontinen 2016, foi encontrada uma axiomatização finita do problema de implicação irrestrita para inclusão, dependência teórica de banco de dados com múltiplos valores funcionais e incorporados através do estudo de um problema semelhante no contexto da semântica de equipes.

5.2 Lógica de dependência e representação de crenças

Conforme discutido em Yang 2014 e Yang & Väänänen 2016, existe uma estreita conexão entre a lógica de dependência intuicionista (proposicional) e a lógica inquisitiva (Ciardelli & Roelofsen, 2011), uma estrutura para o estudo da troca de significado e informação entre agentes. De maneira geral, os átomos de dependência e os conectivos estudados na semântica de equipes admitem interpretações naturais em termos de estados de crença e atualizações de crença, conforme discutido em Galliani 2015. Atualmente, a natureza exata da relação entre essas lógicas e a lógica dinâmico-epistêmica. e suas variantes (Van Ditmarsch, van Der Hoek e Kooi 2007) são amplamente inexploradas, mas há amplas razões para suspeitar de novas conexões entre essas duas áreas da lógica matemática e filosófica.

5.3 Lógica de dependência e teorema de Arrow

O teorema de Arrow (Arrow 1950) é um resultado profundamente influente da teoria da escolha social que, resumidamente, mostra que não existe um sistema de votação (ou seja, nenhum sistema para converter classificações de preferências individuais entre alternativas em uma classificação global de preferências no nível social) que pode satisfazer três condições razoáveis, a saber:

  • Se todo eleitor preferir (A) a (B), o grupo como um todo prefere (A) e (B);
  • Se o grupo como um todo prefere (A) a (B) ou vice-versa depende exclusivamente das preferências de todo eleitor em relação a (A) e (B), e não de suas preferências em relação a outras alternativas possíveis;
  • Nenhum eleitor é um ditador, ou seja, as preferências do grupo não são determinadas pelas preferências de um único eleitor.

Como a própria redação sugere, a segunda e terceira condições admitem uma leitura natural em termos de dependência e independência: de fato, como mostrado em Pacuit & Yang 2016, o teorema de Arrow pode ser formalizado na lógica da independência e comprovado em um sistema de dedução natural adequado.

5.4 Lógica quântica de equipe e desigualdades de Bell

Em Hyttinen, Paolini e Väänänen 2015, é introduzida uma variante da lógica de equipe proposicional, chamada lógica de equipe quântica. Nesse formalismo, as equipes são substituídas por equipes quânticas, que diferem das equipes comuns da lógica proposicional das equipes, pois permitem que os valores de certas variáveis sejam indeterminadas em relação a determinadas avaliações e que permitem múltiplas instâncias da mesma avaliação (adicionando assim um aspecto quantitativo à semântica da equipe). Uma semântica é então definida sobre equipes quânticas para uma linguagem que permite a especificação de desigualdades em relação às probabilidades de eventos, e um sistema de prova completo e sólido é desenvolvido para ela; e, finalmente, mostra-se que as desigualdades de Bell admitem contra-exemplos nesses sistemas,como fazem de acordo com as previsões da mecânica quântica e de acordo com as evidências experimentais (Einstein, Podolsky e Rosen 1935; Bell 1964; Aspect, Grangier e Roger 1981), embora não o façam na versão clássica desse quadro.

Bibliografia

  • Abramsky, Samson e Jouko Väänänen, 2009, “From IF to BI: A Tale of Dependence and Separation”, Synthese, 167 (2): 207-230. doi: 10.1007 / s11229-008-9415-6
  • Arrow, Kenneth J., 1950, “Uma Dificuldade no Conceito de Bem-Estar Social”, The Journal of Political Economy, pp.328-346. doi: 10.1086 / 256963
  • Aspect, Alain, Philippe Grangier e Gérard Roger, 1981, "Testes experimentais de teorias locais realistas via teorema de Bell", Physical Review Letters, 47 (7): 460–463. doi: 10.1103 / PhysRevLett.47.460
  • Bell, JS, 1964, “On the Einstein-Podolsky-Rosen Paradox”, Physics, 1 (3): 195–200.
  • Ciardelli, Ivano e 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 e Barteld Kooi, 2007, Dynamic Epistemic Logic, (Synthese Library 337), Dordrecht: Springer. doi: 10.1007 / 978-1-4020-5839-4
  • Durand, Arnaud e Juha Kontinen, 2012, “Hierarquias na lógica de dependência”, Transações da ACM na lógica computacional (TOCL), 13 (4): 1–21. doi: 10.1145 / 2362355.2362359
  • Ebbing, Johannes e Peter Lohmann, 2012, “Complexidade da verificação de modelos para a lógica de dependência modal”, SOFSEM 2012: Conferência Internacional sobre Tendências Atuais em Teoria e Prática da Ciência da Computação (Notas da Palestra em Ciência da Computação, 7147), Berlim, Heidelberg: Springer, pp. 226–237. doi: 10.1007 / 978-3-642-27660-6_19
  • Ebbing, Johannes, Peter Lohmann e Fan Yang, 2013, “Model Checking for Modal Dependency Intuitionistic Logic Dependence”, Simpósio Internacional de Tbilisi sobre Lógica, Linguagem e Computação 2011, (Notas de Palestra em Ciência da Computação, 7758), Berlim, Heidelberg: Springer 231–256. doi: 10.1007 / 978-3-642-36976-6_15
  • Einstein, A., B. Podolsky e N. Rosen, 1935, "A Descrição Mecânica Quântica da Realidade Física pode ser considerada completa?" Physical Review, 47 (10): 777-780. doi: 10.1103 / PhysRev.47.777
  • Engström, Fredrik, 2012, “Quantificadores generalizados em lógica de dependência”, Journal of Logic, Language and Information, 21 (3): 299–324. doi: 10.1007 / s10849-012-9162-4
  • Fagin, Ronald, 1974, "Espectros generalizados de primeira ordem e conjuntos reconhecíveis no tempo polinomial", Complexidade da computação (SIAM-AMS Proceedings 7), Richard M. Karp (ed.), Providence, RI: American Mathematics Society, pp. 27-41.
  • Galliani, Pietro, 2012, “Dependências de inclusão e exclusão na equipe semântica - em algumas lógicas de informações imperfeitas”, Annals of Pure and Applic Logic, 163 (1): 68–84. doi: 10.1016 / j.apal.2011.08.005
  • –––, 2015, “The Doxastic Interpretation of Team Semantics”, Lógica Sem Fronteiras: Ensaios sobre Teoria dos Conjuntos, Teoria dos Modelos, Lógica Filosófica e Filosofia da Matemática (Ontos Mathematics Logic, 5), Åsa Hirvonen, Juha Kontinen, Roman Kossak, e Andrés Villaveces (eds), Berlim, Boston: De Gruyter, pp. 167-192. doi: 10.1515 / 9781614516873.167
  • Galliani, Pietro e Lauri Hella, 2013, “Lógica de Inclusão e Lógica de Ponto Fixo”, Computer Science Logic 2013 (Procedimentos Internacionais de Informática de Leibniz (LIPIcs), 23), Dagstuhl, Alemanha: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 281-295. doi: 10.4230 / LIPIcs. CSL.2013.281
  • Galliani, Pietro e Jouko Väänänen, 2014, “On Dependence Logic”, em Johan van Benthem sobre lógica e dinâmica da informação (contribuições destacadas para a lógica, 5), Alexandru Baltag e Sonja Smets (eds), Cham: Springer, pp. 101– 119 doi: 10.1007 / 978-3-319-06025-5_4
  • Grädel, Erich e Jouko Väänänen, 2013, “Dependence and Independence”, Studia Logica, 101 (2): 399–410. doi: 10.1007 / s11225-013-9479-2
  • Groenendijk, Jeroen, 2009, “Semântica Inquisitiva: Duas Possibilidades de Disjunção”, em Peter Bosch, David Gabelaia e Jérôme Lang (eds), Sétimo Simpósio Internacional de Tbilisi sobre Linguagem, Lógica e Computação (Notas de aula em Ciência da Computação: Volume 5422), Springer-Verlag, pp. 80-94. doi: 10.1007 / 978-3-642-00665-4_8
  • Hannula, Miika e Juha Kontinen, 2016, “Uma axiomatização finita de independência condicional e dependências de inclusão”. Informação e computação, 249: 121–137. doi: 10.1016 / j.ic.2016.04.001
  • Henkin, Leon, 1961, “Algumas Observações sobre Fórmulas Infinitamente Longas”, em Métodos Infinitísticos (Atas do Simpósio sobre os Fundamentos da Matemática, Varsóvia, 1959), Oxford: Pergamon Press, pp. 167–183.
  • Hodges, Wilfrid, 1997, “Semântica Compositiva para uma Linguagem de Informação Imperfeita”, Logic Journal of the IGPL, 5 (4): 539-563. doi: 10.1093 / jigpal / 5.4.539
  • Hyttinen, Tapani, Gianluca Paolini e Jouko Väänänen, 2015, “Quantum Team Logic e Desigualdades de Bell”, The Review of Symbolic Logic, 8 (4): 722-742. doi: 10.1017 / S1755020315000192
  • Kontinen, Juha e Ville Nurmi, 2009, “Team Logic and Secondic Logic”, em Anais do 16º Workshop Internacional de Lógica, Linguagem, Informação e Computação (Lecture Notes in Computer Science, 5514), Berlin, Heidelberg: Springer 230-241. doi: 10.1007 / 978-3-642-02261-6_19
  • Kontinen, Juha e Jouko Väänänen, 2009, “Sobre a definibilidade na lógica da dependência”, Journal of Logic, Language and Information, 18 (3): 317–332.doi: 10.1007 / s10849-009-9082-0
  • –––, 2011, “Uma observação sobre a negação na lógica da dependência”, Notre Dame Journal of Formal Logic, 52 (1): 55–65. doi: 10.1215 / 00294527-2010-036
  • –––, 2013, “Axiomatizing Conseqüências de Primeira Ordem na Lógica de Dependência”, Annals of Pure and Applic Logic, 164 (11): 1101-1117. doi: 10.1016 / j.apal.2013.05.006
  • Kripke, Saul A., 1965, “Análise Semântica da Lógica Intuicionista I”, em Sistemas Formais e Funções Recursivas: Anais do Oitavo Colóquio Lógico, Oxford, julho de 1963 (Estudos em Lógica e Fundamentos da Matemática, 40), John N. Crossley e Michael AE Dummett (orgs.), Holanda do Norte, pp. 92–130. doi: 10.1016 / S0049-237X (08) 71685-9
  • Lohmann, Peter e Heribert Vollmer, 2013, “Resultados de complexidade para lógica de dependência modal”, Studia Logica, 101 (2): 343–366. doi: 10.1007 / s11225-013-9483-6
  • Pacuit, Eric e Fan Yang, 2016, “Dependência e independência na escolha social: teorema da flecha”, em Dependence Logic, Samson Abramsky, Juha Kontinen, Jouko Väänänen e Heribert Vollmer (eds), Dordrecht: Springer, pp. 235-260. doi: 10.1007 / 978-3-319-31803-5_11
  • Väänänen, Jouko, 2007a, Dependence Logic: A New Approach to Independence Friendly Logic, (textos dos alunos da London Mathematical Society, 70), Cambridge: Cambridge University Press. doi: 10.1017 / CBO9780511611193
  • –––, 2007b, “Team Logic”, em Interactive Logic: Artigos Selecionados do 7º Augustus de Morgan Workshop (Textos em Lógica e Jogos, 1), Johan van Benthem, Dov Gabbay e Benedikt Löwe (eds.), Amsterdã: Amsterdam University Press, pp. 281–302.
  • –––, 2008, “Modal Dependence Logic”, Novas Perspectivas sobre Jogos e Interação (Textos em Lógica e Jogos, 4), Krzysztof R. Apt e Robert van Rooij (eds), Amsterdã: Amsterdam University Press, pp. 254
  • Yang, Fan, 2013, “Expressando frases de segunda ordem na lógica da dependência intuicionista”, Studia Logica, 101 (2): 323–342. doi: 10.1007 / s11225-013-9476-5
  • –––, 2014, “Sobre extensões e variantes da lógica de dependência: um estudo de conectivos intuicionistas no ambiente de semântica de equipes”. Tese de doutorado, Universidade de Helsinque.
  • Yang, Fan e Jouko Väänänen, 2016, “Proposition Logics of Dependence”, Annals of Pure and Applic Logic, 167 (7): 557–589. doi: 10.1016 / j.apal.2016.03.003

Ferramentas Acadêmicas

ícone de homem de sep
ícone de homem de sep
Como citar esta entrada.
ícone de homem de sep
ícone de homem de sep
Visualize a versão em PDF desta entrada nos Amigos da Sociedade SEP.
ícone inpho
ícone inpho
Consulte este tópico de entrada no Internet Philosophy Ontology Project (InPhO).
ícone de papéis phil
ícone de papéis phil
Bibliografia aprimorada para esta entrada na PhilPapers, com links para o banco de dados.

Outros recursos da Internet

  • Lógica de Dependência na Wikipedia
  • Apresentações na Academia Colloquium Dependence Logic, Amsterdã, 2014

Recomendado: