Início > Lógica Matemática > Teoremas da Lógica

Teoremas da Lógica

Os teoremas e lemas a seguir foram retirados exclusivamente de:
Shapiro, Stewart, "Classical Logic", The Stanford Encyclopedia of Philosophy
(Winter 2009 Edition), Edward N. Zalta (ed.)
http://plato.stanford.edu/entries/logic-classical/

Conceitos

1.Regras de formação

Seja L uma linguagem de primeira ordem

(1) Pi ϵ L (i ϵ N) – uma variável proposicional é uma fórmula (wff)

(2) φ ϵ L => ¬φ ϵ L

(3) φ , ψ ϵ  L =>

(3.1) (φ ˄ ψ),

(3.2) (φ ˅ ψ),

(3.3) (φ → ψ),

(3.4)  (φ ↔ ψ) ϵ X

(4) φ ϵ L e x é uma variável => ∀xφ ϵ  L

(5) φ ϵ L e x é uma variável => ∃xφ ϵ  L

(6) todas as wff’s de L são formadas de acordo com as regras (1)-(5)

2.Graus e Princípios de Indução

Para facilitar as provas e definições indutivas, definimos o grau de uma fórmula como o número de ocorrências de conectivos lógicos nela.

(i) Pi (i ϵ N) tem grau zero

(ii) Se φ tem grau n, então ¬φ tem grau n+1

(iii) Se as fórmulas φ e ψ tem, respectivamente, graus n e m, então φ □ ψ tem grau n+m+1

3.Indução Matemática

Seja S um conjunto de fórmulas e P uma certa propriedade que queremos mostrar que vale para todo elemento de S; para isso, as seguintes condições devem ser satisfeitas:

(i) todo elemento de S de grau zero possui a propriedade P

(ii) Se algum elemento de S de grau maior que zero não tiver a propriedade P, então algum elemento de grau inferior não tem a propriedade P

4. Dedução

Seja D um sistema dedutivo. Um argumento é uma coleção não-vazia de fórmulas de L, sendo uma delas chamada de conclusão. Se há quaisquer outras fórmulas no argumento, elas são suas premissas. Por convenção, Γ é utilizado para representar um conjunto de fórmulas. ” Γ, Γ’ ” representa a união de Γ e Γ’ , “Γ, φ” a união de Γ com {φ}.

Um argumento é escrito como <Γ, φ>, onde Γ é o conjunto de premissas e φ a conclusão.

Γ pode ser vazio.

Γ ⊢ φ indica que φ é derivável de Γ, ou, em outras palavras, que o argumento <Γ, φ> é derivável em D.

⊢ φ indica que φ pode ser deduzida de um conjunto vazio de premissas, ou seja, que φ é um teorema.

Regras de inferência

Pressuposto

(As) Se φ é um membro de Γ, então Γ ⊢ φ

As regras de inferência a seguir são relativas aos conectivos e quantificadores. As regras indicam como “introduzir”e “eliminar” fórmulas nas quais cada símbolo é o operador principal. As iniciais I e E, correspondem respectivamente a essas ações.

Conjunção

(˄I) Se Γ1 ⊢ θ e Γ2 ⊢ ψ, então Γ1, Γ2 ⊢ (θ ˄ ψ).

(˄E) Se Γ ⊢ (θ ˄ ψ) então Γ ⊢ θ; e se Γ ⊢ (θ ˄ ψ) então Γ ⊢ ψ.

Os nomes “˄I” e “˄E” significam ˄-Introdução e ˄-Eliminação.

Disjunção

(∨I) Se Γ ⊢ θ então Γ ⊢ (θ ∨ ψ); se Γ ⊢ ψ então Γ ⊢ (θ ∨ ψ).

(∨E) Se Γ1 ⊢ (θ ∨ ψ), Γ2, θ ⊢ φ e Γ3, ψ ⊢ φ, então Γ1, Γ2, Γ3 ⊢ φ.

Condicional

(→I) Se Γ, θ ⊢ ψ, então Γ ⊢ (θ → ψ).

(→E) Se Γ1 ⊢ (θ → ψ) e Γ2 ⊢ θ , então Γ1, Γ2 ⊢ ψ

Negação

(¬I) Se Γ1, θ ⊢ ψ e Γ2, θ ⊢ ¬ψ, então Γ1, Γ2 ⊢ ¬θ.

(DNE) Se Γ ⊢ ¬¬θ, então Γ ⊢ θ.

DNE significa “Double Negation Elimination”.

Quantificador Universal

(∀I) Se Γ ⊢ θ e a variável v não está livre em nenhum membro de Γ, então Γ ⊢ ∀vθ.

(E) Se Γ ⊢ ∀v θ, então Γ ⊢ θ(v|t), desde que t esteja livre para v em θ.

Quantificador Existencial

(∃I) Se Γ ⊢ θ, então Γ ⊢ ∃v θ′, onde θ′ é obtido por θ ao substituir a variável v por zero ou mais ocorrências do termo t, no caso em que (1) se t é  uma variável, então todas as ocorrências substituídas de t estão livres em θ, e (2) todas as ocorrências substituídas de v estão livres em θ′.

(∃E) Se Γ1 ⊢ ∃v θ e Γ2, θ ⊢ φ, então Γ1, Γ2 ⊢ φ, no caso em que v não está livre em φ, nem em qualquer membro de Γ2.

Igualdade

(=I) Γ ⊢ t=t, onde t é qualquer termo.

(=E) Se Γ1 ⊢ t1=t2 e Γ2 ⊢ θ, então Γ1, Γ2 ⊢ θ′, onde θ′ é obtida a partir de θ substituindo zero ou mais ocorrências de t1 com t2, no caso em que nenhuma variável ligada é substituída, e se t2 é uma variável, então todas as suas ocorrências substituídas estão livres.

Uma última regra completa a descrição do sistema dedutivo D.

(*) Γ ⊢ θ somente se θ segue-se dos membros de Γ de acordo com as regras anteriores.

Esta regra permite provas por indução nas regras usadas para estabelecer uma inferência. Se uma propriedade de argumentos é verdadeira para todas as instâncias de (As) e (=I), e se as outra regras preservam a propriedade, então todo argumento que é derivável de D possui a propriedade em questão.

TEOREMAS

Teorema 1. Toda fórmula de L tem o mesmo número de parênteses esquerdos e parênteses direitos.

Cada parênteses esquerdo corresponde a um único parênteses direito, o que acontece à direita do parênteses esquerdo. Similarmente, cada parênteses direito corresponde a um único parênteses esquerdo, o que ocorre à esquerda do parênteses direito. Se um parênteses esquerdo ou direito ocorre entre um par de parênteses já combinados, então o seu par ocorre dentro do par já combinado. Em outras palavras, parênteses que ocorrem no interior de um par fechado, já são fechados entre si.

prova: De acordo com (6) todas as fórmulas são construídas segundo as regras (2) até (5). As fórmulas atômicas não tem parênteses. Parênteses são introduzidos somente na regra (3), e a cada vez que eles são introduzidos, são introduzidos como um par combinado. Então em qualquer estágio da construção da fórmula, os parênteses estão combinados.

A seguir, vamos provar que L é destituída de equívocos e anfibolias.

Lema  2. Cada fórmula consiste em uma expressão com zero ou mais conectivos unários seguidos ou por uma fórmula atômica ou uma fórmula produzida por um conectivo binário, através da regra (3).

prova: Devemos proceder por indução na complexidade da fórmula ou, em outras palavras, no número de regras de formação que são aplicadas. O lema claramente é verdadeiro para fórmulas atômicas. Seja n um número natural, e suponha que o lema é verdadeiro para qualquer fórmula de grau n. Então seja θ uma fórmula de grau n+1. O lema é verdadeiro se a última regra usada para construir θ foi (3). Se a regra usada para construir θ foi (2), então θ é ¬ψ. Desde que ψ possui grau n, então o lema é verdadeiro para ψ (por hipótese de indução), então é verdadeiro para θ.  Raciocínio similar mostra que o lema é verdadeiro se a última regra usada foi (4) ou (5). Pela regra (6), estes são todos os casos, então o lema é verdadeiro para θ, por indução.

Lema 3. Se uma fórmula φ contém um parênteses esquerdo, então termina com um parênteses direito , que se combina com o parênteses mais à esquerda de φ.

prova: Aqui nós temos que proceder por indução nas instâncias de (2)-(5) usadas para construir a fórmula. Evidentemente, o lema é verdadeiro para fórmulas atômicas, desde que elas não possuem parênteses. Suponha, então, que o lema é verdadeiro para fórmulas de grau n construídas de acordo com (2)-(5), e seja φ uma fórmula de grau n+1. Se a última regra aplicada foi (3), então o lema é verdadeiro para φ, desde que φ começa com um parênteses esquerdo e termina com um direito. Se a última regra aplicada foi (2), então φ é ¬ψ, e a hipótese de indução se aplica a ψ. De modo similar, se a última regra aplicada foi (4) ou  (5), então ψ consiste em um quantificador, uma variável, e uma fórmula aos quais nós aplicamos a hipótese de indução. Assim, segue-se que o lema é verdadeiro para φ.

Lema 4. Cada fórmula consiste em pelo menos uma fórmula atômica.

prova: Devemos proceder por indução nas instâncias de (2)-(5) usadas para construir a fórmula. Que o lema é verdadeiro para fórmulas atômicas, é trivial. Suponha, então, que o lema é verdadeiro para fórmulas de grau n construídas de acordo com  (2)-(5). Seja ψ uma fórmula de grau n+1. Se a última regra usada foi (3), então ψ é dividida em duas fórmulas φ e θ. Caso φ seja uma fórmula atômica, o lema é verdadeiro, senão, a última regra aplicada foi (3) a fórmula pode ser decomposta em dois componentes um número finito de vezes, até que encontre-se uma fórmula atômica. O mesmo raciocínio vale para θ. Se a última regra usada foi (2), então ψ é ¬θ, e a hipótese de indução se aplica a θ.  De modo similar, se a última regra usada foi (4) ou (5), a hipótese de indução também se verifica. Assim, segue-se que o lema é verdadeiro para ψ.

Teorema 5. Seja α, β uma sequência não-vazia de caracteres de nosso alfabeto, tais que αβ (i.e. α seguido por β) é uma fórmula. Então α não é uma fórmula.

prova: De acordo com o teorema 1 e lema 3, se α contém um parênteses esquerdo, então o parênteses direito que combina com o parênteses mais à esquerda em αβ está no fim de αβ, assim, o parênteses direito que está em β. Então α possui mais parênteses esquerdos do que direitos. Pelo teorema 1, α não é uma fórmula. Então agora suponha que α não contém nenhum parênteses esquerdo. Pelo lema 2, αβ consiste de uma expressão de zero ou mais operadores unários seguidos por uma fórmula atômica ou uma fórmula produzida por um conectivo binário, através da regra (3). Se a última fórmula foi produzida pela regra (3), então começa com um parênteses esquerdo. Já que α não possui parênteses, então deve ser uma expressão de marcadores unitários. Mas então α não possui nenhuma fórmula atômica, assim, pelo lema 4, α não é uma fórmula. O única caso restante é onde αβ consiste de uma expressão de marcadores unitários seguidos por uma fórmula atômica, da forma t1 = t2 ou pt1… tn. Novamente, se α apenas consistia em marcadores unitários, não seria uma fórmula, e então α deve consistir dos marcadores unitários que iniciam αβ, seguido por t1 sozinho, t1= sozinho, ou o símbolo predicativo P, e talvez alguns (mas não todos) os termos t1,…, tn. Nos dois primeiros casos, α não contém uma fórmula atômica, de acordo com a política de que as categorias não se sobrepõem. Desde que P é um símbolo predicativo n-ário, pela política de que os símbolos predicativos são distintos, P não é um símbolo predicativo m-ário para qualquer m ≠ . Então a parte de α que consiste em P seguida pelos termos não é uma fórmula atômica. Em todos esses casos, então, α não contém uma fórmula atômica. Pelo lema 4, α não é uma fórmula.

Estamos finalmente preparados para demonstrar que não há nenhuma anfibolia na nossa linguagem.

Teorema 6. Seja φ uma fórmula de L. Se φ não é atômica, então existe uma e somente uma dentre (2)-(5) que foi a última regra aplicada para construir φ. Quer dizer, φ não poderia ter sido construída por duas regras diferentes. Além disso, nenhuma fórmula produzida por (3)-(5) é atômica.

prova: A regra (6) diz que φ é atômica ou foi produzida por uma das regras (3)-(5). Portanto, o primeiro símbolo de φ deve ser um símbolo predicativo, um termo, um marcador unitário ou um parênteses esquerdo. Se o primeiro símbolo em φ é um símbolo predicativo ou um termo, então φ é atômica. Neste caso, φ não foi produzida por qualquer uma das regras (2)-(5), desde que todas as fórmulas desses tipos começam com um símbolo predicativo ou um termo. Se o primeiro símbolo em φ é um sinal de negação, então φ foi produzida pela regra (2), e por mais nenhuma outra regra (desde que as outras regras produzem fórmulas que iniciam por um quantificador ou um parênteses esquerdo). De modo similar, se φ começa por um quantificador universal, então é produzida pela regra (4), e por nenhuma outra, e se φ começa com um quantificador existencial, então é produzida pela regra (5) e nenhuma outra. O único caso restante é o que φ começa com um parênteses esquerdo. Neste caso, foi produzida pela regra (3) e nenhuma outra. Nós precisamos somente excluir a possibilidade de que φ foi construída por mais de uma regra de (3.1)-(3.4). Para ilustrar, suponha que φ foi produzida por (3.1) e (3.2). Então φ é (ψ1 ˄ θ1) e φ também é (ψ2 ˅ θ2), onde ψ1, θ1, ψ2 e θ2 são fórmulas. Quer dizer, (ψ1 ˄ θ1) é a mesma fórmula que (ψ2 ˅ θ2). Pelo teorema 5, ψ1 não pode ser parte de ψ2, nem pode ψ2 ser parte de ψ1. Então ψ1 deve ser a mesma fórmula que ψ2. Mas então “˄” deve ser o mesmo símbolo que “˅”, e isso contradiz a regra de que todos os símbolos são diferentes. Então φ não foi produzida simultaneamente por (3.1) e (3.2). Raciocínio similar prova o mesmo sobre as outras combinações.

Este resultado é chamado de “legibilidade única”. O conectivo principal de uma fórmula é o conectivo introduzido pela última regra utilizada na construção da fórmula.

Lema 7. Suponha que Γ ⊢D φ, e seja v′ uma variável que não ocorre livre em φ ou em qualquer membro de Γ. Assuma que v′ está livre para v em φ e em todo membro de Γ. Seja Γ′ {θ(v|v′) | θ ∈ Γ}. Quer dizer, Γ′ é o resultado da substituição de todo ocorrência livre de uma variável v por v′ em todo membro de Γ. Então Γ′ ⊢D φ(v|v′).

prova: A prova deste lema é tediosa, mas será focada sua parte essencial. Nós procedemos por indução no número de regras que foram usadas para chegar a  Γ ⊢ φ. Suponha que n>0 é um número natural, e que o lema é verdadeiro para qualquer argumento que foi derivado usando menos que n regras de inferência. Se n = 1, então a regra aplicada foi (As) ou (=I). Neste caso, Γ′ ⊢ φ(v|v′) segundo a mesma regra. Se a última regra aplicada foi (˄I), então φ tem a forma (θ ˄ ψ), e nós temos Γ1 ⊢ θ e Γ2 ⊢ ψ, com Γ = Γ1, Γ2. Nós aplicamos a hipótese de indução às deduções de θ e ψ, e então aplicamos (˄I) ao resultado. Se a última regra aplicada foi (˄E), nós temos dois subcasos, mas eles são simétricos. Nós temos Γ ⊢ (φ ˄ ψ). Há duas pequenas complicações aqui: a nova variável v′ pode ocorrer livre em ψ e pode não estar livre para v em ψ. Em qualquer um dos casos, primeiro pegamos uma nova variável u que não ocorrer (livre ou ligada) em (φ ˄ ψ) ou em qualquer membro de Γ. Agora aplicamos a hipótese de indução, substituindo u por v′ na dedução Γ ⊢ (φ ˄ ψ). Desde que v′ não ocorre livre em φ ou em qualquer membro de Γ, aquelas fórmulas não são alteradas. A manobra remove quais quer ocorrências livres de v′ da subfórmula ψ. Agora aplicamos a hipóteses de indução ao resultado, substituindo v′ por v, e então aplicamos (˄E). Os casos restantes são similares.

Teorema 8Regra do Enfraquecimento – Se Γ1 ⊢ φ e Γ1 ⊆ Γ2, então Γ2 ⊢ φ.

prova: Novamente, procedemos por indução no número de regras usadas para chegar até Γ1 ⊢ φ. Suponha que n>0 é um número natural, e que o  teorema é verdadeiro para qualquer argumento que foi derivado usando menos que n regras de inferência. Suponha que Γ1 ⊢ φ usando exatamente nregras. Se n=1, então a regras é (As) ou (=I). Nestes casos, Γ2 ⊢ φ pelas mesmas regras. Se a última regra aplicada foi (˄I), então φ tem a forma (θ˄ψ), e nós temos Γ3 ⊢ θ e Γ4 ⊢ ψ, com Γ1 = Γ3, Γ4. Nós aplicamos a hipótese de indução às deduções de θ e ψ, para chegar a Γ2 ⊢ θ e Γ2 ⊢ ψ. E então nós aplicamos (˄I) ao resultado para chegar a Γ2 ⊢ φ. A maioria dos outros casos é exatamente assim. Pequenas complicações surgem somente nas regras (∀I) e (∃E), porque lá nós temos que prestar atenção nas condições das regras. Começando por (∃E), nós temos Γ3 ⊢ ∃vθ e Γ4, θ ⊢ φ, com Γ1 sendo Γ3, Γ4, e v não livre em φ, nem em qualquer membro de Γ4. Nós aplicamos a hipótese de indução para chegar a Γ2 ⊢ ∃vθ, e então (∃E) para terminar com Γ2 ⊢ φ. Suponha que a última regra aplicada para chegar a Γ1 ⊢ φ seja (∀I). Então φ é uma fórmula da forma ∀vθ, e nós temos Γ1 ⊢ θ e a variável v não ocorre livre em qualquer membro de Γ1. O problema é que v pode ocorrer livre em um membro de Γ2, e assim não podemos simplesmente invocar a hipótese de indução e aplicar (∀I) ao resultado. Seja v′ uma variável que não ocorre em θ ou em qualquer membro de Γ2, e seja Γ′ o resultado de substituir v′ por cada ocorrência livre de v em Γ2. Desde que v não ocorre livre em qualquer membro de Γ1, ainda temos Γ1⊆Γ. A hipóteses de indução nos dá Γ′ ⊢ θ, e agora nós aplicamos (∀I) para ter Γ′ ⊢ φ. Agora aplicamos o lema 7,  substituindo v pela nova variável v′. O resultado é Γ2 ⊢ φ.

Teorema 9. Γ ⊢ φ se e somente se há um finito Γ′⊆Γ tal que Γ′ ⊢ φ.

Teorema 10. A regra do ex falso quodlibet é uma “regra derivada” de D. Quer dizer, se Γ1 ⊢ θ e Γ2 ⊢ ¬θ, então Γ12 ⊢ ψ, para qualquer fórmula ψ.

prova: Suponha que Γ1 ⊢ θ e Γ2 ⊢ ¬θ. Então pelo teorema 8, Γ1,¬ψ ⊢ θ, and Γ2,¬ψ ⊢ ¬θ. Então pela (¬I), Γ1, Γ2 ⊢ ¬¬ψ. Pela (DNE), Γ1, Γ2 ⊢ ψ.

Teorema 11. A regra do Corte. Se Γ1 ⊢ ψ e Γ2, ψ ⊢ θ, então Γ1, Γ2 ⊢ θ.

prova: Suponha que Γ1 ⊢ ψ e Γ2, ψ ⊢ θ. Nós procedemos por indução no número de regras usadas para estabelecer Γ2, ψ ⊢ θ. Suponha que n é um número natural, e que o teorema é verdadeiro para qualquer argumento que foi derivado usando menos de n regras. Suponha que Γ2, ψ ⊢ θ derivada usando exatamente n regras. Se a última regra usada foi (=I), então Γ1, Γ2 ⊢ θ é também uma instância de (=I). Se Γ2, ψ ⊢ θ é uma instância de (As), então θ é ψ, ou θ é um membro de Γ2. No caso anterior, nós temos Γ1 ⊢ θ por suposição, e temos Γ1, Γ2 ⊢ θ por Enfraquecimento (Teorema 8). No último caso, Γ1, Γ2 ⊢ θ é uma instância de (As). Suponha que Γ2, ψ ⊢ θ foi obtida usando (˄E). Então, nós temos Γ2, ψ ⊢ (θ˄φ). A hipótese de indução nos dá Γ1, Γ2 ⊢ (θ˄φ), e (˄E) produz Γ1, Γ2 ⊢ θ. Os casos restantes são similares.

Anúncios
Categorias:Lógica Matemática
  1. Nenhum comentário ainda.
  1. No trackbacks yet.

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 )

Imagem do Twitter

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

Foto do Facebook

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

Foto do Google+

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

Conectando a %s

%d blogueiros gostam disto: