Estrutura de interpretação (lógica)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na lógica, uma estrutura (ou estrutura de interpretação) é um objeto que dá significado semântico ou interpretação aos símbolos definidos pela assinatura de uma linguagem. Uma estrutura possui diferentes configurações, seja em lógicas de primeira ordem, seja em linguagens lógicas poli-sortidas ou de ordem superior.

Estruturas de primeira ordem[editar | editar código-fonte]

Uma assinatura Σ de uma linguagem de primeira ordem consiste de um conjunto Cst de símbolos de constantes e de conjuntos Funn e Reln de símbolos de funções e relações n-árias, respectivamente. Uma Σ-estrutura \mathcal{M} para tal linguagem consiste de um par \mathcal{M} = \langle \mathcal{D}_I,\mathcal{I} \rangle, no qual DI será o universo (ou domínio) de discurso, e I é uma intepretação para os símbolos da linguagem, na qual vale as definições:

  • Os símbolos de constantes são interpretados como "nomes" que se referem a um objeto do universo, são funções 0-árias em DI. Em outras palavras, para cada cCst, há um objeto específico cIDI
  • Cada símbolo de função n-ária fnFunn é interpretado como uma função específica  f_{n}^I: \mathcal{D}^n_I \rightarrow \mathcal{D}_I .
  • Cada símbolo de relação n-ária RnReln é interpretado como um subconjunto do produto cartesiano  \mathcal{D}^n_I , ou seja, o conjunto das n-uplas ordenadas que satisfazem RIn.
Exemplo[editar | editar código-fonte]

Na álgebra booleana binária uma assinatura é constituída por:

  • Cst = \lbrace 0,1 \rbrace, Fun_1=\lbrace \neg \rbrace, Fun_2= \lbrace \lor, \land \rbrace

E uma estrutura para essa assinatura é:

  • \mathcal{D}_I = \lbrace 0,1 \rbrace
  • O símbolo de constante 0 é interpretado como o próprio objeto 0 (valor de verdade falso) e o símbolo 1, como o próprio 1 (verdadeiro).
  • \lor (x,y)\quad \mbox{ou} \quad x \lor y\quad :     X ou y é verdadeiro (1);
  • \land (x,y)\quad \mbox{ou} \quad x \land y\quad :     X e y são verdadeiros.

Assim, a sentença  (x \land \neg y) = 1 é verdadeira apenas para uma atribuição ρ tal que ρ(x)=1 e ρ(y)=0.

Algumas definições sobre estruturas[editar | editar código-fonte]

Subestrutura[editar | editar código-fonte]

Uma estrutura \mathcal{M} é dita subestrutura de outra estrutura \mathcal{M'} para a mesma assinatura, denotado por \mathcal{M} \subseteq \mathcal{M'}, se:

  • \mathcal{D}_I \subseteq \mathcal{D}_{I'} ;
  • c^I = c^{I'}     para toda constante cCst;
  • f^I = f^{I'}|_{D_I^n}     para toda função fnFunn. Assim sendo,     f^{I'}|_{D_I^n} : \mathcal{D}_I^n \rightarrow \mathcal{D}_I;
  • R^I = R^{I'} \cap \mathcal{D}_I     para toda relação RnReln.

Homomorfismo e Isomorfismo[editar | editar código-fonte]

Dadas duas estruturas \mathcal{M} e \mathcal{M'} para uma mesma assinatura, um homomorfismo h : \mathcal{M} \rightarrow \mathcal{M'} é uma função h : \mathcal{D}_I \rightarrow \mathcal{D}_{I'} tal que:

  • Para todo cCst,
h(c^I) = c^{I'}
  • Para toda fnFunn e {a1,...,an} ⊆ DI,
h(f^I(a_1,\dots,a_n)) = f^{I'}(h(a_1),\dots,h(a_n))
  • Para toda RnReln e {a1,...,an} ⊆ DI,
(a_1,\dots,a_n) \in R^I \Longrightarrow (h(a_1),\dots,h(a_n)) \in R^{I'}

Diz-se que h é isomorfismo se a função for bijetiva, ou seja, o homomorfismo h : \mathcal{M'} \rightarrow \mathcal{M} também vale.

Relação de satisfação[editar | editar código-fonte]

Seja φ uma fórmula bem-formada, \mathcal{M} uma estrutura, e ρ uma atribuição, a relação de satisfação ou consequência, na qual ρ satisfaz φ em M denotado por \mathcal{M} \vDash_{\rho} \phi, define-se através do esquema-T por:

  • \phi\quad \acute{\mbox{e}} \quad(t_1 = t_2):\quad \mathcal{M} \vDash_{\rho} (t_1 = t_2)\quad \mbox{sse} \quad t_1 = t_2;
  • \phi\quad \acute{\mbox{e}} \quad R(t_1,...,t_n):\quad \mathcal{M} \vDash_{\rho} R(t_1,...,t_n)\quad \mbox{sse} \quad (\rho(t_1),...,\rho(t_n)) \in R^I;
  • \phi\quad \acute{\mbox{e}} \quad(\alpha_1 \lor \alpha_2):\quad \mathcal{M} \vDash_{\rho} \alpha_1 \lor \alpha_2\quad \mbox{sse} \quad\mathcal{M} \vDash_{\rho} \alpha_1\quad \mbox{ou} \quad\mathcal{M} \vDash_{\rho} \alpha_2 ;
  • \phi\quad \acute{\mbox{e}} \quad\neg\alpha:\quad \mathcal{M} \vDash_{\rho} \neg\alpha\quad \mbox{sse} \quad\mathcal{M} \nvDash_{\rho} \alpha;
  • \phi\quad \acute{\mbox{e}} \quad\forall x\alpha:\quad \mathcal{M} \vDash_{\rho} \forall x\alpha\quad \mbox{sse} \quad\mathcal{M} \vDash_{\rho'} \alpha    para toda atribuição ρ'=ρ[x:=k], para todo k ∈ DI.

Modelo de teorias de primeira-ordem[editar | editar código-fonte]

Uma estrutura é dita um modelo de uma teoria quando ambas têm a mesma linguagem e toda sentença consistente da teoria é satisfeita por tal estrutura. Assim, por exemplo, um anel é uma estrutura que satisfaz todos os axiomas da teoria dos anéis, e um modelo para a teoria das ordens parciais é uma estrutura com apenas um símbolo ≤ e que deve satisfazer os axiomas das ordens parciais.

"M é modelo de φ" denota-se por  \vDash_{\mathcal{M}} \phi.

Definibilidade em uma estrutura[editar | editar código-fonte]

Uma relação n-ária R em um universo DI de uma estrutura M é dita definível (ou explicitamente definível) se há uma fórmula φ(x1,...,xn), onde x1,...,xn são as variáveis livres de φ, tal que:

R = (a_1,\dots,a_n) \in \mathcal{D}^n_I : \mathcal{M} \vDash_{\rho} \phi (x_1, \dots ,x_n); \quad\rho[x_1:=a_1;\dots;x_n:=a_n]

Ou seja,

(a_1, \dots ,a_n) \in R \Leftrightarrow \mathcal{M} \vDash \phi (x_1, \dots ,x_n).

Um caso especial importante é a definibilidade de elementos específicos. Um elemento aDI é definível em M sse há uma fórmula φ(x) tal que

\mathcal{M} \vDash \forall x(x=m \leftrightarrow \phi(x)).

Definibilidade com parâmetros[editar | editar código-fonte]

Uma relação R é dita definível em parâmetros se há uma sentença φ com parâmetros de M tal que R é definível usando φ. Todo elemento da uma estrutura é definível usando ele próprio como parâmetro.

Definibilidade implícita[editar | editar código-fonte]

Provém das definições acima que a fórmula φ pode não mencionar R, já que o mesmo pode não estar na linguagem de M. Se há uma fórmula φ na linguagem estendida contendo M e o novo símbolo R, e R é a única relação tal que \mathcal{M} \vDash \phi, então R é dita implicitamente definível em M.

Generalizações[editar | editar código-fonte]

Estruturas poli-sortidas[editar | editar código-fonte]

Uma linguagem poli-sortida inclui mais de um domínio de discurso. Por exemplo, a axiomatização em primeira ordem da lógica de segunda ordem inclui um tipo para números naturais e um tipo para conjuntos de números naturais. A definição de uma estrutura poli-sortida é a convencional, porém ao invés de um único universo de discurso, há vários, um para cada tipo.

Linguagens de ordem superior[editar | editar código-fonte]

Há mais de uma semântica possível para lógicas de ordem superior. Uma vez usando a semântica de ordem superior completa, uma estrutura necessita apenas de um universo para predicados, e o Esquema T é expandido para um quantificador sobre um tipo de ordem superior.

Requerimento de domínio não-vazio[editar | editar código-fonte]

Afirma-se acima que uma interpretação deve especificar um domínio não-vazio para ser o universo de discurso. Uma razão importante para isto é assim de modo a equivalências como

(\phi \lor \exists x \psi) \leftrightarrow \exists x (\phi \lor \psi),

onde x não é livre em φ, serem logicamente válidas. Esta equivalência não é logicamente válida quando estruturas vazias são permitidas (por exemplo, assuma que φ seja \forall y ( y = y) e ψ seja  x = x). Portanto, a teoria da demonstração da lógica de primeira ordem torna-se muito mais complicada quando estruturas com domínio vazio são permitidas, enquanto que o ganho em permití-las é pequeno, já que tanto as interpretações pretendidas como as interpretações interessantes das teorias que as pessoas estudam possuem domínios não-vazios. A dificuldade com domínios vazios está em certas regras de inferência que permitem que quantificadores sejam externalizados sobre conectivos lógicos. Para um exemplo concreto, considere

\forall y ( y = y) \lor \exists x ( x = x)

Esta estrutura é satisfeita por um domínio vazio. Para colocá-la na forma normal prenex, queremos mover o quantificador existencial para obter

\exists x ( \forall y ( y = y) \lor  x = x)

Mas esta nova fórmula não é satisfeita por um domínio vazio, já que não existe nenhum elemento com o qual o quantificador existencial possa ser instanciado. O problema subjacente é que o escopo do quantificador existencial foi modificado para incluir o disjunto mais à esquerda.

As relações vazias, entretanto, não causam este problema, uma vez que não existe um conceito semelhante de externalizar um símbolo de relação sobre um conectivo lógico, alargando seu escopo no processo.

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]