Completude (lógica)


Origem: Wikipédia, a enciclopédia livre.

Saltar para a navegaçãoSaltar para a pesquisa

Em lógica matemática e na metalógica, um sistema formal é chamado completo com respeito a uma propriedade específica se toda fórmula tendo a propriedade pode ser obtida usando esse sistema, isto é, é um de seus teoremas; caso contrário, o sistema é dito incompleto. O termo “completo” também é usado sem qualificação, com significados diferentes dependendo do contexto, geralmente se referindo à propriedade da validade semântica. Intuitivamente, um sistema é chamado de completo nesse sentido particular, se ele pode obter todas as fórmulas verdadeiras. Kurt GödelLeon Henkin, e Emil Leon Post publicaram provas de completude.

Outras propriedades relacionadas a completude[editar | editar código-fonte]

A propriedade recíproca da completude é chamada corretude: um sistema é correto com respeito a uma propriedade (principalmente validade semântica) se cada um dos seus teoremas possuem essa propriedade.

Formas da completude[editar | editar código-fonte]

Completude expressiva[editar | editar código-fonte]

Uma linguagem formal é expressivamente completa se pode expressar o objeto que é destinado.

Completude funcional[editar | editar código-fonte]

Um conjunto de conectivos lógicos associados com o sistema formal é funcionalmente completo se pode expressar todas as funções proposicionais.

Completude semântica[editar | editar código-fonte]

Completude semântica é a recíproca da corretude para sistemas formais. Um sistema formal é completo com respeito a tautologia quando todas suas tautologias são teoremas, enquanto que um sistema formal é correto quando todos os teoremas são tautologias (isto é, eles são fórmulas semanticamente válidas: fórmulas que são verdadeiras em qualquer interpretação da linguagem do sistema que é consistente com as regras do sistema. Isto é:

{\displaystyle \models _{\mathcal {S}}\varphi \ \to \ \vdash _{\mathcal {S}}\varphi .}[1]

Completude forte[editar | editar código-fonte]

Um sistema formal S é fortemente completo ou completo no sentido forte se para todo conjunto de premissas Γ, qualquer fórmula que semanticamente segue de Γ é obtida de Γ. Isto é:

Refutação da completude[editar | editar código-fonte]

Um sistema formal S é refutação-completo se for possível obter um falso de todo conjunto de fórmulas insatisfatível. Isto é,

{\displaystyle \Gamma \models _{\mathcal {S}}\bot \to \ \Gamma \vdash _{\mathcal {S}}\bot .}[2]

Todo sistema fortemente completo é também refutação-completo. Indutivamente, completude forte significa que, dado um conjunto de fórmulas {\displaystyle \Gamma }, é possível computar toda consequência semântica {\displaystyle \varphi } de {\displaystyle \Gamma }, enquanto a refutação-completude significa que, dado um conjunto de fórmulas {\displaystyle \Gamma } e a fórmula {\displaystyle \varphi }, é possível conferir se {\displaystyle \varphi } é um consequência semântica de {\displaystyle \Gamma }.

Exemplos do sistema de refutação completude inclui: resolução SLD nas cláusulas de Hornsuperposição em cláusulas equacionais da lógica de primeira ordem, Princípio da Resolução de Robinson em conjunto de cláusulas.[3] Esse último não é fortemente completo: por exemplo, {\displaystyle \{a\}\models a\lor b} se verifica mesmo no subconjunto proposicional da lógica de primeira ordem, mas {\displaystyle a\lor b} não pode ser obtido de {\displaystyle \{a\}} pela resolução. Todavia, {\displaystyle \{a,\lnot (a\lor b)\}\vdash \bot } pode ser obtido.

Completude sintática[editar | editar código-fonte]

Um sistema formal S é sintaticamente completo ou dedutivamente completo ou maximamente completo se para toda sentença (fórmula fechada) φ da linguagem do sistema, φ ou ¬φ é um teorema de S. Isso também é chamado de negação-completude. Em outro sentido, um sistema formal é sintaticamente completo se e somente se não é possível adicionar uma sentença não demonstrável sem introduzir uma inconsistência. A lógica proposicional verofuncional e a lógica de predicados de primeira ordem são semanticamente completas, mas não sintaticamente completas (por exemplo, a declaração da lógica proposicional consistindo de uma única variável proposicional A, não é um teorema, e nem sua negação, mas essas não são tautologia). O Teorema da incompletude de Gödel mostra que qualquer sistema recursivo que é suficientemente poderoso, como o axioma de Peano, não pode ser consistente e sintaticamente completo ao mesmo tempo.

Referências[editar | editar código-fonte]

  1.  Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971
  2.  David A. Duffy (1991). Principles of Automated Theorem Proving. [S.l.]: Wiley
  3.  Stuart J. Russell, Peter Norvig (1995). Artificial Intelligence: A Modern Approach. [S.l.]: Prentice Hall

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s