Completude (lógica)

A completude é um meta-resultado lógico importante, que garante que toda sentença válida pode ser formalmente derivada, estabelecendo assim uma certa relação entre o universo semântico e sintático de um determinado cálculo lógico:

Dizemos que uma dada lógica é completa se para toda tautologia φ, podemos apresentar uma derivação formal para φ, a partir de um conjunto vazio de premissas. Esta noção de completude também é denominada por alguns autores completude fraca.

Dizemos que uma determinada lógica é fortemente completa se, dado um conjunto de fórmulas $\Gamma \cup \{\varphi\}$, temos: se $\varphi \,\!$ é consequência lógica (ou consequência semântica) do conjunto de premissas $\Gamma \,\!$ em conjunto com uma fórmula arbitrária $\alpha \,\!$, então pode-se apresentar uma dedução formal de $\varphi \,\!$ a partir deste mesmo $\Gamma \,\!$. Em símbolos, denotamos isto por:

$\Gamma \models \varphi$ implica $\Gamma \vdash \varphi$

Uma outra definição simples de uma lógica completa diz que nenhum axioma ou regra de inferência extra precisa ser adicionado à teoria forma desta lógica para que ela seja capaz de derivar formalmente todas as fórmulas válidas.

Completude na Lógica Proposicional

Demonstração

Seja $\Gamma \,\!$ um conjunto arbitrário de fórmulas bem-formadas pertencentes à linguagem da lógica proposicional, e $\alpha \,\!$ uma fórmula bem-formada, tal que $\alpha \not\in \Gamma$.

Para demonstrar o Teorema da Completude para a lógica proposicional, procederemos por contraposição:

Suposição: $\Gamma \not\vdash \alpha$.

Demonstraremos agora que $\Gamma \not\models \alpha$:

Demonstração (Lema de Lidenbaum-Asser):

1. Primeiramente, ordenamos todas as fórmulas da linguagem proposicional e numeramos cada uma delas: $\beta_1{,} \beta_2{,}{...}{,}\beta_n \,\!$ (a ordem é arbirária, como por exemplo, a ordem alfabética)
2. Definimos $\Gamma^* \,\!$ como o Conjunto Maximal em relação à $\alpha \,\!$ (infinito) definido como a união de todos os $\Gamma_i \,\!$, onde:
   • $\Gamma_0 = \Gamma \,\!$
   • Se temos que $\Gamma_i \cup \beta_{i+1} \not\vdash \alpha$ então $\Gamma_{i+1} = \Gamma_i \cup \beta_{i+1}$. Senão, temos que $\Gamma_{i+1} = \Gamma_i \,\!$
3. Podemos verificar agora que:
   • $\Gamma^* \,\!$ contém $\Gamma \,\!$.
   • $\Gamma^* \not\vdash \alpha$, pois em caso contrário, teríamos adicionado a algum $\Gamma_i \,\!$ fórmula $\beta_i \,\!$ responsável pela demonstrabilidade de $\alpha \,\!$, porém esta possibilidade foi excluída na definição da sequência de $\Gamma_i \,\!$'s que compõe $\Gamma^* \,\!$
   • O termo "conjunto maximal" vem do fato que toda e qualquer fórmula ainda não presente neste, ao ser adicionada, faria $\Gamma^* \vdash \alpha$
4. Se $\Gamma^* \,\!$ é um conjunto maximal, então ele também será "verídico". isto é, ele contém uma determinada fórmula $\gamma \,\!$ se e somente se não contiver $\lnot\gamma \,\!$; Se contém $\omega \,\!$ e $\omega \rightarrow \theta$, então também irá conter $\theta \,\!$
5. Se $\Gamma^* \,\!$ é "verídico", então existe uma determinada valoração canônica tal que as fórmulas de $\Gamma^*$ assumem um valor verdadeiro e todas as outras fórmulas da linguagem são falsificadas.

Temos então que para esta dada valoração, $v(\Gamma) = 1 \,\!$ e $v(\alpha) = 0 \,\!$, donde segue que $\Gamma \not\models \alpha$

Completude na Lógica de Primeira Ordem

O cálculo de predicados de primeira ordem descreve uma lógica fortemente completa. Este resultado foi demonstrado pela primeira vez por Kurt Gödel em 1929. Posteriormente, o lógico Leon Henkin desenvolveu um teorema mais prático, usado até hoje. Para mais informações sobre o Teorema da Completude, consulte a seção Ver também.

Teoremas de Incompletude

Também demonstrado por Kurt Gödel, o teorema da incompletude garante que todos os cálculos lógicos pelo menos tão fortes quanto o sistema da Aritmética Peano não podem ser simulâneamente completos e consistentes. Um exemplo deste caso é a lógica de segunda ordem, que não possui um teorema da completude. Para mais informações, consulte a seção Ver também.

Outras noções de completude

• Na teoria de complexidade computacional, um problema P é dito completo para uma determinda classe de compexidade C, sob uma dada redução, se P está na classe C e todo problema desta pode ser reduzido à P utilizando-se esta redução. Por exemplo, os problemas na ckasse NP-Completa são completos para a classe NP sob um tempo polinomial e uma redução muitos para um

• Um procedimento ou algoritmo de decisão é completo se sempre que a resposta para um dado problema for "sim", este algoritmo à encontra corretamente.

Ver também

• Lógica proposicional
• Lógica de primeira ordem
• Teorema da completude de Gödel
• Teorema da incompletude de Gödel
• Kurt Gödel

Ligações externas

• (em inglês)-Completness em Wordnet. Acessado em 29 de julho de 2007.