DEDUÇÃO NATURAL
O objetivo deste texto consiste em apresentar o método da dedução natural a partir do uso de regras de inferência. Para tanto, foi utilizado como referência os vídeos do canal Lógica pô disponíveis aqui. Este texto é composto das seguintes partes:
(1) REGRAS DE INFERÊNCIA;
(2) REGRAS DERIVADAS;
(3) PROVA LÓGICA;
(4) CONSEQUÊNCIA SINTÁTICA E SEMÂNTICA;
(5) TEOREMAS DA COMPLETUDE E DA CORREÇÃO;
(6) VALIDADE SINTÁTICA E SEMÂNTICA;
(7) PRINCÍPIO DA EXPLOSÃO;
(8) DEDUÇÃO NATURAL POR PROVA DIRETA;
(9) DEDUÇÃO NATURAL POR PROVAS HIPOTÉTICAS;
(10) DEDUÇÃO NATURAL POR PROVA POR CONTRADIÇÃO.
I. REGRAS DE INFERÊNCIA
A noção de dedução natural envolve o uso de regras de inferência. Uma inferência é o processo de fazer uma passagem de uma fórmula a outra de tal modo a garantir que a verdade seja preservada. Cada operador verofuncional (implicação →, conjunção ∧, disjunção ∨, negação ¬ e bi-implicação ↔), uma de introdução do operador e outra de eliminação do operador.
(1) Implicação (→)
Regra de Eliminação (Modus Ponens) | Regra de Introdução (Condicionalização) |
P→Q P Q | P Q →P [em que Q é qualquer variável] |
(2) Conjunção (∧)
Regra de Eliminação | Regra de Introdução |
P∧Q P
P∧Q Q | P Q P∧Q
|
(3) Disjunção (∨)
Regra de Eliminação (Silogismo Disjuntivo) | Regra de Introdução |
P∨Q ¬P Q
P∨Q ¬Q Q | P P∨Q [em que Q é qualquer variável] |
(4) Negação (¬)
Regra de Eliminação (Dupla negação) | Regra de Introdução (Redução ao absurdo) |
¬¬P P | P →⊥ [⊥ significa contradição] ¬P |
5. Bi-implicação (↔)
Regra de Eliminação (definição do Bicondicional) | Regra de Introdução |
P↔Q P→Q
P↔Q Q→P | P→Q Q→P P↔Q
|
Assim, temos:
Operador | Regra de Eliminação | Regra de Introdução |
Implicação (→) | P→Q P Q
| P Q →P |
Conjunção (∧) | P∧Q P
P∧Q Q | P Q P∧Q
|
Disjunção (∨) | P∨Q ¬P Q
P∨Q ¬Q Q | P P∨Q |
Negação (¬) | ¬¬P P | P →⊥ ¬P
|
Bi-implicação | P↔Q P→Q
P↔Q Q→P | P→Q Q→P P↔Q
|
II. REGRAS DERIVADAS
Além das regras básicas de inferência, existem regras derivadas que permitem operar com as variáveis e operadores mantendo o valor de verdade. Essas regras são: (i) regra da prova condicional; (ii) silogismo hipotético; (iii) modus tollens; (iv) regra da contraposição ou transposição; (v) regra de De Morgan; (vi) negação do condicional; (vii) regra da distribuição; (viii) regra da comutatividade; (ix) regra da associatividade:
(1) Regra da prova condicional:
P
.
.
.
Q
P →Q
(2) Silogismo Hipotético [Transitividade da Implicação]
P→Q
Q→R
P→R
(3) Modus Tollens
P→Q
¬Q
¬P
(4) Regra de De Morgan
¬ (P∧Q) ¬P ∨¬Q | ¬(P∨Q) ¬P∧¬Q |
(5) Negação do Condicional
¬(P→Q)
P∧¬Q
(6) Regra da Distribuição
(P∨Q) ∧R
(P∧R) ∨ (Q∧R)
(7) Regra da Comutatividade [a ordem dos fatores não altera o valor de verdade da fórmula no caso da conjunção ∧, disjunção ∨ e bi-implicação]
Conjunção ∧ | Disjunção ∨ | Bi-implicação ↔ |
P∧Q Q∧P | P∨Q Q∨P | P ↔Q Q ↔P |
(8) Regra da associatividade [a relação de associação entre parêntesis no caso da conjunção ∧. disjunção ∨ e bi-implicação ↔ não altera o valor de verdade da fórmula]
Conjunção ∧ | Disjunção ∨ | Bi-implicação ↔ |
(P∧Q)∧R Q∧(P∧R) | (P∨Q) ∨R Q∨(P∨R) | (P ↔Q) ↔R Q ↔(P ↔R) |
Assim, temos:
REGRAS DERIVADAS
Regra da prova condicional | P . . . Q P →Q |
Silogismo Hipotético | P→Q Q→R P→R |
Modus Tollens
| P→Q ¬Q ¬P
|
Regra de De Morgan | ¬ (P∧Q) ¬P ∨¬Q ¬(P∨Q) ¬P∧¬Q
|
Negação do condicional | ¬(P→Q) P∧¬Q |
Regra da Distribuição | (P∨Q)∧R (P∧R)∨(Q∧R) |
Comutatividade da Conjunção | P∧Q Q∧P |
Comutatividade da Disjunção | P∧Q Q∧P |
Comutatividade da Bi-implicação | P ↔Q Q ↔P |
Associatividade da Conjunção | (P∧Q)∧R Q∧(P∧R) |
Associatividade da Disjunção | (P∨Q) ∨R Q∨(P∨R) |
Associatividade da Bi-implicação | (P ↔Q) ↔R Q ↔(P ↔R) |
III. PROVA LÓGICA (⊢)
Seja α uma fórmula e Δ um conjunto de fórmulas, uma prova α a partir de Δ é uma sequência limitada de fórmulas φ1, φ2 ... φn de fórmulas, tal que φn= α e para cada φi, 1≤ i ≤ n, φi , φi ∈Δ ou φi é obtida a partir de fórmulas anteriores através de regras de inferência.
Exemplo:
Δ = {P→Q, ¬Q∨R, ¬R}
1. P→Q (premissa)
2. ¬Q∨R (premissa)
3. ¬R (premissa)
4. ¬Q (2, 3 Silogismo Disjuntivo)
5. ∴ ¬P (1, 4, Modus Tollens)
Δ⊢¬P [Existe uma prova de ¬P a partir do conjunto Δ]
IV. CONSEQUÊNCIA SINTÁTICA E SEMÂNTICA
Uma determinada fórmula α é uma consequência sintática de um conjunto de sentenças Δ quando existe uma prova de α a partir das premissas do conjunto: Δ⊢α.
Exemplo:
Δ={P→Q, ¬P→(Q∨R), ¬Q}
1. P→Q (premissa)
2. ¬P→(Q∨R) (premissa)
3. ¬Q (premissa)
4. ¬P (1,3 Modus Tollens)
5. Q∨R (2,4 Modus Ponens)
6. ∴ R (3,5 Silogismo Disjuntivo)
Δ⊢R [R é uma consequência sintática de Δ]
Uma fórmula α é consequência semântica de um conjunto de fórmulas Δ se e somente se toda interpretação I que tornam verdadeiras todas as fórmulas de Δ também tornam α verdadeira: Δ⊨α, isto é, em todos os casos em que as premissas são verdadeiras, a conclusão também será verdadeira.
Exemplo:
Δ={P→Q, ¬P(Q∨R), ¬Q}
Δ⊨R
P | Q | R | ¬P | Q∨R | P→Q | ¬P→(Q∨R) | ¬Q | R |
V | V | V | F | V | V | V | F | V |
V | V | F | F | V | V | V | F | F |
V | F | V | F | V | F | V | V | V |
V | F | F | F | F | F | V | V | F |
F | V | V | V | V | V | V | F | V |
F | V | F | V | V | V | V | F | F |
F | F | V | V | V | V | V | V | V |
F | F | F | V | F | V | F | V | F |
Em todos os casos em que as premissas são verdadeiras, a conclusão é verdadeira.
V. TEOREMAS DA COMPLETUDE E DA CORREÇÃO
De acordo com o Teorema da Completude, se uma fórmula é uma consequência semântica de um conjunto Δ, então essa fórmula também é uma consequência sintática do conjunto Δ:
(Δ⊨α) → (Δ⊢α)
Assim, de acordo com o teorema da completude, se Δ⊨α, então Δ⊢α, ou seja, se Δ for assumido como um conjunto de axiomas, então tudo que é verdadeiro pode ser provado (pelas regras de inferência). Assim, de acordo com o Teorema da Completude, todas as fórmulas que são verdadeiras são passíveis de prova.
Já, de acordo com o Teorema da Correção, se uma fórmula é uma consequência sintática de um conjunto Δ, então essa fórmula também é uma consequência semântica de Δ:
(Δ⊢α) → (Δ⊨α). Isto é, se uma fórmula é um teorema, a conclusão de uma prova lógica, então essa fórmula também é uma tautologia.
Dado os teoremas da completude e da correção, temos uma relação de equivalência entre eles. Uma fórmula é uma consequência sintática Δ de um conjunto se e somente (⬄) ela é uma consequência semântica do conjunto Δ.
(Δ⊢α) ⬄ (Δ⊨α)
Teorema da Completude | Teorema da Correção | Equivalência |
(Δ⊨α) → (Δ⊢α) | (Δ⊢α) → (Δ⊨α) | (Δ⊢α) ⬄ (Δ⊨α) |
VI. VALIDADE SINTÁTICA E SEMÂNTICA
Validade é sempre um atributo de argumentos, nunca de proposições. Proposições são verdadeiras ou falsas, nunca válidas ou inválidas. Do mesmo modo, argumentos são válidos ou inválidos, nunca verdadeiros ou falsos. Um argumento é sintaticamente válido se e somente se a sua conclusão for uma consequência sintática de suas premissas. Um argumento é semanticamente válido se e somente se a sua conclusão é uma consequência semântica de suas premissas.
O termo “validade” também pode ser empregado para fórmulas, mas não para proposições, que são verdadeiras ou falsas. Uma fórmula é semanticamente válida se ela for uma tautologia, isto é, verdadeira em todas as interpretações. Todo argumento pode ser transformado em uma única fórmula de modo embora verdade não seja um atributo de argumentos, pode-se falar indiretamente da verdade de um argumento, pois uando um argumento é válido, a fórmula correspondente a esse argumento é uma tautologia.
VII. PRINCÍPIO DA EXPLOSÃO
De acordo com o princípio da explosão, “ex falso quodlibet” (“do falso qualquer coisa se segue”), isto é, havendo uma contradição (⊥) em um argumento, pode-se derivar qualquer conclusão. Argumentos a partir de uma contradição podem ser semanticamente e sintaticamente válidos. Dado que pelo menos a premissa contraditória é falsa em todas as interpretações, quando não há nenhum caso em que todas as premissas são verdadeiras, dizemos que há uma verdade por vacuidade.
VIII. DEDUÇÃO NATURAL POR PROVA DIRETA
Dedução natural é um método sintático a partir do uso de regras de inferência, sendo um método mais simples e contraposto ao método axiomático. Em provas diretas, o método da dedução natural consiste em tirar diretamente uma conclusão de um conjunto de premissas pelo uso de regras de inferência.
Exemplo:
1. P→Q (Premissa 1)
2. R∨(Q→P) (Premissa 2)
3. S→¬R (Premissa 3)
4. S (Premissa 4)
5. ¬R (3, 4, Modus Tollens)
6. Q→P (2,5, Silogismo Disjuntivo)
7. P↔Q (1,6 Introdução do bi-condicional)
IX. DEDUÇÃO NATURAL POR PROVAS HIPOTÉTICAS
Na dedução natural por provas hipotéticas, utiliza-se a Regra de Prova Condicional, segundo a qual se temos uma determinada fórmula α da qual se pode derivar uma fórmula β, então α→β. Na dedução natural por prova hipotética, pelo menos em algum passo da dedução, assume-se uma fórmula como verdadeira a fim de mostrar que conclusão ela implica. Usa-se uma linha vertical para sinalizar as etapas dentro de uma hipótese.
Na prova hipotética, uma nova hipótese pode ser assumida dentro de outra hipótese. Exemplo:
A prova hipotética pode ser usada mesmo na ausência de premissas, além disso, em uma prova hipotética pode-se utilizar o chamada Regra da Reinteração, segundo a qual, se já foi assumido que uma fórmula α é verdadeira, ela pode ser repetida em qualquer lugar da hipótese. Exemplo:
X. DEDUÇÃO NATURAL POR PROVA POR CONTRADIÇÃO
Na prova por contradição, busca-se mostrar que a negação de uma determinada hipótese (¬α) implica em uma contradição (⊥), o que, por redução ao absurdo, mostra que a hipótese inicial é verdadeira (α).
Exemplo:
Quando o método da redução ao absurdo é utilizado em uma fórmula que não é uma tautologia, mas uma contingência, o método revela um contraexemplo da fórmula.
Exemplo:
O método revela, assim que, embora a negação da fórmula (P→ Q)→(Q→ P) não implique em uma contradição, um contraexemplo à fórmula, isto é, um caso em que a fórmula resulta em falso, é aquele em que Q é verdadeiro e P é falso.
Comentários