Wikiversidade

Lógica: Cálculo Proposicional Clássico: Dedução Natural - Parte I



Introdução

editar

Até agora nós temos dois métodos que sempre determinam a validade de argumentos e fórmulas no CPC: as tabelas de verdade e os tablôs semânticos. Claro que também podemos determinar a validade de uma fórmula mostrando que esta se trata de uma instância de outra fórmula válida, ou por interdefinibilidade de operadores mostrar que ela é equivalente a uma outra fórmula válida, mas estes métodos não são aplicáveis em quaisquer circunstâncias. Agora aprenderemos um terceiro método que sempre determina a validade de fórmulas e argumentos no CPC, além de consistir em um método de derivação, a Dedução Natural.

Tomemos o seguinte argumento:

 
 
 

As tabelas de verdade não parecem muito práticas neste caso. Afinal, temos quatro fórmulas atômicas, o que requer uma tabela de 16 linhas. Sem falar que teríamos muitas colunas também, dada a quantidade de sub-fórmulas.

A alternativa é provar a validade do argumento por tablôs. Contudo, repare que intuitivamente este argumento não passa da simples combinação de vários argumentos válidos, simples e que nós já conhecemos.

Temos o Modus Ponens:

 
 
 

A eliminação da dupla negação:

 
 

Também sabemos que se uma fórmula   é verdadeira, então entre   e uma fórmula arbitrária  , ao menos uma é verdadeira. Ou seja:

 
 

Este argumento é chamado de "Expansão". Oras, o seguinte argumento é obviamente uma instância da expansão:

 
 

Se sabemos de tudo isso, então porque usar o método de tablôs semânticos se estes nos obrigam a considerar o valor de proposições arbitrárias como  , assim como lidar com os valores de   e de  , quando sabemos que a primeira é equivalente a  ?

É justamente isto que a Dedução Natural permite: por meio de um pequeno número de regras de inferência, demonstrar a validade de uma infinidade fórmulas e argumentos sem a necesidade de considerar os valores que cada fórmula ou subfórmula recebe. Ou seja, não estamos mais lidando com a semântica, mas com a sintaxe.

Agora incrementaremos nossa notação e terminologia. Até agora usamos o martelo semântico, " ". Agora usaremos o martelo sintático, " ".

A leitura que fazemos de cada:

 
  é conseqüência semântica de  , ou   implica semanticamente em  .
 
  é conseqüência sintática de  , ou a partir de   prova-se  .
 
  é uma fórmula válida (tautologia no caso do CPC).
 
  é um teorema.

É dito de um sistema lógico que ele é correto se ele verifica a seguinte propriedade:

 
Ou seja, que todos os argumentos sintaticamente válidos também são semanticamente válidos.

É dito de um sistema lógico que ele é completo se ele verifica a seguinte propriedade:

 
Ou seja, que todos os argumentos semanticamente válidos também são sintaticamente válidos.

O CPC verifica ambas propriedades, ou seja, o CPC verifica que:

 

Obviamente, isto também é verificado na instância em que  . Portanto:

 

Ou seja, todo teorema é tautologia e toda tautologia é teorema.

Regras de Inferência Diretas

editar

Nas disciplinas matemáticas como a lógica, a geometria, a aritmética etc., é preferível demonstrar o máximo (de teoremas, construções... válidos, obviamente) por meio do mínimo (de conceitos primitivos, axiomas, regras de inferência etc.).

Na Dedução Natural trabalhamos apenas com regras de inferência. Para que a correção do sistema seja verificada, as regras escolhidas devem ser reconhecidas como válidas. A completude é um pouco mais complicada. Digamos que para verificar a completude o ideal seria ter duas regras para cada operador usado: uma que o insira e outra que o remova.

Trabalharemos primeiramente com as regras de infererência diretas. Como o nome sugere, estas regras regulam quais fórmulas podemo inferir diretamente de outras fórmulas.

Agora vejamos como construir uma dedução usando as regras de inferência diretas. Vamos provar aquele argumento da introdução:

 

O primeiro passo é colocar cada premissa em uma linha enumerada:

 
1.       Premissa
2.       Premissa

Agora, aplicamos as regras de inferência que julgarmos úteis para chegar ao resultado esperado. Para cada nova fórmula inferida, inserimos uma linha enumerada, indicando à direita as linhas que contém as fórmulas a partir das quais foi efetuada a inferência, assim como a regra aplicada.

Por exemplo, vamos aplicar nas linhas 1 e 2 o Modus Ponens (MP):

 
1.       Premissa
2.       Premissa
3.       1,2 MP

Agora aplicaremos a regra de Dupla Negação (DN) na linha 3 a fim de derivar  . Então aplicaremos a Expansão (E) a fim de obter  .

 
1.       Premissa
2.       Premissa
3.       1,2 MP
4.       3 DN
5.       4 E

Ou seja, sob o conjunto de premissas  , derivamos, por meio de inferências reconhecidas como válidas,  . Portanto,  .

Repare também que na linha 3 provamos que   , e na linha 4,  .

Façamos mais uma derivação a fim de aplicar outras regras. Vamos provar que  .

 
1.       Premissa
2.       Premissa
3.       1 BC
4.       2 S
5.       3,4 MP
6.       5,4 C

Nas linhas 1 e 2 temos as premissas   e  , respectivamente. Aplicamos Bi-condicionais para Condicionais (BC) na linha 1 e derivamos   na linha 3. Então aplicamos Separação (S) na linha 2 a fim de derivar   na linha 4. Aplicamos Modus Ponens nas linhas 3 e 4 a fim de derivar   na linha 5. Então aplicamos Conjunção (C) nas linhas 5 e 4 a fim de derivar  . Q.e.d

Exercícios

editar

Prove por dedução natural que:

  1.  
  2.  
  3.  

Resolução dos Exercícios

Trabalhando com Hipóteses

editar

Você deve ter reparado que faltou uma regra para inserir a negação, assim como uma regra para inserir a implicação independentemente da bi-implicação. Para tal, fazemos uso das regras hipotéticas, ou seja, regras que nos permitem trabalhar com hipóteses.

Em Dedução Natural, hipóteses são quaisquer fórmulas bem construídas que inserimos na derivação sem derivá-las de quaisquer outras fórmulas. Com as regras hipotéticas, nosso sistema fica completo. Vejamos então um esquema geral para trabalhar com as hipóteses.

 
1.       Premissa
 
2.         Hipótese

Inserimos uma hipótese   na linha 2. Isto nos obriga a inserir uma linha vertical. Esta linha permanecerá aí até aplicarmos uma regra hipotética que remova-a. Até então, tudo o que derivarmos por meio das regras diretas estará à direita da linha de hipótese:

 
1.       Premissa
 
2.         Hipótese
3.         2 E
4.         1,2 C
5.         1 E
6.         5,3 C
7.       alguma regra hipotética

Também podemos levantar hipóteses dentro de hipóteses, inserindo novas linhas verticais:

 
1.       Premissa
 
2.         Hipótese
3.         2 E
4.           Hipótese
5.           4,3 C
6.         alguma regra hipotética
7.       alguma regra hipotética

Antes de apresentarmos as regras hipotéticas, lembre-se de sempre respeitar as seguintes prescrições:

  1. Introduzir uma linha vertical para cada nova hipótese.
  2. Uma vez que uma linha é descartada, não usar mais qualquer fórmula que esteja a sua direita.
  3. As hipóteses devem ser descartadas na ordem inversa nas quais são levantadas.
  4. Uma dedução não está terminada enquanto não forem descartadas todas as hipóteses.

Redução ao Absurdo (RAA)

editar

Se a partir de uma hipótese   derivarmos uma contradição, então descartamos a hipótese e introduzimos   na derivação.

Um exemplo:

 
1.       Premissa
 
2.         Hipótese
3.         1,2 C
4.           2,3 RAA

Na linha 1 temos   como premissa. Na linha 2 levantamos a hipótese  . Na linha 3 aplicamos a conjunção em   e  , obtendo a contradição  . Como a partir da hipótese derivamos uma contradição, a descartamos e deduzimos sua negação,  .

Portanto,  

Regra de Prova Condicional (RPC)

editar

Se ao levantarmos uma hipótese   inferimos  , então podemos descartar a hipótese e inserir   na derivação.

Por exemplo:

 
1.       Premissa
2.       Premissa
 
3.         Hipótese
4.         1,3 MP
5.         2,4 MP
6.       2,5 RPC

Aqui temos as premissas   e   nas linhas 1 e 2, respectivamente. Na linha 3 levantamos a hipótese  . Aplicando Modus Ponens nas linhas 1 e 3, inferimos   na linha 4. Aplicando Modus Ponens nas linhas 2 e 4, inferimos   na linha 5. Dado que apartir de   inferimos  , descartamos a hipótese e inserimos   na dedução.

Portanto,  

Exercícios

editar

Fazendo uso das regras hipotéticas, demonstre que:

  1.  
  2.  
  3.  
  4.  
  5.  

Resolução dos Exercícios


Obtida de "https://pt.wikiversity.org/w/index.php?title=Lógica:_Cálculo_Proposicional_Clássico:_Dedução_Natural_-_Parte_I&oldid=126038"