Qual é a intuição por trás da lógica linear?

Estou tentando entender a lógica linear para entender melhor os sistemas de tipos lineares. No entanto, quando li as regras, eu não conseguem obter uma intuição por trás dele como eu fiz na lógica modal - significa é exigido como em Kripke quadros é necessário para cada mundo acessível [ é é possível mutatis mutandis]. Mas não consigo encontrar nenhuma explicação intuitiva para a dualidade e qual dos pares de conjunção / disjunção (se houver) corresponde a e . $\Box A$ $A$ $A$ $\Diamond A$ $A$ $\land$ $\lor$

lo.logic type-theory linear-logic Maciej Piechotka
fonte

O artigo original de Girard é onde você deve procurar se quiser entender a intuição por trás deles. A questão como está é muito geral e a resposta seria procurar na página da Wikipedia lógica lógica.

Kaveh

Concordo que este é um pouco demais e definitivamente não é um nível de pesquisa; talvez você deva fazer a pergunta no CS Stack Exchange. No entanto, eu o desencorajaria a usar o artigo original de Girard como ponto de entrada para a lógica linear. Talvez a Wikipedia seja um lugar melhor para começar.

Damiano Mazza

Isso é bem amplo. Uma sugestão, talvez, poderia estar começando a considerar as fórmulas como uma "moeda" que pode ser gasta, em vez de declarações de verdade. Então, conjunto poderia ser

que significa que podemos passar tanto um

moeda e uma

moeda. Outro tipo de conjunção pode ser

, o que significa que podemos escolher entre gastar

e gastar

(mas não os dois!). Você pode encontrar alguns exemplos na Wikipedia, como Damiano sugeriu.

a \otimes b

$a \otimes b$

a

$a$

b

$b$

a & b

$a \& b$

a

$a$

b

$b$

chi

@chi Não sei se a "interpretação de recursos" é a melhor maneira de entender a dualidade no LL. A interpretação do processo é muito mais compreensível.

Martin Berger

Não tenho certeza se essa pergunta é ideal para o CSTheory, mas, como já está recebendo votos, aqui está uma resposta que alguém poderia ter dado se a pergunta fosse publicada em cs.stackexchange .

A fim de compreender a noção de lógica linear da dualidade , que as forças de conjunção e disjunção além muito mais longe do que estamos acostumados na lógica convencional, eu recomendo não pensar em lógica linear em termos de recursos (embora esta é uma leitura importante ) Em vez disso, pense nas fórmulas lógicas lineares como processos que se comunicam em uma porta / nome / canal. Essa interpretação foi desenvolvida primeiro em (1) com o melhor de meu conhecimento, mas já foi mencionada no trabalho original de Girard. Como uma imagem: $(\cdot)^{\bot}$ $A$

(Não sei ao certo como centralizar as imagens aqui.) A conjunção linear é interpretada como executando os processos e em paralelo . O processo comunica pares em sua porta, onde vem de e é a comunicação de $A \otimes B$ $A$ $B$ $A \otimes B$ $(a, b)$ $a$ $A$ $b$ $B$

A dualização (que é a negação da lógica linear) alterna entrada e saída. Portanto, o dual de é $(.)^{\bot}$ $A \otimes B$

(A \otimes B)^{⊥} = A^{⊥} ⅋ B^{⊥}

$(A \otimes B)^{\bot} \quad = \quad A^{\bot} ⅋ B^{\bot}$

Nesta leitura é o processo que comunica com . $A^{\bot} ⅋ B^{\bot}$ $A \otimes B$

O equivalente da lógica linear à disjunção pode receber uma leitura teórica do processo semelhante. A fórmula

A & B

$A\ \&\ B$

também devem ser vistos como dois processos e em paralelo, mas, em vez de enviar mensagens ativamente, eles esperam que o ambiente decida qual executar. Então fica lá, esperando em seu canal para um pouco de informação que decide se deve ser executado como ou como . Esta é uma versão 'paralela' do em linguagens seqüenciais de programação. O duplo de é $A$ $B$ $A \& B$ $A \& B$ $A$ $B$ $if/then/else$ $(A \& B)^{\bot}$ $A \& B$

(A & B)^{⊥} = A^{⊥} \oplus B^{⊥}

$(A \& B)^{\bot} \quad = \quad A^{\bot} \oplus B^{\bot}$

pode ser visto como um processo que envia 1 bit de informação para , a saber: "continue como " ou "continue como ". Isso é semelhante ao estiver avaliando para enquanto estiver avaliando como , exceto que a escolha entre e agora é feita pelo ambiente. $A \& B$ $A$ $B$ $if\ true\ then\ P\ else\ Q$ $P$ $if\ false\ then\ P\ else\ Q$ $Q$ $A$ $B$

O operador! Também possui uma interpretação teórica do processo: se é lido como um processo, então pode ser lido como executando infinitamente muitos processos em paralelo.

A

$A$

! A

$!A$

A

$A$

Neste ler o axiomas das lógicas tornam-se simples 'fios' lineares que encaminhar mensagens de processos para os processos . Essa interpretação dos axiomas já está nas redes de prova de Girard (3). $A \vdash A$ $A^{\bot}$ $A$

Essa interpretação teórica do processo foi influente e deu origem a muitos trabalhos de acompanhamento, como por exemplo (2) para tipos de sessão. No entanto, existem alguns casos extremos que o tornam um pouco estranho e, pelo que sei, não foi feito para funcionar perfeitamente para a lógica linear completa , mesmo em 2017.

_{1. S. Abramsky, Interpretações Computacionais de Lógica Linear .

2. P. Wadler, Proposições como sessões .

3. Wikipedia, Rede de prova .}

Martin Berger
fonte

Qual é a intuição por trás da lógica linear?

Respostas: