Interpretação (lógica)

atribuição de significado para os símbolos de uma Linguagem formal
Nota: Para outros significados de Interpretação, ver Interpretação (desambiguação).

Uma interpretação é uma atribuição de significado para os símbolos de uma Linguagem formal. Muitas linguagens formais usadas na Matemática, Lógica, e Ciência da computação teórica são definidas em termos sintáticos exclusivos, e assim, não tem nenhum significado até que lhes seja dada alguma interpretação. O estudo geral das interpretações de linguagens formais é chamado Semântica Formal.

As mais comumente estudadas lógicas formais são a Lógica proposicional, Lógica de predicados e seus análogos, e para estes existem formas padronizadas de apresentar uma interpretação. Nesses contextos, uma interpretação é uma função que provê a extensão de símbolos e cadeias de símbolos de uma linguagem-objeto. Por exemplo, uma função de interpretação pode tomar o predicado T (para "alto") e atribui-lo a extensão {a} (para "Abraham Lincoln"). Note que todas as nossas interpretações fazem a atribuição de {a} para a constante não-lógica T, e nem argumenta se T é para representar tall nem se 'a' para Abraham Lincoln. Nem as interpretações lógicas tem nada a dizer sobre conectivos lógicos como 'e', 'ou' e 'não'. Apesar de podermos tomar esses símbolos para certas coisas ou conceitos, isto não é determinado pela função de interpretação.

Uma interpretação frequentemente (mas não sempre) provê um modo de determinar os valores verdade de sentenças numa linguagem. Se uma dada interpretação atribui o valor Verdadeiro para uma sentença ou teoria, a interpretação é chamada estrutura daquela sentença ou teoria.

Linguagens Formais

editar
 Ver artigo principal: Linguagem formal

Uma linguagem formal consistem numa coleção fixa de sentenças (também chamadas de palavras ou formulas, dependendo do contexto) compostas por um conjunto fixado de letras ou símbolos. O conjunto de onde essas letras são tomadas é chamado de alfabeto sobre o qual a linguagem é definida. A característica essencia de uma linguagem formal é que sua sintaxe pode ser definida sem referências a interpretação. Pode-se determinar que (P ou Q) é uma fórmula bem formada mesmo sem saber se ela é verdadeira ou falsa.

Para distinguir as cadeias de símbolos que estão em uma linguagem formal das cadeia de símbolos arbitrários, as cadeias que estão na linguagem formal são comumente chamados de fórmulas bem-formadas(fbf).

Exemplo

editar

Uma linguagem formal é definida com o alfabeto α = {  ,   }. Uma palavra é declarada para ser em   se ela começa com   e é composta exclusivamente dos símbolos   e  .

Uma possível interpretação de   atribuiria o dígito decimal '1' para   e '0' para  . Portanto       denotariam 101 sobre essa interpretação de  .

Constantes Lógicas

editar

Nos casos específicos da lógica proposicional e da lógica de predicados, as linguagens formais consideradas tem alfabetos que são divididos em dois grupos: símbolos lógicos (Constantes lógicas) e símbolos não-lógicos. A ideia por trás dessa terminologia é que símbolos lógicostem o mesmo significado, independentemente do assunto que está sendo estudado, enquanto símbolos não-lógicos mudam dependendo da área de investigação.

Constantes lógicas são sempre atribuídas para os mesmos significados por toda interpretação de tipo padrão, então apenas o significado de símbolos não-lógicos são trocados. Constantes lógicas incluem símbolos de quantificador ∀ e ∃, símbolos para Conectivos lógicos, parênteses e outros símbolos de agrupamento, e (na maioria dos casos) o símbolo de igualdade =.

Propriedades gerais de interpretações-verdade

editar

Muitas das interpretações comumente estudadas associam cada sentença numa linguagem formal com um único valor verdade, sendo Verdadeiro ou Falso. essas interpretações são chamadas valoração-verdade; elas incluem a usual interpretação da lógica proposicional e de primeira-ordem. As sentenças que são ditas verdadeiras por uma atribuição particular são ditas satisfatíveis por aquela atribuição.

Nenhuma sentença pode ser feita tanto verdadeira quanto falsa pela mesma interpretação, mas é possível que o valor verdade de uma mesma sentença possa ser diferente sobre diferentes interpretações. Uma sentença é consistente se é verdadeira sobre pelo menos uma interpretação; do contrário ela é inconsistente. Uma sentença φ é dita logicamente válida se ela é satisfeita por toda interpretação (se φ é satisfeita por toda interpretação que satisfaz ψ então φ é dita consequência lógica de ψ).

Interpretação de uma Teoria

editar
 Ver artigo principal: Theory (mathematical logic)

Uma Interpretação de uma Teoria é a relação entre a teoria e algum assunto quando há várias-para-uma correspondencia entre certas declarações elementares da teoria, e certas declarações relacionadas ao assunto. Se toda declaração elementar na teoria tem um correspondente chamamos então de uma interpretação completa, do contrário, ela é chamada de interpretação parcial.[1]

Interpretações para a Lógica Proposicional

editar

A linguagem formal para a Lógica proposicional consistem em fórmulas criadas a partir de símbolos proposicionais (também chamados de símbolos sentenciais, variáveis sentenciais, e variáveis proposicionais) e conectivos lógicos. Os únicos Símbolo não lógicos numa linguagem formal da lógica proposicional são os símbolos proposicionais, que são frequentemente denotados por letras maiúsculas. Para tornar a linguagem formal precisa, um conjunto especificado de símbolos proposicionais deve ser fixado.

O tipo padrão de interpretação nesse grupo é a função que mapeia cada símbolo proposicional para um dos valores verdades verdadeiro e falso. Essa função é conhecida como uma atribuição de valor ou valoração. Em várias apresentações, ela é literalmente um valor verdade atribuído, mas algumas outras apresentações atribuem en:truthbearers no lugar.

Para uma linguagem com n variáveis proposicionais distintas existem 2n possíveis interpretações distintas. Para cada variável particular a, por exemplo, existem 21=2 interpretações possíveis: 1) a é atribuído T, ou 2) a é atribuído F. Para o par a, b existem 22=4 possíveis interpretações: 1) a ambos é atribuído T, 2) a ambos é atribuído F, 3) a é atribuído T e b é atribuído F, ou 4) a é atribuído F e b é atribuído T.

Dada qualquer atribuição verdade para um conjunto de símbolos proposicionais, existe uma única extensão para uma interpretação para todas as formulas proposicionais derivadas daquelas variáveis. Essa interpretação estendida é definida indutivamente, usando a tabela verdade dos conectivos lógicos mostrada anteriormente.

Lógica de Primeira-Ordem

editar

Diferente da lógica proposicional, onde cada linguagem é a mesma independente de uma escolha de um conjunto diferente de variáveis proposicionais, existem várias linguagens de primeira-ordem diferentes. Cada linguagem de primeira-ordem é definida por uma assinatura. A assinatura consiste de um conjunto de símbolos não-lógicos e uma identificação de cada um desses símbolos como um símbolo de constante, ou um símbolo de predicado. No caso de funções e símbolos de predicado, uma Aridade também é atribuída. O alfabeto para a linguagem formal consiste de constantes lógicas, a relação de igualdade =, todos os símbolos da assinatura, e um conjunto adicional infinito de símbolos conhecidos como variáveis.

Novamente, devemos definir uma linguagem de primeira-ordem L, consistindo dos símbolos individuais a, b, e c; símbolos de predicado F,G, H, I e J; variáveis x,y,z; letras de não-símbolos; símbolos não sentenciais.

Linguagens formais para lógica de primeira-ordem

editar

Dada a assinatura σ, a linguagem formal correspondente é conhecida como o conjunto de σ-formulas. Cada σ-formula é construída a partir das fórmulas atômicas pelos significados dos conectivos lógicos; fórmulas atômicas são construídas a partir de termos utilizando símbolos de predicados. A definição formal do conjunto de σ-formulas prossegue em outra direção: primeiro, termos são montados a partir de símbolos de constantes e funções unidos variáveis. Então, termos podem ser combinados em fórmulas atômicas utilizando um símbolo de predicado da assinatura ou o símbolo de predicado da igualdade "=" (ver a sessão "Interpretando Igualdade" abaixo). Finalmente, as formulas da linguagem são montadas de fórmulas atômicas utilizando conectivos lógicos e quantificadores.

Interpretações de uma linguagem formal em lógica de primeira-ordem

editar

Para atribuir significado a todas as sentenças de uma linguagem de primeira ordem, a seguinte informação é necessária:

  • Um domínio[2] D, normalmente requerido que não seja vazio (ver adiante).
  • Para cada símbolo de constante, um elemento de D como sua interpretação.
  • Para cada símbolo de função n-ária, uma função n-ária de D para D como sua interpretação (isto é, a função Dn → D).
  • Para cada símbolo de predicado n-ário, uma relação n-ária em D como sua interpretação (isto é, um subconjunto de Dn).

Um objeto contendo essa informação é conhecido como uma estrutura (de assinatura σ, ou σ-estrutura, ou L-estrutura), ou como um modelo.

As informações especificadas na interpretação fornecem informações suficientes para dar um valor de verdade a qualquer fórmula atômica, depois de cada uma de suas variáveis livres, se possuir alguma, deve ter sido substituída por um elemento do domínio. O valor de verdade de uma sentença arbitrária é então definido indutivamente usando o en:T-schema, que é uma definição da semântica de primeira-ordem desenvolvido por Alfred Tarski. O T-schema interpreta os conectivos lógicos, utilizando tabelas verdade, como discutido acima.Assim, por exemplo, φ & ψ é satisfeita se e somente se ambos φ e ψ são satisfeitos.

Isso deixa a questão de como interpretar as fórmulas da forma x φ(x) e x φ(x). O domínio constitui o alcance para esses quantificadores. A ideia é de que a sentença x φ(x) é verdadeira sob uma interpretação exatamente quando cada substituição de φ(x), onde x é substituído por algum elemento do domínio, está satisfeito. A fórmula x φ(x) é satisfeita se existe, pelo menos, um elemento d do domínio tal que φ(d) é satisfeito.

Estritamente falando, um exemplo de substituição, tais como a fórmula φ(d)mencionado acima não é uma fórmula na linguagem formal original φ, porque d é um elemento do domínio. Há duas maneiras de lidar com este problema técnico. O primeiro é para passar para um idioma maior, no qual cada elemento do domínio é denominado por um símbolo constante. O segundo é adicionar a interpretação a uma função que atribui cada variável para um elemento do domínio. Em seguida, a T-esquema pode quantificar sobre as variações da interpretação original em que esta função atribuição de variável é alterada, em vez de quantificar sobre casos de substituição.

Alguns autores também admitem propositional variables em logica de primeira-ordem, que deve também ser interpretada. Uma variável proposicional pode ficar como sua própria fórmula atômica. A interpretação de uma variável proposicional é um dos dois valores de verdade verdadeiro e falso.[3]

Porque as interpretações de primeira-ordem descritas aqui são definidas em teoria de conjuntos, elas não associam cada símbolo de predicado com uma propriedade [4](or relação), mas preferencialmente com a extensão daquela propriedade (ou relação). Em outras palavras, essas interpretações de primeira-ordem são extensionais [5] não intensional.

Exemplo de uma interpretação de primeira-ordem

editar

Um exemplo de interpretação   da linguagem L descrita abaixo como se segue.

  • Domínio: Um tabuleiro de xadrez
  • Constantes: a: O rei branco b: A rainha preta c: o pião branco da frente do rei
  • F(x): x é uma peça
  • G(x): x é um pião
  • H(x): x é preto
  • I(x): x é branco
  • J(x, y): x pode capturar y

Na interpretação   de L:

  • São sentenças verdadeiras: F(a), G(c), H(b), I(a) J(b, c),
  • São sentenças falsas: J(a, c), G(a).

Domínio não-vazio requerido

editar

Como indicado acima, uma interpretação de primeira ordem é geralmente necessária para especificar um conjunto não vazio como o domínio de discurso. A razão para esta exigência é para garantir que as equivalências, como

 ,

onde x não é uma variável livre de φ, são logicamente equivalentes. Esta equivalência detém em cada interpretação com um domínio não vazio, mas nem sempre quando domínios vazias são permitidas. Por exemplo, a equivalência

 

falha em qualquer estrutura com um domínio vazio. Assim, a teoria da prova de lógica de primeira ordem torna-se mais complicada quando são permitidas estruturas de domínio vazio. No entanto, o ganho, permitindo-lhes é insignificante, porque ambas as interpretações pretendidas e as interpretações interessantes do estudo têm domínios não vazios.[6][7]

Relações vazias não causam nenhum problema para interpretações de primeira ordem, porque não há nenhuma noção semelhante de passar um símbolo de relação através de um conectivo lógico, ampliando seu alcance no processo. Assim, é aceitável para símbolos de relação a ser interpretadas como sendo identicamente falsa. No entanto, a interpretação de um símbolo de função deve sempre atribuir uma função bem definida e total do símbolo.

Interpretando a Igualdade

editar

A relação de igualdade é muitas vezes tratada especialmente na lógica de primeira ordem e outras lógicas subjacentes. Existem duas abordagens gerais.

A primeira abordagem é tratar a igualdade como não diferente de qualquer outra relação binária. Neste caso, se um símbolo de igualdade é incluído na assinatura, é geralmente necessário adicionar várias axiomas acerca da igualdade para os sistemas axiomaticos (por exemplo, a substituição do axioma dizendo que se a = b e R(a) detém então R(b) também a detém). Esta abordagem para a igualdade é mais útil quando se estudam as assinaturas que não incluem a relação de igualdade, tais como a assinatura para set theory ou a assinatura para second-order arithmetic em que existe apenas uma relação de igualdade para os números, mas não uma relação de igualdade para conjunto de números.

A segunda abordagem é a de tratar o símbolo relação de igualdade lógico como uma constante, que deve ser interpretado pela relação de igualdade verdadeira em qualquer interpretação. Uma interpretação que interpreta a igualdade desta maneira é conhecida como um modelo normal, assim esta segunda abordagem é o mesmo que estudar apenas interpretações que venham a ser os modelos normais. A vantagem dessa abordagem é que os axiomas relacionados com a igualdade são automaticamente satisfeitos por cada modelo normal, e por isso eles não precisam ser explicitamente incluídos nas teorias de primeira ordem quando a igualdade é tratado dessa maneira. Esta segunda abordagem é às vezes chamada ordem de primeira-ordem com igualdade, mas muitos autores adotam o estudo geral da lógica de primeira ordem, sem comentários.

Há algumas outras razões para restringir o estudo da lógica de primeira ordem para os modelos normais. Em primeiro lugar, sabe-se que qualquer interpretação de primeira ordem em que a igualdade é interpretada por uma equivalence relation e satisfaz os axiomas de substituição para a igualdade pode ser reduzido a uma interpretação elementar equivalente num subconjunto do domínio original. Assim, há pouca generalidade adicional no estudo de modelos não-normal. Em segundo lugar, se os modelos não-normais são considerados, então cada teoria consistente tem um modelo infinito, o que afeta as demonstrações dos resultados, tais como o Löwenheim–Skolem theorem, que foi declarado sob a suposição de que apenas modelos normais são considerados.

Lógica de predicados de maior-ordem

editar

Uma linguagem formal para Lógica de predicados de maior-ordem parece muito o mesmo que uma linguagem formal para a lógica de primeira ordem. A diferença é que agora existem muitos tipos diferentes de variáveis. Algumas variáveis correspondem aos elementos do domínio, como na lógica de primeira ordem. Outras variáveis correspondem aos objetos do tipo mais elevado: subconjuntos do domínio, as funções do domínio, funções que levam um subconjunto do domínio e retornar uma função do domínio de subconjuntos do domínio, etc Todos estes tipos de variáveis podem ser quantificados.

Existem dois tipos de interpretações comumente empregados para a lógica de ordem superior. Semântica completa' exigi que, uma vez que o domínio do discurso está satisfeito, as variáveis de ordem superior variam sobre todos os elementos possíveis do tipo correto (todos os subconjuntos do domínio, todas as funções do domínio para si, etc.) Assim, a especificação de uma interpretação completa é a mesma que a especificação de uma interpretação de primeira ordem. Semântica de Henkin, que são essencialmente multi-classificadas semântica de primeira ordem, exigem a interpretação para especificar um domínio separado para cada tipo de ordem superior variável para variar mais. Assim, uma interpretação semântica de Henkin inclui um domínio D, uma coleção de subconjuntos de D,uma coleção de funções de D para D, etc. A relação entre esses dois semântica é um tópico importante na lógica de ordem superior.

Interpretações não-clássicas

editar

As interpretações da lógica proposicional e lógica de predicados acima descritos não são os únicos possíveis interpretações. Em particular, existem outros tipos de interpretações que são usados no estudo de non-classical logic (como a intuitionistic logic), e no estudo da lógica modal.

Interpretações usados para estudar a lógica não-clássica incluem topological models, Boolean valued models, e Kripke models. Modal logic também é estudado usando o modelo de Kripke.

Interpretação pretendida

editar
 Ver artigo principal: Intended interpretation

Predefinição:Merge from Muitas linguagens formais estão associados com uma interpretação particular, que é utilizado para as motivar. Por exemplo, a assinatura de primeira ordem para a teoria dos conjuntos inclui apenas uma relação binária, ∈, que pretende representar a adesão definida, e o domínio do discurso em uma teoria de primeira ordem dos números naturais visa o conjunto dos números naturais . No entanto, há sempre interpretações indesejadas em que tanto o domínio de discurso ou os símbolos não-lógicos não são dados os seus significados pretendidos.

No contexto da Peano arithmetic, a interpretação pretendida é chamada de modelo padrão da aritmética. Trata-se de números naturais, com suas operações aritméticas comuns. Todos os modelos que são isomorphic ao que acabou de dar são também chamados de padrão; esses modelos todos satisfazem os Peano axioms. Também existem non-standard models of the Peano axioms, que contêm elementos não correlacionados com qualquer número natural.

Outros conceitos de interpretação

editar

Há outros usos do termo "interpretação" que são comumente usados, que não se referem à atribuição de significados para as linguagens formais.

Em teoria de modelos, uma estrutura A é dita como interpretação de B se existe um subconjunto definível D de A, e as relações definidas e funções D, tal como B é isomórfica para a estrutura com domínio D e estas funções e relações. Em alguns lugares, não é o domínio D que é usado, mas sim D modula uma relação de equivalência definida em A. Para obter informações adicionais, consulte Interpretation (model theory).

Uma teoria T é dita como um interprete de outra teoria S se existe finitas extension by definitions T′ de T tal que S é contido em T′.

Ver também

editar

Referências

  1. Curry, Haskell, Foundations of Mathematical Logic p.48
  2. As vezes chamado de "universo"
  3. Mates, Benson (1972), Elementary Logic, Second Edition, ISBN 0-19-501491-X, New York: Oxford University Press 
  4. A extensão de uma propriedade (também chamado de atributo) é um conjunto de individuais, então uma propriedade é uma relação unária. E.g. As propriedades "amarelo" e "primo" são relações unárias.
  5. veja também Extension (predicate logic)
  6. Hailperin, Theodore (1953), «Quantification theory and empty individual-domains», Association for Symbolic Logic, The Journal of Symbolic Logic, 18 (3): 197–200, JSTOR 2267402, doi:10.2307/2267402, MR0057820 
  7. Quine, W. V. (1954), «Quantification and the empty domain», Association for Symbolic Logic, The Journal of Symbolic Logic, 19 (3): 177–179, JSTOR 2268615, doi:10.2307/2268615, MR0064715 

Ligações externas

editar